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:
- 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 non-empty, 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