![](/images/graphics-bg.png)
Approximation of Interactive Betweenness Centrality in Large Complex Networks
Joint Authors
Sun, Xiaoqian
Wandelt, Sebastian
Shi, Xing
Source
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-16, 16 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-02-27
Country of Publication
Egypt
No. of Pages
16
Main Subjects
Abstract EN
The analysis of real-world systems through the lens of complex networks often requires a node importance function.
While many such views on importance exist, a frequently used global node importance measure is betweenness centrality, quantifying the number of times a node occurs on all shortest paths in a network.
This centrality of nodes often significantly depends on the presence of nodes in the network; once a node is missing, e.g., due to a failure, other nodes’ centrality values can change dramatically.
This observation is, for instance, important when dismantling a network: instead of removing the nodes in decreasing order of their static betweenness, recomputing the betweenness after a removal creates tremendously stronger attacks, as has been shown in recent research.
This process is referred to as interactive betweenness centrality.
Nevertheless, very few studies compute the interactive betweenness centrality, given its high computational costs, a worst-case runtime complexity of O(N∗∗4) in the number of nodes in the network.
In this study, we address the research questions, whether approximations of interactive betweenness centrality can be obtained with reduction of computational costs and how much quality/accuracy needs to be traded in order to obtain a significant reduction.
At the heart of our interactive betweenness approximation framework, we use a set of established betweenness approximation techniques, which come with a wide range of parameter settings.
Given that we are interested in the top-ranked node(s) for interactive dismantling, we tune these methods accordingly.
Moreover, we explore the idea of batch removal, where groups of top-k ranked nodes are removed before recomputation of betweenness centrality values.
Our experiments on real-world and random networks show that specific variants of the approximate interactive betweenness framework allow for a speedup of two orders of magnitude, compared to the exact computation, while obtaining near-optimal results.
This work contributes to the analysis of complex network phenomena, with a particular focus on obtaining scalable techniques.
American Psychological Association (APA)
Wandelt, Sebastian& Shi, Xing& Sun, Xiaoqian. 2020. Approximation of Interactive Betweenness Centrality in Large Complex Networks. Complexity،Vol. 2020, no. 2020, pp.1-16.
https://search.emarefa.net/detail/BIM-1141765
Modern Language Association (MLA)
Wandelt, Sebastian…[et al.]. Approximation of Interactive Betweenness Centrality in Large Complex Networks. Complexity No. 2020 (2020), pp.1-16.
https://search.emarefa.net/detail/BIM-1141765
American Medical Association (AMA)
Wandelt, Sebastian& Shi, Xing& Sun, Xiaoqian. Approximation of Interactive Betweenness Centrality in Large Complex Networks. Complexity. 2020. Vol. 2020, no. 2020, pp.1-16.
https://search.emarefa.net/detail/BIM-1141765
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1141765