Link-Space and Network Analysis

Abstract

Many networks contain correlations and often conventional analysis is incapable of incorporating this often essential feature. In arXiv:0708.2176, we introduced the link-space formalism for analysing degree-degree correlations in evolving networks. In this extended version, we provide additional mathematical details and supplementary material. We explore some of the common oversights when these correlations are not taken into account, highlighting the importance of the formalism. The formalism is based on a statistical description of the fraction of links l_{i,j} connecting nodes of degrees i and j. To demonstrate its use, we apply the framework to some pedagogical network models, namely, random-attachment, Barabasi-Albert preferential attachment and the classical Erdos and Renyi random graph. For these three models the link-space matrix can be solved analytically. We apply the formalism to a simple one-parameter growing network model whose numerical solution exemplifies the effect of degree-degree correlations for the resulting degree distribution. We also employ the formalism to derive the degree distributions of two very simple network decay models, more specifically, that of random link deletion and random node deletion. The formalism allows detailed analysis of the correlations within networks and we also employ it to derive the form of a perfectly non-assortative network for arbitrary degree distribution.

57 pages, 25 figures; Updated to include recent results

References in corpus (34)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Assortative mixing in networks
• Evolution of networks
• Specificity and stability in topology of protein networks
• Network robustness and fragility: Percolation on random graphs
• Characterization of complex networks: A survey of measurements
• Dynamical and correlation properties of the Internet
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Connectivity of Growing Random Networks
• Growing Scale-Free Networks with Tunable Clustering
• Organization of Growing Random Networks
• Large-scale topological and dynamical properties of Internet
• Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations
• Epidemic spreading in correlated complex networks
• Absence of epidemic threshold in scale-free networks with connectivity correlations
• Class of correlated random networks with hidden variables
• Are randomly grown graphs really random?
• Pattern Detection in Complex Networks: Correlation Profile of the Internet
• Epidemic threshold in structured scale-free networks
• Growing Scale-Free Networks with Small World Behavior
• Modeling the evolution of weighted networks
• The origin of degree correlations in the Internet and other networks
• A Model for Social Networks
• Assortative model for social networks
• Scale-Free Networks Generated By Random Walkers
• Rate equation approach for correlations in growing network models
• Mean-field theory for clustering coefficients in Barabasi-Albert networks
• Evolving networks through deletion and duplication
• Assortative mixing by degree makes a network more unstable
• Accelerating networks
• Synchronization of degree correlated physical networks
• Synchronizability and synchronization dynamics of weighed and unweighed scale free networks with degree mixing