New Influence-Aware Centrality Measures for Influence Maximization in Social Networks

Document Type : Research Article

Author

Department of Computer Engineering, Shahreza Campus, University of Isfahan, Iran.

Abstract

Influence maximization in social networks is defined as determining a subset of seed nodes where triggering the influence diffusion through the social network leads to the maximum number of final influenced nodes. The tradeoff between the runtime efficiency and effectiveness in the quality of response is the main issue in presenting solutions for this NP-hard optimization problem. Centrality-based methods are applied as a category of efficient heuristic-based solutions to this problem. The two leading causes of losing effectiveness in centrality-based methods are 1) only the link structure and non-awareness of influence diffusion are considered in determining the importance of nodes, and 2) influence overlap exists among selected seed nodes. To address the first cause, an influence-aware betweenness centrality measure is proposed considering both IC and LT models. Moreover, an existing influence-aware closeness centrality measure for LT model is adopted to cover both LT and IC models. To address the second cause, a greedy-based method is proposed by applying influence-aware centrality measures to identify the influential nodes, next to proposing a Jacquard-based measure to overcome the influence overlap problem. The experiments consist of two parts where two real-world datasets are applied: 1) the proposed influence-aware centrality measures are compared with their original versions, and 2) the greedy-based method is compared with benchmark methods. The results indicate the effectiveness of the influence-aware centrality measures and the proposed greedy-based method in maximizing the influence spread in social networks.

Keywords

Main Subjects

References

