On the use of random graphs as null model of large connected networks

Sebastian Wandelt, Xiaoqian Sun, Ernestina Menasalvas, Alejandro Rodríguez-González and Massimiliano Zanin

Chaos, Solitons & Fractals, 2019, vol. 119, issue C, 318-325

Abstract: Addressing topological properties of real-world networks requires the use of null models, of which the most common are random Erdős-Rényi graphs with the same number of nodes and links than the network under study. Yet, these latter graphs are completely structure agnostic, and can therefore be disconnected. In this study we analyse the bias introduced by the use of such null models when evaluating the topology of networks that are connected by construction, as is the case of transportation systems. By using large sets of synthetic and real-world networks, we show that metrics like the average shortest path length are consistently overestimated, while others, like the diameter, are underestimated. We further propose an efficient algorithm for creating large connected random networks, which outperforms the naïve strategy of creating Erdős-Rényi graphs until a connected one is obtained. We finally discuss the bias introduced by the use of a Z-Score when the underlying metrics are not normally distributed.

Keywords: Complex networks; Null models; Random graphs (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077919300098
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:119:y:2019:i:c:p:318-325

DOI: 10.1016/j.chaos.2018.12.032

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().