University of Sussex
Browse
cnw011.pdf (1.08 MB)

Generation and analysis of networks with a prescribed degree sequence and subgraph family: higher-order structure matters

Download (1.08 MB)
Version 2 2023-06-12, 06:38
Version 1 2023-06-09, 01:06
journal contribution
posted on 2023-06-12, 06:38 authored by Martin Ritchie, Luc BerthouzeLuc Berthouze, Istvan Kiss
Designing algorithms that generate networks with a given degree sequence while varying both subgraph composition and distribution of subgraphs around nodes is an important but challenging research problem. Current algorithms lack control of key network parameters, the ability to specify to what subgraphs a node belongs to, come at a considerable complexity cost or, critically and sample from a limited ensemble of networks. To enable controlled investigations of the impact and role of subgraphs, especially for epidemics, neuronal activity or complex contagion, it is essential that the generation process be versatile and the generated networks as diverse as possible. In this article, we present two new network generation algorithms that use subgraphs as building blocks to construct networks preserving a given degree sequence. Additionally, these algorithms provide control over clustering both at node and global level. In both cases, we show that, despite being constrained by a degree sequence and global clustering, generated networks have markedly different topologies as evidenced by both subgraph prevalence and distribution around nodes, and large-scale network structure metrics such as path length and betweenness measures. Simulations of standard epidemic and complex contagion models on those networks reveal that degree distribution and global clustering do not always accurately predict the outcome of dynamical processes taking place on them. We conclude by discussing the benefits and limitations of both methods.

Funding

EPSRC DTA for 2014-15; G1429; EPSRC-ENGINEERING & PHYSICAL SCIENCES RESEARCH COUNCIL; EP/M506667/1

History

Publication status

  • Published

File Version

  • Published version

Journal

Journal of Complex Networks

ISSN

2051-1310

Publisher

Oxford University Press

Issue

1

Volume

5

Page range

1-31

Department affiliated with

  • Informatics Publications

Full text available

  • Yes

Peer reviewed?

  • Yes

Legacy Posted Date

2016-05-05

First Open Access (FOA) Date

2017-03-02

First Compliant Deposit (FCD) Date

2016-05-05

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC