cdlib.algorithms.gdmp2

gdmp2(g_original: object, min_threshold: float = 0.75) → cdlib.classes.node_clustering.NodeClustering

Gdmp2 is a method for identifying a set of dense subgraphs of a given sparse graph. It is inspired by an effective technique designed for a similar problem—matrix blocking, from a different discipline (solving linear systems).

Supported Graph Types

Undirected	Directed	Weighted	Bipartite
Yes	Yes	No	Yes

Parameters:

• g_original – a networkx/igraph object
• min_threshold – the minimum density threshold parameter to control the density of the output subgraphs, default 0.75

Returns:

NodeClustering object

Example:

>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> com = algorithms.gdmp2(G)

References:

Chen, Jie, and Yousef Saad. Dense subgraph extraction with application to community detection. IEEE Transactions on Knowledge and Data Engineering 24.7 (2012): 1216-1230.

Note

Reference implementation: https://github.com/imabhishekl/CSC591_Community_Detection