cdlib.algorithms.lemon

lemon(g_original: object, seeds: list, min_com_size: int = 20, max_com_size: int = 50, expand_step: int = 6, subspace_dim: int = 3, walk_steps: int = 3, biased: bool = False) → cdlib.classes.node_clustering.NodeClustering

Lemon is a large scale overlapping community detection method based on local expansion via minimum one norm.

The algorithm adopts a local expansion method in order to identify the community members from a few exemplary seed members. The algorithm finds the community by seeking a sparse vector in the span of the local spectra such that the seeds are in its support. LEMON can achieve the highest detection accuracy among state-of-the-art proposals. The running time depends on the size of the community rather than that of the entire graph.

Supported Graph Types

Undirected Directed Weighted
Yes No No
Parameters:
  • g_original – a networkx/igraph object
  • seeds – Node list
  • min_com_size – the minimum size of a single community in the network, default 20
  • max_com_size – the maximum size of a single community in the network, default 50
  • expand_step – the step of seed set increasement during expansion process, default 6
  • subspace_dim – dimension of the subspace; choosing a large dimension is undesirable because it would increase the computation cost of generating local spectra default 3
  • walk_steps – the number of step for the random walk, default 3
  • biased – boolean; set if the random walk starting from seed nodes, default False
Returns:

NodeClustering object

Example:
>>> from cdlib import algorithms
>>> import networkx as nx
>>> G = nx.karate_club_graph()
>>> seeds = ["$0$", "$2$", "$3$"]
>>> coms = algorithms.lemon(G, seeds, min_com_size=2, max_com_size=5)
References:

Yixuan Li, Kun He, David Bindel, John Hopcroft Uncovering the small community structure in large networks: A local spectral approach. Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, 2015.

Note

Reference implementation: https://github.com/YixuanLi/LEMON