cdlib.algorithms.lemon¶
- cdlib.algorithms.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) 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