In networks, dynamic phenomena such as opinions, behaviors, and information are propagated through connections between entities. Indeed, one of the main issues about a dynamic process is to find a set of individuals with a high influence on other’s decisions which is defined as the “influence maximization” problem, and aims to find a subset of nodes to maximize the total number of adopters at the end of the process.
In this paper, by combining the community structure and influence maximization problem, we proposed a two-layered method for identifying influential nodes so that in the first layer an optimization-based method is applied to detect the potential communities. Then, in the second layer, a criterion is used which is a tradeoff between the low-relevant centralities and methods with high complexity. Our method is implemented on real social networks with different scales, and the performance is evaluated by using the total number of infected nodes at the end of the process. The experimental results indicate the superiority of our method in comparison to other considered approaches by considering the efficiency and scalability.
AgryzkovT.TortosaL. and VicentJ.F., New highlights and a new centrality measure based on the Adapted PageRank Algorithm for urban networks, Applied Mathematics and Computation291 (2016), 14–29.
2.
AnjeraniM. and MoeiniA., Selecting influential nodes for detected communities in real-world social networks, in: 2011 19th Iranian Conference on Electrical Engineering, 2011, pp. 1–6.
3.
BediP. and SharmaC., Community detection in social networks, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery6 (2016), 115–135.
4.
BelloG.A.AngusM.PedemaneN.HarlalkaJ.K.SemazziF.H.M.KumarV. and SamatovaN.F., Response-Guided Community Detection: Application to Climate Index Discovery, in: Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, Porto, Portugal, September 7–11, 2015, Proceedings, Part IIAppiceA.RodriguesP.P.Santos CostaV.GamaJ.JorgeA.SoaresC., eds., Springer International Publishing, Cham, 2015, pp. 736–751.
5.
ChenD.-B.GaoH.LüL. and ZhouT., Identifying Influential Nodes in Large-Scale Directed Networks: The Role of Clustering, PLoS ONE8 (2013), e77455.
6.
ChenD.LüL.ShangM.-S.ZhangY.-C. and ZhouT., Identifying influential nodes in complex networks, Physica A: Statistical Mechanics and Its Applications391 (2012), 1777–1787.
7.
ChenY.-C.ChangS.-H.ChouC.-L.PengW.-C. and LeeS.-Y., Exploring Community Structures for Influence Maximization in Social Networks, in: The 6th SNA-KDD Workshop’12, ACM, Beijing, China, 2012, pp. 1–9.
8.
DomingosP. and RichardsonM., Mining the network value of customers, in: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, San Francisco, California, 2001, pp. 57–66.
9.
DuY.GaoC.HuY.MahadevanS. and DengY., A new method of identifying influential nodes in complex networks based on TOPSIS, Physica A: Statistical Mechanics and Its Applications399 (2014), 57–69.
10.
EstevezP.A.VeraP. and SaitoK., Selecting the Most Influential Nodes in Social Networks, in: 2007 International Joint Conference on Neural Networks, 2007, pp. 2397–2402.
11.
FreemanL.C.BorgattiS.P. and WhiteD.R., Centrality in valued graphs: A measure of betweenness based on network flow, Social Networks13 (1991), 141–154.
12.
FriedkinN.E., Theoretical Foundations for Centrality Measures, American Journal of Sociology96 (1991), 1478–1504.
13.
FuY.-H.HuangC.-Y. and SunC.-T., Using global diversity and local topology features to identify influential network spreaders, Physica A: Statistical Mechanics and Its Applications433 (2015), 344–355.
14.
GaoC.WeiD.HuY.MahadevanS. and DengY., A modified evidential methodology of identifying influential nodes in weighted networks, Physica A: Statistical Mechanics and Its Applications392 (2013), 5490–5500.
15.
GongM.FuB.JiaoL. and DUH., Memetic algorithm for community detection in networks, Phys. Rev. E.84 (2011), 1–9.
16.
GongM.CaiQ.ChenX. and MaL., Complex Network Clustering by Multiobjective Discrete Particle Swarm Optimization Based on Decomposition, IEEE Transactions on Evolutionary Computation18 (2014), 82–97.
17.
GoyalA.LuW. and LakshmananL., CELF++: optimizing the greedy algorithm for influence maximization in social networks, in: Proceedings of the 20th International Conference Companion on World Wide Web, ACM, Hyderabad, India, 2011, pp. 47–48.
18.
HouB.YaoY. and LiaoD., Identifying all-around nodes for spreading dynamics in complex networks, Physica A: Statistical Mechanics and Its Applications391 (2012), 4012–4017.
19.
JungK.HeoW. and ChenW., IRIE: Scalable and Robust Influence Maximization in Social Networks, in: Proceedings of the 2012 IEEE 12th International Conference on Data Mining, IEEE Computer Society, 2012, pp. 918–923.
20.
KempeD.KleinbergJ. and TardosE., Maximizing the Spread of Influence through a social Network, Theory of Computing11 (2015), 104–147.
21.
KeyvanpourM. and AzizaniF., Classification of Approaches and Challenges of Frequent Subgraphs Mining in Biological Networks, CoRR abs/1207.3543 (2012).
22.
KeyvanpourM.R.JavidehM. and EbrahimiM.R., Detecting and investigating crime by means of data mining: a general crime matching framework, in, 2011, pp. 872–880.
23.
KeyvanpourM.R.MoradiM. and HasanzadehF., Digital Forensics 2.0, in: Computational Intelligence in Digital Forensics: Forensic Investigation and ApplicationsMudaA.K.ChooY.-H.AbrahamA.SrihariS.N., eds., Springer International Publishing, Cham, 2014, pp. 17–46.
24.
KumariA. and SinghS.N., Online influence maximization using rapid continuous time independent cascade model, in: 2017 7th International Conference on Cloud Computing, Data Science & Engineering – Confluence, 2017, pp. 356–361.
25.
LeskovecJ.KrauseA.GuestrinC.FaloutsosC.VanBriesenJ. and GlanceN., Cost-effective outbreak detection in networks, in: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, San Jose, California, USA, 2007, pp. 420–429.
26.
LiX.LiuY.JiangY. and LiuX., Identifying social influence in complex networks: A novel conductance eigenvector centrality model, Neurocomputing210 (2016), 141–154.
27.
LiuJ.XiongQ.ShiW.ShiX. and WangK., Evaluating the importance of nodes in complex networks, Physica A: Statistical Mechanics and Its Applications452 (2016), 209–219.
28.
LiuY.TangM.ZhouT. and DoY., Identify influential spreaders in complex networks, the role of neighborhood, Physica A: Statistical Mechanics and Its Applications452 (2016), 289–298.
29.
LuZ.SunX.WenY.CaoG. and PortaT.L., Algorithms and Applications for Community Detection in Weighted Networks, IEEE Transactions on Parallel and Distributed Systems26 (2015), 2916–2926.
30.
LvJ. and GuoJ., Mining communities in social network based on information diffusion, IEEJ Transactions on Electrical and Electronic Engineering11 (2016), 604–617.
31.
LvJ.GuoJ.YangZ.ZhangW. and JocshiA., Improved Algorithms OF CELF and CELF++ for Influence Maximization, Journal of Engineering Science and Technology Review7 (2014), 32–38.
32.
MaL.-l.MaC.ZhangH.-F. and WangB.-H., Identifying influential spreaders in complex networks based on gravity formula, Physica A: Statistical Mechanics and Its Applications451 (2016), 205–212.
33.
MaQ. and MaJ., Identifying and ranking influential spreaders in complex networks with consideration of spreading probability, Physica A: Statistical Mechanics and Its Applications465 (2017), 312–330.
34.
MalliarosF.D.RossiM.-E.G. and VazirgiannisM., Locating influential nodes in complex networks, Scientific Reports6 (2016).
35.
NarayanamR. and NarahariY., A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks, Transactions On Automation Science and Engineering8 (2011), 130–147.
36.
Pastor-SatorrasR. and VespignaniA., Epidemic Spreading in Scale-Free Networks, Physical Review Letters86 (2001), 3200–3203.
37.
PizzutiC., A Multiobjective Genetic Algorithm to Find Communities in Complex Networks, IEEE Transactions on Evolutionary Computation16 (2012), 418–430.
38.
PourkazemiM. and KeyvanpourM., A survey on community detection methods based on the nature of social networks, in: ICCKE 2013, 2013, pp. 114–120.
39.
PourkazemiM. and KeyvanpourM., Community Detection in Social Network by Using a Multi-objective Evolutionary algorithm, Intelligent Data Analysis21 (2017), 385–409.
40.
RahimkhaniK.AleahmadA.RahgozarM. and MoeiniA., A fast algorithm for finding most influential people based on the linear threshold model, Expert Systems with Applications42 (2015), 1353–1361.
41.
RahnamayanS.TizhooshH.R. and SalamaM.M.A., A novel population initialization method for accelerating evolutionary algorithms, Computers & Mathematics with Applications53 (2007), 1605–1614.
42.
RichardsonM. and DomingosP., Mining knowledge-sharing sites for viral marketing, in: Proceedings of the Gighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Edmonton, Alberta, Canada, 2002, pp. 61–70.
43.
RoelensI.BaeckeP. and BenoitD.F., Identifying influencers in a social network: The value of real referral data, Decision Support Systems91 (2016), 25–36.
44.
SaitoK.NakanoR. and KimuraM., Prediction of Information Diffusion Probabilities for Independent Cascade Model, in: Knowledge-Based Intelligent Information and Engineering Systems: 12th International Conference, KES 2008, Zagreb, Croatia, September 3–5, 2008, Proceedings, Part IIILovrekI.HowlettR.-J.JainL.-C., eds., Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 67–75.
45.
SheikhahmadiA.NematbakhshM.A. and ShokrollahiA., Improving detection of influential nodes in complex networks, Physica A: Statistical Mechanics and Its Applications436 (2015), 833–845.
46.
ShiC.YanZ.CaiY. and WuB., Multi-objective community detection in complex networks, Applied Soft Computing12 (2012), 850–859.
47.
SrinivasA. and VelusamyR.L., Identification of influential nodes from social networks based on Enhanced Degree Centrality Measure, in: 2015 IEEE International Advance Computing Conference (IACC), 2015, pp. 1179–1184.
48.
TsaiC.W.YangY.C. and ChiangM.C., A Genetic NewGreedy Algorithm for Influence Maximization in Social Network, in: 2015 IEEE International Conference on Systems, Man, and Cybernetics, 2015, pp. 2549–2554.
49.
VentrescaM. and AlemanD., Efficiently identifying critical nodes in large complex networks, Computational Social Networks6 (2015).
50.
WangQ.JinY.LinZ.ChengS. and YangT., Influence maximization in social networks under an independent cascade-based model, Physica A: Statistical Mechanics and Its Applications444 (2016), 20–34.
51.
WangY.CongG.SongG. and XieK., 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, ACM, Washington, DC, USA, 2010, pp. 1039–1048.
52.
WangZ.ZhaoY.XiJ. and DuC., Fast ranking influential nodes in complex networks using a k-shell iteration factor, Physica A: Statistical Mechanics and Its Applications461 (2016), 171–181.
53.
WassermanS. and FaustK., Social Network Analysis: Methods and Application, Cambridge University Press, Cambridge, United Kingdom, 1994.
54.
WeiC.YajunW. and SiyuY., Efficient influence maximization in social networks, in: Proceedings of the 15th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining, ACM, Paris, France, 2009, pp. 199–208.
55.
YangY. and XieG., Efficient identification of node importance in social networks, Information Processing & Management52 (2016), 911–922.
56.
ZangW.WangX.YaoQ. and GuoL., A Fast Climbing Approach for Diffusion Source Inference in Large Social Networks, in: Data Science: Second International Conference, ICDS 2015, Sydney, Australia, August 8–9, 2015, ProceedingsZhangC.HuangW.ShiY.YuP.ZhuY.TianY.ZhangP.HeJ., eds., Springer International Publishing, Cham, 2015, pp. 50–57.
57.
ZhangX.ZhuJ.WangQ. and ZhaoH., Identifying influential nodes in complex networks with community structure, Knowledge-Based Systems42 (2013), 74–84.
58.
ZhaoY.LiS. and JinF., Identification of influential nodes in social networks with community structure based on label propagation, Neurocomputing210 (2016), 34–44.
59.
ZhouC.ZhangZ.GuoJ. and GuoL., An upper bound based greedy algorithm for mining top-k influential nodes in social networks, in: Proceedings of the 23rd International Conference on World Wide Web, ACM, Seoul, Korea, 2014, pp. 421–422.
