Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/community/kclique.py: 21%

1from collections import defaultdict 

2 

3import networkx as nx 

4 

5__all__ = ["k_clique_communities"] 

6 

7 

8@nx._dispatch 

9def k_clique_communities(G, k, cliques=None): 

10 """Find k-clique communities in graph using the percolation method. 

11 

12 A k-clique community is the union of all cliques of size k that 

13 can be reached through adjacent (sharing k-1 nodes) k-cliques. 

14 

15 Parameters 

16 ---------- 

17 G : NetworkX graph 

18 

19 k : int 

20 Size of smallest clique 

21 

22 cliques: list or generator 

23 Precomputed cliques (use networkx.find_cliques(G)) 

24 

25 Returns 

26 ------- 

27 Yields sets of nodes, one for each k-clique community. 

28 

29 Examples 

30 -------- 

31 >>> G = nx.complete_graph(5) 

32 >>> K5 = nx.convert_node_labels_to_integers(G, first_label=2) 

33 >>> G.add_edges_from(K5.edges()) 

34 >>> c = list(nx.community.k_clique_communities(G, 4)) 

35 >>> sorted(list(c[0])) 

36 [0, 1, 2, 3, 4, 5, 6] 

37 >>> list(nx.community.k_clique_communities(G, 6)) 

38 [] 

39 

40 References 

41 ---------- 

42 .. [1] Gergely Palla, Imre Derényi, Illés Farkas1, and Tamás Vicsek, 

43 Uncovering the overlapping community structure of complex networks 

44 in nature and society Nature 435, 814-818, 2005, 

45 doi:10.1038/nature03607 

46 """ 

47 if k < 2: 

48 raise nx.NetworkXError(f"k={k}, k must be greater than 1.") 

49 if cliques is None: 

50 cliques = nx.find_cliques(G) 

51 cliques = [frozenset(c) for c in cliques if len(c) >= k] 

52 

53 # First index which nodes are in which cliques 

54 membership_dict = defaultdict(list) 

55 for clique in cliques: 

56 for node in clique: 

57 membership_dict[node].append(clique) 

58 

59 # For each clique, see which adjacent cliques percolate 

60 perc_graph = nx.Graph() 

61 perc_graph.add_nodes_from(cliques) 

62 for clique in cliques: 

63 for adj_clique in _get_adjacent_cliques(clique, membership_dict): 

64 if len(clique.intersection(adj_clique)) >= (k - 1): 

65 perc_graph.add_edge(clique, adj_clique) 

66 

67 # Connected components of clique graph with perc edges 

68 # are the percolated cliques 

69 for component in nx.connected_components(perc_graph): 

70 yield (frozenset.union(*component)) 

71 

72 

73def _get_adjacent_cliques(clique, membership_dict): 

74 adjacent_cliques = set() 

75 for n in clique: 

76 for adj_clique in membership_dict[n]: 

77 if clique != adj_clique: 

78 adjacent_cliques.add(adj_clique) 

79 return adjacent_cliques