A New PageRank-Based Method for Influence Maximization in Signed Social Networks

Document Type : Research Article

Authors

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

Abstract

Influence maximization is one of the most important topics in the social network analysis field. As all the social networks can be considered signed, explicitly or implicitly, assessing influence maximization in these networks is inevitable. Due to the NP-hard nature of this problem, the category of node-ranking-based solutions is of concern, where, the PageRank algorithm is outstanding. Original PageRank is merely defined based on the trust relationships and it is not applicable in signed social networks. Upon an agreement on the scheme of trust propagation, where trust propagates step by step in the social network, the two main schemes of distrust propagation are: a) distrust propagates step by step throughout the social network, and b) distrust propagates up to one step of the neighborhood. Despite the claims made by related researches that scheme (b) is the dominant behavior compared to (a); available PageRank algorithms are updated to incorporate scheme (a). In this study, a new PageRank-based method, which adopts scheme (b) to model the distrust-based influence propagation in signed social networks, is proposed. Accordingly, the importance of each node is computed considering that every node propagates the received influence from its trusted neighbors to other nodes, while it blocks the received influence from its untrusted neighbors. Assessments run on the three real datasets reveal the superiority of this proposed method over other existing PageRank algorithms in maximizing influence in signed social networks. The outperformance is between 22% to 46% considering all experimental settings in comparison with the most effective benchmark method.

Keywords

Main Subjects

References

