A Community-Based Method for Identifying Influential Nodes Using Network Embedding

Vafaei, Narges; Keyvanpour, Mohammad Reza

doi:10.52547/itrc.14.1.38

Volume 14, Issue 1 (3-2022) itrc 2022, 14(1): 38-47 | Back to browse issues page

‎ 10.52547/itrc.14.1.38

Mendeley

Zotero

RefWorks

Vafaei N, Keyvanpour M R. A Community-Based Method for Identifying Influential Nodes Using Network Embedding. itrc 2022; 14 (1) :38-47
URL: http://journal.itrc.ac.ir/article-1-528-en.html

A Community-Based Method for Identifying Influential Nodes Using Network Embedding

Narges Vafaei¹

, Mohammad Reza Keyvanpour

1- Department of Computer Engineering Faculty of Engineering Alzahra University Tehran, Iran
2- Department of Computer Engineering Faculty of Engineering Alzahra University Tehran, Iran , keyvanpour@alzahra.ac.ir

Abstract: (2156 Views)

People's influence on their friends' personal opinions and decisions is an essential feature of social networks. Due to this, many businesses use social media to convince a small number of users in order to increase awareness and ultimately maximize sales to the maximum number of users. This issue is typically expressed as the influence maximization problem. This paper will identify the most influential nodes in the social network during two phases. In the first phase, we offer a community detection approach based on the Node2Vec method to detect the potential communities. In the second phase, larger communities are chosen as candidate communities, and then the heuristicbased measurement approach is utilized to identify influential nodes within candidate communities. Evaluations of the proposed method on three real datasets demonstrate the superiority of this method over other compared methods.

Keywords: social network mining, influence analysis, influence maximization problem, influential nodes

Full-Text [PDF 1171 kb] (952 Downloads)

Type of Study: Research | Subject: Information Technology

References

1. M. Xu, "Understanding graph embedding methods and their applications," SIAM Review, vol. 63, no. 4, pp. 825853, 2021.

2. S. Banerjee, M. Jenamani, and D. K. Pratihar, "A survey on influence maximization in a social network," Knowledge and Information Systems, pp. 1-39, 2020.

3. L. Qiu, X. Tian, S. Sai, and C. Gu, "LGIM: A global selection algorithm based on local influence for influence maximization in social networks," IEEE Access, vol. 8, pp. 4318-4328, 2019.

4. S. S. Singh, D. Srivastva, M. Verma, and J. Singh, "Influence maximization frameworks, performance, challenges and directions on social network: A theoretical study," Journal of King Saud UniversityComputer and Information Sciences, 2021

5. D. Chen, L. Lü, M.-S. Shang, Y.-C. Zhang, and T. Zhou, "Identifying influential nodes in complex networks," Physica a: Statistical mechanics and its applications, vol. 391, no. 4, pp. 1777-1787, 2012.

6. W. Xu and W. Wu, Optimal Social Influence. Springer, 2020.

7. S. Tian, S. Mo, L. Wang, and Z. Peng, "Deep reinforcement learning-based approach to tackle topicaware influence maximization," Data Science and Engineering, pp. 1-11, 2020.

8. H. Huang, Z. Meng, and S. Liang, "Recurrent Neural Variational Model for Follower-based Influence Maximization," Information Sciences, 2020.

9. D. A. Vega-Oliveros, L. da Fontoura Costa, and F. A. Rodrigues, "Influence maximization by rumor spreading on correlated networks through community identification," Communications in Nonlinear Science and Numerical Simulation, vol. 83, p. 105094, 2020.

10. W. Ju, L. Chen, B. Li, W. Liu, J. Sheng, and Y. Wang, "A new algorithm for positive influence maximization in signed networks," Information Sciences, vol. 512, pp. 1571-1591, 2020.

11. 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, 2003, pp. 137-146.

12. D. J. Watts, "A simple model of global cascades on random networks," Proceedings of the National Academy of Sciences, vol. 99, no. 9, pp. 5766-5771, 2002.

13. S. S. Singh, A. Kumar, K. Singh, and B. Biswas, "C2IM: Community based context-aware influence maximization in social networks," Physica A: Statistical Mechanics and its Applications, vol. 514, pp. 796-818, 2019.

14. 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, 2007, pp. 420-429.

15. 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, 2011, pp. 47-48.

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, 2013, pp. 509-518.

17. 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, 2014, pp. 946-957:SIAM

18. E. Cohen, D. Delling, T. Pajor, and R. F. Werneck,"Sketch-based influence maximization and computation:Scaling up with guarantees," in Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, 2014, pp. 629-638.

19. 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, 2014,pp. 75-86

20. 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, 2015, pp. 1539-1554.

21. H. T. Nguyen, M. T. Thai, and T. N. Dinh, "Stop-andstare: Optimal sampling algorithms for viral marketing in billion-scale networks," in Proceedings of the 2016 international conference on management of data, 2016,pp. 695-710.

22. 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, 2009, pp. 199-208

23. 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, 2010, pp. 88-97: IEEE.

24. 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, 2011, pp. 211-220: IEEE.

25. R. Narayanam and Y. Narahari, "A shapley value-based approach to discover influential nodes in social networks," IEEE Transactions on Automation Scienceand Engineering, vol. 8, no. 1, pp. 130-147, 2010.

26. K. Jung, W. Heo, and W. Chen, "Irie: Scalable and robust influence maximization in social networks," in 2012 IEEE 12th International Conference on Data Mining,2012, pp. 918-923: IEEE

27. 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, 2015, pp.35-36.

28. S. Galhotra, A. Arora, and S. Roy, "Holistic influence maximization: Combining scalability and efficiency with opinion-aware models," in Proceedings of the 2016 International Conference on Management of Data, 2016,pp. 743-758.

