Skip to main content
`Ctrl`+`K`

# Source code for networkx.algorithms.community.kclique

    from collections import defaultdict

    import networkx as nx

    __all__ = ["k_clique_communities"]

    @nx._dispatchable
    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.community.k_clique_communities(G, 4))
        >>> sorted(list(c[0]))
        [0, 1, 2, 3, 4, 5, 6]
        >>> list(nx.community.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