Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time

Benjamin F. Maier*, Cristián Huepe, Dirk Brockmann

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

Networks that are organized as a hierarchy of modules have been the subject of much research, mainly focusing on algorithms that can extract this community structure from data. The question of why modular hierarchical (MH) organizations are so ubiquitous in nature, however, has received less attention. One hypothesis is that MH topologies may provide an optimal structure for certain dynamical processes. We revisit a MH network model that interpolates, using a single parameter, between two known network topologies: from strong hierarchical modularity to an Erdos-Rényi random connectivity structure. We show that this model displays a similar small-world effect as the Kleinberg model, where the connection probability between nodes decays algebraically with distance. We find that there is an optimal structure, in both models, for which the pair-averaged first passage time (FPT) and mean cover time of a discrete-time random walk are minimal, and provide a heuristic explanation for this effect. Finally, we show that analytic predictions for the pair-averaged FPT based on an effective medium approximation fail to reproduce these minima, which implies that their presence is due to a network structure effect.

Original languageEnglish (US)
Pages (from-to)865-895
Number of pages31
JournalJournal of Complex Networks
Volume7
Issue number6
DOIs
StatePublished - Apr 15 2019

Keywords

  • cover time
  • effective medium approximation
  • first passage time
  • Kleinberg networks
  • modular hierarchical networks
  • random walks
  • small-world networks

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Management Science and Operations Research
  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time'. Together they form a unique fingerprint.

Cite this