Fast and Accurate Mining the Community Structure: Integrating Center Locating and Membership Optimization
The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Abstract
Mining communities or clusters in networks is valuable in analyzing, designing, and optimizing many natural and engineering complex systems, e.g., protein networks, power grid, and transportation systems. Most of the existing techniques view the community mining problem as an optimization problem based on a given quality function(e.g., modularity), however none of them are grounded with a systematic theory to identify the central nodes in the network. Moreover, how to reconcile the mining efficiency and the community quality still remains an open problem. In this paper, we attempt to address the above challenges by introducing a novel algorithm. First, a kernel function with a tunable influence factor is proposed to measure the leadership of each node, those nodes with highest local leadership can be viewed as the candidate central nodes. Then, we use a discrete-time dynamical system to describe the dynamical assignment of community membership; and formulate the serval conditions to guarantee the convergence of each node's dynamic trajectory, by which the hierarchical community structure of the network can be revealed. The proposed dynamical system is independent of the quality function used, so could also be applied in other community mining models. Our algorithm is highly efficient: the computational complexity analysis shows that the execution time is nearly linearly dependent on the number of nodes in sparse networks. We finally give demonstrative applications of the algorithm to a set of synthetic benchmark networks and also real-world networks to verify the algorithmic performance.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424
Community structure in social and biological networks
Girvan, M., & Newman, M. E. J. (2002) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.122653799 · Cited by 15,502 · cited 3×
“Finally, the proposed algorithm is applied on a large-scale scientific collaboration network [64], which illustrates the investigation cooperation among 56,276 physicists according to their coauthored papers posted on the Physics E-print Archive at arxiv:org .”
MethodFinding and evaluating community structure in networks
Newman, M. E. J., & Girvan, M. (2004) · Physical Review E · doi:10.1103/physreve.69.026113 · Cited by 13,931 · cited 2×
“(19) clearly match many well-known measures by following considerations: (1) Modularity [31] where m is the number of all edges in the network and k i is the degree of node i .”
BackgroundMethodFortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293 · cited 4×
“According to the notion of community or cluster structure [7], the density of inner-community links is larger compared with the rest part of the network.”
BackgroundInfluentialFinding community structure in very large networks
Clauset, A., Newman, M. E. J., & Moore, C. (2004) · Physical Review E · doi:10.1103/physreve.70.066111 · Cited by 7,390
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
Uncovering the overlapping community structure of complex networks in nature and society
Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005) · Nature · doi:10.1038/nature03607 · Cited by 5,373 · cited 2×
“Palla et al. proposed a clique percolation technique [29] which is mainly used to find overlapping communities in networks.”
MethodMaps of random walks on complex networks reveal community structure
Rosvall, M., & Bergstrom, C. T. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0706851105 · Cited by 4,583
Functional cartography of complex metabolic networks
Guimerà, R., & Nunes Amaral, L. A. (2005) · Nature · doi:10.1038/nature03288 · Cited by 3,983 · cited 2×
“Other well-known optimization approaches used in community detection literature include simulated annealing (SA) [39], external optimization (DA) [40], expectation maximization [67], Bayesian inference [41] and model selection analysis [55], [56] (for more detail please refer to Supporting…”
MethodResolution limit in community detection
Fortunato, S., & Barthélemy, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0605965104 · Cited by 3,024
Hierarchical organization in complex networks
Ravasz, E., & Barabási, A.-L. (2003) · Physical Review E · doi:10.1103/physreve.67.026112 · Cited by 2,160
Statistical mechanics of community detection
Reichardt, J., & Bornholdt, S. (2006) · Physical Review E · doi:10.1103/physreve.74.016110 · Cited by 2,048
Cited by
Non-ferrous metals price forecasting based on variational mode decomposition and LSTM network
Liu, Y., Yang, C., Huang, K., & Gui, W. (2020) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.105006 · Cited by 253
Metadata
- Authors
- Li, H.-J., Bu, Z., Li, A., Liu, Z., & Shi, Y.
- Venue
- IEEE Transactions on Knowledge and Data Engineering
- Published
- 2016-09-01
- Volume
- 28
- Issue
- 9
- Pages
- 2349-2362
- ISSN
- 1041-4347 (ISSN-L)
- OpenAlex
- W2346847115
- Cited by
- 164
- References
- 12
- FWCI
- 22.28
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.