The weighted random graph model

Abstract

We introduce the weighted random graph (WRG) model, which represents the weighted counterpart of the Erdos-Renyi random graph and provides fundamental insights into more complicated weighted networks. We find analytically that the WRG is characterized by a geometric weight distribution, a binomial degree distribution and a negative binomial strength distribution. We also characterize exactly the percolation phase transitions associated with edge removal and with the appearance of weighted subgraphs of any order and intensity. We find that even this completely null model displays a percolation behavior similar to what observed in real weighted networks, implying that edge removal cannot be used to detect community structure empirically. By contrast, the analysis of clustering successfully reveals different patterns between the WRG and real networks.

A Mathematica demonstration (by Tiziano Squartini) allowing to generate small weighted graphs according to the model is available online at http://demonstrations.wolfram.com/WeightedRandomGraph/

References in corpus (12)

• Structure and tie strengths in mobile communication networks
• Generalizations of the clustering coefficient to weighted complex networks
• Prominence and control: The weighted rich-club effect
• Analysis of a large-scale weighted network of one-to-one human communication
• Emergence of communities in weighted networks
• Maximum likelihood: extracting unbiased information from complex networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Transport on Complex Networks: Flow, Jamming and Optimization
• Correlations in weighted networks
• An ensemble approach to the analysis of weighted networks
• The structural role of weak and strong links in a financial market network
• Rich-club vs rich-multipolarization phenomena in weighted networks

Cited by in corpus (23)

• Robust Detection of Dynamic Community Structure in Networks
• Analytical maximum-likelihood method to detect patterns in real networks
• Reciprocity of weighted networks
• The hidden geometry of weighted complex networks
• Unbiased sampling of network ensembles
• Transfer entropy between communities in complex networks
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• Multiplexity versus correlation: the role of local constraints in real multiplexes
• Ensemble nonequivalence in random graphs with modular structure
• Detecting mesoscale structures by surprise
• Spatial effects in real networks: measures, null models, and applications
• Topological optimization of hybrid quantum key distribution networks
• Stylized facts in social networks: Community-based static modeling
• Network structure of cascading neural systems predicts stimulus propagation and recovery
• On Strategic Defense of Stochastic Networks
• Geometric randomization of real networks with prescribed degree sequence
• A Synthetic Network Generator for Covert Network Analytics
• Probability-graphons: Limits of large dense weighted graphs
• Generalizations of Edge Overlap to Weighted and Directed Networks
• A Survey of Evolving Models for Weighted Complex Networks based on their Dynamics and Evolution
• Abrupt efficiency collapse in real-world complex weighted networks: robustness decrease with link weights heterogeneity
• Extrema Analysis of Node Centrality in Weighted Networks
• Mean-field theory of vector spin models on networks with arbitrary degree distributions