Fast graph centrality computation via sampling: a case study of influence maximisation over OSNs. (8th May 2019)

• Record Type: Journal Article
• Authors: Wang, Rui; Lv, Min; Wu, Zhiyong; Li, Yongkun; Xu, Yinlong
• Is Part Of: International journal of high performance computing and networking. Volume 14:Number 1(2019)
• Page Start: 92
• Page End: 101
• Publication Date: 2019-05-08
• Subjects: random walk -- sampling -- graph centrality -- online social networks -- influence maximisation; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

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.