使用NetworkX分析网络

image.png

NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

https://networkx.github.io/documentation/stable/tutorial.html

%matplotlib inline
import networkx as nx
import matplotlib.cm as cm
import matplotlib.pyplot as plt
import networkx as nx

G=nx.Graph() # G = nx.DiGraph() # 有向网络
# 添加(孤立)节点
G.add_node("spam")
# 添加节点和链接
G.add_edge(1,2)

print(G.nodes())

print(G.edges())
['spam', 1, 2]
[(1, 2)]
# 绘制网络
nx.draw(G, with_labels = True)
_images/17-networkx_4_0.png

WWW Data download

https://snap.stanford.edu/data/web-NotreDame.html

上面的数据也可以在Barabasi的networksciencebook网页下载 http://networksciencebook.com/translations/en/resources/data.html

World-Wide-Web: [README] [DATA] Réka Albert, Hawoong Jeong and Albert-László Barabási: Diameter of the World Wide Web Nature 401, 130 (1999) [ PDF ]

作业

  • 下载www数据

  • 构建networkx的网络对象g(提示:有向网络)

  • 将www数据添加到g当中

  • 计算网络中的节点数量和链接数量

G = nx.Graph()
n = 0
with open ('/Users/datalab/bigdata/cjc/www.dat.gz.txt') as f:
    for line in f:
        n += 1
        #if n % 10**4 == 0:
            #flushPrint(n)
        x, y = line.rstrip().split(' ')
        G.add_edge(x,y)
        
nx.info(G)
'Name: \nType: Graph\nNumber of nodes: 325729\nNumber of edges: 1117563\nAverage degree:   6.8619'

描述网络

nx.karate_club_graph

我们从karate_club_graph开始,探索网络的基本性质。

G = nx.karate_club_graph()
 
clubs = [G.nodes[i]['club'] for i in G.nodes()]
colors = []
for j in clubs:
    if j == 'Mr. Hi':
        colors.append('r')
    else:
        colors.append('g')
 
nx.draw(G,  with_labels = True, node_color = colors)
_images/17-networkx_10_0.png
G.nodes[1], G.nodes[9] # 节点1的属性 # 节点1的属性
({'club': 'Mr. Hi'}, {'club': 'Officer'})
G.edges# 前三条边的id
#dir(G)
EdgeView([(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)])
nx.info(G)
"Name: Zachary's Karate Club\nType: Graph\nNumber of nodes: 34\nNumber of edges: 78\nAverage degree:   4.5882"
G.nodes()
NodeView((0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33))
list(G.edges())[:3]
[(0, 1), (0, 2), (0, 3)]
print(*G.neighbors(1))
0 2 3 7 13 17 19 21 30
nx.average_shortest_path_length(G) 
2.408199643493761

网络直径

nx.diameter(G)#返回图G的直径(最长最短路径的长度)
5

密度

nx.density(G)
0.13903743315508021
nodeNum = len(G.nodes())
edgeNum = len(G.edges())

2.0*edgeNum/(nodeNum * (nodeNum - 1))
0.13903743315508021

作业

  • 计算www网络的网络密度

聚集系数

cc = nx.clustering(G)
cc.items()
dict_items([(0, 0.15), (1, 0.3333333333333333), (2, 0.24444444444444444), (3, 0.6666666666666666), (4, 0.6666666666666666), (5, 0.5), (6, 0.5), (7, 1.0), (8, 0.5), (9, 0), (10, 0.6666666666666666), (11, 0), (12, 1.0), (13, 0.6), (14, 1.0), (15, 1.0), (16, 1.0), (17, 1.0), (18, 1.0), (19, 0.3333333333333333), (20, 1.0), (21, 1.0), (22, 1.0), (23, 0.4), (24, 0.3333333333333333), (25, 0.3333333333333333), (26, 1.0), (27, 0.16666666666666666), (28, 0.3333333333333333), (29, 0.6666666666666666), (30, 0.5), (31, 0.2), (32, 0.19696969696969696), (33, 0.11029411764705882)])
plt.hist(cc.values(), bins = 15)
plt.xlabel('$Clustering \, Coefficient, \, C$', fontsize = 20)
plt.ylabel('$Frequency, \, F$', fontsize = 20)
plt.show()
_images/17-networkx_26_0.png

