cdlib.algorithms.congo

congo(g_original: object, number_communities: int, height: int = 2) → cdlib.classes.node_clustering.NodeClustering

CONGO (CONGA Optimized) is an optimization of the CONGA algortithm. The CONGO algorithm is the same as CONGA but using local betweenness. The complete CONGO algorithm is as follows:

  1. Calculate edge betweenness of edges and split betweenness of vertices.
  2. Find edge with maximum edge betweenness or vertex with maximum split betweenness, if greater.
  3. Recalculate edge betweenness and split betweenness:
    1. Subtract betweenness of h-region centred on the removed edge or split vertex.
    2. Remove the edge or split the vertex.
    3. Add betweenness for the same region.
  4. 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
  • height – The lengh of the longest shortest paths that CONGO considers, default 2
Returns:

NodeClustering object

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

Gregory, Steve. A fast algorithm to find overlapping communities in networks. Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, Heidelberg, 2008.