Pattern Detection in Complex Networks: Correlation Profile of the Internet

Abstract

A general scheme for detecting and analyzing topological patterns in large complex networks is presented. In this scheme the network in question is compared with its properly randomized version that preserves some of its low-level topological properties. Statistically significant deviation of any measurable property of a network from this null model likely reflect its design principles and/or evolutionary history. We illustrate this basic scheme on the example of the correlation profile of the Internet quantifying correlations between connectivities of its neighboring nodes. This profile distinguishes the Internet from previously studied molecular networks with a similar scale-free connectivity distribution. We finally demonstrate that clustering in a network is very sensitive to both the connectivity distribution and its correlation profile and compare the clustering in the Internet to the appropriate null model.

6 pages, 7 figures

References in corpus (7)

• Community structure in social and biological networks
• Specificity and stability in topology of protein networks
• Large-scale topological and dynamical properties of Internet
• Modeling the Internet's Large-Scale Topology
• Fluctuation-driven dynamics of the Internet topology
• Topological Properties of Citation and Metabolic Networks
• Growing dynamics of Internet providers

Cited by in corpus (136)

• The structure and function of complex networks
• Epidemic processes in complex networks
• Why social networks are different from other types of networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• The Anatomy of the Facebook Social Graph
• Generation of uncorrelated random scale-free networks
• Popularity versus Similarity in Growing Networks
• Classes of complex networks defined by role-to-role connectivity profiles
• Module identification in bipartite and directed networks
• The Statistical Physics of Real-World Networks
• Fitness-dependent topological properties of the World Trade Web
• Contact patterns among high school students
• Cut-offs and finite size effects in scale-free networks
• Edge direction and the structure of networks
• Construction and properties of assortative random networks
• Networks and Cities: An Information Perspective
• Dynamical Patterns of Cattle Trade Movements
• The origin of degree correlations in the Internet and other networks
• Subgraphs in random networks
• Accurately modeling the Internet topology
• Analytical maximum-likelihood method to detect patterns in real networks
• Evaluating Local Community Methods in Networks
• Quantifying randomness in real networks
• Identifying "communities" within energy landscapes
• Percolation on correlated networks
• Reciprocity of weighted networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• The entropic origin of disassortativity in complex networks
• Evolving networks in the human epileptic brain
• Hierarchy Measures in Complex Networks
• Systematic Topology Analysis and Generation Using Degree Correlations
• Randomizing world trade. I. A binary network analysis
• Factors determining nestedness in complex networks
• Self-organized network evolution coupled to extremal dynamics
• Diffusion-annihilation processes in complex networks
• Gender homophily from spatial behavior in a primary school: a sociometric study
• Random graph models for directed acyclic networks
• Uncovering disassortativity in large scale-free networks
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Searchability of Networks
• On the rich-club effect in dense and weighted networks
• Reconstructing the world trade multiplex: the role of intensive and extensive biases
• From brain to earth and climate systems: Small-world interaction networks or not?
• Rich-cores in networks
• Scaling of degree correlations and the influence on diffusion in scale-free networks
• Local Leaders in Random Networks
• Hide and seek on complex networks
• The weighted random graph model
• Exploring the assortativity-clustering space of a network's degree sequence
• Null Models of Economic Networks: The Case of the World Trade Web
• Assortative mixing in functional brain networks during epileptic seizures
• Structural constraints in complex networks
• Unraveling Spurious Properties of Interaction Networks with Tailored Random Networks
• The networked seceder model: Group formation in social and economic systems
• Constrained Markovian dynamics of random graphs
• Graph Annotations in Modeling Complex Network Topologies
• Modularity produces small-world networks with dynamical time-scale separation
• Multi-species grandcanonical models for networks with reciprocity
• Emergence of Symmetry in Complex Networks
• Degree correlations in directed scale-free networks
• Bosonic reaction-diffusion processes on scale-free networks
• The Phase Stability Network of all Inorganic Materials
• A critical look at power law modelling of the Internet
• Complex Networks and Symmetry I: A Review
• Enhancing neural-network performance via assortativity
• Spatial network surrogates for disentangling complex system structure from spatial embedding of nodes
• Understanding the internet topology evolution dynamics
• Tailored graph ensembles as proxies or null models for real networks I: tools for quantifying structure
• Chinese Internet AS-level Topology
• Triadic motifs and dyadic self-organization in the World Trade Network
• Scale-free networks as preasymptotic regimes of superlinear preferential attachment
• Navigating Networks with Limited Information
• Constrained Randomisation of Weighted Networks
• Surrogate-assisted analysis of weighted functional brain networks
• Phase transitions in social networks inspired by the Schelling model
• Improvement of the robustness on geographical networks by adding shortcuts
• Randomizing hypergraphs preserving degree correlation and local clustering
• Fluctuation-dissipation relations for complex networks
• Organization of complex networks without multiple connections
• Clustering Spectrum of scale-free networks
• Evolving Networks and the Development of Neural Systems
• Epidemic risk from friendship network data: an equivalence with a non-uniform sampling of contact networks
• Revising the simple measures of assortativity in complex networks
• Gene communities in co-expression networks across different tissues
• Lower bound of assortativity coefficient in scale-free networks
• Preferential attachment during the evolution of a potential energy landscape
• Networks with arbitrary edge multiplicities
• Link and subgraph likelihoods in random undirected networks with fixed and partially fixed degree sequence
• Same Stats, Different Graphs: Exploring the Space of Graphs in Terms of Graph Properties
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• Observability transitions in correlated networks
• Assortative Mixing in Weighted Directed Networks
• Models and average properties of scale-free directed networks
• Are the different layers of a social network conveying the same information?
• Second-Order Assortative Mixing in Social Networks
• Weighted reciprocity in human communication networks
• Degree Landscapes in Scale-Free Networks
• Phase transitions for scaling of structural correlations in directed networks
• Evolutionary Construction of Geographical Networks with Nearly Optimal Robustness and Efficient Routing Properties
• Scale-free network clustering in hyperbolic and other random graphs
• A self-consistent approach to measure preferential attachment in networks and its application to an inherent structure network
• Latent Poisson models for networks with heterogeneous density
• Modules in the metabolic network of E.coli with regulatory interactions
• Self-Organization and Complex Networks
• Radial Structure of the Internet
• Interplay between tie strength and neighbourhood topology in complex networks: Granovetter's theory and beyond
• Activity patterns on random scale-free networks: Global dynamics arising from local majority rules
• Analytic solution of the two-star model with correlated degrees
• Generating random networks that consist of a single connected component with a given degree distribution
• Dose-response functions and surrogate models for exploring social contagion in the Copenhagen Networks Study
• Heterogeneous information network model for equipment-standard system
• Why the Internet is so 'small'?
• Identification of intrinsic long-range degree correlations in complex networks
• Scatter Networks: A New Approach for Analyzing Information Scatter on the Web
• Disassortativity of random critical branching trees
• Ensembles related to the rich-club coefficient for non-evolving networks
• Influence of long-range interactions on strategy selection in crowd
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Deductive Way of Reasoning about the Internet AS Level Topology
• Research on Life Characteristics of Internet Based on Network Motifs
• Ensembles based on the Rich-Club and how to use them to build soft-communities
• Long-range disassortative correlations in generic random trees
• Detecting contagious spreading of urban innovations on the global city network
• Link-Space and Network Analysis
• A Self-organized model for network evolution
• Hierarchical modularity of nested bow-ties in metabolic networks
• Interplay between Network Topology and Dynamics in Neural Systems
• Social insect colony as a biological regulatory system: Information flow in dominance networks
• Approximate Conditional Sampling for Pattern Detection in Weighted Networks
• Characterizing Faculty Online Learning Community Interactions Using Social Network Analysis
• Bow-tie topological features of metabolic networks and the functional significance
• Effects of missing data in social networks
• Modular co-evolution of metabolic networks
• Same Stats, Different Graphs (Graph Statistics and Why We Need Graph Drawings)