[1] 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, pages 137--146, 2003. [ bib | DOI ]
[2] LC. Freeman. Centrality in social networks: Conceptual clarification. Social network: critical concepts in sociology. Londres: Routledge, 2002. [ bib ]
[3] A. Landherr, B. Friedl, and J. Heidemann. A critical review of centrality measures in social networks. Wirtschaftsinformatik, 52:367--382, 2010. [ bib | DOI ]
[4] U. Kang, S. Papadimitriou, J. Sun, and H. Tong. Centralities in large networks: Algorithms and observations. In Proceedings of the 2011 SIAM international conference on data mining, pages 119--130. SIAM, 2011. [ bib | DOI ]
[5] S. Banerjee, M. Jenamani, and DK. Pratihar. A survey on influence maximization in a social network. Knowledge and Information Systems, 62:3417--3455, 2020. [ bib | DOI ]
[6] X. Gong, H. Yu, and T. Yu. Literature review on the influence of social networks. In SHS Web of Conferences, volume 153, page 01009. EDP Sciences, 2023. [ bib | DOI ]
[7] F. Gammoudi, M. Sendi, and MN. Omri. A Survey on Social Media Influence Environment and Influencers Identification. Social Network Analysis and Mining, 12(1):145, 2022. [ bib | DOI ]
[8] J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In Proceedings of the SIGCHI conference on human factors in computing systems, pages 1361--1370, 2010. [ bib | DOI ]
[9] J. Tang, Y. Chang, Ch. Aggarwal, and H. Liu. A survey of signed network mining in social media. ACM Computing Surveys (CSUR), 49(3):1--37, 2016. [ bib | DOI ]
[10] M. Ozer, MY. Yildirim, and H. Davulcu. Negative link prediction and its applications in online political networks. In Proceedings of the 28th ACM Conference on Hypertext and Social Media, pages 125--134, 2017. [ bib | DOI ]
[11] R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In Proceedings of the 13th international conference on World Wide Web, pages 403--412, 2004. [ bib | DOI ]
[12] M. Hosseini-Pozveh, K. Zamanifar, and AR. Naghsh-Nilchi. Assessing information diffusion models for influence maximization in signed social networks. Expert Systems with Applications, 119:476--490, 2019. [ bib | DOI ]
[13] Sh. Chen and K. He. Influence maximization on signed social networks with integrated pagerank. In 2015 IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity), pages 289--292. IEEE, 2015. [ bib | DOI ]
[14] X. Yin, X. Hu, Y. Chen, X. Yuan, and B. Li. Signed-PageRank: An efficient influence maximization framework for signed social networks. IEEE Transactions on Knowledge and Data Engineering, 33(5):2208--2222, 2019. [ bib | DOI ]
[15] A. Mohammadinejad, R. Farahbakhsh, and N. Crespi. Employing personality feature to rank the influential users in signed networks. In 2016 IEEE International Conferences on Big Data and Cloud Computing (BDCloud), Social Computing and Networking (SocialCom), Sustainable Computing and Communications (SustainCom)(BDCloud-SocialCom-SustainCom), pages 346--353. IEEE, 2016. [ bib | DOI ]
[16] Y. Ni, L. Xie, and Z. Liu. Minimizing the expected complete influence time of a social network. Information Sciences, 180(13):2514--2527, 2010. [ bib | DOI ]
[17] Ch. 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 ]
[18] J. Leskovec, A. Krause, C. Guestrin, Ch. 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, pages 420--429, 2007. [ bib | DOI ]
[19] W. Chen, Y. Wang, and S. Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 199--208, 2009. [ bib | DOI ]
[20] 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 ]
[21] Amit Goyal, Wei Lu, and Laks VS 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, 2011. [ bib | DOI ]
[22] A. Goyal, W. Lu, and VS. 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 ]
[23] Ch. Wang, W. Chen, and Y. Wang. Scalable influence maximization for independent cascade model in large-scale social networks. Data Mining and Knowledge Discovery, 25:545--576, 2012. [ bib | DOI ]
[24] 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, pages 509--518, 2013. [ bib | DOI ]
[25] Ch. 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, 2014. [ bib | DOI ]
[26] S. Galhotra, A. Arora, S. Virinchi, and Sh. 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, 2015. [ bib | DOI ]
[27] 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, 2014. [ bib | DOI ]
[28] 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, pages 1539--1554, 2015. [ bib | DOI ]
[29] Hung T Nguyen, My T Thai, and Thang 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, 2016. [ bib | DOI ]
[30] H. Nguyen, M. Thai, and TN. Dinh. A billion-scale approximation algorithm for maximizing benefit in viral marketing. IEEE/ACM Transactions On Networking, 25(4):2419--2429, 2017. [ bib | DOI ]
[31] X. Li, J. Smith, T. Dinh, and MT. Thai. Tiptop:(almost) exact solutions for influence maximization in billion-scale networks. IEEE/ACM Transactions on Networking, 27(2):649--661, 2019. [ bib | DOI ]
[32] Y. Li, J. Fan, Y. Wang, and KL. Tan. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 30(10):1852--1872, 2018. [ bib | DOI ]
[33] S. Banerjee, M. Jenamani, and D. Pratihar. A survey on influence maximization in a social network. Knowledge and Information Systems, 62:3417--3455, 2020. [ bib | DOI ]
[34] S. Pal, S. Kundu, and CA. Murthy. Centrality measures, upper bound and influence maximization in large scale directed social networks. Fundamenta Informaticae, 130(3):317--342, 2014. [ bib | DOI ]
[35] Q. Liu, B. Xiang, E. Chen, H. Xiong, F. Tang, and J. 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, pages 171--180, 2014. [ bib | DOI ]
[36] Y. Wang, B. Zhang, V. Athanasios Vasilakos, and J. Ma. Prdiscount: A heuristic scheme of initial seeds selection for diffusion maximization in social networks. In Intelligent Computing Theory: 10th International Conference, ICIC 2014, Taiyuan, China, August 3-6, 2014. Proceedings 10, pages 149--161. Springer, 2014. [ bib | DOI ]
[37] 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 ]
[38] 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 ]
[39] M. Hosseini-Pozveh. New influence-aware centrality measures for influence maximization in social networks. Journal of Computing and Security, 9(2):23--38, 2022. [ bib | DOI ]
[40] W. Liu, X. Chen, B. Jeon, L. Chen, and B. Chen. Influence maximization on signed networks under independent cascade model. Applied Intelligence, 49:912--928, 2019. [ bib | DOI ]
[41] J. Sheng, L. Chen, Y. Chen, B. Li, and W. Liu. Positive influence maximization in signed social networks under independent cascade model. Soft Computing, 24:14287--14303, 2020. [ bib | DOI ]
[42] D. Li, Zh. Xu, N. Chakraborty, A. Gupta, K. Sycara, and Sh. Li. Polarity related influence maximization in signed social networks. PloS one, 9(7):e102199, 2014. [ bib | DOI ]
[43] C. Qu, J. Bi, and G. Wang. Personalized information diffusion in signed social networks. Journal of Physics: Complexity, 2(2):025002, 2021. [ bib | DOI ]
[44] X. He, H. Du, M Feldman, and G. Li. Information diffusion in signed networks. PloS one, 14(10):e0224177, 2019. [ bib | DOI ]
[45] D. Li and J. Liu. Modeling influence diffusion over signed social networks. IEEE Transactions on Knowledge and Data Engineering, 33(2):613--625, 2019. [ bib | DOI ]
[46] S. Kim and S. Lee. An improved computation of the pagerank algorithm. In Advances in Information Retrieval: 24th BCS-IRSG European Colloquium on IR Research Glasgow, UK, March 25--27, 2002 Proceedings, volume 2291, pages 73--85. Springer, 2002. [ bib ]
[47] W. Xing and A. Ghorbani. Weighted pagerank algorithm. In Proceedings. Second Annual Conference on Communication Networks and Services Research, 2004., pages 305--314. IEEE, 2004. [ bib | DOI ]
[48] R. West, H. Paskov, J. Leskovec, and Ch. Potts. Exploiting social network structure for person-to-person sentiment analysis. Transactions of the Association for Computational Linguistics, 2:297--310, 2014. [ bib | DOI ]
[49] P. Massa, K. Souren, M. Salvetti, and D. Tomasoni. Trustlet, open research on trust metrics. Scalable Computing: Practice and Experience, 9(4), 2008. [ bib ]

Files

History

  • Receive Date: 22 January 2023
  • Revise Date: 29 April 2023
  • Accept Date: 09 May 2023

Share

How to cite

Statistics