Analysis of noisy incomplete networks

Monday, October 22, 2018

16.00 p.m.

ISI seminar room 1st floor

Dr. Soumya Sarkar - Indian Institute of Technology, Kharagpur, West Bengal, India

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 betweenness 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 effective 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  modification model that can efficiently 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 find effective seed nodes for spreading information and for improving the resilience of the network under perturbation and, finally,
(iii) We present a modification algorithm that can insert RCC within networks, while not affecting their other structural properties. Taken together, these contributions present one of the first comprehensive studies of the properties and applications of rich clubs for path based centralities