An algorithm for network community structure determination by surprise

Daniel Gamermann and José Antônio Pellizzaro

Physica A: Statistical Mechanics and its Applications, 2022, vol. 595, issue C

Abstract: A community in a network is an intuitive idea for which there is no consensus on its objective mathematical definition. Therefore, different algorithms and metrics have been suggested in order to identify these structures in graphs. In this work, we propose a new benchmark and a new approach based on a metric known as surprise. We compare our approach to several others in the literature, in different kinds of benchmarks, including our own (that tackles separately the different ways in which one may degrade a network’s community structure) and discuss the different biases we identify for each algorithm and benchmark. In particular, we identify a possible flaw in the way the LFR benchmark constructs its communities and that algorithms suffering from bad resolution are biased towards identifying communities with similar sizes. We show that the surprise based approaches perform better than the modularity based ones, specially for heterogeneous graphs (with very different community sizes coexisting).

Keywords: Graphs; Community detection; Surprise; Modularity; Pielou index (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437122001170
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:595:y:2022:i:c:s0378437122001170

DOI: 10.1016/j.physa.2022.127063

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 ().