comparison env/lib/python3.9/site-packages/networkx/algorithms/community/kclique.py @ 0:4f3585e2f14bdraftdefaulttip

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal inserted replaced
-1:000000000000 0:4f3585e2f14b
1 from collections import defaultdict
2 import networkx as nx
3
4 __all__ = ["k_clique_communities"]
5
6
7 def k_clique_communities(G, k, cliques=None):
8 """Find k-clique communities in graph using the percolation method.
9
10 A k-clique community is the union of all cliques of size k that
11 can be reached through adjacent (sharing k-1 nodes) k-cliques.
12
13 Parameters
14 ----------
15 G : NetworkX graph
16
17 k : int
18 Size of smallest clique
19
20 cliques: list or generator
21 Precomputed cliques (use networkx.find_cliques(G))
22
23 Returns
24 -------
25 Yields sets of nodes, one for each k-clique community.
26
27 Examples
28 --------
29 >>> from networkx.algorithms.community import k_clique_communities
30 >>> G = nx.complete_graph(5)
31 >>> K5 = nx.convert_node_labels_to_integers(G, first_label=2)
33 >>> c = list(k_clique_communities(G, 4))
34 >>> sorted(list(c[0]))
35 [0, 1, 2, 3, 4, 5, 6]
36 >>> list(k_clique_communities(G, 6))
37 []
38
39 References
40 ----------
41 .. [1] Gergely Palla, Imre Derényi, Illés Farkas1, and Tamás Vicsek,
42 Uncovering the overlapping community structure of complex networks
43 in nature and society Nature 435, 814-818, 2005,
44 doi:10.1038/nature03607
45 """
46 if k < 2:
47 raise nx.NetworkXError(f"k={k}, k must be greater than 1.")
48 if cliques is None:
49 cliques = nx.find_cliques(G)
50 cliques = [frozenset(c) for c in cliques if len(c) >= k]
51
52 # First index which nodes are in which cliques
53 membership_dict = defaultdict(list)
54 for clique in cliques:
55 for node in clique:
56 membership_dict[node].append(clique)
57
58 # For each clique, see which adjacent cliques percolate
59 perc_graph = nx.Graph()
61 for clique in cliques:
63 if len(clique.intersection(adj_clique)) >= (k - 1):
65
66 # Connected components of clique graph with perc edges
67 # are the percolated cliques
68 for component in nx.connected_components(perc_graph):
69 yield (frozenset.union(*component))
70
71