Title: Fast graph centrality computation via sampling: a case study of influence maximisation over OSNs

Authors: Rui Wang; Min Lv; Zhiyong Wu; Yongkun Li; Yinlong Xu

Addresses: School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China ' School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China ' School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China ' School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China ' School of Computer Science and Technology, University of Science and Technology of China, Hefei, Anhui, China

Abstract: Graph centrality computation, e.g., asking for the most important vertices in a graph, may incur a high time cost with the increasing size of graphs. To address this challenge, this paper presents a sampling-based framework to speed up the computation of graph centrality. As a use case, we study the problem of influence maximisation (IM), which asks for the k most influential nodes in a graph to trigger the largest influence spread, and present an IM-RWS algorithm. We experimentally compare IM-RWS with the state-of-the-art influence maximisation algorithms IMM and IM-RW, and the results show that our solution can bring a significant improvement in efficiency as well as a certain extent of improvement in empirical accuracy. In particular, our algorithm can solve the influence maximisation problem in graphs containing millions of nodes within tens of seconds with an even better performance result in terms of influence spread.

Keywords: random walk; sampling; graph centrality; online social networks; influence maximisation.

DOI: 10.1504/IJHPCN.2019.099747

International Journal of High Performance Computing and Networking, 2019 Vol.14 No.1, pp.92 - 101

Received: 15 Oct 2016
Accepted: 03 Feb 2017
Published online: 21 May 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article