Welcome to Francis Academic Press

Academic Journal of Computing & Information Science, 2020, 3(3); doi: 10.25236/AJCIS.2020.030307.

Research on Influence Maximization Method for Complex Network

Author(s)

Qipeng Lu1, *, Pengfei Ding2

Corresponding Author:
Qipeng Lu
Affiliation(s)

1 Nanjing University of Finance and Economics, Nanjing 210000, Jiangsu,China
2 Nanjin Institute of Technology , Nanjing 211100, Jiangsu, China
*Corresponding author e-mail: qipenglu@qq.com

Abstract

The influence maximization (IM) is a key algorithm problem in information dissemination research. it aims to select a set of K users (also called seed sets) from a network and maximize the number of affected users (influence spread) through a specific information dissemination model. However, despite its huge application potential, with the advent of the era of big data, all kinds of networks tend to be complicated, and there is relatively little research on influence maximization of multilayer networks in complex networks, because in these networks, nodes are different types. On the other hand, most of the existing research on influence maximization relies on greedy algorithms and can only obtain a single solution. With that in mind, we focus on the influence maximization problem of multilayer networks in complex networks. specifically, we first define some novel concepts about the process of information dissemination in multilayer networks; then, we construct the influence maximization problem in multilayer networks into a multi-objective optimization problem. Finally, we do a lot of experiments on the real datasets, and the results show that the algorithm in this paper has a large competitive advantage in the influence spread and running time compared with the existing influence maximization algorithm.

Keywords

Influence Maximization, Multilayer Networks, Multi-objective Optimization

Cite This Paper

Qipeng Lu, Pengfei Ding. Research on Influence Maximization Method for Complex Network. Academic Journal of Computing & Information Science (2020), Vol. 3, Issue 3: 53-69. https://doi.org/10.25236/AJCIS.2020.030307.

References

[1] Doina Bucur, Giovanni Iacca and Andrea Marcelli, et al (2018). Improving Multi-objective Evolutionary Influence Maximization in Social Networks. In International Conference on the Applications of Evolutionary Computation. p.117–124.
[2] Domingos P, Richardson M (2001). Mining the network value of customers//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p.57-66.
[3] Richardson M, Domingos P (2002). Mining knowledge-sharing sites for viral marketing//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p.61-70.
[4] Kempe D, Kleinberg J, Tardos E (2003). Maximizing the spread of influence through a social network//Proceeding of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p.137-146.
[5] Leskovec J, Krause A, Guestrin C, et al (2007). Cost-effective outbreak detection in networks//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p.420-429.
[6] Goyal A, Lu W, Lakshmanan L V (2011). CELF++: Optimizing the greedy algorithm for influence maximization in social networks//Proceedings of the 20th International Conference Companion on Word Wide Web. p.47-48.
[7] Wei Chen, Yajun Wang, and Siyu Yang (2009). Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining.  p.199–208.
[8] Wei Chen, Chi Wang, and Yajun Wang (2010). Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. P.1029–1038.
[9] Jung K, Heo W, Chen W (2012). IRIE: Scalable and robust influence maximization in social networks//Proceedings of the 2012 IEEE 12th Internation Conference on Data Mining. Brussels,Belgium,p.918-923.
[10] Jiang Q, Song G, Gao C, et al (2011). Simulated annealing based influence maximization in social networks//Proceedings of the 25th AAAI Conference on Artificial Intelligence. California, p.127-132.
[11] Bucur D, Iacca G, Marcelli A, et al (2018). Improving multi-objective evolutionary influence maximization in social networks. Applications of Evolutionary Computation, p.117-124.
[12] Weskida M, Michalski R (2016). Evolutionary algorithm for seed selection in social influence process//Peoceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. San Francisco, p.1189-1196.
[13] Salehi M, Sharma R, Marzolla M, et al (2015). Spreading processes in multilayer networks. IEEE Transactions on Network Science and Engineering, p.65-83.
[14] Deb K, Pratap A, Agarwal S,et al (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, p.182-197.
[15] E. Tardos, D. Kempe, and J. Kleinberg (2003). Maximizing the spread of influence in a social network. In ACM SIGKDD international conference on knowledge discovery and data mining. P.137–146.
[16] Brin S, Page L (1998). The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, p.107-117.
[17] Chen W, Yuan Y, Zhang L (2010). Scalable influence maximization in social networks under the linear threshold model//Proceedings of the 10th IEEE International Conference on Data Mining. p.88-97.