/usr/lib/python2.7/dist-packages/networkx/algorithms/community/kclique.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #-*- coding: utf-8 -*-
# Copyright (C) 2011 by
# Conrad Lee <conradlee@gmail.com>
# Aric Hagberg <hagberg@lanl.gov>
# All rights reserved.
# BSD license.
from collections import defaultdict
import networkx as nx
__author__ = """\n""".join(['Conrad Lee <conradlee@gmail.com>',
'Aric Hagberg <aric.hagberg@gmail.com>'])
__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
--------
>>> G = nx.complete_graph(5)
>>> K5 = nx.convert_node_labels_to_integers(G,first_label=2)
>>> G.add_edges_from(K5.edges())
>>> c = list(nx.k_clique_communities(G, 4))
>>> list(c[0])
[0, 1, 2, 3, 4, 5, 6]
>>> list(nx.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
|