Finding Influential Nodes by a Fast Marginal Ranking Method

Zhang, Y, Zhang, P, Bao, Z, Xie, Z, Liu, Q and Zhang, B 2018, 'Finding Influential Nodes by a Fast Marginal Ranking Method', in Proceedings of the 29th Australasian Database Conference (ADC 2018), Gold Coast, QLD, 24-27 May 2018, pp. 249-261.


Document type: Conference Paper
Collection: Conference Papers

Title Finding Influential Nodes by a Fast Marginal Ranking Method
Author(s) Zhang, Y
Zhang, P
Bao, Z
Xie, Z
Liu, Q
Zhang, B
Year 2018
Conference name ADC 2018
Conference location Gold Coast, QLD
Conference dates 24-27 May 2018
Proceedings title Proceedings of the 29th Australasian Database Conference (ADC 2018)
Publisher Springer
Place of publication Gold Coast, Australia
Start page 249
End page 261
Total pages 13
Abstract The problem of Influence Maximization (IM) aims to find a small set of k nodes (seed nodes) in a social network G that could maximize the expected number of nodes. It has been proven to be #P-hard, and many approximation algorithms and heuristic algorithms have been proposed to solve this problem in polynomial time. Those algorithms, however, either trade effectiveness for practical efficiency or vice versa. In order to make a good balance between effectiveness and efficiency, this paper introduces a novel ranking method to identify the influential nodes without computing their exact influence. In particular, our method consists of two phases, the influence ranking and the node selection. At the first phase, we rank the nodes influence based on the centrality of the network. At the second phase, we greedily pick the nodes of high ranks as seeds by considering their marginal influence to the current seed set. Experiments on real-world datasets show that the effectiveness of our method outperforms the state-of-the-art heuristic methods by 3% to 25%; and its speed is faster than the approximate method by at least three orders of magnitude (e.g., the approximate method could not complete in 12 h even for a social network of |V| = 196,591 and |E| = 950,327, while our method completes in 100 s).
Subjects Database Management
Copyright notice ©
ISBN 9783319920122
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 0 times in Scopus Article
Access Statistics: 8 Abstract Views  -  Detailed Statistics
Created: Thu, 21 Feb 2019, 12:10:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us