ioftools / networkxMiCe / networkxmaster / networkx / algorithms / community / asyn_fluid.py @ 5cef0f13
History  View  Annotate  Download (5.87 KB)
1 
# * coding: utf8 *


2 
# Copyright (C) 20172019

3 
# All rights reserved.

4 
# BSD license.

5 
# Author: Ferran Parés <ferran.pares@bsc.es>

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

7  
8 
from collections import Counter 
9 
from networkx.exception import NetworkXError 
10 
from networkx.algorithms.components import is_connected 
11 
from networkx.utils import groups 
12 
from networkx.utils import not_implemented_for 
13 
from networkx.utils import py_random_state 
14  
15 
__all__ = ['asyn_fluidc']

16  
17  
18 
@py_random_state(3) 
19 
@not_implemented_for('directed', 'multigraph') 
20 
def asyn_fluidc(G, k, max_iter=100, seed=None): 
21 
"""Returns communities in `G` as detected by Fluid Communities algorithm.

22 

23 
The asynchronous fluid communities algorithm is described in

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

25 
in an environment, expanding and pushing each other. It's initialization is

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

27 

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

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

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

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

32 
process is performed several times until convergence.

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

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

35 
community, vertex densities of affected communities are adjusted

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

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

38 
and returns.

39 

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

41 
Unfortunately, it does not support weighted graphs yet.

42 

43 
Parameters

44 


45 
G : Graph

46 

47 
k : integer

48 
The number of communities to be found.

49 

50 
max_iter : integer

51 
The number of maximum iterations allowed. By default 15.

52 

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

54 
Indicator of random number generation state.

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

56 

57 
Returns

58 


59 
communities : iterable

60 
Iterable of communities given as sets of nodes.

61 

62 
Notes

63 


64 
k variable is not an optional argument.

65 

66 
References

67 


68 
.. [1] Parés F., GarciaGasulla D. et al. "Fluid Communities: A

69 
Competitive and Highly Scalable Community Detection Algorithm".

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

71 
"""

72 
# Initial checks

73 
if not isinstance(k, int): 
74 
raise NetworkXError("k must be an integer.") 
75 
if not k > 0: 
76 
raise NetworkXError("k must be greater than 0.") 
77 
if not is_connected(G): 
78 
raise NetworkXError("Fluid Communities require connected Graphs.") 
79 
if len(G) < k: 
80 
raise NetworkXError("k cannot be bigger than the number of nodes.") 
81 
# Initialization

82 
max_density = 1.0

83 
vertices = list(G)

84 
seed.shuffle(vertices) 
85 
communities = {n: i for i, n in enumerate(vertices[:k])} 
86 
density = {} 
87 
com_to_numvertices = {} 
88 
for vertex in communities.keys(): 
89 
com_to_numvertices[communities[vertex]] = 1

90 
density[communities[vertex]] = max_density 
91 
# Set up control variables and start iterating

92 
iter_count = 0

93 
cont = True

94 
while cont:

95 
cont = False

96 
iter_count += 1

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

98 
vertices = list(G)

99 
seed.shuffle(vertices) 
100 
for vertex in vertices: 
101 
# Updating rule

102 
com_counter = Counter() 
103 
# Take into account self vertex community

104 
try:

105 
com_counter.update({communities[vertex]: 
106 
density[communities[vertex]]}) 
107 
except KeyError: 
108 
pass

109 
# Gather neighbour vertex communities

110 
for v in G[vertex]: 
111 
try:

112 
com_counter.update({communities[v]: 
113 
density[communities[v]]}) 
114 
except KeyError: 
115 
continue

116 
# Check which is the community with highest density

117 
new_com = 1

118 
if len(com_counter.keys()) > 0: 
119 
max_freq = max(com_counter.values())

120 
best_communities = [com for com, freq in com_counter.items() 
121 
if (max_freq  freq) < 0.0001] 
122 
# If actual vertex com in best communities, it is preserved

123 
try:

124 
if communities[vertex] in best_communities: 
125 
new_com = communities[vertex] 
126 
except KeyError: 
127 
pass

128 
# If vertex community changes...

129 
if new_com == 1: 
130 
# Set flag of nonconvergence

131 
cont = True

132 
# Randomly chose a new community from candidates

133 
new_com = seed.choice(best_communities) 
134 
# Update previous community status

135 
try:

136 
com_to_numvertices[communities[vertex]] = 1

137 
density[communities[vertex]] = max_density / \ 
138 
com_to_numvertices[communities[vertex]] 
139 
except KeyError: 
140 
pass

141 
# Update new community status

142 
communities[vertex] = new_com 
143 
com_to_numvertices[communities[vertex]] += 1

144 
density[communities[vertex]] = max_density / \ 
145 
com_to_numvertices[communities[vertex]] 
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()) 