cdlib.algorithms.conga¶

conga
(g_original: object, number_communities: int) → cdlib.classes.node_clustering.NodeClustering¶ CONGA (ClusterOverlap 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:
 Calculate edge betweenness of all edges in network.
 Calculate vertex betweenness of vertices, from edge betweennesses.
 Find candidate set of vertices: those whose vertex betweenness is greater than the maximum edge betweenness.
 If candidate set is nonempty, calculate pair betweennesses of candidate vertices, and then calculate split betweenness of candidate vertices.
 Remove edge with maximum edge betweenness or split vertex with maximum split betweenness (if greater).
 Recalculate edge betweenness for all remaining edges in same component(s) as removed edge or split vertex.
 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.
Note
Reference implementation: https://github.com/Lab41/Circulo/tree/master/circulo/algorithms