Community structure is an important feature of networks, and the correct detection of communities is a fundamental problem in network analysis. Statistical inference has recently been proposed for successful detection, provided the number of communities can be appropriately estimated a priori. In the absence of such information, model selection by determination of the number of communities remains an issue. We show here that correlation between communities from a highly parceled partition can be used to estimate a narrow range of variation for the real number of communities. This range, further elaborated by modularity-based belief propagation, correctly identifies communities. Testing on synthetic networks generated by a stochastic block model and a set of real-world networks shows that our method can alleviate the effects of modularity fluctuations well and enhance the ability of community detection of the bare modularity-based belief propagation method.

Correlation enhanced modularity-based belief propagation method for community detection in networks

Nardini Christine
2016

Abstract

Community structure is an important feature of networks, and the correct detection of communities is a fundamental problem in network analysis. Statistical inference has recently been proposed for successful detection, provided the number of communities can be appropriately estimated a priori. In the absence of such information, model selection by determination of the number of communities remains an issue. We show here that correlation between communities from a highly parceled partition can be used to estimate a narrow range of variation for the real number of communities. This range, further elaborated by modularity-based belief propagation, correctly identifies communities. Testing on synthetic networks generated by a stochastic block model and a set of real-world networks shows that our method can alleviate the effects of modularity fluctuations well and enhance the ability of community detection of the bare modularity-based belief propagation method.
2016
Istituto Applicazioni del Calcolo ''Mauro Picone''
analysis of algorithms
clustering techniques
message-passing algorithms
random graphs
networks
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/386747
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact