Fast algorithm for successive computation of group betweenness centrality
Authors:
- 29 November 2007
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 76 (5) , 056709
Abstract
In this paper, we propose a method for rapid computation of group betweenness centrality whose running time (after preprocessing) does not depend on network size. The calculation of group betweenness centrality is computationally demanding and, therefore, it is not suitable for applications that compute the centrality of many groups in order to identify new properties. Our method is based on the concept of path betweenness centrality defined in this paper. We demonstrate how the method can be used to find the most prominent group. Then, we apply the method for epidemic control in communication networks. We also show how the method can be used to evaluate distributions of group betweenness centrality and its correlation with group degree. The method may assist in finding further properties of complex networks and may open a wide range of research opportunities.Keywords
This publication has 33 references indexed in Scilit:
- Efficient routing on complex networksPhysical Review E, 2006
- Protein interaction networks from yeast to humanCurrent Opinion in Structural Biology, 2004
- CONGESTION AND CENTRALITY IN TRAFFIC FLOW ON COMPLEX NETWORKSAdvances in Complex Systems, 2003
- Modeling the Internet's large-scale topologyProceedings of the National Academy of Sciences, 2002
- Exploring complex networksNature, 2001
- On power-law relationships of the Internet topologyACM SIGCOMM Computer Communication Review, 1999
- Social Network Analysis1994
- Social Network AnalysisSociology, 1988
- Centrality in social networks conceptual clarificationSocial Networks, 1978
- A Set of Measures of Centrality Based on BetweennessSociometry, 1977