29. D. Bucur and G. Iacca, "Influence maximization in social networks with genetic algorithms," in European conference on the applications of evolutionary computation, 2016, pp. 379-392: Springer.

30. Q. Jiang, G. Song, C. Gao, Y. Wang, W. Si, and K. Xie,"Simulated annealing based influence maximization in social networks," in Twenty-fifth AAAI conference on artificial intelligence, 2011.

31. J. J. Lotf, M. A. Azgomi, and M. R. E. Dishabi, "An improved influence maximization method for social networks based on genetic algorithm," Physica A:Statistical Mechanics and its Applications, vol. 586, p.126480, 2022

32. W. Li, Y. Li, W. Liu, and C. Wang, "An influence maximization method based on crowd emotion under an emotion-based attribute social network," Information Processing & Management, vol. 59, no. 2, p. 102818,2022.

33. Y. Wang, G. Cong, G. Song, and K. Xie, "Communitybased 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, 2010, pp. 1039-1048.

34. Y.-C. Chen, W.-Y. Zhu, W.-C. Peng, W.-C. Lee, and S.-Y. Lee, "CIM: Community-based influence maximization in social networks," ACM Transactions on Intelligent Systems and Technology (TIST), vol. 5, no. 2,pp. 1-31, 2014

35. W. Chen, C. Wang, and Y. Wang, "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, 2010, pp. 1029-1038.

36. X. Li, X. Cheng, S. Su, and C. Sun, "Community-based seeds selection algorithm for location aware influence maximization," Neurocomputing, vol. 275, pp. 1601-1613, 2018

37. M. Pourkazemi and M. Keyvanpour, "CNLPSO-SL: A two-layered method for identifying influential nodes in social networks," International Journal of Knowledgebased and Intelligent Engineering Systems, vol. 22, no. 2,pp. 109-123, 2018.

38. M. Pourkazemi and M. R. Keyvanpour, "Community detection in social network by using a multi-objective evolutionary algorithm," Intelligent Data Analysis, vol.21, no. 2, pp. 385-409, 2017.

39. F. Ye, J. Liu, C. Chen, G. Ling, Z. Zheng, and Y. Zhou, "Identifying influential individuals on large-scale social networks: A community based approach," IEEE Access, vol. 6, pp. 47240-47257, 2018.

40. N. Vafaei, M. R. Keyvanpour, and S. V. Shojaedini, "Influence Maximization in Social Media: Network Embedding for Extracting Structural Feature Vector," in 2021 7th International Conference on Web Research (ICWR), 2021, pp. 35-40: IEEE

41. Y. Li, J. Fan, Y. Wang, and K.-L. Tan, "Influence maximization on social graphs: A survey," IEEE Transactions on Knowledge and Data Engineering, vol.30, no. 10, pp. 1852-1872, 2018.

42. P. Cui, X. Wang, J. Pei, and W. Zhu, "A survey on network embedding," IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 5, pp. 833-852, 2018.

43. A. Grover and J. Leskovec, "node2vec: Scalable feature learning for networks," in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855-864.

44. T. Mikolov, K. Chen, G. Corrado, and J. Dean, "Efficient estimation of word representations in vector space,"arXiv preprint arXiv:1301.3781, 2013.

45. B. Wilder12, N. Immorlica, E. Rice24, and M. Tambe12,"Maximizing influence in an unknown social network,"2018

46. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E.Slooten, and S. M. Dawson, "The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations," Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396-405, 2003.

47. M. E. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical review E, vol. 74, no. 3, p. 036104, 2006.

48. B. Hou, Y. Yao, and D. Liao, "Identifying all-around nodes for spreading dynamics in complex networks," Physica A: Statistical Mechanics and its Applications,vol. 391, no. 15, pp. 4012-4017, 2012.

49. M. Gong, Q. Cai, X. Chen, and L. Ma, "Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition," IEEE Transactions on evolutionary computation, vol. 18, no. 1,pp. 82-97, 2013.

50. J. Liu, Q. Xiong, W. Shi, X. Shi, and K. Wang, "Evaluating the importance of nodes in complex networks," Physica A: Statistical Mechanics and its Applications, vol. 452, pp. 209-219, 2016

51. Z. Wang, Y. Zhao, J. Xi, and C. Du, "Fast ranking influential nodes in complex networks using a k-shell iteration factor," Physica A: Statistical Mechanics and its Applications, vol. 461, pp. 171-181, 2016.

52. X. Liu, N. Ding, C. Liu, Y. Zhang, and T. Tang, "Novel social network community discovery method combined local distance with node rank optimization function," Applied Intelligence, pp. 1-18, 2021.

53. A. Kumari, R. K. Behera, A. S. Shukla, S. P. Sahoo, S. Misra, and S. K. Rath, "Quantifying Influential Communities in Granular Social Networks Using Fuzzy Theory," in International Conference on Computational Science and Its Applications, 2020, pp. 906-917:Springer.

54. L. Li, Y. Liu, Q. Zhou, W. Yang, and J. Yuan, "Targeted influence maximization under a multifactor-based information propagation model," Information Sciences,vol. 519, pp. 124-140, 2020.

55. F. Wang et al., "Maximizing positive influence in competitive social networks: A trust-based solution," Information sciences, vol. 546, pp. 559-572, 2021

56. F. Ghayour-Baghbani, M. Asadpour, and H. Faili, "MLPR: Efficient influence maximization in linear threshold propagation model using linear programming," Social Network Analysis and Mining, vol. 11, no. 1, pp.1-10, 2021.

Send email to the article author

Rights and permissions
	This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Principal Contact