Multiple phases in modularity-based community detection

Christophe Schülke and Federico Ricci-Tersenghi
Phys. Rev. E 92, 042804 – Published 7 October 2015

Abstract

Detecting communities in a network, based only on the adjacency matrix, is a problem of interest to several scientific disciplines. Recently, Zhang and Moore have introduced an algorithm [Proc. Natl. Acad. Sci. USA 111, 18144 (2014)], called mod-bp, that avoids overfitting the data by optimizing a weighted average of modularity (a popular goodness-of-fit measure in community detection) and entropy (i.e., number of configurations with a given modularity). The adjustment of the relative weight, the “temperature” of the model, is crucial for getting a correct result from mod-bp. In this work we study the many phase transitions that mod-bp may undergo by changing the two parameters of the algorithm: the temperature T and the maximum number of groups q. We introduce a new set of order parameters that allow us to determine the actual number of groups q̂, and we observe on both synthetic and real networks the existence of phases with any q̂{1,q}, which were unknown before. We discuss how to interpret the results of mod-bp and how to make the optimal choice for the problem of detecting significant communities.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 16 June 2015
  • Revised 22 September 2015

DOI:https://doi.org/10.1103/PhysRevE.92.042804

©2015 American Physical Society

Authors & Affiliations

Christophe Schülke*

  • Université Paris Diderot, Sorbonne Paris Cité, 75205 Paris, France and Dipartimento di Fisica, Università di Roma “La Sapienza,” Piazzale Aldo Moro 2, 00185 Rome, Italy

Federico Ricci-Tersenghi

  • Dipartimento di Fisica, INFN–Sezione di Roma 1, and CNR-NANOTEC, UOS di Roma, Università di Roma “La Sapienza,” Piazzale Aldo Moro 2, 00185 Rome, Italy

  • *christophe.schulke@espci.fr
  • federico.ricci@roma1.infn.it

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 92, Iss. 4 — October 2015

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×