یک روش جدید حریصانه مبتنی بر مدل آبشاری برای محاسبه‌ی حداکثر سازی نفوذ در شبکه‌های اجتماعی
محورهای موضوعی : عمومىعسگرعلی بویر 1 , حمید احمدی بنی 2
1 - گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز
2 - گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز
کلید واژه: مدل آبشاری مستقل, حداکثر سازی نفوذ, انتشار, شبکه اجتماعی,
چکیده مقاله :
در مسئله حداکثر سازی نفوذ، هدف یافتن حداقل تعدادی گره هست که بیشترین انتشار و نفوذ را در شبکه داشته باشند. مطالعات راجع به حداکثر سازی نفوذ و انتشار به‌صورت گسترده ای در حال گسترش است. در سال های اخیر الگوریتم‌های زیادی درزمینهٔ مسئله حداکثر سازی نفوذ در شبکه های اجتماعی ارائه‌شده است. این مطالعات شامل بازار یابی ویروسی، گسترش شایعات، اتخاذ نوآوری و شیوع بیماری‌های همه گیر و ... است. هر یک از مطالعات پیشین دارای کاستی‌هایی دریافتن گره‌های مناسب و یا پیچیدگی زمانی بالا هستند. در این مقاله، روشی جدید با عنوان ICIM-GREEDY برای حل مسئله حداکثر سازی نفوذ ارائه کرده ایم. در الگوریتم ICIM-GREEDY دو معیار مهم که در کارهای انجام‌شده قبلی در نظر گرفته نشده اند را در نظر می گیریم، یکی قدرت نفوذ و دیگری حساسیت به نفوذ. این دو معیار همیشه در زندگی اجتماعی انسان‌ها وجود دارد. روش پیشنهادی روی دیتاست‌های استاندارد مورد ارزیابی قرارگرفته‌شده است. نتایج به‌دست‌آمده نشان می‌دهد که روش مذکور نسبت به دیگر الگوریتم‌های مقایسه شده از کیفیت بهتری در پیدا کردن نودهای بانفوذ در 30 گره Seed برخوردار است. همچنین این روش از لحاظ زمانی نیز نسبت به الگوریتم‌های مقایسه شده به لحاظ همگرایی نسبتاً سریع، بهتر عمل می‌کند.
In the case of penetration maximization, the goal is to find the minimum number of nodes that have the most propagation and penetration in the network. Studies on maximizing penetration and dissemination are becoming more widespread. In recent years, many algorithms have been proposed to maximize the penetration of social networks. These studies include viral marketing, spreading rumors, innovating and spreading epidemics, and so on. Each of the previous studies has shortcomings in finding suitable nodes or high time complexity. In this article, we present a new method called ICIM-GREEDY to solve the problem of maximizing penetration. In the ICIM-GREEDY algorithm, we consider two important criteria that have not been considered in the previous work, one is penetration power and the other is penetration sensitivity. These two criteria are always present in human social life. The proposed method is evaluated on standard datasets. The obtained results show that this method has a better quality in finding penetrating nodes in 30 seed nodes than other compared algorithms. This method also performs better in terms of time compared to the comparative algorithms in terms of relatively fast convergence.
P. Domingos and M. Richardson, "Mining the network value of customers," in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, 2001, pp. 57-66: ACM.
2. 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: ACM.
3. S. Bharathi, D. Kempe, and M. Salek, "Competitive influence maximization in social networks," in International workshop on web and internet economics, 2007, pp. 306-311: Springer.
4. C. Budak, D. Agrawal, and A. El Abbadi, "Limiting the spread of misinformation in social networks," in Proceedings of the 20th international conference on World wide web, 2011, pp. 665-674.
5. W. Chen et al., "Influence maximization in social networks when negative opinions may emerge and propagate," in Proceedings of the 2011 siam international conference on data mining, 2011, pp. 379-390: SIAM.
6. X. He, G. Song, W. Chen, and Q. Jiang, "Influence blocking maximization in social networks under the competitive linear threshold model," in Proceedings of the 2012 siam international conference on data mining, 2012, pp. 463-474: SIAM.
7. W. Lu, W. Chen, and L. V. Lakshmanan, "From competition to complementarity: comparative influence diffusion and maximization," arXiv preprint arXiv:1507.00317, 2015.
8. H. Ma, Y. Zhu, D. Li, D. Kim, and J. Liang, "Improving the influence under IC-N model in social networks," Discrete Mathematics, Algorithms and Applications, vol. 7, no. 03, p. 1550037, 2015.
9. N. Pathak, A. Banerjee, and J. Srivastava, "A generalized linear threshold model for multiple cascades," in 2010 IEEE International Conference on Data Mining, 2010, pp. 965-970: IEEE.
10. C. Wang, W. Chen, and Y. Wang, "Scalable influence maximization for independent cascade model in large-scale social networks," Data Mining and Knowledge Discovery, vol. 25, no. 3, pp. 545-576, 2012.
11. H. A. Beni and A. Bouyer, "TI-SC: top-k influential nodes selection based on community detection and scoring criteria in social networks," Journal of Ambient Intelligence and Humanized Computing, pp. 1-20, 2020.
12. Y. Chen, Q. Qu, Y. Ying, H. Li, and J. Shen, "Semantics-aware influence maximization in social networks," Information Sciences, vol. 513, pp. 442-464, 2020.
13. Q. He et al., "CAOM: A community-based approach to tackle opinion maximization for social networks," Information Sciences, vol. 513, pp. 252-269, 2020.
14. M. M. Keikha, M. Rahgozar, M. Asadpour, and M. F. Abdollahi, "Influence maximization across heterogeneous interconnected networks based on deep learning," Expert Systems with Applications, vol. 140, p. 112905, 2020.
15. J. Ko, K. Lee, K. Shin, and N. Park, "MONSTOR: An Inductive Approach for Estimating and Maximizing Influence over Unseen Social Networks," arXiv preprint arXiv:2001.08853, 2020.
16. J. Tang, R. Zhang, P. Wang, Z. Zhao, L. Fan, and X. Liu, "A discrete shuffled frog-leaping algorithm to identify influential nodes for influence maximization in social networks," Knowledge-Based Systems, vol. 187, p. 104833, 2020.
17. A. Zareie, A. Sheikhahmadi, and M. Jalili, "Identification of influential users in social network using gray wolf optimization algorithm," Expert Systems with Applications, vol. 142, p. 112971, 2020.
18. J. Leskovec et al., "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: ACM.
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, 2009, pp. 199-208: ACM.
20. R. Narayanam and Y. Narahari, "A shapley value-based approach to discover influential nodes in social networks," IEEE Transactions on Automation Science and Engineering, vol. 8, no. 1, pp. 130-147, 2010.
21. M. Kitsak et al., "Identification of influential spreaders in complex networks," Nature physics, vol. 6, no. 11, p. 888, 2010.
22. 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: ACM.
23. 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.
24. 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, p. 25, 2014.
25. W. Chen, T. Lin, Z. Tan, M. Zhao, and X. Zhou, "Robust influence maximization," in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 795-804: ACM.
26. J.X. Zhang, D.-B. Chen, Q. Dong, and Z.-D. Zhao, "Identifying a set of influential spreaders in complex networks," Scientific reports, vol. 6, p. 27823, 2016. 27. J. Shang, S. Zhou, X. Li, L. Liu, and H. Wu, "CoFIM: A community-based framework for influence maximization on large-scale networks," Knowledge-Based Systems, vol. 117, pp. 88-100, 2017.
28. F. Morone, B. Min, L. Bo, R. Mari, and H. A. Makse, "Collective influence algorithm to find influencers via optimal percolation in massively large social media," Scientific reports, vol. 6, p. 30062, 2016.
29. 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, vol. 7, p. 43330, 2017.
30. S. Ahajjam and H. Badir, "Identification of influential spreaders in complex networks using HybridRank algorithm," Scientific reports, vol. 8, no. 1, p. 11932, 2018.
31. D.-L. Nguyen, T.-H. Nguyen, T.-H. Do, and M. Yoo, "Probability-based multi-hop diffusion method for influence maximization in social networks," Wireless Personal Communications, vol. 93, no. 4, pp. 903-916, 2017.
32. H. Wu, J. Shang, S. Zhou, Y. Feng, B. Qiang, and W. Xie, "LAIM: A linear time iterative approach for efficient influence maximization in large-scale networks," IEEE Access, vol. 6, pp. 44221-44234, 2018.
33. S. Banerjee, M. Jenamani, and D. K. Pratihar, "ComBIM: A community-based solution approach for the Budgeted Influence Maximization Problem," Expert Systems with Applications, vol. 125, pp. 1- 13, 2019.
34. G. Xie, Y. Chen, H. Zhang, and Y. Liu, "MBIC: A Novel Influence Propagation Model for Membership-Based Influence Maximization in Social Networks," IEEE Access, vol. 7, pp. 75696-75707, 2019.
35. X. Rui, F. Meng, Z. Wang, and G. Yuan, "A reversed node ranking approach for influence maximization in social networks," Applied Intelligence, vol. 49, no. 7, pp. 2684-2698, 2019.
36. L. Qiu, W. Jia, J. Yu, X. Fan, and W. Gao, "PHG: A Three-Phase Algorithm for Influence Maximization Based on Community Structure," IEEE Access, vol. 7, pp. 62511-62522, 2019.
37. S. Milgram, "Behavioral study of obedience," The Journal of abnormal and social psychology, vol. 67, no. 4, p. 371, 1963.
38. V. Batagelj and M. Zaversnik, "An O (m) algorithm for cores decomposition of networks," arXiv preprint cs/0310049, 2003.
39. J. Kunegis, "Konect: the koblenz network collection," in Proceedings of the 22nd International Conference on World Wide Web, 2013, pp. 1343-1350.
40. A.L. Barabási and R. Albert, "Emergence of scaling in random networks," science, vol. 286, no. 5439, pp. 509-512, 1999.
