The origin of degree correlations in the Internet and other networks

Abstract

It has been argued that the observed anticorrelation between the degrees of adjacent vertices in the network representation of the Internet has its origin in the restriction that no two vertices have more than one edge connecting them. Here we introduce a formalism for modeling ensembles of graphs with single edges only and derive values for the exponents and correlation coefficients characterizing them. Our results confirm that the conjectured mechanism does indeed give rise to correlations of the kind seen in the Internet, although only a part of the measured correlation can be accounted for in this way.

arXiv comment7 pages, 3 figures, 1 table

References in corpus (11)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Mixing patterns in networks
• Dynamical and correlation properties of the Internet
• Universal Behavior of Load Distribution in Scale-free Networks
• Bose-Einstein condensation in complex networks
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Principles of statistical mechanics of random networks

Cited by in corpus (116)

• Finding and evaluating community structure in networks
• Epidemic processes in complex networks
• Characterization of complex networks: A survey of measurements
• Why social networks are different from other types of networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Generation of uncorrelated random scale-free networks
• The statistical mechanics of networks
• Structure and Evolution of the World Trade Network
• Class of correlated random networks with hidden variables
• Classes of complex networks defined by role-to-role connectivity profiles
• The Statistical Physics of Real-World Networks
• Fitness-dependent topological properties of the World Trade Web
• Extending the definition of modularity to directed graphs with overlapping communities
• Networks in Cognitive Science
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Cut-offs and finite size effects in scale-free networks
• On the uniform generation of random graphs with prescribed degree sequences
• Construction and properties of assortative random networks
• Structure and Time-Evolution of an Internet Dating Community
• Analytical maximum-likelihood method to detect patterns in real networks
• Maximum likelihood: extracting unbiased information from complex networks
• The International Trade Network: weighted network analysis and modelling
• Solution of the 2-star model of a network
• Identifying "communities" within energy landscapes
• Clustering in complex networks. I. General formalism
• Self-similar disk packings as model spatial scale-free networks
• Reciprocity of weighted networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Tuning clustering in random networks with arbitrary degree distributions
• The entropic origin of disassortativity in complex networks
• Hierarchy Measures in Complex Networks
• Entropy of stochastic blockmodel ensembles
• Randomizing world trade. I. A binary network analysis
• Evolution of a large online social network
• Factors determining nestedness in complex networks
• Self-organized network evolution coupled to extremal dynamics
• Diffusion-annihilation processes in complex networks
• Polynomial growth in age-dependent branching processes with diverging reproductive number
• Clustering of correlated networks
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Uncovering disassortativity in large scale-free networks
• Characterizing the network topology of the energy landscapes of atomic clusters
• Reconstructing networks with unknown and heterogeneous errors
• Local Leaders in Random Networks
• The weighted random graph model
• Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (Extended Version)
• Disassortative mixing in online social networks
• The networked seceder model: Group formation in social and economic systems
• Constrained Markovian dynamics of random graphs
• Constructing and sampling directed graphs with given degree sequences
• Multi-species grandcanonical models for networks with reciprocity
• Degree correlations in directed scale-free networks
• Bosonic reaction-diffusion processes on scale-free networks
• Complex Networks and Symmetry I: A Review
• Percolation in self-similar networks
• Intrinsic degree-correlations in static model of scale-free networks
• Diffusion and networks: A powerful combination!
• Clustering of random scale-free networks
• Mean first-passage time for maximal-entropy random walks in complex networks
• Mapping from Architecture to Dynamics: A Unified View of Dynamical Processes on Networks
• Degree correlations in signed social networks
• Multiplexity versus correlation: the role of local constraints in real multiplexes
• Effect of node deleting on network structure
• Enhancing automated reaction discovery with boxed molecular dynamics in energy space
• Multiplexity and multireciprocity in directed multiplexes
• Fluctuation-dissipation relations for complex networks
• Organization of complex networks without multiple connections
• Evolving Networks and the Development of Neural Systems
• Clustering Spectrum of scale-free networks
• Scaling of nestedness in complex networks
• Networks with given two-point correlations: hidden correlations from degree correlations
• Randomizing growing networks with a time-respecting null model
• Revising the simple measures of assortativity in complex networks
• Gene communities in co-expression networks across different tissues
• Low-temperature behaviour of social and economic networks
• A general formulation of long-range degree correlations in complex networks
• Properties of Kinetic Transition Networks for Atomic Clusters and Glassy Solids
• Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence
• Graph animals, subgraph sampling and motif search in large networks
• Observability transitions in correlated networks
• The Multi-Scale Network Landscape of Collaboration
• Weighted hypersoft configuration model
• Multiscale network renormalization: scale-invariance without geometry
• Weighted reciprocity in human communication networks
• Link-space formalism for network analysis
• Degree Landscapes in Scale-Free Networks
• Emergence of collective memories
• Scale-free networks with a large- to hypersmall-world transition
• Phase transitions for scaling of structural correlations in directed networks
• Evolution of the Internet AS-Level Ecosystem
• Latent Poisson models for networks with heterogeneous density
• A Statistical Test of Walrasian Equilibrium by Means of Complex Networks Theory
• Self-Organization and Complex Networks
• Mechanism for linear preferential attachment in growing networks
• Characterizing the intrinsic correlations of scale-free networks
• Adaptive networks of trading agents
• Structure of international trade hypergraphs
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Generating random networks that consist of a single connected component with a given degree distribution
• Convergence of rank based degree-degree correlations in random directed networks
• Degree correlations in scale-free null models
• Generalised thresholding of hidden variable network models with scale-free property
• Correlations in Networks associated to Preferential Growth
• Disassortativity of random critical branching trees
• Random degree-degree correlated networks
• Representation of degree correlation using eigenvalue decomposition and its application to epidemic models
• Network topology mapping of Chemical Compounds Space
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Link-Space and Network Analysis
• Long-range disassortative correlations in generic random trees
• Relevance of the minimum degree to dynamic fluctuation in strongly heterogeneous networks
• Interplay between Network Topology and Dynamics in Neural Systems
• A Model of Random Industrial SAT
• Construction of simplicial complexes with prescribed degree-size sequences
• A Self-organized model for network evolution