TY - GEN
T1 - On rich clubs of path-based centralities in networks
AU - Sarkar, Soumya
AU - Bhowmick, Sanjukta
AU - Mukherjee, Animesh
N1 - Funding Information:
SB has been funded by NSF-CCF Award: # 1533918
PY - 2018/10/17
Y1 - 2018/10/17
N2 - Many scale-free networks exhibit a rich club structure, where high degree vertices form tightly interconnected subgraphs. In this paper, we explore the emergence of rich clubs in the context of shortest path based centrality metrics. We term these subgraphs of connected high closeness or high betweeness vertices as rich centrality clubs (RCC). Our experiments on real world and synthetic networks highlight the inter-relations between RCCs, expander graphs, and the core-periphery structure of the network. We show empirically and theoretically that RCCs exist, if the core-periphery structure of the network is such that each shell is an expander graph, and their density decreases from inner to outer shells. We further demonstrate that in addition to being an interesting topological feature, the presence of RCCs is useful in several applications. The vertices in the subgraph forming the RCC are eective seed nodes for spreading information. Moreover, networks with RCCs are robust under perturbations to their structure. Given these useful properties of RCCs, we present a network modication model that can eciently create a RCC within networks where they are not present, while retaining other structural properties of the original network. The main contributions of our paper are: (i) we demonstrate that the formation of RCC is related to the core-periphery structure and particularly the expander like properties of each shell, (ii) we show that the RCC property can be used to nd eective seed nodes for spreading information and for improving the resilience of the network under perturbation and, nally, (iii) we present a modication algorithm that can insert RCC within networks, while not aecting their other structural properties. Taken together, these contributions present one of the rst comprehensive studies of the properties and applications of rich clubs for path based centralities.
AB - Many scale-free networks exhibit a rich club structure, where high degree vertices form tightly interconnected subgraphs. In this paper, we explore the emergence of rich clubs in the context of shortest path based centrality metrics. We term these subgraphs of connected high closeness or high betweeness vertices as rich centrality clubs (RCC). Our experiments on real world and synthetic networks highlight the inter-relations between RCCs, expander graphs, and the core-periphery structure of the network. We show empirically and theoretically that RCCs exist, if the core-periphery structure of the network is such that each shell is an expander graph, and their density decreases from inner to outer shells. We further demonstrate that in addition to being an interesting topological feature, the presence of RCCs is useful in several applications. The vertices in the subgraph forming the RCC are eective seed nodes for spreading information. Moreover, networks with RCCs are robust under perturbations to their structure. Given these useful properties of RCCs, we present a network modication model that can eciently create a RCC within networks where they are not present, while retaining other structural properties of the original network. The main contributions of our paper are: (i) we demonstrate that the formation of RCC is related to the core-periphery structure and particularly the expander like properties of each shell, (ii) we show that the RCC property can be used to nd eective seed nodes for spreading information and for improving the resilience of the network under perturbation and, nally, (iii) we present a modication algorithm that can insert RCC within networks, while not aecting their other structural properties. Taken together, these contributions present one of the rst comprehensive studies of the properties and applications of rich clubs for path based centralities.
UR - http://www.scopus.com/inward/record.url?scp=85058064409&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85058064409&partnerID=8YFLogxK
U2 - 10.1145/3269206.3271763
DO - 10.1145/3269206.3271763
M3 - Conference contribution
AN - SCOPUS:85058064409
T3 - International Conference on Information and Knowledge Management, Proceedings
SP - 567
EP - 576
BT - CIKM 2018 - Proceedings of the 27th ACM International Conference on Information and Knowledge Management
A2 - Paton, Norman
A2 - Candan, Selcuk
A2 - Wang, Haixun
A2 - Allan, James
A2 - Agrawal, Rakesh
A2 - Labrinidis, Alexandros
A2 - Cuzzocrea, Alfredo
A2 - Zaki, Mohammed
A2 - Srivastava, Divesh
A2 - Broder, Andrei
A2 - Schuster, Assaf
PB - Association for Computing Machinery
T2 - 27th ACM International Conference on Information and Knowledge Management, CIKM 2018
Y2 - 22 October 2018 through 26 October 2018
ER -