Influence maximization is a fundamental problem, which is aimed to specify a small number of individuals as seed set to influence the largest number of individuals under a certain influence cascade model. Most existing works on influence maximization may have either high effectiveness or good efficiency,which can not balance both the effectiveness and efficiency. One of the reason is that they do not consider the effect of influence overlap on the effectiveness. That is, these works ignore the phenomenon that the same set of nodes may be influenced by a subset of different influential nodes. To tackle the effectiveness of heuristic algorithm, we propose a three-phase-based heuristic algorithm, called Three-Phase-based Heuristic (TPH), which uses K-shell method to find influential nodes firstly. Moreover, we utilize weighed degree to make up for the coarse-grained of K-shell method. At last, we take advantage of similarity index to reduce the effect of influence overlap by covering the similar neighbor nodes with low influence. Furthermore, exhaustive experiments indicate that the proposed algorithm outperforms the other baseline algorithms in the aspects of influence spread and running time.
LiuY., LumingZ., et al., Fortune Teller: Predicting Your Career Path, AAAI, (2016).
2.
LiuY., NieL., LiuL., et al., From action to activity: Sensor-based activity recognition, Neurocomputing (2015), 108–115.
3.
Preot̆iuc-PietroD., LiuY., HopkinsD., et al., Beyond Binary Labels: Political Ideology Prediction of Twitter Users, Meeting of the Association for Computational Linguistics (2017).
4.
DomingosP. and RichardsonM., Mining the network value of customers, in Proc. KDD, (2001).
5.
RichardsonM. and DomingosP., Mining knowledge-sharing sites for viral marketing, in Proc. KDD, New York, NY, USA, (2002).
6.
KempleD., KleinbergJ.M. and TardosÉ., Maximizing the spread of influence through a social network, Proceedings of the 9th ACM SIGKDD conference on knowledge discovery and data mining, New York, NY, USA, (2003).
7.
LeskovecJ., et al., Cost-effective outbreak detection in networks, in Proc. KDD, New York, NY, USA, (2007).
8.
ChenW., YuanY. and ZhangL., Scalable influence maximization for independent cascade model in large-scale social networks[J], Data Mining and Knowledge Discovery25(3) (2012), 545–576.
9.
CaoJ.X., DongD., XuS., et al., Ak-core based algorithm for influence maximization in social networks, Chinese Journal of Computers (2015), 1–7.
10.
ChenW., WangY. and YangS., Efficient influence maximization in social networks, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM (2009), 199–208.
11.
WangZ.X. and ZhaoY., Fast ranking influential nodes in complex networks using a k-shell iteration factor, Physica A461 (2016), 171–181.
12.
LiuQ., XiangB., ChenE., et al., Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach, in Proc. KDD, Shang Hai, China, (2014).
13.
JungK., HeoW. and ChenW., IRIE: Scalable and Robust Influence Maximization in Social Networks, Proceedings of the 2014 IEEE International Conference on Data Mining. IEEE,Washington, DC, USA, (2013).
14.
WangX., ZhangY., ZhangW., et al., Bring Order into the Samples: A Novel Scalable Method for Influence Maximization (Extended Abstract), IEEE Transactions on Knowledge & Data Engineering (2017), 243-256.
15.
LiY., FanJ., WangY., et al., Influence Maximization on Social Graphs: A Survey, IEEE Transactions on Knowledge and Data Engineering (2018), 1-1.
16.
ChengS., ShenH., HuangJ., et al., IMRank: influence maximization via finding self-consistent ranking, Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval, Gold Coast , Australia, ACM (2014), 475–484.
17.
ZhaoQ., LuH., GanZ., et al., A K-shell Decomposition Based Algorithm for Influence Maximization, International Conference on Engineering the Web in the Big Data Era. Springer-VerlagNew York, Inc. (2015).
18.
PeiS. and MakseH.A., Spreading dynamics in complex networks, Stat Mech Theory (2013).
19.
LiL., LiK. and XiangC., A Hierarchy Based Influence Maximization Algorithm in Social Networks, Proceedings of the 27th International Conference on Artificial Neural Networks, (2018).
20.
LiH., ZhangR., ZhaoZ., et al., An Efficient Influence Maximization Algorithm Based on Clique in Social Networks, IEEE ACCESS7 (2019), 141083–141093.
21.
ShangJ., ZhouS., LiX., et al., CoFIM: A community-based framework for influence maximization on large-scale networks, Knowledge-Based Systems (2016), 88–100.
22.
HuaY., ChenB., YuanY., ZhuG., MaJ., et al., An Influence Maximization Algorithm Based on the Mixed Importance of Nodes, CMC-Computers Materials & Continua59(2) (2019), 517–531.
23.
TianJ.T., WangY.T. and FengX.J., A New Hybrid Algorithm for Influence Maximization in Social Networks, Chinese Journal of Computers (2011), 1956–1965.
24.
TangJ., TangX. and YuanJ., An efficient and effective hop-based approach for influence maximization in social networks, Social Network Analysis & Mining (2018), 1–19.
25.
MonteserinA. and ArmentanoM.G., Influence me! Predicting links to influential users, Information Retrieval Journal2(22) (2019), 32–54.
26.
GallagherB., TongH., Eliassi-RadT., et al., Using Ghost Edges for Classification in Sparsely Labeled Networks, Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, August (2008), 24–27.
27.
HolmeP., HussM. and Soc.J.R., Interface, 2 (2005).
28.
KitsakM., GallosL.K., HavlinS., LiljerosF., MuchnikL., StanleyH.E. and MakseH.A., Identification of influential spreaders in complex networks, Nat Phys6(11) (2010), 888–893.
29.
LiuY., TangM., ZhouT., et al., Improving the accuracy of the k-shell method by removing redundant links: From a perspective of spreading dynamics, Scientific Reports5(13172) (2015).
30.
ChenD., LuL., ShangM.-S., ZhangY.-C. and ZhouT., Identifying influential nodes in complex networks, Physica A (2012), 1777–1787.
31.
GaoS., MaJ., ChenZ., WangG. and XingC., Ranking the spreading capability of nodes in complex networks based on local structure, Physica A (2014), 130–147.
32.
ZhaQ., DongY., ZhangH., ChiclanaF. and Herrera-ViedmaE., A Personalized Feedback Mechanism Based on Bounded Confidence Learning to Support Consensus Reaching in Group Decision Making, IEEE Transactions on Systems, Man, and Cybernetics: Systems (2019). DOI: 10.1109/TSMC.2019.2945922
