Dataset Information

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.

SUBMITTER: Hartle H

PROVIDER: S-EPMC7735290 | biostudies-literature | 2020 Nov

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Network comparison and the within-ensemble graph distance.

Hartle Harrison H Klein Brennan B McCabe Stefan S Daniels Alexander A St-Onge Guillaume G Murphy Charles C Hébert-Dufresne Laurent L

Proceedings. Mathematical, physical, and engineering sciences 20201104 2243

Quantifying the differences between networks is a challenging and ever-present problem in network science. In recent years, a multitude of diverse, <i>ad hoc</i> 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 th ...[more]

PMID: 33363435

Similar Datasets

Project description:BACKGROUND:The body-bar Pebble Game (PG) algorithm is commonly used to calculate network rigidity properties in proteins and polymeric materials. To account for fluctuating interactions such as hydrogen bonds, an ensemble of constraint topologies are sampled, and average network properties are obtained by averaging PG characterizations. At a simpler level of sophistication, Maxwell constraint counting (MCC) provides a rigorous lower bound for the number of internal degrees of freedom (DOF) within a body-bar network, and it is commonly employed to test if a molecular structure is globally under-constrained or over-constrained. MCC is a mean field approximation (MFA) that ignores spatial fluctuations of distance constraints by replacing the actual molecular structure by an effective medium that has distance constraints globally distributed with perfect uniform density. RESULTS:The Virtual Pebble Game (VPG) algorithm is a MFA that retains spatial inhomogeneity in the density of constraints on all length scales. Network fluctuations due to distance constraints that may be present or absent based on binary random dynamic variables are suppressed by replacing all possible constraint topology realizations with the probabilities that distance constraints are present. The VPG algorithm is isomorphic to the PG algorithm, where integers for counting "pebbles" placed on vertices or edges in the PG map to real numbers representing the probability to find a pebble. In the VPG, edges are assigned pebble capacities, and pebble movements become a continuous flow of probability within the network. Comparisons between the VPG and average PG results over a test set of proteins and disordered lattices demonstrate the VPG quantitatively estimates the ensemble average PG results well. CONCLUSIONS:The VPG performs about 20% faster than one PG, and it provides a pragmatic alternative to averaging PG rigidity characteristics over an ensemble of constraint topologies. The utility of the VPG falls in between the most accurate but slowest method of ensemble averaging over hundreds to thousands of independent PG runs, and the fastest but least accurate MCC.

Dataset Information

Network comparison and the within-ensemble graph distance.

Publications

Network comparison and the within-ensemble graph distance.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets