کد مقاله : 202006218181 بازدید : 12978 صفحه: 85 - 98

نوع مقاله: پژوهشی

یک روش جدید حریصانه مبتنی بر مدل آبشاری برای محاسبه‌ی حداکثر سازی نفوذ در شبکه‌های اجتماعی

محورهای موضوعی : عمومى

عسگرعلی بویر ¹ (گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز)
حمید احمدی بنی ² (گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز)

تاریخ دریافت : 1398/04/26 تاریخ پذیرش : 1398/04/26 تاریخ انتشار : 1399/04/01

کلید واژه: مدل آبشاری مستقل, حداکثر سازی نفوذ, انتشار, شبکه اجتماعی,

چکیده مقاله :

در مسئله حداکثر سازی نفوذ، هدف یافتن حداقل تعدادی گره هست که بیشترین انتشار و نفوذ را در شبکه داشته باشند. مطالعات راجع به حداکثر سازی نفوذ و انتشار به‌صورت گسترده ای در حال گسترش است. در سال های اخیر الگوریتم‌های زیادی درزمینهٔ مسئله حداکثر سازی نفوذ در شبکه های اجتماعی ارائه‌شده است. این مطالعات شامل بازار یابی ویروسی، گسترش شایعات، اتخاذ نوآوری و شیوع بیماری‌های همه گیر و ... است. هر یک از مطالعات پیشین دارای کاستی‌هایی دریافتن گره‌های مناسب و یا پیچیدگی زمانی بالا هستند. در این مقاله، روشی جدید با عنوان 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.

متن کامل:

فصلنامة علمي- پژوهشي

فناوري اطلاعات و ارتباطات ایران

سال دهم، شماره‌هاي 37 و 38، پاییز و زمستان 1397

صص: 85- 100

$E:\E Drive\logo\iicta Logo0.JPG$

یک روش جدید حریصانه مبتنی بر مدل آبشاری برای محاسبه‌ی حداکثر سازی نفوذ در شبکه‌های اجتماعی

* عسگرعلی بویر ** حمید احمدی بنی

* دانشیار، گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز

** کارشناسی ارشد، گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز

تاریخ دریافت:26/04/1398 تاریخ پذیرش: 18/02/1399

چكيده

در مسئله حداکثر سازی نفوذ، هدف یافتن حداقل تعدادی گره هست که بیشترین انتشار و نفوذ را در شبکه داشته باشند. مطالعات راجع به حداکثر سازی نفوذ و انتشار به‌صورت گستردهای در حال گسترش است. در سالهای اخیر الگوریتم‌های زیادی درزمینهٔ مسئله حداکثر سازی نفوذ در شبکههای اجتماعی ارائه‌شده است. این مطالعات شامل بازاریابی ویروسی، گسترش شایعات، اتخاذ نوآوری و شیوع بیماری‌های همهگیر و ... است. هر یک از مطالعات پیشین دارای کاستی‌هایی دریافتن گره‌های مناسب و یا پیچیدگی زمانی بالا هستند. در این مقاله، روشی جدید با عنوان ICIM-GREEDY برای حل مسئله حداکثر سازی نفوذ ارائه کردهایم. در الگوریتم ICIM-GREEDY دو معیار مهم که در کارهای انجام‌شده قبلی در نظر گرفته نشدهاند را در نظر میگیریم، یکی قدرت نفوذ و دیگری حساسیت به نفوذ. این دو معیار همیشه در زندگی اجتماعی انسان‌ها وجود دارد. روش پیشنهادی روی دیتاست‌های استاندارد مورد ارزیابی قرارگرفته‌شده است. نتایج به‌دست‌آمده نشان می‌دهد که روش مذکور نسبت به دیگر الگوریتم‌های مقایسه شده از کیفیت بهتری در پیدا کردن نودهای بانفوذ در 30 گره Seed برخوردار است. همچنین این روش از لحاظ زمانی نیز نسبت به الگوریتم‌های مقایسه شده به لحاظ همگرایی نسبتاً سریع، بهتر عمل می‌کند.

واژههای كليدي: مدل آبشاری مستقل، حداکثر سازی نفوذ، انتشار، شبکه اجتماعی

نویسندۀ عهدهدار مکاتبات: عسگرعلی بویر a.bouyer@azaruniv.ac.ir

1- مقدمه

مطالعه گسترش نفوذ در شبکههای اجتماعی و شبکههای پیچیده به‌صورت قابل‌توجهی افزایش پیداکرده است. حداکثر سازی نفوذ برای اولین بار توسط دومنیکس و ریچاردسون در سال 2001 مطرح شد [1].کمپ و همکارانش برای اولین بار به مسئله حداکثر سازی نفوذ پرداختند [2]. در شبکه‌های اجتماعی و البته مسئله حداکثر سازی نفوذ به دنبال نودهایی با ضریب نفوذ بالا هستیم که بیشترین تأثیر را بر روی شبکه داشته باشند. برای حداکثر سازی نفوذ دو مدل پایهای آبشاری مستقل و آستانهی خطی معرفی‌شده است. انتشار اطلاعات و نفوذ در زمان و مراحل گسسته انجام میشود. هر نود V در گراف G در دو حالت فعال یا غیرفعال است. در حالت فعال یک نود تحت نفوذ قرارگرفته است یعنی یک شایعه یا یک ایده یا یک محصول جدید را پذیرفته است. در حالت غیرفعال ایده یا محصول جدید را نپذیرفته است که ناشی از نپذیرفتن یا نرسیدن ایده یا محصول جدید یا یک شایعه باشد. برای درک بهتر مدلهای انتشار اغلب از مدلهای همارزی استفاده میشود. مدلهای تصادفی را همارز میگویند که دارای توزیع احتمال برای نودهای فعال‌شده توسط نودهای یکسان باشد. مدلهای LT وIC دلهای پایهای درحداکثرسازی نفوذ است [2]. هرچند در سالهای اخیر مدلهای دیگر نیز در این زمینه ارائه‌شده است، ولی پایه و اساس مدلهای ارائه‌شده، مدل LT و IC است [3-9].