Spacing in Math Mode

In a math environment, LaTeX ignores the spaces you type and puts in the spacing that it thinks is best. LaTeX formats mathematics the way it’s done in mathematics texts. If you want different spacing, LaTeX provides the following four commands for use in math mode:

; - a thick space

: - a medium space

, - a thin space

\! - a negative thin space

匹配系数

Assortativity measures the similarity of connections in the graph with respect to the node degree.

M. E. J. Newman, Mixing patterns in networks, Physical Review E, 67 026126, 2003

# M. E. J. Newman, Mixing patterns in networks Physical Review E, 67 026126, 2003
nx.degree_assortativity_coefficient(G) #计算一个图的度匹配性。
-0.47561309768461457
Ge=nx.Graph()
Ge.add_nodes_from([0,1],size=2)
Ge.add_nodes_from([2,3],size=3)
Ge.add_edges_from([(0,1),(2,3)])
node_size = [list(Ge.nodes[i].values())[0]*1000 for i in Ge.nodes()]
nx.draw(Ge, with_labels = True, node_size = node_size)

print(nx.numeric_assortativity_coefficient(Ge,'size')) 
1.0
_images/17-networkx_30_1.png
# plot degree correlation  
from collections import defaultdict
import numpy as np

l=defaultdict(list)
g = nx.karate_club_graph()

for i in g.nodes():
    k = []
    for j in g.neighbors(i):
        k.append(g.degree(j))
    l[g.degree(i)].append(np.mean(k))   
    #l.append([g.degree(i),np.mean(k)])
  
x = list(l.keys())
y = [np.mean(i) for i in l.values()]

#x, y = np.array(l).T
plt.plot(x, y, 'ro', label = '$Karate\;Club$')
plt.legend(loc=1,fontsize=10, numpoints=1)
plt.xscale('log'); plt.yscale('log')
plt.ylabel(r'$<knn(k)$> ', fontsize = 20)
plt.xlabel('$k$', fontsize = 20)
plt.show()
_images/17-networkx_31_0.png

Degree centrality measures.(度中心性)

  • degree_centrality(G) # Compute the degree centrality for nodes.

  • in_degree_centrality(G) # Compute the in-degree centrality for nodes.

  • out_degree_centrality(G) # Compute the out-degree centrality for nodes.

  • closeness_centrality(G[, v, weighted_edges]) # Compute closeness centrality for nodes.

  • betweenness_centrality(G[, normalized, …]) # Betweenness centrality measures.(介数中心性)

degree_centrality(G)

The degree centrality values are normalized by dividing by the maximum possible degree.

  • The maximum possible degreein a simple graph is n-1 where n is the number of nodes in G.

closeness_centrality(G[, v, weighted_edges])

Closeness centrality of a node u is the reciprocal of the average shortest path distance to u over all n-1 reachable nodes.

\[C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}\]

For graphs with more than one connected component:

\[C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}\]

Letting N denote the number of nodes in the graph

  • Linton C. Freeman: Centrality in networks: I. Conceptual clarification. Social Networks 1:215-239, 1979.

  • Wasserman, S. and Faust, K., Social Network Analysis: Methods and Applications, 1994, Cambridge University Press.pp.201.

betweenness_centrality(G)

Compute the shortest-path betweenness centrality for nodes.

Betweenness centrality of a node 𝑣 is the sum of the fraction of all-pairs shortest paths that pass through 𝑣

\[c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)}\]
  • s, t denote a node

  • 𝑉 is the set of nodes

  • 𝜎(𝑠,𝑡) is the number of shortest (𝑠,𝑡)-paths

  • 𝜎(𝑠,𝑡|𝑣) is the number of those paths passing through some node 𝑣 other than 𝑠,𝑡.

dc = nx.degree_centrality(G)
closeness = nx.closeness_centrality(G)
betweenness= nx.betweenness_centrality(G)
fig = plt.figure(figsize=(15, 4),facecolor='white')
ax = plt.subplot(1, 3, 1)
plt.hist(dc.values(), bins = 20)
plt.xlabel('$Degree \, Centrality$', fontsize = 20)
plt.ylabel('$Frequency, \, F$', fontsize = 20)

