cdlib.algorithms.demon

demon(g_original: object, epsilon: float, min_com_size: int = 3) → cdlib.classes.node_clustering.NodeClustering

Demon is a node-centric bottom-up overlapping community discovery algorithm. It leverages ego-network structures and overlapping label propagation to identify micro-scale communities that are subsequently merged in mesoscale ones.

Supported Graph Types

Undirected Directed Weighted
Yes No No
Parameters:
  • g_original – a networkx/igraph object
  • epsilon – merging threshold in [0,1], default 0.25.
  • min_com_size – minimum community size, default 3.
Returns:

NodeClustering object
Example: 
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> coms = algorithms.demon(G, min_com_size=3, epsilon=0.25)
References:
  1. Coscia, M., Rossetti, G., Giannotti, F., & Pedreschi, D. (2012, August). Demon: a local-first discovery method for overlapping communities. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 615-623). ACM.
  2. Coscia, M., Rossetti, G., Giannotti, F., & Pedreschi, D. (2014). Uncovering hierarchical and overlapping communities with a local-first approach. ACM Transactions on Knowledge Discovery from Data (TKDD), 9(1), 6.

Note

Reference implementation: https://github.com/GiulioRossetti/DEMON