Quantifying the connectivity of a network: The network correlation function method

Abstract

Networks are useful for describing systems of interacting objects, where the nodes represent the objects and the edges represent the interactions between them. The applications include chemical and metabolic systems, food webs as well as social networks. Lately, it was found that many of these networks display some common topological features, such as high clustering, small average path length (small world networks) and a power-law degree distribution (scale free networks). The topological features of a network are commonly related to the network's functionality. However, the topology alone does not account for the nature of the interactions in the network and their strength. Here we introduce a method for evaluating the correlations between pairs of nodes in the network. These correlations depend both on the topology and on the functionality of the network. A network with high connectivity displays strong correlations between its interacting nodes and thus features small-world functionality. We quantify the correlations between all pairs of nodes in the network, and express them as matrix elements in the correlation matrix. From this information one can plot the correlation function for the network and to extract the correlation length. The connectivity of a network is then defined as the ratio between this correlation length and the average path length of the network. Using this method we distinguish between a topological small world and a functional small world, where the latter is characterized by long range correlations and high connectivity. Clearly, networks which share the same topology, may have different connectivities, based on the nature and strength of their interactions. The method is demonstrated on metabolic networks, but can be readily generalized to other types of networks.

10 figures

References in corpus (13)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Classes of behavior of small-world networks
• Who is the best connected scientist? A study of scientific coauthorship networks
• Evolution of the social network of scientific collaborations
• How Popular is Your Paper? An Empirical Study of the Citation Distribution
• Dynamical and correlation properties of the Internet
• Robust Patterns in Food Web Structure
• Spreading gossip in social networks
• Phase transition in the Ising model on a small-world network with distance-dependent interactions

Cited by in corpus (5)

• Estimating Psychological Networks and their Accuracy: A Tutorial Paper
• Mapping from Architecture to Dynamics: A Unified View of Dynamical Processes on Networks
• Structural and functional networks in complex systems with delay
• Synchronization Invariance Under Network Structural Transformations
• RIDS: Robust Identification of Sparse Gene Regulatory Networks from Perturbation Experiments