مدل آبشاری مستقل برای اولین بار توسط کمپ و همکارانش مطرح شد [2]. در مدل آبشاری مستقل هرگاه نودی فعال میشود با احتمالی میتواند نودهای همسایه خود را فعال کند این احتمال برابر با وزن یال ارتباطی u و v یعنی ا . فعال‌سازی تنها یک‌بار صورت میگیرد به این معنی که اگر نود v ن انست نود u را فعال کند، دیگر شانسی برای فعال‌سازی نود u ن رد. در مدل آستانه خطی احتمال اثرگذاری نود v ب نود u با وزن بین یالها، که با نشان می‌دهیم، بیان میکنیم. هر نود v دارای یک حد آستانه است که به‌صورت تصادفی در بازه [0,1] به‌صورت تصادفی انتخاب میشود. حداکثر سازی نفوذ برای هر دو مدل آبشاری مستقل و حد آستانه خطی یک مسئله NP-hard است [10]. در مدل بشاری مستقل و آستانه خطی (LT) تابع خروجی (0)σ، خواص زیر بخشی و یکنوایی دارد که (0)σ تابع گسترش نفوذ است. الگوریتم حریصانه یک رویکرد طبیعی برای انتخاب مجموعهای از گره‌ها است که حداکثر نفوذ را داشته باشند. الگوریتم حریصانه می‌تواند ضریب تقریبی ارائه دهد که تعداد نودهای گراف است و عددی بسیار ناچیز است [2].

در این مقاله یک الگوریتم جدید به نام ICIM-GREEDY را ارائه میدهیم. در مقالات ارائه‌شده در سالهای اخیر دو نکته بسیار مهم را در نظر گرفته نشده است[11-17]، درصورتی‌که در دنیای واقعی این دو معیار وجود دارد. در دنیای واقعی نفوذ افراد با یکدیگر متفاوت است، افراد در جامعه با توجه به خصوصیات اجتماعی قدرت نفوذ متفاوتی دارند. در این مقاله نفوذ گرهها با توجه به دو معیار دنیای واقعی سنجیده میشود: قدرت نفوذ و حساسیت به نفوذ. قدرت نفوذ برای نودها متفاوت است به‌عنوان‌مثال فرض کنید یک دانشجو مسلماً دارای درجه بالایی است و استاد دانشگاه نسبت به دانشجو دارای درجه پایینتری به دلیل برقراری رابطه با افرادی خاص است. ولی نودهایی که با استاد دانشگاه در ارتباط هستند دارای قدرت نفوذ بیشتری هستند. فرض کنید هر دو نود استاد دانشگاه و دانشجو 50 نود را فعال میکنند ولی آیا قدرت نفوذ هر دو یکسان است، مسلماً اینطور نیست. حساسیت به نفوذ، در نودها میتواند متفاوت باشد که یک نود میتواند در مقابل نفوذ (اتخاذ محصول جدید یا ایده) مقابله کند یا به‌راحتی آن را بپذیرد. در این مقاله برای محاسبه قدرت نفوذ میتوانیم از دو فاکتور مهم نودهای حاشیه و نودهای هسته استفاده کنیم. به این صورت نودهایی که در هسته قرار دارند مسلماً قدرت نفوذ بیشتری دارند و نودهایی که در حاشیه قرار دارند قدرت نفوذ کمتری دارند.

ادامه مقاله به این صورت سازماندهی شده است. در بخش 2 یک دستهبندی کلی از الگوریتم‌های ارائه‌شده درزمینهٔ حداکثر سازی نفوذ موردبررسی و ارزیابی قرارگرفته است. در بخش 3 الگوریتم ICIM-GREEDY با استفاده از فاکتورهای جدید حساسیت به نفوذ و قدرت نفوذ ارائه‌شده است. تحلیل نتایج در بخش 4 صورت گرفته است و در بخش 5 به نتیجهگیری پرداختهایم.

2- کارهای انجام شده

حداکثر سازی نفوذ، به‌عنوان یک روش الگوریتمی برای بازاریابی ویروسی برای اولین بار توسط دومینگوس و ریچاردسون در سال 2001 پیشنهاد شده است [1]. کمپ و همکارانش در سال 2003 برای اولین بار به تدوین و فرموله سازی مسئلهی حداکثر سازی نفوذ به‌عنوان یک مسئله بهینهسازی تصادفی گسسته پرداختند [2]. مسئله حداکثر سازی نفوذ را میتوان طبق رابطهی (1) مطرح کرد که در یک گراف G=(V,E)، یک مدل تصادفی بر روی G، مجموعهی نودهای اولیه فعال را با نشان می‌دهد که هدف آن بیشینه‌سازی است که به‌صورت زیر محاسبه میشود:

وانگ و همکارانش در سال 2010 اثبات کردند که محاسبه گسترش نفوذ در یک گراف اجتماعی G=(V,E) با مجموعه S0، برای هر دو مدل LT و IC، NP-hard است [10]. مسئله حداکثر سازی نفوذ یک مسئله سخت است. روش اصلی توسط کمپ و همکارانش ارائه‌شده است که در این روش از فرایند شبیه‌سازی مونت‌کارلو در فرایند انتشار برای محاسبه گسترش نفوذ استفاده میشود [2]. مجموعه تأثیرگذار S برای R تکرار شبیهسازی میشود. بعد از پایان فرایند انتشار تعداد نودهای فعال شمرده میشود و سپس متوسط آن‌ها را در R تکرار محاسبه میشود. الگوریتم حریصانه با تعداد زیاد تکرار شبیه‌سازی مونت‌کارلو باعث دستیابی به بهترین نود نفوذپذیر در میان الگوریتم‌های مختلف شود. یک مشکل جدی برای الگوریتم حریصانه مونت‌کارلو MC-Greedy(G,K) ناکارآمدی وقتگیر بودن آن است. به همین دلیل لسکوک و همکارانش الگوریتم CELF را مطرح کردند که با استفاده از ارزیابی تنبل، محاسبات گسترش نفوذ را کاهش می‌دهد [18]. ولی همچنان الگوریتم‌های CELF به دلیل استفاده از شبیه‌سازی مونت‌کارلو در تعداد تکرار بالا، ناکارآمد بودند. بدین ترتیب چن و همکارانش الگوریتم NewGreedyIC را مطرح کردند که با استفاده از مجموعه نودهای قابل‌دسترس، گسترش نفوذ را برای هر نود محاسبه می‌کند. همچنین در ادامه، چن و همکاران برای بهبود زمان اجرای NewGreedyIC، الگوریتم DegreeDiscount را مطرح کردند که بعد از انتخاب نودی با بالاترین درجه به‌عنوان اولین نود Seed، برای انتخاب نودهای seed بعدی، درجه‌ی نودهایی که در همسایگی آن‌ها، seed وجود دارد، را کاهش می‌دهد [19]. این الگوریتم تقریب بهینه را برای مسئله حداکثر سازی نفوذ تضمین نمی‌کند ولی زمان اجرای بسیار مناسبی به نسبت الگوریتم‌های Greedy، CELF و NewGreedyIC دارد. سپس، نارایانام و همکارانش الگوریتم SPIN را ارائه دادند که با استفاده از مقدار شیپلی، گسترش نفوذ را برای هر نود محاسبه می‌کند [20]. این الگوریتم زمان اجرای مناسبی دارد ولی تقریب بهینه را در مقایسه با الگوریتم Greedy تضمین نمیکند. سپس، کیتساک و همکاران، الگوریتم K-core را مطرح کردند که نودهای هسته و حاشیه را در گراف مشخص می‌کند و نودهای هسته را به‌عنوان نود seed در نظر می‌گیرد [21]. در ادامه، چانگ و همکارانش الگوریتم StaticGreedyDU را برای بهبود زمان اجرای الگوریتم NewGreedyIC مطرح کردند [22]. اما الگوریتم StaticGreedyDU تقریب بهینه را تضمین نمی‌کند. در ادامه برای بالا بردن سرعت محاسبات گسترش نفوذ، گویال و همکارانش الگوریتم SIMPATH را مطرح کردند که با استفاده از محدود کردن شمارش مسیرهای ساده، نودهای seed را انتخاب می‌کند [23]. الگوریتم Simpath زمان اجرای مناسبی برای انتخاب k نود seed دارد و همچنین سربار حافظه مصرفی کمی دارد ولی ضریب تقریب بهینه را تضمین نمی‌کند به همین دلیل الگوریتم MIA توسط وانگ و همکارانش مطرح شد که الگوریتمی مقیاس‌پذیر است و با استفاده از درخت arborescence گسترش نفوذ به‌صورت محلی محاسبه می‌شود [10]. الگوریتم MIA به دلیل اینکه محاسبات گسترش نفوذ را بدون استفاده از شبیه‌سازی مونت‌کارلو انجام می‌دهد، زمان اجرای مناسبی دارد. ولی این الگوریتم سربار حافظه مصرفی بالایی دارد. سپس، چن و همکارانش الگوریتم CIM که مبتنی بر تشخیص جامعه می باشد را مطرح کردند که الگوریتم CIM ابتدا تشخیص جامعه انجام می‌شود و پس‌ازآن نودهای کاندید تولید می‌شوند و از نودهای کاندید نودهای seed انتخاب می‌شوند [24]. هرچند الگوریتم CIM زمان اجرای مناسبی دارد ولی تقریب بهینه را تضمین نمی‌کند. چن و همکارانش الگوریتم LUGreedy را مطرح کردند که در این الگوریتم با توجه به تصادفی بودن احتمال فعال‌سازی، عدم قطعیت را برای مسئله حداکثر سازی نفوذ در نظر می‌گیرد [25]. ژیانگ و همکارانش، الگوریتم VoteRank را که مبتنی بر رأی‌دهی را مطرح کردند [26]. این الگوریتم زمان اجرای مناسبی دارد. همچنین به دلیل اینکه این الگوریتم خاصیت سابماژولاریتی ندارد، تقریب بهینه را تضمین نمی‌کند. سپس، شانگ و همکارانش الگوریتم CoFIM را مطرح کردند که مبتنی بر تشخیص جامعه است [27]. زمان اجرای الگوریتم CoFIM به تعداد نودهای seed وابسته است. سپس، مورنه و همکاران، الگوریتم CI که مبتنی بر محلی سازی محاسبات گسترش نفوذ بود را مطرح کردند [28]. در این الگوریتم محاسبات گسترش نفوذ در دایره‌ای به شعاع L محدود می‌شود.زمان اجرای الگوریتم CI به L و تعداد نودهای seed، وابسته است. همچنین، لئو همکارانش الگوریتم LIR که مبتنی بر روش‌های اکتشافی بود را مطرح کردند [29]. در الگوریتم LIRمقدار LI برای هر نود بر اساس درجه همسایگان محاسبه می‌شود و سپس، مجموعه نودهای با کمترین مقدار LI بر اساس درجه به‌صورت نزولی مرتب می‌شوند و k نود به‌عنوان seed انتخاب می‌شوند. این الگوریتم، زمان اجرای مناسبی دارد ولی تقریب بهینه را تضمین نمی‌کند. سپس، اهجام و همکارانش الگوریتم HybridRank را مطرح کردند که نودهای تأثیرگذار بر اساس مرکزیت بردار ویژه و coreness انتخاب‌شده‌اند [30]. در این الگوریتم، در انتخاب نودهای تأثیرگذار از پدیده‌ی Rich club اجتناب می‌شود. اگرچه این الگوریتم از پدیدهی Rich club اجتناب می‌کند، اما نودهای تأثیرگذار گسترش نفوذ مناسبی ارائه نمی‌دهند. نگوين و همكارانش، الگوريتم probDeg را مطرح كردند كه نودهاي بانفوذ را با بررسي چند گام از نود و درجه همسايگان آن نود انتخاب ميكند [31]. سپس، وو و همکارانش، الگوریتم زمان خطی LAIM را مطرح کردند که این الگوریتم يك رويكرد تکراري خطي براي مسئله حداكثر تأثیرگذاری در شبکه‌های بزرگ است [32]. همچنین، این الگوریتم سربار حافظهی مصرفی پایینی، در شبکه‌های اجتماعی با مقیاس بزرگ دارد. سپس، بنرجی و همکارانش الگوریتم ComBIM را مطرح کردند که نودهای تأثیرگذار را با توجه به بودجه جامعه، انتخاب می‌کند [33]. همچنین، این الگوریتم تقریب بهینه را تضمین نمی‌کند. در ادامه، ژی و همکارانش، الگوریتم IRR را بر مدل MBIC مطرح کردند [34]. در این الگوریتم انتشار شامل دو مرحلهی شروع و مرجع است. این الگوریتم، گسترش نفوذ بهتری به نسبت الگوریتم DegreeDiscount دارد. روی و همکارانش، الگوریتم RNR را مطرح کردند [35]. این الگوریتم، با استفاده از تأثیر همسایگان، قدرت نفوذ نود را محاسبه می‌کند. در ادامه، کیو همکارانش، الگوریتم PHG را مطرح کردند که در این الگوریتم از رویکرد مبتنی بر تشخیص جامعه استفاده می‌کند. همچنین در این الگوریتم برای محاسبات گسترش نفوذ، از الگوریتم حریصانه ویژگی گراف استفاده می‌کند [36]. همچنین در این الگوریتم، میزان گسترش نفوذ و زمان اجرا، به تعداد نودهای تأثیرگذار که توسط الگوریتم حریصانه انتخاب می‌شوند، وابسته است. پس‌ازآن، احمدی بنی و همکارانش، الگوریتم TI-SC را مطرح کردند که در این الگوریتم با استفاده از نودهای هسته در جوامع الگوریتم PHG را بهبود می‌بخشد [11].

3- روش پیشنهادی

در این مقاله الگوریتم جدیدی با نام ICIM-GREEDY ارائه‌شده است. در الگوریتم ICIM-GREEDY از مدل WC بهبودیافته استفاده‌ شده است. در این الگوریتم ابتدا وزن نفوذ را محاسبه میشود و سپس محاسبات نفوذپذیری را بر اساس دو فاکتور مهم، قدرت نفوذ و حساسیت به نفوذ انجام می‌شود.

1-3- وزن نفوذ

وزن نفوذ، یک فاکتور مهم برای تشخیص نفوذ است، به همین دلیل از یک روش جدید برای محاسبه وزن نفوذ استفاده‌شده است. در مدل WC، وزن نفوذ، محاسبه میشود. اما این یک روش منطقی برای تعیین وزن نفوذ نیست به دلیل اینکه نودها دارای ویژگیهای متفاوتی مثل ضریب خوشهبندی متفاوت، درجه همسایه‌های یک نود، پل محلی بودن یا در مجاورت پل محلی بودن و .. هستند، پس باید بین وزنهای نفوذ در بین نودهای مختلف، تفاوت قائل شویم. بنابراین وزن نفوذ طبق فرمول زیر محاسبه میشود:

(1)

درجه نود u است و درجه نودهای همسایه نود u است و ضریب خوشهبندی نود u است. وزن نفوذ، به این صورت تعیین میشود هر چه درجه همسایگان و درجه همسایگان همسایگان نود v بیشتر باشد، نودهای همسایه v میتوانند نفوذ بیشتری بر روی v داشته باشند و همچنین هرچه همسایههای نود v دارای ضریب خوشه‌بندی کمتر باشند، تمایل بیشتری به برقراری ارتباط دارند. پس مجموع وزن نفوذ که یک گره u میتواند به همسایگان غیرفعال اعمال کند با استفاده از فرمول زیر محاسبه‌شده است:

(2)

مجموعهای از نودهای فعال در میان همسایگان u است. در دنیای واقعی انتشار و نفوذ تحت تأثیر تمامی همسایگان نود است و در صورتی نودی می‌تواند فعال شود که همسایگان فعال نود بتواند نود موردنظر را تحت تأثیر قرار دهند. به همین دلیل معیار به‌صورت مجموع نفوذ همسایگان محاسبه میشود. بنابراین طبق رابطهی زیر احتمال نفوذ به‌صورت زیر محاسبه میشود:

(3)

2-3- حساسیت به نفوذ

علاوه بر قدرت نفوذ، معیار حساسیت به نفوذ برای محاسبه نفوذ در نظر گرفته‌شده است. حساسیت به نفوذ مسئله‌ای بسیار مهم در حداکثر سازی نفوذ است زیرا در دنیای واقعی حساسیت به نفوذ متفاوت است ولی در تمامی کارهای قبلی حساسیت به نفوذ به‌صورت تصادفی تعیین‌شده است . برای نشان دادن اهمیت این موضوع، نگاهی به شکل 1 داشته باشیم. همان‌طور که در این شکل می‌بینید، درجه نود 1و نود 5، برابر است ولی اهمیت نود 1 بیشتر از نود 5 است زیرا گرههای مهم‌تری به نود 1 متصل هستند. ممکن است بر اساس آستانهی نفوذ تصادفی، نود 5 فعال شود که میتواند نودهای کمتری را در ادامه فعال کند درصورتی‌که با فعال شدن نود 1 ممکن است نودهای بیشتری را نسبت به نود 5 فعال کند. در کارهای قبلی آستانهی نفوذ به‌صورت تصادفی تعیین میشود، ولی در این الگوریتم آستانه نفوذ، بر اساس اهمیت نفوذ نود و نودهای پل/پل محلی، تعداد نودهای فعال‌شده، طول مسیر از مبدأ و همسایگان فعال نشده تعیین میشود.

(4)

$C:\Users\pc\Pictures\Screenshots\Screenshot (272).png$

شکل 1 - گره‌های 1و 2 درجه یکسانی دارند ولی گره 1 دارای اهمیت نفوذ بیشتری است.

اساس این ایده، آزمایش میلگرم است آزمایشی برای سنجش میزان فرمانبداری افراد از اقتدار ¹ در انجام کارهایی مغایر با وجدان شخصی افراد بود که به ابتکار روانشناس معروف استنلی میلگرام صورت گرفت[37]. آزمایش‌هایی که توسط میلگرام صورت گرفت نشان داد که حضور افراد دیگری که از فرمان‌ها پیروی نمی‌کردند، میزان فرمان‌برداری شرکت‌کننده را به نحو زیادی کاهش می‌دهد. وقتی کسانی دیگری در کنار شرکت‌کننده حضور داشتند که از اجرای فرمان‌ها سرباز می‌زدند، 36 نفر از 40 شرکت‌کننده از دادن ماکزیمم شوک خودداری کردند[37]. بر همین اساس، هرچه تعداد نودهای فعال‌شده با ایده یا محصول جدید، بیشتر باشند حساسیت به نفوذ در نود کمتر میشود و این باعث میشود ایده یا محصول جدید به‌راحتی پذیرفته شود.

برای محاسبه حساسیت به نفوذ فاکتورهای زیر بسیار مهم می‌باشند:

· تعداد نودهای فعال‌شده از همسایگان نود: هرچقدر تعداد نودهای فعال‌شده بیشتر باشند حساسیت به نفوذ پایینتر است.

· فاصله از نود مبدأ: هرچقدر فاصله نود از منبع شایعه دورتر باشد، حساسیت به نفوذ آن بیشتر میشود.(فاصله از نود تأثیرگذار)

· تعداد نودهای همسایگان فعال نشده از همسایگان نود: هرچقدر تعداد نودهای فعال نشده به نسبت تعداد نودهای فعال‌شده کمتر باشد، حساسیت به نفوذ نود کمتر میشود.

· تعداد نودهای فعال همسایهی یک نود فعال: این فاکتور برای بیان اهمیت نودهای پل/پل محلی، مطرح‌شده است. زیرا این گره‌ها، نقش مهمی در فرایند انتشار اطلاعات دارند. هرچقدر تعداد نودهای فعال همسایهی یک نود فعال، بیشتر باشد حساسیت به نفوذ پایینتر است.

بنابراین برای محاسبه وزن نفوذ از رابطهی زیر استفاده میکنیم:

در رابطه 5، تعداد نودهای همسایگان فعال نشده نود است. تعداد نودهای فعال‌شده از همسایگان نود است. تعداد نودهای فعال همسایهی نودهای فعال، است. درجه نودهای همسایگان نود، که فعال نشدهاند، است. درواقع در این فرمول، اهمیت نودهای پل/پل محلی به نحو مناسبی در نظر گرفته ‌شده است.

3-3- قدرت نفوذ

در رویکرد پیشنهادی، برای اینکه بین نفوذ نودهای مختلف تفاوتی وجود داشته باشد از مفهوم جدید توپولوژی شبکه که بر اساس تجزیه k-shell انجام خواهد شد، استفاده‌شده است. انتشار اطلاعات و الگوی رفتاری، وابسته به ساختار و توپولوژی شبکه است. به‌عنوان‌مثال، اگر یک hub در انتهای شبکه وجود داشته باشد، آن ممکن است حداقل گسترش را داشته باشد، درحالی‌که یک نود با کمترین اتصال در هسته شبکه، ممکن است گسترش قابل‌توجهی داشته باشد. در توپولوژی شبکه، موقعیت یک نود با استفاده از تجزیه K-Shell تعریف میشود. در k-shell ابتدا همهی نودها با درجه k=1 حذف میشود، پس از هرس مرحله اول ممکن است گرههایی جدید با k=1 ظاهر شود. دوباره تمامی نودهای با درجه K=1 حذف میشوند. برای نودهای با درجههای متفاوت این روش ادامه مییابد. بنابراین نودهایی با درجه پایین در حاشیه و نودهایی با درجه بالا، در هسته قرار میگیرند. همان‌طور که در شکل 2 قابل مشاهده است نود 8 و 9 درجهشان 8 است ولی نود9 به دلیل اینکه در هسته قرار دارد، گسترش نفوذ بهتری نسبت به نود 8 دارد. با توجه به نتایج آزمایش‌ها، زمانی که یک نود اولیه را به‌صورت تصادفی فعال میشود، نودهایی که در لایههایی با بالاتر قرار دارند، احتمال بیشتری دارند که فعال شوند. البته زمانی موقعیت نود مهم است که به‌عنوان یک نود منبع در نظر گرفته شود. بنابراین، نودهایی که در هستههای داخلی ( بزرگ‌تری دارند) قرار دارند، نفوذ بیشتری دارند.

به دلیل موارد فوق، دو فاکتور k و برای محاسبه قدرت نفوذ در نظر گرفته‌شده است. برای هر مجموعه از نودهای تأثیرگذارS، است. برای محاسبه قدرت نفوذ زمانی که از فرمول زیر استفاده میشود:

(5)

در این رابطه، Count تعداد نودهای فعال‌شده است. تعداد نودها در هر است. علاوه بر این، در ابتدای کار نفوذ همه نودها برابر با1 در نظر گرفته‌شده است، به این معنی که اگر آن گره فعال شود، حداقل خودش را فعال کرده و یک گره فعال را نتیجه می‌دهد. مقادیر PID در یک بردار ذخیره میشود که قدرت نفوذ را برای هر نود مشخص می‌کند.

البته برای محاسبه قدرت نفوذ میتوان مشخصههای رفتاری و یا غیر ساختاری مانند سن، جنسیت و زمان تبلیغات و غیره نیز در نظر گرفت. ولی در نظر گرفتن این مشخصهها در شبکه اجتماعی کمی مشکل است زیرا در اکثر مواقع به دلایلی مانند حفظ حریم خصوصی این مشخصهها قابل‌دسترس نیستند.

[1] authority

$C:\Users\pc\Pictures\Screenshots\Screenshot (271).png$ $C:\Users\pc\Pictures\Screenshots\Screenshot (270).png$

شکل 2- مثالی از روش k-Shell. گره 8 و 9 هر دو درجهشان 8 است ولی گره 9 به دلیل اینکه در هسته قرار دارد، میتواند گسترش نفوذ بیشتری داشته باشد.

(6)

Algorithm 1:ICIM-GREEDY: Improved Cascade model for Influence Maximization.

Input: G: Social graph, k: size seed set, R=1

1:for j=0 to R do

2: if

3: for 1 to H do

6: if() then

7: number of active node

8: countcount+

9: end if

10: end for

11: end if

12:end for

13: return

3-4- الگوریتم حریصانه

ما میتوانیم به‌سادگی برای انتخاب مجموعه تأثیرگذار با اندازه k، الگوریتم 2 را k بار فراخوانی کنیم. به دلیل اینکه الگوریتم حریصانه عمومی بسیار وقتگیر است، از الگوریتم NewGreedyWC استفاده‌شده است. در الگوریتم ICIM-GREEDY وزن نفوذ و حد آستانه به‌صورت تصادفی انتخاب نمیشوند به همین دلیل از شبیهسازی مونتکارلو استفاده نمی‌شود (به‌عبارتی‌دیگر R=1 است). به همین دلیل الگوریتم NewGreedyWC نسبت به الگوریتم حریصانه عمومی از لحاظ زمان اجرا بهتر میشود. در این الگوریتم باید توجه شود، نودهایی که گسترش نفوذ مناسبی ندارند، باعث ایجاد سربار محاسباتی می‌شوند. به همین دلیل برای کاهش سربار محاسباتی گسترش نفوذ باید نودهایی که گسترش نفوذ مناسبی ندارند در محاسبات گسترش نفوذ نادیده گرفته شوند. بدین ترتیب، برای محاسبات گسترش نفوذ، نود با بالاترین درجه در نظر گرفته می‌شوند که تعداد یال‌های گراف و تعداد نودهای گراف است. در مدل WC گراف جهتدار در نظر گرفته میشود. اگر درجه v در گراف G و یال در گراف باشد. در این مدل، اگر نود فعال‌شده باشد، آنگاه نود با احتمال در گام ام، فعال میشود [19]. در خط 2 از الگوریتم 2 ابتدا الگوریتم ICIM-GREEDY فراخوانی میشود. در خط 4 -5 الگوریتم به این صورت است که برای هر یال ، با احتمال از G پاک میشود. RanWC(G) نشاندهنده این فرایند است و نتایج را بر روی گراف جهت‌دار نشان می‌دهد. در خط 6-11 در الگوریتم 2 از الگوریتم کوهن برای تخمین تعداد نودهای قابل‌دسترس از هر نود استفاده‌شده است که در اولین گام در گراف تمام کامپونتهای قویاً متصل را محاسبه‌شده است. گراف جهتدار غیر مدور(DAG) است و نشاندهنده مجموعه نودهای است.

الگوریتم 1 تنها یکبار اجرا میشود تا بردار PID را مشخص کند. بردار PID قدرت نفوذ را برای هر نود ارائه می‌دهد. بردار PID به‌عنوان ورودی برای الگوریتم NewGreedyWC است. بنابراین پیچیدگی کلی الگوریتمNewGreedyWC برابر است با O(kTn) بطوری‌که k تعداد نودهای seed است و m تعداد یالها است. در واقع T=5 است زیرا برآورد خوبی از گسترش نفوذ را می‌دهد.

برای محاسبه بردار PID نیاز به محاسبه و است که این دو مقدار با استفاده از الگوریتم K-Shell محاسبه میشود [38]. پیچیدگی زمانی K-shell، O(m) است [38]. به دلیل اینکه به‌صورت پویا تعداد نودهای همسایهی فعال، تعداد نودهای همسایهی غیرفعال و تعداد نودهای همسایگان همسایگان نود فعال محاسبه میشود، پیچیدگی محاسبات است که n تعداد نودها است. پیچیدگی الگوریتم1، O(2m+2n)=O(m+n) میشود. مرتبه زمانی کلی الگوریتم به‌صورت O(kTn+2m+2n) است که همان‌طور که در بالا اشاره شد T=5 است پس پیچیدگی زمانی کلی به‌صورت O(kn+2m+2n)=O(kn+m) میشود.

Algorithm 2 NewGreedyWC

Input: G: Social graph, k: size seed set

Output: selected seed set

1: initialize

2: call algorithm ICIM-GREEDY

3: for i= 1 to k do

4: set for all vertices.

5: obtain

6: compute DAG and weights for all

7: for to T do

8: for each , generate random value from

The exponential distribution with mean

9: for each , compute =

10: for each

11: end for

12: for each

13: end for

15:

16: end for

17: output S

4- آزمایش‌ها و ارزیابی

ما ابتدا الگوریتم ICIM-Greedy را بر روی 8 مجموعه داده (دیتاست) مورد ارزیابی قرار می‌دهیم. دیتاستها بدون جهت می‌باشند. اندازهی دیتاستها بزرگ و متوسط می‌باشند. هر 8 دیتاست از سایت KONECT دانلود شدهاند.

NetHEPT: این شبکه از بخش "High Energy Physics-Theory" است که مقالات مربوط سال 1991 تا 2003 است هر نود در شبکه یک نویسنده را ارائه می‌دهد و یالهای بین دو نود برابر با همکاری دو نویسنده در یک مقاله است [19]. این شبکه شامل 15k نود و 58k یال است.

Physics: این شبکه شامل تمامی مقالات بخش "Physics" است. در شبکه Physics نیز هر نود در شبکه یک نویسنده را ارائه می‌دهد و یالهای بین دو نود برابر با همکاری دو نویسنده در یک مقاله است [19]. این شبکه شامل 15k نود و 231k یال است.

Email: دیتاست Email شبکه‌ای از ایمیل در دانشگاه Rovira i Virgili است که اگر افراد به یکدیگر ایمیلی ارسال کرده باشند، یال بدون جهت بین ایمیلها تشکیل میشود [39]. شبکه شامل 1k نود و 5k یال است.

Netscience : این یک شبکه از همکاریهای نویسندگان در حوزه علوم شبکه است[39]. این شبکه شامل 1k نود و 2k یال است.

M-Fo115: شبکه M-Fo115 از مدل جنگل آتش با احتمال اتصال p = 0.115 تولیدشده است که شامل 10k نود و 23k یال است [40].

M-Fo120: با استفاده از مدل جنگل آتش، شبکه M-Fo120 با احتمال p=0.120 که شامل 10k نود و 29k ساخته می‌شود[40].

M-Fo-0.1: شبکه M-Fo-0.1 از مدل جنگل آتش با احتمال اتصال p = 0.1 تولیدشده است که شامل 5k نود و 7k یال است [40].

M-Fo-0.2: با استفاده از مدل جنگل آتش، شبکه M-Fo-0.2با احتمال p=0.120 که شامل 5k نود و 23k ساخته می‌شود [40].

جدول 1- مشخصات دیتاستهای موردنظر برای آزمایش

NetScience	Email	M-Fo-0.2	M-Fo-0.1	M-Fo120	M-Fo115	Physics	NetHEPT	Data set
1k	1k	5k	5k	10k	10k	6k	317k	Node
2k	5k	23k	7k	29k	23k	13k	1M	Edge
43	209	336	20	229	155	1459	343	Max Degree
1	1	1	1	1	1	1	1	Min Degree

4-1- پارامترهای مورداستفاده در آزمایش:

الف: تولید احتمال انتشار. به‌صورت کلی بر روی الگوریتم‌های مقایسه شده توزیع احتمال انتشار به‌صورت توزیع یکنواخت است، که از مدل زیر برای تولید این احتمال یکنواخت استفاده میکنیم:

ب: استفاده از مدلWC. مدل آبشاری وزندار توسط کمپ و همکارانش در سال 2003 پیشنهادشده است [19].احتمال بر روی یالها به‌صورت است که درجه نود v است. گراف انتشار بر روی این مدل به‌صورت جهتدار است به دلیل اینکه احتمال انتشار از یال (u,v) به یال (v,u) متفاوت است و تعداد تکرار شبیه‌سازی مونت‌کارلو 20000 تکرار است.

4-2- الگوریتم‌های مورد مقایسه

الگوریتم ICIM-GREEDY را با دو نوع از الگوریتم‌های حریصانه و هیوریستیک مقایسه کردیم. لیستی از الگوریتم‌های مقایسه شده را در زیر ارائه دادهایم:

· ICIM-GREEDY: الگوریتم 1

· Greedy: الگوریتم حریصانه معمولی که از شبیهسازی مونتکارلو استفاده می‌کند [19].

· MixedGreedy: ترکیبی از الگوریتم حریصانه که در دور اول از NewGreedy و در دور دوم از CELF استفاده می‌کند، که R=20000 وT=5 است[19].

· Degree: الگوریتم اکتشافی که k نود با بالاترین درجه را انتخاب می‌کند [19].

· SingleDiscount: الگوریتم اکتشافی ساده است وقتی‌که هر یک از همسایههای که به‌عنوان تأثیرگذار انتخاب میشوند درجه کاهش آن یک است [19].

· Distance: یک الگوریتم اکتشافی ساده است که k نود با کوچک‌ترین میانگین فاصله را انتخاب می‌کند [5].

· Random: الگوریتمی است که k نود را به‌صورت تصادفی انتخاب می‌کند [5].

· LIR: الگوریتمی که با استفاده از توپولوژی شبکه k نود را انتخاب می‌کند [29].

· ProbDeg: الگوریتمی که با تأثیر درجه همسایگان، k نود را انتخاب می‌کند [31].

· TI-SC: الگوریتمی که با استفاده از تشخیص جامعه، k نود را انتخاب می‌کند [11].

4-3- فرایند آزمایش

در این مقاله ، آزمایش شبیه‌سازی توسط پایتون را بر روی سروری با پردازندهی Intel Xeon E5410 و 32 گیگابایت حافظه انجام‌شده است که شش مجموعه داده شبکه اجتماعی و ده الگوریتم مقایسه اتخاذشده است.

4-4 نتایج

برای این الگوریتمها گسترش نفوذ را برای مجموعه تأثیرگذار در محدودهی 1تا 30 مقایسه میکنیم. همچنین زمان اجرا را برای k=30 مقایسه میکنیم.

گسترش نفوذ و زمان اجرا. نتایج گسترش نفوذ بر 8 دیتاست بررسی‌شده است. اندازهی مجموعه تأثیرگذار رنجی بین 1 تا 30 است. شکل‌های 3 تا 10 نتایج گسترش نفوذ را بر 8 دیتاست با مدل WC را نشان می‌دهد و شکل 4 زمان اجرای الگوریتم‌های متفاوت را نشان می‌دهد. . در این آزمایش، هدف اصلی مقایسه الگوریتم‌های حریصانه با روش پیشنهادی ICIM-GREEDY می باشد زیرا روش‌هایی مانند Random و Degree به خاطر ضعف بارز در گسترش نفوذ به دلیل عدم انتخاب آگاهانه، الگوریتم‌های خوبی نیستند. بر روی دیتاست NetHEPT (شکل 3) الگوریتم ICIM-GREEDY گسترش نفوذ بهتر و چشمگیرتری نسبت به بقیهی الگوریتمها دارد و Random بدترین گسترش نفوذ را دارد. در دیتاست Physics (شکل 4) الگوریتم‌های Greedy و MixedGreedy و ICIM-GREEDY گسترش نفوذ بهتری نسبت به بقیه دارند که هر سه ازنظر گسترش نفوذ تقریباً یکسان و بعضاً با اختلاف بسیار ناچیز ظاهرشده‌اند. در دیتاست Physics، روش Random بدترین گسترش نفوذ را دارد. همچنین، شکلهای 5 تا 10 نیز نشان می دهد که روش پیشنهادی بر روی مابقی دیتاست‌ها از نظر گسترش نفوذ، نتایج بهتری نسبت به الگوریتم‌های دیگر دارد.

