diff env/lib/python3.9/site-packages/networkx/algorithms/community/kclique.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/community/kclique.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,78 @@
+from collections import defaultdict
+import networkx as nx
+
+__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))
+    >>> sorted(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(f"k={k}, k must be greater than 1.")
+    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