Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/community/centrality.py: 21%

1"""Functions for computing communities based on centrality notions.""" 

2 

3import networkx as nx 

4 

5__all__ = ["girvan_newman"] 

6 

7 

8@nx._dispatch(preserve_edge_attrs="most_valuable_edge") 

9def girvan_newman(G, most_valuable_edge=None): 

10 """Finds communities in a graph using the Girvan–Newman method. 

11 

12 Parameters 

13 ---------- 

14 G : NetworkX graph 

15 

16 most_valuable_edge : function 

17 Function that takes a graph as input and outputs an edge. The 

18 edge returned by this function will be recomputed and removed at 

19 each iteration of the algorithm. 

20 

21 If not specified, the edge with the highest 

22 :func:`networkx.edge_betweenness_centrality` will be used. 

23 

24 Returns 

25 ------- 

26 iterator 

27 Iterator over tuples of sets of nodes in `G`. Each set of node 

28 is a community, each tuple is a sequence of communities at a 

29 particular level of the algorithm. 

30 

31 Examples 

32 -------- 

33 To get the first pair of communities:: 

34 

35 >>> G = nx.path_graph(10) 

36 >>> comp = nx.community.girvan_newman(G) 

37 >>> tuple(sorted(c) for c in next(comp)) 

38 ([0, 1, 2, 3, 4], [5, 6, 7, 8, 9]) 

39 

40 To get only the first *k* tuples of communities, use 

41 :func:`itertools.islice`:: 

42 

43 >>> import itertools 

44 >>> G = nx.path_graph(8) 

45 >>> k = 2 

46 >>> comp = nx.community.girvan_newman(G) 

47 >>> for communities in itertools.islice(comp, k): 

48 ... print(tuple(sorted(c) for c in communities)) 

49 ... 

50 ([0, 1, 2, 3], [4, 5, 6, 7]) 

51 ([0, 1], [2, 3], [4, 5, 6, 7]) 

52 

53 To stop getting tuples of communities once the number of communities 

54 is greater than *k*, use :func:`itertools.takewhile`:: 

55 

56 >>> import itertools 

57 >>> G = nx.path_graph(8) 

58 >>> k = 4 

59 >>> comp = nx.community.girvan_newman(G) 

60 >>> limited = itertools.takewhile(lambda c: len(c) <= k, comp) 

61 >>> for communities in limited: 

62 ... print(tuple(sorted(c) for c in communities)) 

63 ... 

64 ([0, 1, 2, 3], [4, 5, 6, 7]) 

65 ([0, 1], [2, 3], [4, 5, 6, 7]) 

66 ([0, 1], [2, 3], [4, 5], [6, 7]) 

67 

68 To just choose an edge to remove based on the weight:: 

69 

70 >>> from operator import itemgetter 

71 >>> G = nx.path_graph(10) 

72 >>> edges = G.edges() 

73 >>> nx.set_edge_attributes(G, {(u, v): v for u, v in edges}, "weight") 

74 >>> def heaviest(G): 

75 ... u, v, w = max(G.edges(data="weight"), key=itemgetter(2)) 

76 ... return (u, v) 

77 ... 

78 >>> comp = nx.community.girvan_newman(G, most_valuable_edge=heaviest) 

79 >>> tuple(sorted(c) for c in next(comp)) 

80 ([0, 1, 2, 3, 4, 5, 6, 7, 8], [9]) 

81 

82 To utilize edge weights when choosing an edge with, for example, the 

83 highest betweenness centrality:: 

84 

85 >>> from networkx import edge_betweenness_centrality as betweenness 

86 >>> def most_central_edge(G): 

87 ... centrality = betweenness(G, weight="weight") 

88 ... return max(centrality, key=centrality.get) 

89 ... 

90 >>> G = nx.path_graph(10) 

91 >>> comp = nx.community.girvan_newman(G, most_valuable_edge=most_central_edge) 

92 >>> tuple(sorted(c) for c in next(comp)) 

93 ([0, 1, 2, 3, 4], [5, 6, 7, 8, 9]) 

94 

95 To specify a different ranking algorithm for edges, use the 

96 `most_valuable_edge` keyword argument:: 

97 

98 >>> from networkx import edge_betweenness_centrality 

99 >>> from random import random 

100 >>> def most_central_edge(G): 

101 ... centrality = edge_betweenness_centrality(G) 

102 ... max_cent = max(centrality.values()) 

103 ... # Scale the centrality values so they are between 0 and 1, 

104 ... # and add some random noise. 

105 ... centrality = {e: c / max_cent for e, c in centrality.items()} 

106 ... # Add some random noise. 

107 ... centrality = {e: c + random() for e, c in centrality.items()} 

108 ... return max(centrality, key=centrality.get) 

109 ... 

110 >>> G = nx.path_graph(10) 

111 >>> comp = nx.community.girvan_newman(G, most_valuable_edge=most_central_edge) 

112 

113 Notes 

114 ----- 

115 The Girvan–Newman algorithm detects communities by progressively 

116 removing edges from the original graph. The algorithm removes the 

117 "most valuable" edge, traditionally the edge with the highest 

118 betweenness centrality, at each step. As the graph breaks down into 

119 pieces, the tightly knit community structure is exposed and the 

120 result can be depicted as a dendrogram. 

121 

122 """ 

123 # If the graph is already empty, simply return its connected 

124 # components. 

125 if G.number_of_edges() == 0: 

126 yield tuple(nx.connected_components(G)) 

127 return 

128 # If no function is provided for computing the most valuable edge, 

129 # use the edge betweenness centrality. 

130 if most_valuable_edge is None: 

131 

132 def most_valuable_edge(G): 

133 """Returns the edge with the highest betweenness centrality 

134 in the graph `G`. 

135 

136 """ 

137 # We have guaranteed that the graph is non-empty, so this 

138 # dictionary will never be empty. 

139 betweenness = nx.edge_betweenness_centrality(G) 

140 return max(betweenness, key=betweenness.get) 

141 

142 # The copy of G here must include the edge weight data. 

143 g = G.copy().to_undirected() 

144 # Self-loops must be removed because their removal has no effect on 

145 # the connected components of the graph. 

146 g.remove_edges_from(nx.selfloop_edges(g)) 

147 while g.number_of_edges() > 0: 

148 yield _without_most_central_edges(g, most_valuable_edge) 

149 

150 

151def _without_most_central_edges(G, most_valuable_edge): 

152 """Returns the connected components of the graph that results from 

153 repeatedly removing the most "valuable" edge in the graph. 

154 

155 `G` must be a non-empty graph. This function modifies the graph `G` 

156 in-place; that is, it removes edges on the graph `G`. 

157 

158 `most_valuable_edge` is a function that takes the graph `G` as input 

159 (or a subgraph with one or more edges of `G` removed) and returns an 

160 edge. That edge will be removed and this process will be repeated 

161 until the number of connected components in the graph increases. 

162 

163 """ 

164 original_num_components = nx.number_connected_components(G) 

165 num_new_components = original_num_components 

166 while num_new_components <= original_num_components: 

167 edge = most_valuable_edge(G) 

168 G.remove_edge(*edge) 

169 new_components = tuple(nx.connected_components(G)) 

170 num_new_components = len(new_components) 

171 return new_components