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:
- 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.
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