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