Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.72 KB)

1
#-*- coding: utf-8 -*-
2
#    Copyright (C) 2011 by
3
#    Conrad Lee <conradlee@gmail.com>
4
#    Aric Hagberg <hagberg@lanl.gov>
5
#    All rights reserved.
6
#    BSD license.
7
from collections import defaultdict
8
import networkx as nx
9
__author__ = """\n""".join(['Conrad Lee <conradlee@gmail.com>',
10
                            'Aric Hagberg <aric.hagberg@gmail.com>'])
11
__all__ = ['k_clique_communities']
12

    
13

    
14
def k_clique_communities(G, k, cliques=None):
15
    """Find k-clique communities in graph using the percolation method.
16

17
    A k-clique community is the union of all cliques of size k that
18
    can be reached through adjacent (sharing k-1 nodes) k-cliques.
19

20
    Parameters
21
    ----------
22
    G : NetworkX graph
23

24
    k : int
25
       Size of smallest clique
26

27
    cliques: list or generator       
28
       Precomputed cliques (use networkx.find_cliques(G))
29

30
    Returns
31
    -------
32
    Yields sets of nodes, one for each k-clique community.
33

34
    Examples
35
    --------
36
    >>> from networkx.algorithms.community import k_clique_communities
37
    >>> G = nx.complete_graph(5)
38
    >>> K5 = nx.convert_node_labels_to_integers(G,first_label=2)
39
    >>> G.add_edges_from(K5.edges())
40
    >>> c = list(k_clique_communities(G, 4))
41
    >>> list(c[0])
42
    [0, 1, 2, 3, 4, 5, 6]
43
    >>> list(k_clique_communities(G, 6))
44
    []
45

46
    References
47
    ----------
48
    .. [1] Gergely Palla, Imre Derényi, Illés Farkas1, and Tamás Vicsek,
49
       Uncovering the overlapping community structure of complex networks 
50
       in nature and society Nature 435, 814-818, 2005,
51
       doi:10.1038/nature03607
52
    """
53
    if k < 2:
54
        raise nx.NetworkXError("k=%d, k must be greater than 1." % k)
55
    if cliques is None:
56
        cliques = nx.find_cliques(G)
57
    cliques = [frozenset(c) for c in cliques if len(c) >= k]
58

    
59
    # First index which nodes are in which cliques
60
    membership_dict = defaultdict(list)
61
    for clique in cliques:
62
        for node in clique:
63
            membership_dict[node].append(clique)
64

    
65
    # For each clique, see which adjacent cliques percolate
66
    perc_graph = nx.Graph()
67
    perc_graph.add_nodes_from(cliques)
68
    for clique in cliques:
69
        for adj_clique in _get_adjacent_cliques(clique, membership_dict):
70
            if len(clique.intersection(adj_clique)) >= (k - 1):
71
                perc_graph.add_edge(clique, adj_clique)
72

    
73
    # Connected components of clique graph with perc edges
74
    # are the percolated cliques
75
    for component in nx.connected_components(perc_graph):
76
        yield(frozenset.union(*component))
77

    
78

    
79
def _get_adjacent_cliques(clique, membership_dict):
80
    adjacent_cliques = set()
81
    for n in clique:
82
        for adj_clique in membership_dict[n]:
83
            if clique != adj_clique:
84
                adjacent_cliques.add(adj_clique)
85
    return adjacent_cliques