Statistics
| Branch: | Revision:

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

 1 ```#-*- coding: utf-8 -*- ``` ```# Copyright (C) 2011 by ``` ```# Conrad Lee ``` ```# Aric Hagberg ``` ```# All rights reserved. ``` ```# BSD license. ``` ```from collections import defaultdict ``` ```import networkx as nx ``` ```__author__ = """\n""".join(['Conrad Lee ', ``` ``` 'Aric Hagberg ']) ``` ```__all__ = ['k_clique_communities'] ``` ```def k_clique_communities(G, k, cliques=None): ``` ``` """Find k-clique communities in graph using the percolation method. ``` ``` ``` ``` A k-clique community is the union of all cliques of size k that ``` ``` can be reached through adjacent (sharing k-1 nodes) k-cliques. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` ``` ``` k : int ``` ``` Size of smallest clique ``` ``` ``` ``` cliques: list or generator ``` ``` Precomputed cliques (use networkx.find_cliques(G)) ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` Yields sets of nodes, one for each k-clique community. ``` ``` ``` ``` Examples ``` ``` -------- ``` ``` >>> from networkx.algorithms.community import k_clique_communities ``` ``` >>> G = nx.complete_graph(5) ``` ``` >>> K5 = nx.convert_node_labels_to_integers(G,first_label=2) ``` ``` >>> G.add_edges_from(K5.edges()) ``` ``` >>> c = list(k_clique_communities(G, 4)) ``` ``` >>> list(c[0]) ``` ``` [0, 1, 2, 3, 4, 5, 6] ``` ``` >>> list(k_clique_communities(G, 6)) ``` ``` [] ``` ``` ``` ``` References ``` ``` ---------- ``` ``` .. [1] Gergely Palla, Imre Derényi, Illés Farkas1, and Tamás Vicsek, ``` ``` Uncovering the overlapping community structure of complex networks ``` ``` in nature and society Nature 435, 814-818, 2005, ``` ``` doi:10.1038/nature03607 ``` ``` """ ``` ``` if k < 2: ``` ``` raise nx.NetworkXError("k=%d, k must be greater than 1." % k) ``` ``` if cliques is None: ``` ``` cliques = nx.find_cliques(G) ``` ``` cliques = [frozenset(c) for c in cliques if len(c) >= k] ``` ``` # First index which nodes are in which cliques ``` ``` membership_dict = defaultdict(list) ``` ``` for clique in cliques: ``` ``` for node in clique: ``` ``` membership_dict[node].append(clique) ``` ``` # For each clique, see which adjacent cliques percolate ``` ``` perc_graph = nx.Graph() ``` ``` perc_graph.add_nodes_from(cliques) ``` ``` for clique in cliques: ``` ``` for adj_clique in _get_adjacent_cliques(clique, membership_dict): ``` ``` if len(clique.intersection(adj_clique)) >= (k - 1): ``` ``` perc_graph.add_edge(clique, adj_clique) ``` ``` # Connected components of clique graph with perc edges ``` ``` # are the percolated cliques ``` ``` for component in nx.connected_components(perc_graph): ``` ``` yield(frozenset.union(*component)) ``` ```def _get_adjacent_cliques(clique, membership_dict): ``` ``` adjacent_cliques = set() ``` ``` for n in clique: ``` ``` for adj_clique in membership_dict[n]: ``` ``` if clique != adj_clique: ``` ``` adjacent_cliques.add(adj_clique) ``` ``` return adjacent_cliques ```