文章目录
矩阵常见统计
adjacency_matrix=[
[0,1,0,1],
[1,0,1,1],
[0,1,0,0],
[1,1,0,0]
]
adjacency_matrix_directed = [
[0,1,0,1],
[0,0,1,0],
[0,0,0,1],
[0,0,0,0]
]
数量统计
- the number of species
S, that in graph theory corresponds to the number of vertices n which is themeasureof the graph. - the number of predations
L, that in graph theory corresponds to the number of edges m, which is thesizeof the graph.
# 数量统计
num_species = len(adjacency_matrix_directed[0])
num_predations = 0
for i in range(num_species):
for j in range(num_species):
if adjacency_matrix_directed[i][j] != 0:
num_predations = num_predations + 1
print('num_predations: '.format(), num_predations)
# num_predations: 4
行列统计
# 行，列统计
row_count = [0,0,0,0]
column_count = [0,0,0,0]
for i in range(num_species):
for j in range(num_species):
row_count[i] = row_count[i] + adjacency_matrix_directed[i][j]
column_count[j] = column_count[j] + adjacency_matrix_directed[i][j]
print('row_count: '.format(), row_count)
print('column_count: '.format(), column_count)
# row_count: [2, 1, 1, 0]
# column_count: [0, 1, 1, 2]
基底、顶部、中间
The connectance C ≃ L / S 2 C \simeq L / S^{2} C≃L/S2 , corresponding to the density of the graph.
number_B = 0
number_T = 0
number_I = 0
for n in range(num_species):
if row_count[n] == 0:
number_T += 1
continue
elif column_count[n] == 0:
number_B += 1
continue
else:
number_I += 1
print('classes Basal, Top, Intermediate: ', number_B, number_T, number_I)
print("connectance", float(num_predations)/float(num_species**2))
# classes Basal, Top, Intermediate: 1 1 2
# connectance 0.25
度-degree
度： k i = ∑ j = 1 , n a i j k_{i}=\sum_{j=1, n} a_{i j} ki=∑j=1,naij，入度： k i I = ∑ j = 1 , n a i j k_{i}^{I}=\sum_{j=1, n} a_{i j} kiI=∑j=1,naij，出度： k i O = ∑ j = 1 , n a i j k_{i}^{O}=\sum_{j=1, n} a_{i j} kiO=∑j=1,naij，带权重度： s i = ∑ j = 1 , n a i j w s_{i}=\sum_{j=1, n} a_{i j}^w si=∑j=1,naijw
# in this case the node “2”, for the undirected network
degree_node_2 = 0
for j in adjacency_matrix[1]:
degree_node_2 = degree_node_2 + j
print('degree of node_2: ', degree_node_2)
# degree of node_2: 3
# 有向图
out_degree_node_3 = row_count[2]
in_degree_node_4 = column_count[3]
print("out_degree of node_3: ", out_degree_node_3)
print("in_degree of node_4: ", in_degree_node_4)
# out_degree of node_3: 1
# in_degree of node_4: 2
degree in Networkx
import networkx as nx
G = nx.Graph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_edge(1,2)
G.add_edge(1,4)
G.add_edge(2,3)
G.add_edge(2,4)
# degree of the node_2
print(G.degree(2)) # 3
degree sequence
degree_suquence = []
for row in range(len(adjacency_matrix)):
degree = 0
for j in adjacency_matrix[row]:
degree = degree + j
degree_suquence.append(degree)
print(degree_suquence)
# [2, 3, 1, 2]
clustering coefficient
聚类系数：度量某顶点的两个邻居节点也互为邻居节点的平均概率 (“我朋友的朋友是朋友的概率”)
- 节点
i的 k i k_i ki个邻居节点之间实际存在的边数 E i E_i Ei和总的可能边数之比
C
i
=
2
e
i
k
i
(
k
i
−
1
)
C_{i}=\frac{2 e_{i}}{k_{i}\left(k_{i}-1\right)}
Ci=ki(ki−1)2ei
e
i
e_{i}
ei 表示的是在红点它的邻居之间存在连边的个数
k
i
k_{i}
ki 指的是红点i的它的度值
邻接矩阵中计算:
C
i
=
2
e
i
k
i
(
k
i
−
1
)
=
1
k
i
(
k
i
−
1
)
∑
j
,
k
=
1
N
a
i
j
a
j
k
a
k
i
C_{i}=\frac{2 e_{i}}{k_{i}\left(k_{i}-1\right)}=\frac{1}{k_{i}\left(k_{i}-1\right)} \sum_{j, k=1}^{N} a_{i j} a_{j k} a_{k i}
Ci=ki(ki−1)2ei=ki(ki−1)1j,k=1∑Naijajkaki
row=1 # stands for the node ‘2’
node_index_count = 0
node_index_list=[]
for a_ij in adjacency_matrix[row]:
if a_ij == 1:
node_index_list.append(node_index_count)
node_index_count = node_index_count + 1
print('node_index_list: ', node_index_list)
# node_index_list: [0, 2, 3]
# then check for all the possible neighbours copules if a link actually exist
neighb_conn = 0
for n1 in node_index_list:
for n2 in node_index_list:
if adjacency_matrix[n1][n2] == 1:
neighb_conn = neighb_conn + 1
#we have indeed counted them twice...
neighb_conn = neighb_conn / 2.0
print('neighb_conn: ', neighb_conn)
# neighb_conn: 1.0
#Finally the clustering coefficient for node '2' is given by the expression:
clustering_coefficient = neighb_conn / (degree_node_2 * (degree_node_2-1) / 2.0)
print('clustering_coefficient: ', clustering_coefficient)
# clustering_coefficient: 0.3333333333333333
食物链网络-food webs
领结模式
食物链顶端（如狮子）用T表示，底端（如草）用B表示，中间量用I表示。
# Ythan_Estuary.txt 数据描述
46 15
47 19
47 22
48 19
49 14
50 14
51 18
51 19
...
# loading the network
file_name = './data/Ythan_Estuary.txt'
DG = nx.DiGraph()
in_file = open(file_name, 'r')
while True:
next_line = in_file.readline()
if not next_line:
break
next_line_fields = next_line[:-1].split(' ')
node_a = next_line_fields[1] # there is a space in the beginning of each edge
node_b = next_line_fields[2]
# print(node_a, ' - ',node_b)
DG.add_edge(node_a, node_b)
nx.draw(DG)
# deleting the environment
DG.remove_node('0')
# getting the biggest strongly connected component
scc = [(len(c), c) for c in sorted(nx.strongly_connected_components(DG), key=len, reverse=True)][0][1]
print(scc) # {'89', '90'}
# preparing the IN and OUT component
IN_component=[]
for n in scc:
for s in DG.predecessors(n):
if s in scc:
continue
if s not in IN_component:
IN_component.append(s)
OUT_component=[]
for n in scc:
for s in DG.successors(n):
if s in scc:
continue
if s not in OUT_component:
OUT_component.append(s)
# generating the subgraph
bowtie = list(scc) + IN_component +OUT_component
DG_bowtie = DG.subgraph(bowtie)
# defining the proper layout
pos = {}
in_y = 100.
pos['89'] = (150. , in_y)
in_step = 700.
for in_n in IN_component:
pos[in_n] = (100., in_y)
in_y = in_y + in_step
out_y = 100.
out_step = 500.
for out_n in OUT_component:
pos[out_n] = (200, out_y)
out_y = out_y + out_step
pos['90'] = (150., out_y)
# plot the bowtie structure
nx.draw(DG_bowtie, pos, node_size=50)
nx.draw_networkx_nodes(DG_bowtie, pos, IN_component, node_size=100, node_color='Blue')
nx.draw_networkx_nodes(DG_bowtie, pos, OUT_component, node_size=100, node_color='red')
nx.draw_networkx_nodes(DG_bowtie, pos, scc, node_size=200, node_color='Green')
Distance with Breadth First Search(BFS)
# create the undirected graph
G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('C', 'D'), ('C', 'E'), ('D', 'F'),
('D', 'H'), ('D', 'G'), ('E', 'H'), ('E', 'I')])
# printing the neighbors of the node 'A'
# print(G.neighbors('A'))
for n in G.neighbors('A'):
print(n,end=' ') # B C
nx.draw(G,with_labels=True)
root_node='A'
queue = []
queue.append('A')
G.node['A']['distance'] = 0
while len(queue):
working_node = queue.pop(0)
for n in G.neighbors(working_node):
if len(G.node[n]) == 0:
G.node[n]['distance']=G.node[working_node]['distance']+1
queue.append(n)
for n in G.node():
print(n, G.node[n]['distance'])
# A 0
# B 1
# C 1
# D 2
# E 2
# F 3
# H 3
# G 3
# I 3
参考-《Data Science & Complex Networks》