[1] D. Kempe, J. Kleinberg, and É. 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, page 137–146. ACM, 2003. [ bib | DOI ]
[2] Y. Li, J. Fan, Y. Wang, and K. Tan. Influence Maximization on Social Graphs: A Survey. IEEE Transactions on Knowledge and Data Engineering, 30(10):1852 -- 1872, 2018. [ bib | DOI ]
[3] S. Banerjee, M. Jenamani, and D. K. Pratihar. A survey on influence maximization in a social network. Knowledge and Information Systems, 62(9):3417–3455, 2020. [ bib | DOI ]
[4] A. Landherr, B. Friedl, and J. Heidemann. A Critical Review of Centrality Measures in Social Networks. Business & Information Systems Engineering, 2(6):371–385, 2010. [ bib | DOI ]
[5] D. Kempe, J. Kleinberg, and É. Tardos. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, page 199–208. ACM, 2009. [ bib | DOI ]
[6] 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(1):1--8, 2017. [ bib | DOI ]
[7] B. Xiang, Q. Liu, E. Chen, H. Xiong, Y. Zheng, and Y. Yang. Pagerank with priors: An influence propagation perspective. In Twenty-Third International Joint Conference on Artificial Intelligence, page 2740–2746. Citeseer, 2013. [ bib | DOI ]
[8] Q. Liu, B. Xiang, E. Chen, H. Xiong, F. Tang, and J. X. Yu. Influence Maximization over Large-Scale Social Networks: A Bounded Linear Approach. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, page 171–180. ACM, 2014. [ bib | DOI ]
[9] Y. Wang, B. Zhang, A. V. Vasilakos, and J. Ma. PRDiscount: A Heuristic Scheme of Initial Seeds Selection for Diffusion Maximization in Social Networks. In International Conference on Intelligent Computing, page 149–161. Springer, 2014. [ bib | DOI ]
[10] M. Hosseini-Pozveh, K. Zamanifar, and A. R. Naghsh-Nilchi. A community-based approach to identify the most influential nodes in social networks. Journal of Information Science, 43(2):204--220, 2017. [ bib | DOI ]
[11] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, page 420–429. ACM, 2014. [ bib | DOI ]
[12] W. Chen, Y. Yuan, and L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In 2010 IEEE International Conference on Data Mining, pages 88--97. IEEE, 2010. [ bib | DOI ]
[13] A. Goyal, W. Lu, and L. V. Lakshmanan. CELF++: optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th international conference companion on World wide web, pages 47--48. ACM, 2011. [ bib | DOI ]
[14] A. Goyal, W. Lu, and L. V. Lakshmanan. SIMPATH: An Efficient Algorithm for Influence Maximization under the Linear Threshold Model. In 2011 IEEE 11th International Conference on Data Mining, pages 211--220. IEEE, 2011. [ bib | DOI ]
[15] C. Wang, W. Chen, and Y. Wang. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 25(3):545–576, 2012. [ bib | DOI ]
[16] S. Cheng, H. Shen, J. Huang, G. Zhang, and X. Cheng. StaticGreedy: solving the scalability-accuracy dilemma in influence maximization. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, page 509–518. ACM, 2013. [ bib | DOI ]
[17] C. Zhou, P. Zhang, J. Guo, and L. Guo. 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, pages 421--422. ACM, 2011. [ bib | DOI ]
[18] S. Galhotra, A. Arora, S. Virinchi, and S. Roy. ASIM: A Scalable Algorithm for Influence Maximization under the Independent Cascade Model. In Proceedings of the 24th International Conference on World Wide Web, pages 35--36. ACM, 2015. [ bib | DOI ]
[19] C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. Maximizing Social Influence in Nearly Optimal Time. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 946--957. SIAM, 2014. [ bib | DOI ]
[20] Y. Tang, X. Xiao, and Y. Shi. Influence maximization: near-optimal time complexity meets practical efficiency. In Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pages 75--86. ACM, 2014. [ bib | DOI ]
[21] Y. Tang, Y. Shi, and X. Xiao. Influence Maximization in Near-Linear Time: A Martingale Approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, page 1539–1554. ACM, 2015. [ bib | DOI ]
[22] H. T. Nguyen, M. T. Thai, and T. N. Dinh. Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks. In Proceedings of the 2016 International Conference on Management of Data, pages 695--710. ACM, 2016. [ bib | DOI ]
[23] H. T. Nguyen, M. T. Thai, and T. N. Dinh. A Billion-Scale Approximation Algorithm for Maximizing Benefit in Viral Marketing. IEEE/ACM Transactions on Networking, 25(4):2419 -- 2429, 2017. [ bib | DOI ]
[24] X. Li, J. D. Smith, T. N. Dinh, and M. T. Thai. TipTop: (Almost) Exact Solutions for Influence Maximization in Billion-Scale Networks. IEEE/ACM Transactions on Networking, 27(2):649 -- 661, 2019. [ bib | DOI ]
[25] S. K. Pal, S. Kundu, and C. Murthy. Centrality Measures, Upper Bound, and Influence Maximization in Large Scale Directed Social Networks. Fundamenta Informaticae, 130(3):317--342, 2014. [ bib | DOI ]
[26] A. Namtirtha, A. Dutta, and B.Dutta. Weighted kshell degree neighborhood: A new method for identifying the influential spreaders from a variety of complex network connectivity structures. Expert Systems with Applications, 139:112859, 2020. [ bib | DOI ]
[27] W. Jia, L. Yan, Z. Ma, and W. Niu. TPH: A Three-Phase-based Heuristic algorithm for influence maximization in social networks. Journal of Intelligent & Fuzzy Systems, 39(3):4393--4403, 2020. [ bib | DOI ]
[28] O. Green, R. McColl, and D. A. Bader. A Fast Algorithm for Streaming Betweenness Centrality. In 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing, pages 11--20. IEEE, 2012. [ bib | DOI ]
[29] J. Leskovec, J. Kleinberg, and C. Faloutsos. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2--es, 2007. [ bib | DOI ]
[30] M. Richardson, R. Agrawal, and P. Domingos. Trust Management for the Semantic Web. In International Semantic Web Conference, pages 351--368. Springer, 2003. [ bib | DOI ]
Journal of Computing and Security
Volume 9, Issue 2
July 2022
Pages 23-38

Files

History

  • Receive Date: 25 June 2022
  • Revise Date: 11 September 2022
  • Accept Date: 18 September 2022

Share

How to cite

Statistics