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

Ritchie, Martin, Berthouze, Luc and Kiss, Istvan Z (2016) Generation and analysis of networks with a prescribed degree sequence and subgraph family: higher-order structure matters. Journal of Complex Networks, 5 (1). pp. 1-31. ISSN 2051-1310

[img] PDF - Accepted Version
Available under License Creative Commons Attribution.

Download (637kB)
[img] PDF - Published Version
Available under License Creative Commons Attribution.

Download (1MB)

Abstract

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.

Item Type: Article
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Subjects: Q Science > QA Mathematics
Depositing User: Richard Chambers
Date Deposited: 05 May 2016 11:15
Last Modified: 12 Sep 2017 12:57
URI: http://sro.sussex.ac.uk/id/eprint/60762

View download statistics for this item

📧 Request an update
Project NameSussex Project NumberFunderFunder Ref
EPSRC DTA for 2014-15G1429EPSRC-ENGINEERING & PHYSICAL SCIENCES RESEARCH COUNCILEP/M506667/1