$D:\My Article\NMI\code\hep_INF.png$

شکل 3- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی NetHEPT

$D:\My Article\NMI\code\phy_INF.png$

شکل 4- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی Physics

$D:\My Article\NMI\code\p115_INF.png$

شکل 5- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی M-Fo115

$D:\My Article\NMI\code\p120_INF.png$

شکل 6- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی M-Fo120

$D:\My Article\NMI\code\Email_INF.png$

شکل 7- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی Email

$D:\My Article\NMI\code\NetScience_INF.png$

شکل 8- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی NetScience

شکل 9- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی M-Fo-0.1

شکل 10- گسترش نفوذ بر روی الگوریتم‌های متفاوت بر روی M-Fo-0.2

در شکل 7 گسترش نفوذ بر دیتاست Email مورد بررسی قرارگرفته است که الگوریتم‌های ICIM-GREEDY و Greedy گسترش نفوذ تقریباً نزدیکی دارند و به نسبت دیگر الگوریتم‌ها گسترش نفوذ بهتری ارائه می‌دهند. البته الگوریتم ICIM-GREEDY با اختلاف بسیار کم گسترش نفوذ بهتری از الگوریتم Greedy ارائه می‌دهد. در شکل 8، گسترش نفوذ بر دیتاست NetScience مورد بررسی قرارگرفته است که الگوریتم ICIM-GREEDY گسترش نفوذ بهتری ارائه می‌دهد. در این دیتاست الگوریتم Greedy گسترش نفوذ تقریباً نزدیکی به الگوریتم ICIM-GREEDY ارائه می‌دهد ولی گسترش نفوذ در الگوریتم ICIM-GREEDY بیشتر از الگوریتم Greedy است. به‌ عنوان‌مثال در الگوریتم ICIM-Greedy گسترش نفوذ در k=25 و k= 30 نسبت به الگوریتم Greedy بهتر است. در شکل 9 و 10 گسترش نفوذ بر دیتاستهای M-Fo-0.1 و M-Fo-0.2 مورد بررسی قرارگرفته است که الگوریتم‌های ICIM-GREEDY و Greedy گسترش نفوذ تقریباً نزدیکی دارند و به نسبت دیگر الگوریتم‌ها گسترش نفوذ بهتری ارائه می‌دهند.

در شکل‌های 11 تا 18، الگوریتمها از نظر زمان اجرا روی دیتاستهای مذکور مورد آزمایش قرارگرفته‌اند. همان‌طور که در این شکل‌ها قابل‌مشاهده است، الگوریتم پیشنهادی نسبت به الگوریتم‌های حریصانه مورد مقایسه زمان اجرای کمتری دارد. البته الگوریتم‌های Random و Degree دارای کمترین مرتبهی زمانی هستند ولی این الگوریتمها دارای دقت بسیار پایینی در محاسبه گسترش نفوذ دارند.

$D:\My Article\NMI\code\Runtime_hep.png$

شکل 11- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاست NetHEPT

$D:\My Article\NMI\code\Runtime_hep.png$

شکل 12- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاست Physics

$D:\My Article\NMI\code\Runtime_p115.png$

شکل 13- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاستM-FO115

$D:\My Article\NMI\code\Runtime_p120.png$

شکل 14- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاستM-FO120

$D:\My Article\NMI\code\Runtime_email.png$

شکل 15- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاستEmail

$D:\My Article\NMI\code\Runtime_email.png$

شکل 16- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاستNetscience

شکل 17- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاست M-Fo-0.1

شکل 18- زمان اجرای الگوریتم‌های متفاوت بر روی دیتاست M-Fo-0.2

در این آزمایش، هدف اصلی مقایسه الگوریتم‌های حریصانه با ICIM-GREEDY است زیرا روش‌هایی مثل روش Random و Degree به خاطر ضعف بارز در گسترش نفوذ به دلیل عدم انتخاب آگاهانه، الگوریتم‌های خوبی نیستند و در این حوزه هم چندان موردتوجه نیستند.

5- نتیجهگیری

در این مقاله بر اساس معیارهای جدید حساسیت به نفوذ و قدرت نفوذ یک الگوریتم بهینه برای مسئله حداکثر سازی نفوذ ارائه‌شده است.در الگوریتم ICIM-GREEDY از معیارهای که در دنیای واقعی وجود دارد، برای محاسبه حساسیت به نفوذ و قدرت نفوذ استفاده‌شده است. الگوریتم‌های حریصانه برای دقت بیشتر نیاز به تکرار بیشتر توسط شبیهسازی مونتکارلو دارند درصورتی‌که الگوریتم ICIM-GREEDY تنها با یکبار اجرا دارای دقت بالایی در گسترش نفوذ است به همین دلیل در این الگوریتم زمان اجرا نسبت به الگوریتم حریصانه کاهش داده‌شده است و دقت انتخاب مجموعه نودهای تأثیرگذار بر اساس گسترش نفوذ افزایش داده‌شده است. زمانی که زمان اجرا اهمیت دارد الگوریتم‌های SingleDiscount پیشنهاد میشود و زمانی که دقت اجرا اهمیت دارد الگوریتم‌های ICIM-GREEDY، MixedGreedy و TI-SC پیشنهاد
میشود.

منابع

1. 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.

رایمگ

سامانه رایمگ تمامی فرآیندهای دریافت، ارزیابی و داوری، ویراستاری، صفحه‌آرایی و انتشار الکترونیکی نشریات علمی را به انجام می‌رساند

اشتراک گذاری

آدرس مقاله

یک روش جدید حریصانه مبتنی بر مدل آبشاری برای محاسبه‌ی حداکثر سازی نفوذ در شبکه‌های اجتماعی

رایمگ

پیوندهای سایت

مراکز مرتبط

پشتیبانی

صفحات رسمی