Discovering natural communities in networks

Angsheng Li, Jiankou Li and Yicheng Pan

Physica A: Statistical Mechanics and its Applications, 2015, vol. 436, issue C, 878-896

Abstract: Understanding and detecting natural communities in networks have been a fundamental challenge in networks, and in science generally. Recently, we proposed a hypothesis that homophyly/kinship is the principle of natural communities based on real network experiments, proposed a model of networks to explore the principle of natural selection in nature evolving, and proposed the measure of structure entropy of networks. Here we proposed a community finding algorithm by our measure of structure entropy of networks. We found that our community finding algorithm exactly identifies almost all natural communities of networks generated by natural selection, if any, and that the algorithm exactly identifies or precisely approximates almost all the communities planted in the networks of the existing models. We verified that our algorithm identifies or very well approximates the ground-truth communities of some real world networks, if the ground-truth communities are semantically well-defined, that our algorithm naturally finds the balanced communities, and that the communities found by our algorithm may have larger modularity than that by the algorithms based on modularity, for some networks. Our algorithm provides for the first time an approach to detecting and analyzing natural or true communities in real world networks. Our results demonstrate that structure entropy minimization is the principle of detecting the natural or true communities in large-scale networks.

Keywords: Community detection; Networks; Modularity; Structure entropy; Natural community (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437115004549
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:436:y:2015:i:c:p:878-896

DOI: 10.1016/j.physa.2015.05.039

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().