Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/community/kclique.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
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) | |
32 >>> G.add_edges_from(K5.edges()) | |
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() | |
60 perc_graph.add_nodes_from(cliques) | |
61 for clique in cliques: | |
62 for adj_clique in _get_adjacent_cliques(clique, membership_dict): | |
63 if len(clique.intersection(adj_clique)) >= (k - 1): | |
64 perc_graph.add_edge(clique, adj_clique) | |
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 | |
72 def _get_adjacent_cliques(clique, membership_dict): | |
73 adjacent_cliques = set() | |
74 for n in clique: | |
75 for adj_clique in membership_dict[n]: | |
76 if clique != adj_clique: | |
77 adjacent_cliques.add(adj_clique) | |
78 return adjacent_cliques |