Micro, Meso, Macro: the effect of triangles on communities in networks

Abstract

Meso-scale structures (communities) are used to understand the macro-scale properties of complex networks, such as their functionality and formation mechanisms. Micro-scale 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 micro-structures 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 micro-level. 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).

arXiv comment9 pages, 4 figures. A repository with our codes is available at https://github.com/sophiewharrie/micro-meso-macro-code

References in corpus (21)

• Community detection in graphs
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Resolution limit in community detection
• Community detection in networks: A user guide
• Modularity from Fluctuations in Random Graphs and Complex Networks
• The map equation
• Spectral redemption: clustering sparse networks
• Random graphs with clustering
• The ground truth about metadata and community detection in networks
• Class of correlated random networks with hidden variables
• Statistical physics of inference: Thresholds and algorithms
• Phase transition in the detection of modules in sparse networks
• A Classification for Community Discovery Methods in Complex Networks
• Triadic closure as a basic generating mechanism of communities in complex networks
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Clustering Drives Assortativity and Community Structure in Ensembles of Networks
• An Empirical Study of the Relation Between Community Structure and Transitivity
• Sampling motif-constrained ensembles of networks

Cited by in corpus (4)

• Characterizing the Interactions Between Classical and Community-aware Centrality Measures in Complex Networks
• Comparative evaluation of community-aware centrality measures
• Disentangling homophily, community structure and triadic closure in networks
• Emergence of network communities driven by local rules