Consistency of community structure in complex networks

Maria A. Riolo and M. E. J. Newman
Phys. Rev. E 101, 052306 – Published 8 May 2020

Abstract

The most widely used techniques for community detection in networks, including methods based on modularity, statistical inference, and information theoretic arguments, all work by optimizing objective functions that measure the quality of network partitions. There is a good case to be made, however, that one should not look solely at the single optimal community structure under such an objective function but rather at a selection of high-scoring structures. If one does this, one typically finds that the resulting structures show considerable variation, which could be taken as evidence that these community detection methods are unreliable, since they do not appear to give consistent answers. Here we argue that, upon closer inspection, the structures found are in fact consistent in a certain way. Specifically, we show that they can all be assembled from a set of underlying “building blocks,” groups of network nodes that are usually found together in the same community. Different community structures correspond to different arrangements of blocks, but the blocks themselves are largely invariant. We propose an information theoretic method for discovering the building blocks in specific networks and demonstrate it with several example applications. We conclude that traditional community detection does in fact give a significant amount of insight into network structure.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
1 More
  • Received 3 September 2019
  • Revised 17 February 2020
  • Accepted 27 March 2020

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

©2020 American Physical Society

Physics Subject Headings (PhySH)

Networks

Authors & Affiliations

Maria A. Riolo1,2 and M. E. J. Newman1,2,3

  • 1Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501, USA
  • 2Center for the Study of Complex Systems, University of Michigan, Ann Arbor, Michigan 48109, USA
  • 3Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 101, Iss. 5 — May 2020

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
×