Identifying Influential Spreaders in a Social Network (While Preserving Privacy)
# 76
Abstract
In order to disseminate information in a social network, it is important to first identify the influential spreaders in the network. Using them as the seed spreaders, the aim is to ensure that the information is cascaded throughout the network. The traditional approach to identifying influential nodes is to determine the top-r ranked nodes in accordance with various ranking methods such as PageRank, k-Shell decomposition, ClusterRank and VoteRank. In the current work, we study the problem of ranking the nodes when the underlying graph is distributedly held by a set of individuals, who consider their share of the data as private information. In particular, we design efficient secure multiparty computation (MPC) protocols for k-Shell decomposition, PageRank and VoteRank. For improved efficiency, we employ the oblivious RAM construct in conjunction with efficient data-oblivious graph data structures. We are the first to propose a secure variant of the VoteRank algorithm. We prove that the proposed protocols are asymptotically more efficient and have lower runtime in practice than the previous best known MPC protocols for computing k-Shell decomposition and PageRank centrality scores.
Varsha Bhat, IISc Bangalore
Varsha Bhat is currently an IoE Post-doctoral Researcher at CSA working with professor Arpita Patra. She completed her PhD from Indian Institute of Technology Ropar, under the guidance of Dr. Sudarshan Iyengar. Her PhD thesis was focused on the use of secure multiparty computation (MPC) to design secure variants of popularly used social network analysis algorithms. In general, her research interests include MPC, social network analysis and graph theory.