Clique percolation in Python with no external dependencies.

clique_percolation.py

"""Finds communities in the given graph using clique percolation."""


def _add_edge_to_adjancy_list(adjancy_list, node1, node2):
    if node1 in adjancy_list:
        adjancy_list[node1].add(node2)
    else:
        adjancy_list[node1] = set([node2])


def _find_connected_components(adjancy_list):
    connected_components = []
    node_set = set(adjancy_list.keys())
    while node_set:
        node = node_set.pop()
        component = {node}
        comp_queue = [node]
        while comp_queue:
            node = comp_queue.pop(0)
            neighbors = adjancy_list[node]
            new_nodes = neighbors - component
            node_set -= new_nodes
            component.update(new_nodes)
            comp_queue.extend(new_nodes)
        connected_components.append(component)
    return connected_components


def find_cliques(adjancy_list, k):
    """Uses brute-force search to find all k-cliques in the input graph."""
    node_set = set(adjancy_list.keys())
    cliques = set()
    for subset in combinations(node_set, k):
        subset = frozenset(subset)
        connected = [
            (subset - set([node])).issubset(adjancy_list[node])
            for node in subset
        ]
        if all(connected):
            cliques.add(subset)
    return cliques


def clique_percolation(adjancy_list, k):
    """Finds communities in the given graph using clique percolation."""
    k_cliques = list(find_cliques(adjancy_list, k))
    cliq_adjancy_list = {}
    for i, j in combinations(range(len(k_cliques)), 2):
        if len(k_cliques[i].intersection(k_cliques[j])) >= k - 1:
            _add_edge_to_adjancy_list(cliq_adjancy_list, i, j)
            _add_edge_to_adjancy_list(cliq_adjancy_list, j, i)
    connected_components = _find_connected_components(cliq_adjancy_list)
    communities = []
    for component in connected_components:
        community = set()
        for node in component:
            community.update(k_cliques[node])
        communities.append(sorted(community))
    return communities