Phys. Rev. E 100, 022315 (2019) - Micro-, meso-, macroscales: The effect of triangles on communities in networks

Learn about our response to COVID-19, including freely available research and expanded remote access support.

Micro-, meso-, macroscales: The effect of triangles on communities in networks

Sophie Wharrie, Lamiae Azizi, and Eduardo G. Altmann

Phys. Rev. E 100, 022315 – Published 21 August 2019

Abstract

Mesoscale structures (communities) are used to understand the macroscale properties of complex networks, such as their functionality and formation mechanisms. Microscale structures are known to exist in most complex networks (e.g., large number of triangles or motifs), but they are absent in the simple random-graph models considered (e.g., as null models) in community-detection algorithms. In this paper we investigate the effect of microstructures on the appearance of communities in networks. We find that alone the presence of triangles leads to the appearance of communities even in methods designed to avoid the detection of communities in random networks. This shows that communities can emerge spontaneously from simple processes of motiff generation happening at a microlevel. Our results are based on four widely used community-detection approaches (stochastic block model, spectral method, modularity maximization, and the Infomap algorithm) and three different generative network models (triadic closure, generalized configuration model, and random graphs with triangles).

Received 22 April 2019

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

©2019 American Physical Society

Physics Subject Headings (PhySH)

Clustering Community structure Discontinuous phase transition Network formation & growth Network phase transitions

NetworksInterdisciplinary PhysicsStatistical Physics

Authors & Affiliations

Sophie Wharrie, Lamiae Azizi, and Eduardo G. Altmann

School of Mathematics and Statistics, University of Sydney, 2006 NSW, Australia

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 100, Iss. 2 — August 2019

Reuse & Permissions

Physical Review A•B•C•D - 50 Years

To celebrate 50 years of enduring discoveries, APS is offering 50% off APCs for any manuscript submitted in 2020, published in any of its hybrid journals: PRL, PRA, PRB, PRC, PRD, PRE, PRApplied, PRFluids, and PRMaterials. Learn More »

Access Options

APS and the Physical Review Editorial Office Continue to Support Researchers

COVID-19 has impacted many institutions and organizations around the world, disrupting the progress of research. Through this difficult time APS and the Physical Review editorial office are fully equipped and actively working to support researchers by continuing to carry out all editorial and peer-review functions and publish research in the journals as well as minimizing disruption to journal access.

We appreciate your continued effort and commitment to helping advance science, and allowing us to publish the best physics journals in the world. And we hope you, and your loved ones, are staying safe and healthy.

Ways to Access APS Journal Articles Off-Campus

Many researchers now find themselves working away from their institutions and, thus, may have trouble accessing the Physical Review journals. To address this, we have been improving access via several different mechanisms. See Off-Campus Access to Physical Review for further instructions.

Triangles affect the number of communities. The number of detected communities as a function of the size of the networks (number of nodes) for the triadic closure model with (a) (low clustering) and (b) (high clustering), for the four community detection algorithms. The insets show a sample network obtained in each of the cases for . Error bars were computed over an ensemble of 5 different networks. The scaling lines show that, in the high clustering case, scales roughly linearly with for the Spectral and Infomap methods, and scales as approximately for the Modularity and SBM methods.
Different methods identify similar communities for the clustered model. (Left) Plots of networks generated by the triadic closure model with , with communities obtained using the SBM and modularity maximization methods. The inset emphasizes that triangles are inside communities. (Right) adjusted mutual information between the results of the different methods for various network sizes . The adjusted mutual information [] quantifies the similarity between the communities and varies between 0 (completely different communities) and 1 (identical communities), with 0 indicating the overlap between communities expected by chance.
Dependence of the number of communities in networks with clustering coefficient . Each curve corresponds to a different community detection method (see legend and Appendix ). Each panel shows the results for a different network model: (a) triadic closure model with and ; (b) the configuration model with ; and (c) the random graph with triangles with . The points (error bars) correspond to averages (standard deviation) across five different networks (realizations of the network model).
Phase transition in SBM. (a) The scaled number of communities for networks generated by the triadic closure model with varying probability of closing triangles and different number of nodes (see legend). As the network size increases we observe a sharper transition, accumulating around the critical probability (). The dashed (black) line corresponds to the results of the hierarchical SBM method []. (b) The detectability condition —Eq. ()—plotted as a function of , averaged across 5 trials of triadic closure networks. Since there is some noise in the data around the critical value (due to the algorithm detecting one large community and a few small communities near the threshold), we fit a line of best fit to the portion of the curve with and extrapolate to . This obtains an estimate (red point) for the critical value , which agrees with the the critical value observed in panel (a).

Sign up to receive regular email alerts from Physical Review E