CoChat

Exploring the Morphospace of Communication Efficiency in Complex Networks

Open access
Goñi, Joaquín, Avena-Koenigsberger, Andrea, Velez de Mendizabal, Nieves, van den Heuvel, Martijn P., Betzel, Richard F., Sporns, Olaf · 2013 · PLoS ONE

The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.

Abstract

Graph theoretical analysis has played a key role in characterizing global features of the topology of complex networks, describing diverse systems such as protein interactions, food webs, social relations and brain connectivity. How system elements communicate with each other depends not only on the structure of the network, but also on the nature of the system's dynamics which are constrained by the amount of knowledge and resources available for communication processes. Complementing widely used measures that capture efficiency under the assumption that communication preferentially follows shortest paths across the network ("routing"), we define analytic measures directed at characterizing network communication when signals flow in a random walk process ("diffusion"). The two dimensions of routing and diffusion efficiency define a morphospace for complex networks, with different network topologies characterized by different combinations of efficiency measures and thus occupying different regions of this space. We explore the relation of network topologies and efficiency measures by examining canonical network models, by evolving networks using a multi-objective optimization strategy, and by investigating real-world network data sets. Within the efficiency morphospace, specific aspects of network topology that differentially favor efficient communication for routing and diffusion processes are identified. Charting regions of the morphospace that are occupied by canonical, evolved or real networks allows inferences about the limits of communication efficiency imposed by connectivity and dynamics, as well as the underlying selection pressures that have shaped network topology.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1371/journal.pone.0058070

Cites

46 of 46 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Relation of routing efficiency and shortest-path-probability for canonical network models. Scatter plot of and for four canonical network models at different densities: the Erdös-Rényi model (gray), the preferential attachment model (green), the Watts-Strogatz small-world model (red) and the one-dimensional lattice model (blue). The average degree is indicated at the plot line for the lattice model and dotted lines indicate equivalent average degrees for the rest of the models. Network size is fixed at 50 nodes. Each point represents mean values and shaded areas correspond to the 90% confidence interval. To obtain each data point (for each model and each average degree), 100 sample graphs were generated, except for the regular lattice given its deterministic nature. The clique coordinates are given as a reference point with maximum density and thus maximum but very low . As the density increases, monotonically increases whereas tends to monotonically decrease.
Figure 1 Relation of routing efficiency and shortest-path-probability for canonical network models. Scatter plot of and for four canonical network models at different densities: the Erdös-Rényi model (gray), the preferential attachment model (green), the Watts-Strogatz small-world model (red) and the one-dimensional lattice model (blue). The average degree is indicated at the plot line for the lattice model and dotted lines indicate equivalent average degrees for the rest of the models. Network size is fixed at 50 nodes. Each point represents mean values and shaded areas correspond to the 90% confidence interval. To obtain each data point (for each model and each average degree), 100 sample graphs were generated, except for the regular lattice given its deterministic nature. The clique coordinates are given as a reference point with maximum density and thus maximum but very low . As the density increases, monotonically increases whereas tends to monotonically decrease.CC BY · PubMed Central
Figure 2 Graph and efficiency measures for seven idealized network topologies. Descriptors shown are: number of nodes , average degree , characteristic path length , routing efficiency , shortest-path probability , diffusion efficiency and resources efficiency .
Figure 2 Graph and efficiency measures for seven idealized network topologies. Descriptors shown are: number of nodes , average degree , characteristic path length , routing efficiency , shortest-path probability , diffusion efficiency and resources efficiency .CC BY · PubMed Central
Figure 3 Multi-objective optimization in the efficiency morphospace. Results shown are for evolutionary processes driven by network efficiency measures for networks with and . Blue and red squares indicate the reference points of regular lattices and randomized networks respectively. Green points indicate the initial seed population. Gray circles indicate evolving networks over epochs, with darker shades of gray indicating networks encountered in later epochs. Orange points show Pareto-front (non-dominated) solutions. (a) Snapshots illustrating the expansion of the Pareto fronts at epochs 2, 25, 50, 100, and 200. (b) Final solutions were reached after 517, 704, 977, and 433 epochs for fronts 1, 2, 3, and 4 respectively. Black asterisks denote positions of the example graphs shown in insets. Yellow points show dominated solutions of the final populations. Grey points show coordinates visited during the evolutionary process at different epochs (denoted by the gray-level).
Figure 3 Multi-objective optimization in the efficiency morphospace. Results shown are for evolutionary processes driven by network efficiency measures for networks with and . Blue and red squares indicate the reference points of regular lattices and randomized networks respectively. Green points indicate the initial seed population. Gray circles indicate evolving networks over epochs, with darker shades of gray indicating networks encountered in later epochs. Orange points show Pareto-front (non-dominated) solutions. (a) Snapshots illustrating the expansion of the Pareto fronts at epochs 2, 25, 50, 100, and 200. (b) Final solutions were reached after 517, 704, 977, and 433 epochs for fronts 1, 2, 3, and 4 respectively. Black asterisks denote positions of the example graphs shown in insets. Yellow points show dominated solutions of the final populations. Grey points show coordinates visited during the evolutionary process at different epochs (denoted by the gray-level).CC BY · PubMed Central
Figure 4 Graph measures for evolved networks. Results shown are for networks with and . Heat maps are based on a square grid with cells measuring 0.05 units in each dimension. For each cell, graph measures coming from graphs falling on those coordinates at any epoch of the evolutionary processes (one for each front) were averaged. (a) Degree entropy. (b) Assortativity. (c) Modularity. (d) Scaled resource efficiency .
Figure 4 Graph measures for evolved networks. Results shown are for networks with and . Heat maps are based on a square grid with cells measuring 0.05 units in each dimension. For each cell, graph measures coming from graphs falling on those coordinates at any epoch of the evolutionary processes (one for each front) were averaged. (a) Degree entropy. (b) Assortativity. (c) Modularity. (d) Scaled resource efficiency .CC BY · PubMed Central
Figure 5 Placing real-world networks in the efficiency morphospace. The figure shows a scatter plot of and for 23 real-world networks (for description of data sets see Text S1). Blue and red squares indicate lattice and random reference points, respectively, linked by the green reference line. The gray line represents the linear regression across all 23 real-world networks ().
Figure 5 Placing real-world networks in the efficiency morphospace. The figure shows a scatter plot of and for 23 real-world networks (for description of data sets see Text S1). Blue and red squares indicate lattice and random reference points, respectively, linked by the green reference line. The gray line represents the linear regression across all 23 real-world networks ().CC BY · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 46 references

