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

1"""Asynchronous Fluid Communities algorithm for community detection.""" 

2 

3from collections import Counter 

4 

5import networkx as nx 

6from networkx.algorithms.components import is_connected 

7from networkx.exception import NetworkXError 

8from networkx.utils import groups, not_implemented_for, py_random_state 

9 

10__all__ = ["asyn_fluidc"] 

11 

12 

13@not_implemented_for("directed", "multigraph") 

14@py_random_state(3) 

15@nx._dispatch 

16def asyn_fluidc(G, k, max_iter=100, seed=None): 

17 """Returns communities in `G` as detected by Fluid Communities algorithm. 

18 

19 The asynchronous fluid communities algorithm is described in 

20 [1]_. The algorithm is based on the simple idea of fluids interacting 

21 in an environment, expanding and pushing each other. Its initialization is 

22 random, so found communities may vary on different executions. 

23 

24 The algorithm proceeds as follows. First each of the initial k communities 

25 is initialized in a random vertex in the graph. Then the algorithm iterates 

26 over all vertices in a random order, updating the community of each vertex 

27 based on its own community and the communities of its neighbours. This 

28 process is performed several times until convergence. 

29 At all times, each community has a total density of 1, which is equally 

30 distributed among the vertices it contains. If a vertex changes of 

31 community, vertex densities of affected communities are adjusted 

32 immediately. When a complete iteration over all vertices is done, such that 

33 no vertex changes the community it belongs to, the algorithm has converged 

34 and returns. 

35 

36 This is the original version of the algorithm described in [1]_. 

37 Unfortunately, it does not support weighted graphs yet. 

38 

39 Parameters 

40 ---------- 

41 G : NetworkX graph 

42 Graph must be simple and undirected. 

43 

44 k : integer 

45 The number of communities to be found. 

46 

47 max_iter : integer 

48 The number of maximum iterations allowed. By default 100. 

49 

50 seed : integer, random_state, or None (default) 

51 Indicator of random number generation state. 

52 See :ref:`Randomness<randomness>`. 

53 

54 Returns 

55 ------- 

56 communities : iterable 

57 Iterable of communities given as sets of nodes. 

58 

59 Notes 

60 ----- 

61 k variable is not an optional argument. 

62 

63 References 

64 ---------- 

65 .. [1] Parés F., Garcia-Gasulla D. et al. "Fluid Communities: A 

66 Competitive and Highly Scalable Community Detection Algorithm". 

67 [https://arxiv.org/pdf/1703.09307.pdf]. 

68 """ 

69 # Initial checks 

70 if not isinstance(k, int): 

71 raise NetworkXError("k must be an integer.") 

72 if not k > 0: 

73 raise NetworkXError("k must be greater than 0.") 

74 if not is_connected(G): 

75 raise NetworkXError("Fluid Communities require connected Graphs.") 

76 if len(G) < k: 

77 raise NetworkXError("k cannot be bigger than the number of nodes.") 

78 # Initialization 

79 max_density = 1.0 

80 vertices = list(G) 

81 seed.shuffle(vertices) 

82 communities = {n: i for i, n in enumerate(vertices[:k])} 

83 density = {} 

84 com_to_numvertices = {} 

85 for vertex in communities: 

86 com_to_numvertices[communities[vertex]] = 1 

87 density[communities[vertex]] = max_density 

88 # Set up control variables and start iterating 

89 iter_count = 0 

90 cont = True 

91 while cont: 

92 cont = False 

93 iter_count += 1 

94 # Loop over all vertices in graph in a random order 

95 vertices = list(G) 

96 seed.shuffle(vertices) 

97 for vertex in vertices: 

98 # Updating rule 

99 com_counter = Counter() 

100 # Take into account self vertex community 

101 try: 

102 com_counter.update({communities[vertex]: density[communities[vertex]]}) 

103 except KeyError: 

104 pass 

105 # Gather neighbour vertex communities 

106 for v in G[vertex]: 

107 try: 

108 com_counter.update({communities[v]: density[communities[v]]}) 

109 except KeyError: 

110 continue 

111 # Check which is the community with highest density 

112 new_com = -1 

113 if len(com_counter.keys()) > 0: 

114 max_freq = max(com_counter.values()) 

115 best_communities = [ 

116 com 

117 for com, freq in com_counter.items() 

118 if (max_freq - freq) < 0.0001 

119 ] 

120 # If actual vertex com in best communities, it is preserved 

121 try: 

122 if communities[vertex] in best_communities: 

123 new_com = communities[vertex] 

124 except KeyError: 

125 pass 

126 # If vertex community changes... 

127 if new_com == -1: 

128 # Set flag of non-convergence 

129 cont = True 

130 # Randomly chose a new community from candidates 

131 new_com = seed.choice(best_communities) 

132 # Update previous community status 

133 try: 

134 com_to_numvertices[communities[vertex]] -= 1 

135 density[communities[vertex]] = ( 

136 max_density / com_to_numvertices[communities[vertex]] 

137 ) 

138 except KeyError: 

139 pass 

140 # Update new community status 

141 communities[vertex] = new_com 

142 com_to_numvertices[communities[vertex]] += 1 

143 density[communities[vertex]] = ( 

144 max_density / com_to_numvertices[communities[vertex]] 

145 ) 

146 # If maximum iterations reached --> output actual results 

147 if iter_count > max_iter: 

148 break 

149 # Return results by grouping communities as list of vertices 

150 return iter(groups(communities).values())