cdlib.algorithms.conga

conga(g_original: object, number_communities: int) → cdlib.classes.node_clustering.NodeClustering

CONGA (Cluster-Overlap Newman Girvan Algorithm) is an algorithm for discovering overlapping communities. It extends the Girvan and Newman’s algorithm with a specific method of deciding when and how to split vertices. The algorithm is as follows:

  1. Calculate edge betweenness of all edges in network.
  2. Calculate vertex betweenness of vertices, from edge betweennesses.
  3. Find candidate set of vertices: those whose vertex betweenness is greater than the maximum edge betweenness.
  4. If candidate set is non-empty, calculate pair betweennesses of candidate vertices, and then calculate split betweenness of candidate vertices.
  5. Remove edge with maximum edge betweenness or split vertex with maximum split betweenness (if greater).
  6. Recalculate edge betweenness for all remaining edges in same component(s) as removed edge or split vertex.
  7. Repeat from step 2 until no edges remain.

Supported Graph Types

Undirected Directed Weighted
Yes No No
Parameters:
  • g_original – a networkx/igraph object
  • number_communities – the number of communities desired
Returns:

NodeClustering object

Example:
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> com = algorithms.conga(G, number_communities=3)
References:

Gregory, Steve. An algorithm to find overlapping community structure in networks. European Conference on Principles of Data Mining and Knowledge Discovery. Springer, Berlin, Heidelberg, 2007.