Cited by

See all 158

Metadata

Authors
Goñi, J., Avena-Koenigsberger, A., Velez de Mendizabal, N., van den Heuvel, M. P., Betzel, R. F., & Sporns, O.
Affiliations
Indiana University Bloomington (US)
Corresponding author
Sporns, Olaf
Venue
PLoS ONE
Published
2013-03-07
Volume
8
Issue
3
Pages
e58070
ISSN
1932-6203 (ISSN-L)
OpenAlex
W2010195483
Cited by
158
References
46
Citations by year
2026: 5 · 2025: 18 · 2024: 13 · 2023: 13 · 2022: 14 · 2021: 17 · 2020: 15 · 2019: 14 · 2018: 13 · 2017: 8 · 2016: 11 · 2015: 5 · 2014: 8 · 2013: 4
FWCI
6.64
Type
journal article
Language
en
Open access
Locations
  • PLoS ONE (publishedVersion, cc-by)
  • Europe PMC (PubMed Central) (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • Pure Amsterdam UMC (publishedVersion, other-oa)
  • Amsterdam UMC (VU Amsterdam) - Institutional Repository (publishedVersion, other-oa)
  • RePEc: Research Papers in Economics (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • Figshare (submittedVersion, cc-by)
  • Data Archiving and Networked Services (DANS) (submittedVersion, other-oa)
Funders
James S. McDonnell Foundation
Topics
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Graph theory and applications
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
Keywords
communication efficiency, complex networks, morphospace, diffusion efficiency, routing efficiency, random walks, network topology
MeSH terms
Algorithms, Communication, Computer Simulation, Models, Theoretical

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.