ax = plt.subplot(1, 3, 2)
plt.hist(closeness.values(), bins = 20)
plt.xlabel('$Closeness \, Centrality$', fontsize = 20)

ax = plt.subplot(1, 3, 3)
plt.hist(betweenness.values(), bins = 20)
plt.xlabel('$Betweenness \, Centrality$', fontsize = 20)
plt.tight_layout()
plt.show() 
_images/17-networkx_37_0.png
fig = plt.figure(figsize=(15, 8),facecolor='white')

for k in betweenness:
    plt.scatter(dc[k], closeness[k], s = betweenness[k]*10000)
    plt.text(dc[k], closeness[k]+0.02, str(k))
plt.xlabel('$Degree \, Centrality$', fontsize = 20)
plt.ylabel('$Closeness \, Centrality$', fontsize = 20)
plt.show()
_images/17-networkx_38_0.png

度分布

from collections import defaultdict
import numpy as np

def plotDegreeDistribution(G):
    degs = defaultdict(int)
    for i in dict(G.degree()).values(): degs[i]+=1
    items = sorted ( degs.items () )
    x, y = np.array(items).T
    y_sum = np.sum(y)
    y = [float(i)/y_sum for i in y]
    plt.plot(x, y, 'b-o')
    plt.xscale('log')
    plt.yscale('log')
    plt.legend(['Degree'])
    plt.xlabel('$K$', fontsize = 20)
    plt.ylabel('$P(K)$', fontsize = 20)
    plt.title('$Degree\,Distribution$', fontsize = 20)
    plt.show()   
    
G = nx.karate_club_graph()     
plotDegreeDistribution(G)
_images/17-networkx_40_0.png

分析网络结构

规则网络

import networkx as nx
import matplotlib.pyplot as plt
RG = nx.random_graphs.random_regular_graph(3,200)  
#生成包含200个节点、 每个节点有3个邻居的规则图RG
pos = nx.spectral_layout(RG)          
#定义一个布局,此处采用了spectral布局方式,后变还会介绍其它布局方式,注意图形上的区别
nx.draw(RG,pos,with_labels=False,node_size = range(1, 201))  
#绘制规则图的图形,with_labels决定节点是非带标签(编号),node_size是节点的直径
plt.show()  #显示图形
_images/17-networkx_43_0.png
plotDegreeDistribution(RG)
_images/17-networkx_44_0.png

ER随机网络

import networkx as nx
import matplotlib.pyplot as plt
ER = nx.random_graphs.erdos_renyi_graph(200,0.1)  
#生成包含20个节点、以概率0.2连接的随机图
pos = nx.spring_layout(ER)          
#定义一个布局,此处采用了shell布局方式
nx.draw(ER,pos,with_labels=False,node_size = 30) 
plt.show()
_images/17-networkx_46_0.png
ER = nx.random_graphs.erdos_renyi_graph(10000,0.1)  
plotDegreeDistribution(ER)
_images/17-networkx_47_0.png

小世界网络

import networkx as nx
import matplotlib.pyplot as plt
WS = nx.random_graphs.watts_strogatz_graph(500,4,0.1)  
#生成包含200个节点、每个节点4个近邻、随机化重连概率为0.3的小世界网络
pos = nx.spring_layout(WS)          
#定义一个布局,此处采用了circular布局方式
nx.draw(WS,pos,with_labels=False,node_size = 30)  
#绘制图形
plt.show()
_images/17-networkx_49_0.png
plotDegreeDistribution(WS)
_images/17-networkx_50_0.png
nx.diameter(WS)
16
cc = nx.clustering(WS)
plt.hist(cc.values(), bins = 10)
plt.xlabel('$Clustering \, Coefficient, \, C$', fontsize = 20)
plt.ylabel('$Frequency, \, F$', fontsize = 20)
plt.show()
_images/17-networkx_52_0.png
import numpy as np
np.mean(list(cc.values()))
0.3736952380952381

BA网络

import networkx as nx
import matplotlib.pyplot as plt
BA= nx.random_graphs.barabasi_albert_graph(200,2)  
#生成n=200、m=2的BA无标度网络
pos = nx.spring_layout(BA)          
#定义一个布局,此处采用了spring布局方式
nx.draw(BA,pos,with_labels=False,node_size = 30)  
#绘制图形
plt.show()
_images/17-networkx_55_0.png
plotDegreeDistribution(BA)
_images/17-networkx_56_0.png
BA= nx.random_graphs.barabasi_albert_graph(20000,2)  
#生成n=20、m=1的BA无标度网络
plotDegreeDistribution(BA) 
_images/17-networkx_57_0.png
import networkx as nx
import matplotlib.pyplot as plt
BA= nx.random_graphs.barabasi_albert_graph(500,1)  
#生成n=20、m=1的BA无标度网络
pos = nx.spring_layout(BA)          
#定义一个布局,此处采用了spring布局方式
nx.draw(BA,pos,with_labels=False,node_size = 30)  
#绘制图形
plt.show() 
_images/17-networkx_58_0.png
nx.degree_histogram(BA)[:10]
[0, 324, 91, 34, 14, 9, 6, 5, 4, 3]
list(dict(BA.degree()).items())[:10]  
[(0, 37),
 (1, 13),
 (2, 19),
 (3, 9),
 (4, 1),
 (5, 6),
 (6, 7),
 (7, 17),
 (8, 2),
 (9, 1)]
plt.hist( list(dict(BA.degree()).values()) , bins = 100)
# plt.xscale('log')
# plt.yscale('log')
plt.show()
_images/17-networkx_61_0.png
from collections import defaultdict
import numpy as np
def plotDegreeDistributionLongTail(G):
    degs = defaultdict(int)
    for i in list(dict(G.degree()).values()): degs[i]+=1
    items = sorted ( degs.items () )
    x, y = np.array(items).T
    y_sum = np.sum(y)
    y = [float(i)/y_sum for i in y]
    plt.plot(x, y, 'b-o')
    plt.legend(['Degree'])
    plt.xlabel('$K$', fontsize = 20)
    plt.ylabel('$P_K$', fontsize = 20)
    plt.title('$Degree\,Distribution$', fontsize = 20)
    plt.show()  
    
BA= nx.random_graphs.barabasi_albert_graph(5000,2)  
#生成n=20、m=1的BA无标度网络    
plotDegreeDistributionLongTail(BA)
_images/17-networkx_62_0.png
def plotDegreeDistribution(G):
    degs = defaultdict(int)
    for i in list(dict(G.degree()).values()): degs[i]+=1
    items = sorted ( degs.items () )
    x, y = np.array(items).T
    x, y = np.array(items).T
    y_sum = np.sum(y)
    plt.plot(x, y, 'b-o')
    plt.xscale('log')
    plt.yscale('log')
    plt.legend(['Degree'])
    plt.xlabel('$K$', fontsize = 20)
    plt.ylabel('$P(K)$', fontsize = 20)
    plt.title('$Degree\,Distribution$', fontsize = 20)
    plt.show()   

BA= nx.random_graphs.barabasi_albert_graph(50000,2)  
#生成n=20、m=1的BA无标度网络        
plotDegreeDistribution(BA)
_images/17-networkx_63_0.png

作业

  • 阅读 Barabasi (1999) Diameter of the world wide web.Nature.401

  • 绘制www网络的出度分布、入度分布

  • 使用BA模型生成节点数为N、幂指数为\(\gamma\)的网络

  • 计算平均路径长度d与节点数量的关系

_images/diameter.png
Ns = [i*10 for i in [1, 10, 100, 1000]]
ds = []
for N in Ns:
    print(N)
    BA= nx.random_graphs.barabasi_albert_graph(N,2)
    d = nx.average_shortest_path_length(BA)
    ds.append(d)
10
100
1000
10000
plt.plot(Ns, ds, 'r-o')
plt.xlabel('$N$', fontsize = 20)
plt.ylabel('$<d>$', fontsize = 20)
plt.xscale('log')
plt.show()
_images/17-networkx_67_0.png

参考

  • https://networkx.readthedocs.org/en/stable/tutorial/tutorial.html

  • http://computational-communication.com/wiki/index.php?title=Networkx