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