Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1import functools
3import networkx as nx
5__all__ = [
6 "edge_betweenness_partition",
7 "edge_current_flow_betweenness_partition",
8]
11@nx._dispatchable(edge_attrs="weight")
12def edge_betweenness_partition(G, number_of_sets, *, weight=None):
13 """Partition created by iteratively removing the highest edge betweenness edge.
15 This algorithm works by calculating the edge betweenness for all
16 edges and removing the edge with the highest value. It is then
17 determined whether the graph has been broken into at least
18 `number_of_sets` connected components.
19 If not the process is repeated.
21 Parameters
22 ----------
23 G : NetworkX Graph, DiGraph or MultiGraph
24 Graph to be partitioned
26 number_of_sets : int
27 Number of sets in the desired partition of the graph
29 weight : key, optional, default=None
30 The key to use if using weights for edge betweenness calculation
32 Returns
33 -------
34 C : list of sets
35 Partition of the nodes of G
37 Raises
38 ------
39 NetworkXError
40 If number_of_sets is <= 0 or if number_of_sets > len(G)
42 Examples
43 --------
44 >>> G = nx.karate_club_graph()
45 >>> part = nx.community.edge_betweenness_partition(G, 2)
46 >>> {0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21} in part
47 True
48 >>> {
49 ... 2,
50 ... 8,
51 ... 9,
52 ... 14,
53 ... 15,
54 ... 18,
55 ... 20,
56 ... 22,
57 ... 23,
58 ... 24,
59 ... 25,
60 ... 26,
61 ... 27,
62 ... 28,
63 ... 29,
64 ... 30,
65 ... 31,
66 ... 32,
67 ... 33,
68 ... } in part
69 True
71 See Also
72 --------
73 edge_current_flow_betweenness_partition
75 Notes
76 -----
77 This algorithm is fairly slow, as both the calculation of connected
78 components and edge betweenness relies on all pairs shortest
79 path algorithms. They could potentially be combined to cut down
80 on overall computation time.
82 References
83 ----------
84 .. [1] Santo Fortunato 'Community Detection in Graphs' Physical Reports
85 Volume 486, Issue 3-5 p. 75-174
86 http://arxiv.org/abs/0906.0612
87 """
88 if number_of_sets <= 0:
89 raise nx.NetworkXError("number_of_sets must be >0")
90 if number_of_sets == 1:
91 return [set(G)]
92 if number_of_sets == len(G):
93 return [{n} for n in G]
94 if number_of_sets > len(G):
95 raise nx.NetworkXError("number_of_sets must be <= len(G)")
97 H = G.copy()
98 partition = list(nx.connected_components(H))
99 while len(partition) < number_of_sets:
100 ranking = nx.edge_betweenness_centrality(H, weight=weight)
101 edge = max(ranking, key=ranking.get)
102 H.remove_edge(*edge)
103 partition = list(nx.connected_components(H))
104 return partition
107@nx._dispatchable(edge_attrs="weight")
108def edge_current_flow_betweenness_partition(G, number_of_sets, *, weight=None):
109 """Partition created by removing the highest edge current flow betweenness edge.
111 This algorithm works by calculating the edge current flow
112 betweenness for all edges and removing the edge with the
113 highest value. It is then determined whether the graph has
114 been broken into at least `number_of_sets` connected
115 components. If not the process is repeated.
117 Parameters
118 ----------
119 G : NetworkX Graph, DiGraph or MultiGraph
120 Graph to be partitioned
122 number_of_sets : int
123 Number of sets in the desired partition of the graph
125 weight : key, optional (default=None)
126 The edge attribute key to use as weights for
127 edge current flow betweenness calculations
129 Returns
130 -------
131 C : list of sets
132 Partition of G
134 Raises
135 ------
136 NetworkXError
137 If number_of_sets is <= 0 or number_of_sets > len(G)
139 Examples
140 --------
141 >>> G = nx.karate_club_graph()
142 >>> part = nx.community.edge_current_flow_betweenness_partition(G, 2)
143 >>> {0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21} in part
144 True
145 >>> {8, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33} in part
146 True
149 See Also
150 --------
151 edge_betweenness_partition
153 Notes
154 -----
155 This algorithm is extremely slow, as the recalculation of the edge
156 current flow betweenness is extremely slow.
158 References
159 ----------
160 .. [1] Santo Fortunato 'Community Detection in Graphs' Physical Reports
161 Volume 486, Issue 3-5 p. 75-174
162 http://arxiv.org/abs/0906.0612
163 """
164 if number_of_sets <= 0:
165 raise nx.NetworkXError("number_of_sets must be >0")
166 elif number_of_sets == 1:
167 return [set(G)]
168 elif number_of_sets == len(G):
169 return [{n} for n in G]
170 elif number_of_sets > len(G):
171 raise nx.NetworkXError("number_of_sets must be <= len(G)")
173 rank = functools.partial(
174 nx.edge_current_flow_betweenness_centrality, normalized=False, weight=weight
175 )
177 # current flow requires a connected network so we track the components explicitly
178 H = G.copy()
179 partition = list(nx.connected_components(H))
180 if len(partition) > 1:
181 Hcc_subgraphs = [H.subgraph(cc).copy() for cc in partition]
182 else:
183 Hcc_subgraphs = [H]
185 ranking = {}
186 for Hcc in Hcc_subgraphs:
187 ranking.update(rank(Hcc))
189 while len(partition) < number_of_sets:
190 edge = max(ranking, key=ranking.get)
191 for cc, Hcc in zip(partition, Hcc_subgraphs):
192 if edge[0] in cc:
193 Hcc.remove_edge(*edge)
194 del ranking[edge]
195 splitcc_list = list(nx.connected_components(Hcc))
196 if len(splitcc_list) > 1:
197 # there are 2 connected components. split off smaller one
198 cc_new = min(splitcc_list, key=len)
199 Hcc_new = Hcc.subgraph(cc_new).copy()
200 # update edge rankings for Hcc_new
201 newranks = rank(Hcc_new)
202 for e, r in newranks.items():
203 ranking[e if e in ranking else e[::-1]] = r
204 # append new cc and Hcc to their lists.
205 partition.append(cc_new)
206 Hcc_subgraphs.append(Hcc_new)
208 # leave existing cc and Hcc in their lists, but shrink them
209 Hcc.remove_nodes_from(cc_new)
210 cc.difference_update(cc_new)
211 # update edge rankings for Hcc whether it was split or not
212 newranks = rank(Hcc)
213 for e, r in newranks.items():
214 ranking[e if e in ranking else e[::-1]] = r
215 break
216 return partition