Skip to content

Instantly share code, notes, and snippets.

@shaypal5
Last active January 24, 2017 19:44
Show Gist options
  • Save shaypal5/dbdd5146b8f0c91708d772368bbd9241 to your computer and use it in GitHub Desktop.
Save shaypal5/dbdd5146b8f0c91708d772368bbd9241 to your computer and use it in GitHub Desktop.
Clique percolation in Python with no external dependencies.
"""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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment