Stability of network centrality measures: a numerical study
- PDF / 6,675,766 Bytes
- 17 Pages / 595.276 x 790.866 pts Page_size
- 81 Downloads / 181 Views
ORIGINAL ARTICLE
Stability of network centrality measures: a numerical study Orsolya Kardos1 · András London1 · Tamás Vinkó1 Received: 6 January 2020 / Revised: 30 August 2020 / Accepted: 2 September 2020 © The Author(s) 2020
Abstract Identifying key actors or nodes in a network is a relevant task regarding many applications. In general, the real-valued function that evaluates the nodes is called node centrality measure. Performing a relevance-based ranking on the list of nodes is also of high practical importance, since the most central nodes by a measure usually provide the highest contribution in explaining the behavior of the whole network. Stability of centrality measures against graph perturbation is an important concept, especially in the analysis of real world—often noise contaminated—datasets from different domains. In this paper, with the utilization of the formal definition of stability introduced by Segarra and Ribeiro (IEEE Trans Signal Process 64(3):543–555, 2015), we discuss three main perturbation categories and experimentally analyze the stability of several node centrality measures.
1 Introduction Given a complex network, being biological (e.g., neural interactions), technological (e.g., IoT systems), social (e.g., online social media platforms) or transportation related (e.g., scheduled flights), the topology of the underlying graph can easily indicate node importance (Ghoshal et al. 2014). Peripheral nodes generally do not have major impact, whereas nodes positioned in the epicenter of the topology can effectively control several structural and functional behaviors of the network. Thus, identifying the most important nodes in a network brings us closer to understand network dynamics’ complexity from multiple aspects. Node centrality measures are the metrics developed in order to determine these important nodes. Since node importance can be interpreted in plenty of disparate ways, many coexisting centrality measures have been introduced and applied This paper is a substantial extension of a Middle-European Conference on Applied Theoretical Computer Science (MATCOS-19) short paper (Kardos et al. 2019). * Tamás Vinkó [email protected]‑szeged.hu Orsolya Kardos [email protected]‑szeged.hu András London [email protected]‑szeged.hu 1
effectively in various domains (Zweig 2016; Das et al. 2018). Depending on the interpretation of node importance, these differently calculated measures can represent local (i.e., neighborhood based) or global information, as well as static and dynamic properties of the network, thus providing relevant metrics for a diverse set of applications. The most commonly known and used centrality measures are degree (Shaw 1954; Nieminen 1973), closeness (Beauchamp 1965; Sabidussi 1966), eigenvector (Bonacich 1972), betweenness (Freeman 1977) and PageRank (Brin and Page 1998). Several studies focused on investigating the stability of node centrality measures in an empirical way. Recently, a formal definition for the stability of node centrality measures has been given by Segarra and Ribeir
Data Loading...
