Fast graph centrality computation via sampling: a case study of influence maximisation over OSNs Online publication date: Tue, 21-May-2019
by Rui Wang; Min Lv; Zhiyong Wu; Yongkun Li; Yinlong Xu
International Journal of High Performance Computing and Networking (IJHPCN), Vol. 14, No. 1, 2019
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of High Performance Computing and Networking (IJHPCN):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com