2015/11/25 by Martin W. Ritchie, Luc Berthouze, Ritchie, Martin +3 · 1 citation
Computer Science · Physics and Astronomy · Psychology · #Complex Network Analysis Techniques #Data Visualization and Analytics #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Physical sciences #Mental Health Research Topics #Physics and Society (physics.soc-ph) #Populations and Evolution (q-bio.PE) #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.1512.01435
openalex publication_date 2015/11/25 · openalex created_date 2022/09/25 · openalex updated_date 2026/07/28
Designing algorithms that generate networks with a given degree sequence\nwhile varying both subgraph composition and distribution of subgraphs around\nnodes is an important but challenging research problem. Current algorithms lack\ncontrol of key network parameters, the ability to specify to what subgraphs a\nnode belongs to, come at a considerable complexity cost or, critically, sample\nfrom a limited ensemble of networks. To enable controlled investigations of the\nimpact and role of subgraphs, especially for epidemics, neuronal activity or\ncomplex contagion, it is essential that the generation process be versatile and\nthe generated networks as diverse as possible. In this paper, we present two\nnew network generation algorithms that use subgraphs as building blocks to\nconstruct networks preserving a given degree sequence. Additionally, these\nalgorithms provide control over clustering both at node and global level. In\nboth cases, we show that, despite being constrained by a degree sequence and\nglobal clustering, generated networks have markedly different topologies as\nevidenced by both subgraph prevalence and distribution around nodes, and\nlarge-scale network structure metrics such as path length and betweenness\nmeasures. Simulations of standard epidemic and complex contagion models on\nthose networks reveal that degree distribution and global clustering do not\nalways accurately predict the outcome of dynamical processes taking place on\nthem. We conclude by discussing the benefits and limitations of both methods.\n