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
1"""Asynchronous Fluid Communities algorithm for community detection."""
3from collections import Counter
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
10__all__ = ["asyn_fluidc"]
13@not_implemented_for("directed")
14@not_implemented_for("multigraph")
15@py_random_state(3)
16@nx._dispatchable
17def asyn_fluidc(G, k, max_iter=100, seed=None):
18 """Returns communities in `G` as detected by Fluid Communities algorithm.
20 The asynchronous fluid communities algorithm is described in
21 [1]_. The algorithm is based on the simple idea of fluids interacting
22 in an environment, expanding and pushing each other. Its initialization is
23 random, so found communities may vary on different executions.
25 The algorithm proceeds as follows. First each of the initial k communities
26 is initialized in a random vertex in the graph. Then the algorithm iterates
27 over all vertices in a random order, updating the community of each vertex
28 based on its own community and the communities of its neighbors. This
29 process is performed several times until convergence.
30 At all times, each community has a total density of 1, which is equally
31 distributed among the vertices it contains. If a vertex changes of
32 community, vertex densities of affected communities are adjusted
33 immediately. When a complete iteration over all vertices is done, such that
34 no vertex changes the community it belongs to, the algorithm has converged
35 and returns.
37 This is the original version of the algorithm described in [1]_.
38 Unfortunately, it does not support weighted graphs yet.
40 Parameters
41 ----------
42 G : NetworkX graph
43 Graph must be simple and undirected.
45 k : integer
46 The number of communities to be found.
48 max_iter : integer
49 The number of maximum iterations allowed. By default 100.
51 seed : integer, random_state, or None (default)
52 Indicator of random number generation state.
53 See :ref:`Randomness<randomness>`.
55 Returns
56 -------
57 communities : iterable
58 Iterable of communities given as sets of nodes.
60 Notes
61 -----
62 k variable is not an optional argument.
64 References
65 ----------
66 .. [1] Parés F., Garcia-Gasulla D. et al. "Fluid Communities: A
67 Competitive and Highly Scalable Community Detection Algorithm".
68 [https://arxiv.org/pdf/1703.09307.pdf].
69 """
70 # Initial checks
71 if not isinstance(k, int):
72 raise NetworkXError("k must be an integer.")
73 if not k > 0:
74 raise NetworkXError("k must be greater than 0.")
75 if not is_connected(G):
76 raise NetworkXError("Fluid Communities require connected Graphs.")
77 if len(G) < k:
78 raise NetworkXError("k cannot be bigger than the number of nodes.")
79 if max_iter <= 0:
80 msg = f"{max_iter=} must be greater than 0"
81 raise ValueError(msg)
82 # Initialization
83 max_density = 1.0
84 vertices = list(G)
85 seed.shuffle(vertices)
86 communities = {n: i for i, n in enumerate(vertices[:k])}
87 density = {}
88 com_to_numvertices = {}
89 for vertex in communities:
90 com_to_numvertices[communities[vertex]] = 1
91 density[communities[vertex]] = max_density
92 # Set up control variables and start iterating
93 iter_count = 0
94 cont = True
95 while cont and iter_count < max_iter:
96 cont = False
97 iter_count += 1
98 # Loop over all vertices in graph in a random order
99 vertices = list(G)
100 seed.shuffle(vertices)
101 for vertex in vertices:
102 # Updating rule
103 com_counter = Counter()
104 # Take into account self vertex community
105 try:
106 com_counter.update({communities[vertex]: density[communities[vertex]]})
107 except KeyError:
108 pass
109 # Gather neighbor vertex communities
110 for v in G[vertex]:
111 try:
112 com_counter.update({communities[v]: density[communities[v]]})
113 except KeyError:
114 continue
115 # Check which is the community with highest density
116 new_com = -1
117 if len(com_counter.keys()) > 0:
118 max_freq = max(com_counter.values())
119 best_communities = [
120 com
121 for com, freq in com_counter.items()
122 if (max_freq - freq) < 0.0001
123 ]
124 # If actual vertex com in best communities, it is preserved
125 try:
126 if communities[vertex] in best_communities:
127 new_com = communities[vertex]
128 except KeyError:
129 pass
131 # If vertex community changes...
132 if new_com == -1:
133 # Set flag of non-convergence
134 cont = True
135 # Randomly chose a new community from candidates
136 new_com = seed.choice(best_communities)
137 # Update previous community status
138 try:
139 com_to_numvertices[communities[vertex]] -= 1
140 density[communities[vertex]] = (
141 max_density / com_to_numvertices[communities[vertex]]
142 )
143 except KeyError:
144 pass
145 # Update new community status
146 communities[vertex] = new_com
147 com_to_numvertices[communities[vertex]] += 1
148 density[communities[vertex]] = (
149 max_density / com_to_numvertices[communities[vertex]]
150 )
151 # If maximum iterations reached --> output actual results
152 # Return results by grouping communities as list of vertices
153 return iter(groups(communities).values())