Using principal eigenvectors of Laplacian-Plus matrix to identify spreaders of social networks under linear threshold diffusion model

Document Type : Original Article

Authors

Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

Abstract

Influence maximization (IM) is a challenging problem in social networks to identify initial spreaders with the best influence on other nodes. It is a need to solve this problem with the minimum diffusion time and the most coverage on the communities. However, the spreaders are rarely dependent on diffusion models. A recent research [N. Binesh, M. Ghatee, Distance-Aware Optimization Model for Influential Nodes Identification in Social Networks with Independent Cascade Diffusion, Information Sciences, 581 (2021) 88-105] proposed DASF algorithm for spreaders selection by the Independent Cascade (IC) diffusion model. Here, we present a new optimization model to find spreaders under Linear Threshold (LT) diffusion model. LT is one of the most important models to imitate the behavior of influence propagation in social networks. Our model is a quadratic programming problem based on LaplacianPlus matrix. We derive its solution by some principal eigenvectors of Laplacian-Plus matrix. We organize the solution process as DALT algorithm. Without community detection, it can identify the spreaders with maximum inter-communities distance, minimum intra-communities distance, and the most significant degrees. By considering various well-known social networks, we show that DALT provides brilliant results and overcomes other local and global spreader finders, especially in social networks with community structures.

Keywords

Main Subjects

References

[1] M. Alshahrani, F. Zhu, L. Zheng, S. Mekouar, and S. Huang, Selection of top-k influential users based on radius-neighborhood degree, multi-hops distance and selection threshold, Journal of Big Data, 5 (2018), p. 28.
[2] N. Binesh and M. Ghatee, Distance-aware optimization model for influential nodes identification in social networks with independent cascade diffusion, Information Sciences, 581 (2021), pp. 88–105.
[3] D. Chen, L. Lu, M.-S. Shang, Y.-C. Zhang, and T. Zhou , Identifying influential nodes in complex networks, Physica A: Statistical Mechanics and its Applications, 391 (2012), pp. 1777–1787.
[4] W. Chen, L. V. Lakshmanan, and C. Castillo, Information and influence propagation in social networks, Synthesis Lectures on Data Management, 5 (2013), pp. 1–177.
[5] D. Fasino and F. Tudisco, Spectral analysis of modularity matrices, SIAM J. Matrix Anal. Appl, 35 (2014), pp. 997–1018.
[6] , The expected adjacency and modularity matrices in the degree corrected stochastic block model, Special Matrices, 6 (2018), pp. 110–121.
[7] , A modularity based spectral method for simultaneous community and anti-community detection, Linear Algebra and its Applications, 542 (2018), pp. 605–623.
[8] L. C. Freeman, A set of measures of centrality based on betweenness, Sociometry, (1977), pp. 35–41.
[9] Y.-H. Fu, C.-Y. Huang, and C.-T. Sun, Using global diversity and local topology features to identify influential network spreaders, Physica A: Statistical Mechanics and its Applications, 433 (2015), pp. 344–355.
[10] A. Garas, F. Schweitzer, and S. Havlin, A k-shell decomposition method for weighted networks, New Journal of Physics, 14 (2012), p. 083030.
[11] Y. Jiang and J. Jiang, Diffusion in social networks: A multiagent perspective, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 45 (2015), pp. 198–213.
[12] K. Jung, W. Heo, and W. Chen, Irie: Scalable and robust influence maximization in social networks, in Data Mining (ICDM), 2012 IEEE 12th International Conference on, IEEE, 2012, pp. 918–923.
[13] D. Kempe, J. Kleinberg, and E. Tardos ´ , Maximizing the spread of influence through a social network, in Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, ACM, 2003, pp. 137–146.
[14] , Maximizing the spread of influence through a social network, Theory OF Computing, 11 (2015), pp. 105– 147.
[15] M. Li, X. Wang, K. Gao, and S. Zhang, A survey on information diffusion in online social networks: Models and methods, Information, 8 (2017), p. 118.
[16] W. Li, K. Zhong, J. Wang, and D. Chen, A dynamic algorithm based on cohesive entropy for influence maximization in social networks, Expert Systems with Applications, 169 (2021), p. Article Number: 114207.
[17] Y. Li, J. Fan, Y. Wang, and K.-L. Tan, Influence maximization on social graphs: A survey, IEEE Transactions on Knowledge and Data Engineering, 30 (2018), pp. 1852–1872.
[18] D. Liu, Y. Jing, J. Zhao, W. Wang, and G. Song, A fast and efficient algorithm for mining top-k nodes in complex networks, Scientific Reports, 7 (2017), p. 43330.
[19] H.-L. Liu, C. Ma, B.-B. Xiang, M. Tang, and H.-F. Zhang, Identifying multiple influential spreaders based on generalized closeness centrality, Physica A: Statistical Mechanics and its Applications, 492 (2018), pp. 2237–2248.
[20] H. Lutkepohl, Handbook of matrices., Computational statistics and Data analysis, 2 (1997), p. 243.
[21] J. McAuley and J. Leskovec, Learning to discover social circles in ego networks, NIPS, (2012).
[22] M. Niksirat and S. N. Hashemi, The complexity of cost constrained vehicle scheduling problem, AUT Journal of Mathematics and Computing, 2 (2021), pp. 109–115.
[23] L. N. Trefethen and D. Bau III, Numerical linear algebra, vol. 50, Siam, 1997.
[24] U. Von Luxburg, A tutorial on spectral clustering, Statistics and computing, 17 (2007), pp. 395–416.
[25] C. Wang, Q. Shi, W. Xian, Y. Feng, and C. Chen, Efficient diversified influence maximization with adaptive policies, Knowledge-Based Systems, 213 (2021), p. 106692.
[26] R. Yarinezhad and S. N. Hashemi, Approximation algorithms for multi-multiway cut and multicut problems on directed graphs, AUT Journal of Mathematics and Computing, 1 (2020), pp. 145–152.
[27] D. Zhang, Y. Wang, and Z. Zhang, Identifying and quantifying potential super-spreaders in social networks, Scientific Reports, 9 (2019), pp. 1–11.
[28] Z. Zhao, X. Wang, W. Zhang, and Z. Zhu, A community-based approach to identifying influential spreaders, Entropy, 17 (2015), pp. 2228–2252.
AUT Journal of Mathematics and Computing
Volume 3, Issue 2
September 2022
Pages 153-164

Files

Share

How to cite

Statistics