Influence maximisation (IM) is the problem of finding a set of k-seed nodes that could maximize the amount of influence spread in a social network. In this article, we point out that the existing methods are taking the source-oriented estimation (SOE), which is the main reason of their failure in accurately estimating the amount of potential influence spread of an individual node. We propose a novel target-oriented estimation (TOE) that understands information diffusion more accurately as well as remedies the drawback of the existing methods. Our extensive experiments on four real-world datasets demonstrate that our proposed method outperforms the existing methods consistently with respect to the quality of the selected seed set.
KwonYKimSParkSet al. The information diffusion model in the blog world. In: Proceedings of the 3rd workshop on social network mining and analysis, Paris, 28 June 2009, article no. 4.
2.
KwonYKimSParkS. An analysis of information diffusion in the blog world. In: Proceedings of the 1st ACM international workshop on complex networks meet information & knowledge management, Hong Kong, China, 2–6 November 2009, pp. 27–30. New York: ACM.
3.
HaJKimSFaloutsosCet al. An analysis on information diffusion through blogcast in a blogosphere. Inform Sciences2015; 290(1): 45–62.
4.
DomingosPRichardsonM. Mining the network value of customers. In: Proceedings of the 7th ACM SIGKDD international conference on knowledge discovery and data mining, San Francisco, CA, 26–29 August 2001, pp. 57–66. New York: ACM.
5.
RichardsonMDomingosP. Mining knowledge-sharing sites for viral marketing. In: Proceedings of the 8th ACM SIGKDD international conference on knowledge discovery and data mining, Edmonton, AB, Canada, 23–26 July 2002, pp. 61–70. New York: ACM.
6.
KempeDKleinbergJTardosE. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD international conference on knowledge discovery and data mining, Washington, DC, 24–27 August 2003, pp. 137–146. New York: ACM.
GongMYanJShenBet al. Influence maximization in social networks based on discrete particle swarm optimization. Inform Sciences2016; 367: 600–614.
9.
ZhuTWangBWuBet al. Maximizing the spread of influence ranking in social networks. Inform Sciences2014; 278: 535–544.
10.
TangYShiYXiaoX. Influence maximization in near-linear time: a martingale approach. In: Proceedings of the ACM SIGMOD international conference on management of data, Melbourne, VIC, Australia, 31 May–4 June 2015, pp. 1539–1554. New York: ACM.
SongCHsuWLeeM. Targeted influence maximization in social networks. In: Proceedings of the 25th ACM international conference on information and knowledge management, Indianapolis, IN, 24–28 October 2016, pp. 1683–1692. New York: ACM.
13.
YangYMaoXPeiJet al. Continuous influence maximization: what discounts should we offer to social network users? In: Proceedings of the international conference on management of data, San Francisco, CA, 26 June–1 July 2016, pp. 727–741. New York: ACM.
14.
LeskovecJKrauseAGuestrinCet al. Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, San Jose, CA, 12–15 August 2007, pp. 420–429. New York: ACM.
15.
GoyalALuWLakshmananL. SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: Proceedings of the 11th IEEE international conference on data mining, Vancouver, BC, Canada, 11–14 December 2011, pp. 211–220. New York: IEEE.
16.
KimJKimSYuH. Scalable and parallelizable processing of influence maximization for large-scale social networks? In: Proceedings of the 29th IEEE international conference on data engineering, Brisbane, QLD, Australia, 8–12 April 2013, pp. 266–277. New York: IEEE.
17.
GoyalALuWLakshmananL. CELF++: optimizing the greedy algorithm for influence maximization in social networks. In: Proceedings of the 20th international conference on world wide web, Hyderabad, India, 28 March–1 April 2011, pp. 47–48. New York: ACM.
18.
WangYCongGSongGet al. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks. In: Proceedings of the 16th ACM SIGKDD international conference on knowledge discovery and data mining, Washington, DC, 25–28 July 2010, pp. 1039–1048. New York: ACM.
19.
SongGZhouXWangYet al. Influence maximization on large-scale mobile social network: a divide-and-conquer method. IEEE T Parall Distr2015; 26: 1379–1392.
20.
BozorgiAHaghighiHZahediMet al. INCIM: a community-based algorithm for influence maximization problem under the linear threshold model. Inform Process Manag2016; 52(6): 1188–1199.
21.
Hosseini-PozvehMZamanifarKNaghsh-NilchA. A community-based approach to identify the most influential nodes in social networks. J Inform Sci2017; 43(2): 204–220.
22.
GalhotraSAroraAVirinchiSet al. ASIM: a scalable algorithm for influence maximization under the independent cascade model. In: Proceedings of the 24th international conference on world wide web, Florence, 18–22 May 2015, pp. 35–36. New York: ACM.
23.
ChenWYuanYZhangL. Scalable influence maximization in social networks under the linear threshold model. In: Proceedings of the 10th IEEE international conference on data mining, Sydney, NSW, Australia, 13–17 December 2010, pp. 88–97. New York: IEEE.
24.
GirvanMNewmanM. Community structure in social and biological networks. Proc Natl Acad Sci U S A2002; 99(12): 7821–7826.
25.
ValiantL. The complexity of enumeration and reliability problems. SIAM J Comput1979; 8(3): 410–421.
26.
LeskovecJLangKDasguptaAet al. Community structure in large networks: natural cluster sizes and the absence of large well-defined clusters. Internet Math2009; 6(1): 29–123.
27.
ChenWWangYYangS. Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, Paris, 28 June–1 July 2009, pp. 199–208. New York: ACM.
