Network comparison and the within-ensemble graph distance.
ABSTRACT: Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years, a multitude of diverse, ad hoc solutions to this problem have been introduced. Here, we propose that simple and well-understood ensembles of random networks-such as Erd?s-Rényi graphs, random geometric graphs, Watts-Strogatz graphs, the configuration model and preferential attachment networks-are natural benchmarks for network comparison methods. Moreover, we show that the expected distance between two networks independently sampled from a generative model is a useful property that encapsulates many key features of that model. To illustrate our results, we calculate this within-ensemble graph distance and related quantities for classic network models (and several parameterizations thereof) using 20 distance measures commonly used to compare graphs. The within-ensemble graph distance provides a new framework for developers of graph distances to better understand their creations and for practitioners to better choose an appropriate tool for their particular task.
Project description:Understanding the structure and the dynamics of networks is of paramount importance for many scientific fields that rely on network science. Complex network theory provides a variety of features that help in the evaluation of network behavior. However, such analysis can be confusing and misleading as there are many intrinsic properties for each network metric. Alternatively, Information Theory methods have gained the spotlight because of their ability to create a quantitative and robust characterization of such networks. In this work, we use two Information Theory quantifiers, namely Network Entropy and Network Fisher Information Measure, to analyzing those networks. Our approach detects non-trivial characteristics of complex networks such as the transition present in the Watts-Strogatz model from k-ring to random graphs; the phase transition from a disconnected to an almost surely connected network when we increase the linking probability of Erd?s-Rényi model; distinct phases of scale-free networks when considering a non-linear preferential attachment, fitness, and aging features alongside the configuration model with a pure power-law degree distribution. Finally, we analyze the numerical results for real networks, contrasting our findings with traditional complex network methods. In conclusion, we present an efficient method that ignites the debate on network characterization.
Project description:Residue networks representing 595 nonhomologous proteins are studied. These networks exhibit universal topological characteristics as they belong to the topological class of modular networks formed by several highly interconnected clusters separated by topological cavities. There are some networks that tend to deviate from this universality. These networks represent small-size proteins having <200 residues. This article explains such differences in terms of the domain structure of these proteins. On the other hand, the topological cavities characterizing proteins residue networks match very well with protein binding sites. This study investigates the effect of the cutoff value used in building the residue network. For small cutoff values, <5 A, the cavities found are very large corresponding almost to the whole protein surface. On the contrary, for large cutoff value, >10.0 A, only very large cavities are detected and the networks look very homogeneous. These findings are useful for practical purposes as well as for identifying protein-like complex networks. Finally, this article shows that the main topological class of residue networks is not reproduced by random networks growing according to Erdös-Rényi model or the preferential attachment method of Barabási-Albert. However, the Watts-Strogatz model reproduces very well the topological class as well as other topological properties of residue network. A more biologically appealing modification of the Watts-Strogatz model to describe residue networks is proposed.
Project description:Small-world networks, according to Watts and Strogatz, are a class of networks that are "highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs." These characteristics result in networks with unique properties of regional specialization with efficient information transfer. Social networks are intuitive examples of this organization, in which cliques or clusters of friends being interconnected but each person is really only five or six people away from anyone else. Although this qualitative definition has prevailed in network science theory, in application, the standard quantitative application is to compare path length (a surrogate measure of distributed processing) and clustering (a surrogate measure of regional specialization) to an equivalent random network. It is demonstrated here that comparing network clustering to that of a random network can result in aberrant findings and that networks once thought to exhibit small-world properties may not. We propose a new small-world metric, ? (omega), which compares network clustering to an equivalent lattice network and path length to a random network, as Watts and Strogatz originally described. Example networks are presented that would be interpreted as small-world when clustering is compared to a random network but are not small-world according to ?. These findings have important implications in network science because small-world networks have unique topological properties, and it is critical to accurately distinguish them from networks without simultaneous high clustering and short path length.
Project description:A main goal in the analysis of a complex system is to infer its underlying network structure from time-series observations of its behaviour. The inference process is often done by using bi-variate similarity measures, such as the cross-correlation (CC) or mutual information (MI), however, the main factors favouring or hindering its success are still puzzling. Here, we use synthetic neuron models in order to reveal the main topological properties that frustrate or facilitate inferring the underlying network from CC measurements. Specifically, we use pulse-coupled Izhikevich neurons connected as in the Caenorhabditis elegans neural networks as well as in networks with similar randomness and small-worldness. We analyse the effectiveness and robustness of the inference process under different observations and collective dynamics, contrasting the results obtained from using membrane potentials and inter-spike interval time-series. We find that overall, small-worldness favours network inference and degree heterogeneity hinders it. In particular, success rates in C. elegans networks - that combine small-world properties with degree heterogeneity - are closer to success rates in Erdös-Rényi network models rather than those in Watts-Strogatz network models. These results are relevant to understand better the relationship between topological properties and function in different neural networks.
Project description:BACKGROUND: Many technological, biological, social, and information networks fall into the broad class of 'small-world' networks: they have tightly interconnected clusters of nodes, and a shortest mean path length that is similar to a matched random graph (same number of nodes and edges). This semi-quantitative definition leads to a categorical distinction ('small/not-small') rather than a quantitative, continuous grading of networks, and can lead to uncertainty about a network's small-world status. Moreover, systems described by small-world networks are often studied using an equivalent canonical network model--the Watts-Strogatz (WS) model. However, the process of establishing an equivalent WS model is imprecise and there is a pressing need to discover ways in which this equivalence may be quantified. METHODOLOGY/PRINCIPAL FINDINGS: We defined a precise measure of 'small-world-ness' S based on the trade off between high local clustering and short path length. A network is now deemed a 'small-world' if S>1--an assertion which may be tested statistically. We then examined the behavior of S on a large data-set of real-world systems. We found that all these systems were linked by a linear relationship between their S values and the network size n. Moreover, we show a method for assigning a unique Watts-Strogatz (WS) model to any real-world network, and show analytically that the WS models associated with our sample of networks also show linearity between S and n. Linearity between S and n is not, however, inevitable, and neither is S maximal for an arbitrary network of given size. Linearity may, however, be explained by a common limiting growth process. CONCLUSIONS/SIGNIFICANCE: We have shown how the notion of a small-world network may be quantified. Several key properties of the metric are described and the use of WS canonical models is placed on a more secure footing.
Project description:Power grids, road maps, and river streams are examples of infrastructural networks which are highly vulnerable to external perturbations. An abrupt local change of load (voltage, traffic density, or water level) might propagate in a cascading way and affect a significant fraction of the network. Almost discontinuous perturbations can be modeled by shock waves which can eventually interfere constructively and endanger the normal functionality of the infrastructure. We study their dynamics by solving the Burgers equation under random perturbations on several real and artificial directed graphs. Even for graphs with a narrow distribution of node properties (e.g., degree or betweenness), a steady state is reached exhibiting a heterogeneous load distribution, having a difference of one order of magnitude between the highest and average loads. Unexpectedly we find for the European power grid and for finite Watts-Strogatz networks a broad pronounced bimodal distribution for the loads. To identify the most vulnerable nodes, we introduce the concept of node-basin size, a purely topological property which we show to be strongly correlated to the average load of a node.
Project description:An approach combining genetic, proteomic, computational, and physiological analysis was used to define a protein network that regulates fat storage in budding yeast (Saccharomyces cerevisiae). A computational analysis of this network shows that it is not scale-free, and is best approximated by the Watts-Strogatz model, which generates "small-world" networks with high clustering and short path lengths. The network is also modular, containing energy level sensing proteins that connect to four output processes: autophagy, fatty acid synthesis, mRNA processing, and MAP kinase signaling. The importance of each protein to network function is dependent on its Katz centrality score, which is related both to the protein's position within a module and to the module's relationship to the network as a whole. The network is also divisible into subnetworks that span modular boundaries and regulate different aspects of fat metabolism. We used a combination of genetics and pharmacology to simultaneously block output from multiple network nodes. The phenotypic results of this blockage define patterns of communication among distant network nodes, and these patterns are consistent with the Watts-Strogatz model.
Project description:We develop a new ensemble of modular random graphs in which degree-degree correlations can be different in each module, and the inter-module connections are defined by the joint degree-degree distribution of nodes for each pair of modules. We present an analytical approach that allows one to analyze several types of binary dynamics operating on such networks, and we illustrate our approach using bond percolation, site percolation, and the Watts threshold model. The new network ensemble generalizes existing models (e.g., the well-known configuration model and Lancichinetti-Fortunato-Radicchi networks) by allowing a heterogeneous distribution of degree-degree correlations across modules, which is important for the consideration of nonidentical interacting networks.
Project description:We introduce the idemetric property, which formalizes the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard amongst small-world network models. Modulo reasonable sparsity assumptions, we are then able to show that a strong form of idemetricity is actually equivalent to a very weak expander condition (PUMP). This provides a direct way of providing short proofs that small-world network models such as the Watts-Strogatz model are strongly idemetric (for a wide range of parameters), and also provides further evidence that being idemetric is a common property. We then consider how satisfaction of the idemetric property is relevant to algorithm design. For idemetric graphs, we observe, for example, that a single breadth-first search provides a solution to the all-pairs shortest paths problem, so long as one is prepared to accept paths which are of stretch close to 2 with high probability. Since we are able to show that Kleinberg's model is idemetric, these results contrast nicely with the well known negative results of Kleinberg concerning efficient decentralized algorithms for finding short paths: for precisely the same model as Kleinberg's negative results hold, we are able to show that very efficient (and decentralized) algorithms exist if one allows for reasonable preprocessing. For deterministic distributed routing algorithms we are also able to obtain results proving that less routing information is required for idemetric graphs than in the worst case in order to achieve stretch less than 3 with high probability: while ?(n 2) routing information is required in the worst case for stretch strictly less than 3 on almost all pairs, for idemetric graphs the total routing information required is O(nlog(n)).
Project description:Real-world complex systems may be mathematically modeled as graphs, revealing properties of the system. Here we study graphs of functional brain organization in healthy adults using resting state functional connectivity MRI. We propose two novel brain-wide graphs, one of 264 putative functional areas, the other a modification of voxelwise networks that eliminates potentially artificial short-distance relationships. These graphs contain many subgraphs in good agreement with known functional brain systems. Other subgraphs lack established functional identities; we suggest possible functional characteristics for these subgraphs. Further, graph measures of the areal network indicate that the default mode subgraph shares network properties with sensory and motor subgraphs: it is internally integrated but isolated from other subgraphs, much like a "processing" system. The modified voxelwise graph also reveals spatial motifs in the patterning of systems across the cortex.