← Back to branch summary

~ubuntu-branches/ubuntu/utopic/python-networkx/utopic

« back to all changes in this revision

Viewing changes to networkx/algorithms/community/kclique.py

  • Committer: Package Import Robot
  • Author(s): Sandro Tosi
  • Date: 2012-08-11 12:41:30 UTC
  • mfrom: (1.4.1) (5.1.13 sid)
  • Revision ID: package-import@ubuntu.com-20120811124130-whr6uso7fncyg8bi
Tags: 1.7-1
* New upstream release
* debian/patches/changeset_*
  - removed, included upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/community/kclique.py
 
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
def k_clique_communities(G, k, cliques=None):
 
14
    """Find k-clique communities in graph using the percolation method.
 
15
 
 
16
    A k-clique community is the union of all cliques of size k that
 
17
    can be reached through adjacent (sharing k-1 nodes) k-cliques.
 
18
 
 
19
    Parameters
 
20
    ----------
 
21
    G : NetworkX graph
 
22
 
 
23
    k : int
 
24
       Size of smallest clique
 
25
 
 
26
    cliques: list or generator       
 
27
       Precomputed cliques (use networkx.find_cliques(G))
 
28
 
 
29
    Returns
 
30
    -------
 
31
    Yields sets of nodes, one for each k-clique community.
 
32
 
 
33
    Examples
 
34
    --------
 
35
    >>> G = nx.complete_graph(5)
 
36
    >>> K5 = nx.convert_node_labels_to_integers(G,first_label=2)
 
37
    >>> G.add_edges_from(K5.edges())
 
38
    >>> c = list(nx.k_clique_communities(G, 4))
 
39
    >>> list(c[0])
 
40
    [0, 1, 2, 3, 4, 5, 6]
 
41
    >>> list(nx.k_clique_communities(G, 6))
 
42
    []
 
43
 
 
44
    References
 
45
    ----------
 
46
    .. [1] Gergely Palla, Imre Derényi, Illés Farkas1, and Tamás Vicsek,
 
47
       Uncovering the overlapping community structure of complex networks 
 
48
       in nature and society Nature 435, 814-818, 2005,
 
49
       doi:10.1038/nature03607
 
50
    """
 
51
    if k < 2:
 
52
        raise nx.NetworkXError("k=%d, k must be greater than 1."%k)
 
53
    if cliques is None:
 
54
        cliques = nx.find_cliques(G)
 
55
    cliques = [frozenset(c) for c in cliques if len(c) >= k]
 
56
 
 
57
    # First index which nodes are in which cliques
 
58
    membership_dict = defaultdict(list)
 
59
    for clique in cliques:
 
60
        for node in clique:
 
61
            membership_dict[node].append(clique)
 
62
 
 
63
    # For each clique, see which adjacent cliques percolate
 
64
    perc_graph = nx.Graph()
 
65
    perc_graph.add_nodes_from(cliques)
 
66
    for clique in cliques:
 
67
        for adj_clique in _get_adjacent_cliques(clique, membership_dict):
 
68
            if len(clique.intersection(adj_clique)) >= (k - 1):
 
69
                perc_graph.add_edge(clique, adj_clique)
 
70
 
 
71
    # Connected components of clique graph with perc edges
 
72
    # are the percolated cliques
 
73
    for component in nx.connected_components(perc_graph):
 
74
        yield(frozenset.union(*component))
 
75
 
 
76
def _get_adjacent_cliques(clique, membership_dict):
 
77
    adjacent_cliques = set()
 
78
    for n in clique:
 
79
        for adj_clique in membership_dict[n]:
 
80
            if clique != adj_clique:
 
81
                adjacent_cliques.add(adj_clique)
 
82
    return adjacent_cliques