networkx/networkx: Network Analysis in Python (github.com)
networkx学习与使用——（2）度、邻居和搜索算法networkx获取邻居节点
首先，我们将加载网络科学中的经典图，即空手道俱乐部网络。我们将探索该图的多个图统计信息
import networkx as nx
空手道俱乐部网络是一个图表，描述了一个由空手道俱乐部的 34 名成员组成的社交网络，并记录了在俱乐部外进行互动的成员之间的联系
G = nx.karate_club_graph()
# G is an undirected graph
type(G)
## networkx.classes.graph.Graph
# Visualize the graph
nx.draw(G, with_labels = True)
image.png
问题1: 空手道社团网络的平均的度是多少?
def average_degree(num_edges, num_nodes):
# TODO: Implement this function that takes number of edges
# and number of nodes, and returns the average node degree of
# the graph. Round the result to nearest integer (for example
# 3.3 will be rounded to 3 and 3.7 will be rounded to 4)
avg_degree = 0
############# Your code here ############
avg_degree=round(2*num_edges/num_nodes)
#########################################
return avg_degree
num_edges = G.number_of_edges()
num_nodes = G.number_of_nodes()
print(num_edges)
print(num_nodes)
avg_degree = average_degree(num_edges, num_nodes)
print("Average degree of karate club network is {}".format(avg_degree))
## 78
## 34
## Average degree of karate club network is 5
问题2：空手道俱乐部网络的平均聚类系数是多少?
def average_clustering_coefficient(G):
# TODO: Implement this function that takes a nx.Graph
# and returns the average clustering coefficient. Round
# the result to 2 decimal places (for example 3.333 will
# be rounded to 3.33 and 3.7571 will be rounded to 3.76)
# avg_cluster_coef = 0
############# Your code here ############
## Note:
## 1: Please use the appropriate NetworkX clustering function
avg_cluster_coef = nx.average_clustering(G)
#########################################
return avg_cluster_coef
avg_cluster_coef = average_clustering_coefficient(G)
print("Average clustering coefficient of karate club network is {}".format(avg_cluster_coef))
问题 3：节点 0（id 为 0 的节点）经过一次 PageRank 迭代后的 PageRank 值是多少
PageRank算法详解 - 知乎 (zhihu.com)
image.png
G.neighbors(0)
for line in G.neighbors(0):
print(line)
#1
#3
#4
#5
#6
#7
#8
#10
#11
#12
#13
#17
#19
#21
#31
def one_iter_pagerank(G, beta, r0, node_id):
# TODO: Implement this function that takes a nx.Graph, beta, r0 and node id.
# The return value r1 is one interation PageRank value for the input node.
# Please round r1 to 2 decimal places.
r1 = 0
for line in G.neighbors(node_id):
r1+=beta*r0/G.degree(line)
r1+=round((1-beta)/G.number_of_nodes(),2)
############# Your code here ############
## Note:
## 1: You should not use nx.pagerank
#########################################
return r1
beta = 0.8
r0 = 1 / G.number_of_nodes()
node = 0
r1 = one_iter_pagerank(G, beta, r0, node)
print("The PageRank value for node 0 after one iteration is {}".format(r1))
问题4：空手道俱乐部网络节点5的（原始）紧密性中心度是多少
度中心性(Degrree centrality)-介数中心性(Betweeness centrality)-特征向量中心性( Eigenvector centrality)-k-壳与k-核 - 言非 - 博客园 (cnblogs.com)
在社会网络分析中，常用“中心性(Centrality)"来判断网络中节点重要性或影响力。最直接的度量是度中心性(Degrree centrality)，即一个节点的度越大就意味着这个节点越重要。
这一指标背后的假设是：重要的节点就是拥有许多连接的节点。你的社会关系越多，你的影响力就越强。
紧密中心性(Closeness centrality)#
点度中心性仅仅利用了网络的局部特征，即节点的连接数有多少，但一个人连接数多，并不代表他/她处于网络的核心位置。
紧密中心性和中介中心性一样，都利用了整个网络的特征，即一个节点在整个结构中所处的位置。
紧密中心性(Closeness centrality)也称接近中心性
紧密度中心性与非中心结点相比，一个中心结点应该能更快地到达网络内的其他结点。
即：如果节点到图中其他节点的最短距离都很小，那么它的接近中心性就很高。相比中介中心性，接近中心性更接近几何上的中心位置。
紧密度中心性用于评价一个结点到其他所有结点的紧密程度。
def closeness_centrality(G, node=5):
# TODO: Implement the function that calculates closeness centrality
# for a node in karate club network. G is the input karate club
# network and node is the node id in the graph. Please round the
# closeness centrality result to 2 decimal places.
closeness = 0
closeness=nx.closeness_centrality(G=G,u=node) ### 这个函数是标准化过的，题目要求非标准化，所以需要转换一下，如上面的链接的那个方程
# closeness = round(closeness /len(nx.node_connected_component(G,node))-1,2)
closeness = round(closeness/(len(nx.node_connected_component(G,node))-1),2)
## Note:
## 1: You can use networkx closeness centrality function.
## 2: Notice that networkx closeness centrality returns the normalized
## closeness directly, which is different from the raw (unnormalized)
## one that we learned in the lecture.
#########################################
return closeness
node = 5
closeness = closeness_centrality(G, node=node)
print("The karate club network has closeness centrality {}".format(closeness))
2 Graph to Tensor
将图 G 转换为 PyTorch 张量，这样我们就可以在图上执行机器学习
import torch
print(torch.__version__)
# Generate 3 x 4 tensor with all ones
ones = torch.ones(3, 4)
print(ones)
# Generate 3 x 4 tensor with all zeros
zeros = torch.zeros(3, 4)
print(zeros)
# Generate 3 x 4 tensor with random values on the interval [0, 1)
random_tensor = torch.rand(3, 4)
print(random_tensor)
# Get the shape of the tensor
print(ones.shape)
# Create a 3 x 4 tensor with all 32-bit floating point zeros
zeros = torch.zeros(3, 4, dtype=torch.float32)
print(zeros.dtype)
# Change the tensor dtype to 64-bit integer
zeros = zeros.type(torch.long)
print(zeros.dtype)
输出
tensor([[1., 1., 1., 1.],
[1., 1., 1., 1.],
[1., 1., 1., 1.]])
tensor([[0., 0., 0., 0.],
[0., 0., 0., 0.],
[0., 0., 0., 0.]])
tensor([[0.3776, 0.6322, 0.4880, 0.0567],
[0.3344, 0.2113, 0.3128, 0.6075],
[0.8854, 0.1048, 0.6645, 0.3627]])
torch.Size([3, 4])
torch.float32
torch.int64
问题5: 获取空手道俱乐部网络的边缘列表，并将其转换为torch.LongTensor.pos_edge_index 张量的 torch.sum 值是多少？
def graph_to_edge_list(G):
# TODO: Implement the function that returns the edge list of
# an nx.Graph. The returned edge_list should be a list of tuples
# where each tuple is a tuple representing an edge connected
# by two nodes.
edge_list = []
for ei in G.edges():
print(ei)
edge_list.append(ei)
print(edge_list)
############# Your code here ############
#########################################
return edge_list
def edge_list_to_tensor(edge_list):
# TODO: Implement the function that transforms the edge_list to
# tensor. The input edge_list is a list of tuples and the resulting
# tensor should have the shape [2 x len(edge_list)].
edge_index = torch.tensor([])
edge_index=torch.tensor(edge_list).T
print(edge_index)
############# Your code here ############
#########################################
return edge_index
pos_edge_list = graph_to_edge_list(G)
pos_edge_index = edge_list_to_tensor(pos_edge_list)
print("The pos_edge_index tensor has shape {}".format(pos_edge_index.shape))
print("The pos_edge_index tensor has sum value {}".format(torch.sum(pos_edge_index)))
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 10), (0, 11), (0, 12), (0, 13), (0, 17), (0, 19), (0, 21), (0, 31), (1, 2), (1, 3), (1, 7), (1, 13), (1, 17), (1, 19), (1, 21), (1, 30), (2, 3), (2, 7), (2, 8), (2, 9), (2, 13), (2, 27), (2, 28), (2, 32), (3, 7), (3, 12), (3, 13), (4, 6), (4, 10), (5, 6), (5, 10), (5, 16), (6, 16), (8, 30), (8, 32), (8, 33), (9, 33), (13, 33), (14, 32), (14, 33), (15, 32), (15, 33), (18, 32), (18, 33), (19, 33), (20, 32), (20, 33), (22, 32), (22, 33), (23, 25), (23, 27), (23, 29), (23, 32), (23, 33), (24, 25), (24, 27), (24, 31), (25, 31), (26, 29), (26, 33), (27, 33), (28, 31), (28, 33), (29, 32), (29, 33), (30, 32), (30, 33), (31, 32), (31, 33), (32, 33)]
tensor([[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4,
4, 5, 5, 5, 6, 8, 8, 8, 9, 13, 14, 14, 15, 15, 18, 18, 19, 20,
20, 22, 22, 23, 23, 23, 23, 23, 24, 24, 24, 25, 26, 26, 27, 28, 28, 29,
29, 30, 30, 31, 31, 32],
[ 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 17, 19, 21, 31, 2, 3,
7, 13, 17, 19, 21, 30, 3, 7, 8, 9, 13, 27, 28, 32, 7, 12, 13, 6,
10, 6, 10, 16, 16, 30, 32, 33, 33, 33, 32, 33, 32, 33, 32, 33, 33, 32,
33, 32, 33, 25, 27, 29, 32, 33, 25, 27, 31, 31, 29, 33, 33, 31, 33, 32,
33, 32, 33, 32, 33, 33]])
The pos_edge_index tensor has shape torch.Size([2, 78])
The pos_edge_index tensor has sum value 2535
问题 6：请实现以下对负边进行采样的函数。然后你会回答空手道俱乐部网络中哪些边（edge_1 到 edge_5）可以是负边？
未完待续
