-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraph_functions.py
121 lines (101 loc) · 2.77 KB
/
graph_functions.py
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
import networkx as nx
import numpy as np
from random import choice
def remove_random_nodes(graph, n):
'''
Randomly removes n nodes from the graph.
------
Inputs
------
graph = networkx graph
n = number of nodes to be removed
------
Output
------
new_graph = networkx graph
'''
node_list = graph.nodes()
while n > 0:
rnode = choice(node_list)
graph.remove_node(rnode)
node_list.remove(rnode)
n = n - 1
return graph
def remove_random_edges(graph, n):
'''
Randomly removes n edges from the graph.
------
Inputs
------
graph = networkx graph
n = number of edges to be removed
------
Output
------
new_graph = networkx graph
'''
edge_list = graph.edges()
while n > 0:
redge = choice(edge_list)
graph.remove_edge(redge[0],redge[1])
edge_list.remove(redge)
n = n - 1
return graph
def within_module_degree(graph, partition):
'''
Computes the within-module degree for each node.
------
Inputs
------
graph = networkx graph
partition = modularity partition of graph
------
Output
------
wd_dict: Dictionary of the within-module degree of each node.
'''
wd_dict = {}
paths = nx.shortest_path_length(G=graph)
for m in partition.keys():
mod_list = partition[m]
mod_wd_dict = {}
for source in mod_list:
count = 0
for target in mod_list:
if paths[source][target] == 1:
count += 1
mod_wd_dict[source] = count
all_mod_wd = mod_wd_dict.values()
avg_mod_wd = float(all_mod_wd.sum()) / len(all_mod_wd)
for source in mod_list:
wd_dict[source] = (mod_wd_dict[source] - avg_mod_wd) / np.std(all_mod_wd)
return wd_dict
def participation_coefficient(graph, partition):
'''
Computes the participation coefficient for each node.
------
Inputs
------
graph = networkx graph
partition = modularity partition of graph
------
Output
------
List of the participation coefficient for each node.
'''
pc_dict = {}
all_nodes = set(graph.nodes())
paths = nx.shortest_path_length(G=graph)
for m in partition.keys():
mod_list = set(partition[m])
between_mod_list = list(set.difference(all_nodes, mod_list))
for source in mod_list:
degree = float(nx.degree(G=graph, nbunch=source))
count = 0
for target in between_mod_list:
if paths[source][target] == 1:
count += 1
bm_degree = count
pc = 1 - (bm_degree / degree)**2
pc_dict[source] = pc
return pc_dict