Triadic closure as a basic generating mechanism of communities in complex networks

Abstract

Most of the complex social, technological and biological networks have a significant community structure. Therefore the community structure of complex networks has to be considered as a universal property, together with the much explored small-world and scale-free properties of these networks. Despite the large interest in characterizing the community structures of real networks, not enough attention has been devoted to the detection of universal mechanisms able to spontaneously generate networks with communities. Triadic closure is a natural mechanism to make new connections, especially in social networks. Here we show that models of network growth based on simple triadic closure naturally lead to the emergence of community structure, together with fat-tailed distributions of node degree, high clustering coefficients. Communities emerge from the initial stochastic heterogeneity in the concentration of links, followed by a cycle of growth and fragmentation. Communities are the more pronounced, the sparser the graph, and disappear for high values of link density and randomness in the attachment procedure. By introducing a fitness-based link attractivity for the nodes, we find a novel phase transition, where communities disappear for high heterogeneity of the fitness distribution, but a new mesoscopic organization of the nodes emerges, with groups of nodes being shared between just a few superhubs, which attract most of the links of the system.

12 pages, 14 figures. Published version

References in corpus (26)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Community detection in graphs
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• The diameter of the world wide web
• Resolution limit in community detection
• Temporal Networks
• Defining and identifying communities in networks
• Why social networks are different from other types of networks
• Growing Scale-Free Networks with Tunable Clustering
• Bose-Einstein condensation in complex networks
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Properties of highly clustered networks
• Emergence of a small world from local interactions: Modeling acquaintance networks
• Characterizing the community structure of complex networks
• Emergence of communities in weighted networks
• A Model for Social Networks
• Duplication-divergence model of protein interaction network
• Log-Networks
• Triadic closure dynamics drives scaling-laws in social multiplex networks
• Clustering Drives Assortativity and Community Structure in Ensembles of Networks

Cited by in corpus (64)

• Networks beyond pairwise interactions: structure and dynamics
• The physics of higher-order interactions in complex systems
• Quantifying randomness in real networks
• Inequality is rising where social network segregation interacts with urban topology
• Cumulative effects of triadic closure and homophily in social networks
• Common neighbours and the local-community-paradigm for link prediction in bipartite networks
• Emergent Complex Network Geometry
• Emergence of Soft Communities from Geometric Preferential Attachment
• Beyond the clustering coefficient: A topological analysis of node neighbourhoods in complex networks
• Structural Transitions in Dense Networks
• Emergence of multiplex communities in collaboration networks
• From calls to communities: a model for time varying social networks
• Mesoscopic Structures Reveal the Network Between the Layers of Multiplex Datasets
• Evolution and structure of technological systems - An innovation output network
• Densification and Structural Transitions in Networks that Grow by Node Copying
• Network clique cover approximation to analyze complex contagions through group interactions
• Network Geometry and Complexity
• The exploration of the Adjacent Possible explains the emergence and evolution of social networks
• Analysing Twitter Semantic Networks: the case of 2018 Italian Elections
• Intelligent social bots uncover the link between user preference and diversity of news consumption
• Disentangling homophily, community structure and triadic closure in networks
• DYMOND: DYnamic MOtif-NoDes Network Generative Model
• Sampling motif-constrained ensembles of networks
• Social nucleation: Group formation as a phase transition
• Dynamical origins of the community structure of multi-layer societies
• A new measure for community structures through indirect social connections
• A framework for second order eigenvector centralities and clustering coefficients
• Coevolving nonlinear voter model with triadic closure
• Interplay between $k$-core and community structure in complex networks
• Coupled dynamics of node and link states in complex networks: A model for language competition
• Local-ring network automata and the impact of hyperbolic geometry in complex network link-prediction
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Emergent Network Modularity
• Complex networks as an emerging property of hierarchical preferential attachment
• Exotic phase transitions of k-cores in clustered networks
• Maximally modular structure of growing hyperbolic networks
• Nonparametric sign prediction of high-dimensional correlation matrix coefficients
• Extraction and integration of genetic networks from short-profile omic datasets
• Exactly Solvable Random Graph Ensemble with Extensively Many Short Cycles
• Nodal heterogeneity can induce ghost triadic effects in relational event models
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Higher-order temporal network effects through triplet evolution
• Symmetric core-cohesive blockmodel in preschool children's interaction networks
• Complex networks with scale-free nature and hierarchical modularity
• The Magic of Networks Grown by Redirection
• On the Triangle Clique Cover and $K_t$ Clique Cover Problems
• Modular Networks for Validating Community Detection Algorithms
• Community Detection on Networks with Ricci Flow
• Strongly clustered random graphs via triadic closure: An exactly solvable model
• Trust based attachment
• Joint Subgraph-to-Subgraph Transitions -- Generalizing Triadic Closure for Powerful and Interpretable Graph Modeling
• Local topological moves determine global diffusion properties of hyperbolic higher-order networks
• Generalizations of Edge Overlap to Weighted and Directed Networks
• A survey on modelling of infectious disease spread and control on social contact networks
• Dynamic patterns of knowledge flows across technological domains: empirical results and link prediction
• Evolutionary Dynamics of Investors Expectations and Market Price Movement
• Free-energy density functional for Strauss's model of transitive networks
• Emergence of network communities driven by local rules
• Homophily and Triadic Closure in Evolving Social Networks
• Around Average Behavior: 3-lambda Network Model
• Construction of a Pragmatic Base Line for Journal Classifications and Maps Based on Aggregated Journal-Journal Citation Relations
• The Dynamics of Triads in Aggregated Journal-Journal Citation Relations: Specialty Developments at the Above-Journal Level
• Diffusion on dynamic contact networks with indirect transmission links
• Network Inequality through Preferential Attachment, Triadic Closure, and Homophily