Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / community / asyn_fluid.py @ 5cef0f13

History | View | Annotate | Download (5.87 KB)

1
# -*- coding: utf-8 -*-
2
#    Copyright (C) 2017-2019
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., Garcia-Gasulla 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 non-convergence
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())