cdlib.algorithms.congo¶
- cdlib.algorithms.congo(g_original: object, number_communities: int, height: int = 2) 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:
Calculate edge betweenness of edges and split betweenness of vertices.
Find edge with maximum edge betweenness or vertex with maximum split betweenness, if greater.
- Recalculate edge betweenness and split betweenness:
Subtract betweenness of h-region centred on the removed edge or split vertex.
Remove the edge or split the vertex.
Add betweenness for the same region.
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.
Note
Reference implementation: https://github.com/Lab41/Circulo/tree/master/circulo/algorithms