یک روش جدید حریصانه مبتنی بر مدل آبشاری برای محاسبهی حداکثر سازی نفوذ در شبکههای اجتماعی
محورهای موضوعی : عمومىعسگرعلی بویر 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.
عسگرعلی بویر و... فصلنامه فناوری اطلاعات و ارتباطات ایران، سال دهم، شمارههای 37و38، پاییز و زمستان 1397
فصلنامة علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال دهم، شمارههاي 37 و 38، پاییز و زمستان 1397 صص: 85- 100 |
|
|
یک روش جدید حریصانه مبتنی بر مدل آبشاری برای محاسبهی حداکثر سازی نفوذ در شبکههای اجتماعی
* عسگرعلی بویر ** حمید احمدی بنی
* دانشیار، گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز
** کارشناسی ارشد، گروه مهندسی کامپیوتر، دانشكده فناوری اطلاعات و مهندسي كامپيوتر، دانشگاه شهید مدنی آذربایجان، تبریز
تاریخ دریافت:26/04/1398 تاریخ پذیرش: 18/02/1399
چكيده
در مسئله حداکثر سازی نفوذ، هدف یافتن حداقل تعدادی گره هست که بیشترین انتشار و نفوذ را در شبکه داشته باشند. مطالعات راجع به حداکثر سازی نفوذ و انتشار بهصورت گستردهای در حال گسترش است. در سالهای اخیر الگوریتمهای زیادی درزمینهٔ مسئله حداکثر سازی نفوذ در شبکههای اجتماعی ارائهشده است. این مطالعات شامل بازاریابی ویروسی، گسترش شایعات، اتخاذ نوآوری و شیوع بیماریهای همهگیر و ... است. هر یک از مطالعات پیشین دارای کاستیهایی دریافتن گرههای مناسب و یا پیچیدگی زمانی بالا هستند. در این مقاله، روشی جدید با عنوان ICIM-GREEDY برای حل مسئله حداکثر سازی نفوذ ارائه کردهایم. در الگوریتم ICIM-GREEDY دو معیار مهم که در کارهای انجامشده قبلی در نظر گرفته نشدهاند را در نظر میگیریم، یکی قدرت نفوذ و دیگری حساسیت به نفوذ. این دو معیار همیشه در زندگی اجتماعی انسانها وجود دارد. روش پیشنهادی روی دیتاستهای استاندارد مورد ارزیابی قرارگرفتهشده است. نتایج بهدستآمده نشان میدهد که روش مذکور نسبت به دیگر الگوریتمهای مقایسه شده از کیفیت بهتری در پیدا کردن نودهای بانفوذ در 30 گره Seed برخوردار است. همچنین این روش از لحاظ زمانی نیز نسبت به الگوریتمهای مقایسه شده به لحاظ همگرایی نسبتاً سریع، بهتر عمل میکند.
واژههای كليدي: مدل آبشاری مستقل، حداکثر سازی نفوذ، انتشار، شبکه اجتماعی
نویسندۀ عهدهدار مکاتبات: عسگرعلی بویر a.bouyer@azaruniv.ac.ir |
مطالعه گسترش نفوذ در شبکههای اجتماعی و شبکههای پیچیده بهصورت قابلتوجهی افزایش پیداکرده است. حداکثر سازی نفوذ برای اولین بار توسط دومنیکس و ریچاردسون در سال 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) |
شکل 1 - گرههای 1و 2 درجه یکسانی دارند ولی گره 1 دارای اهمیت نفوذ بیشتری است.
اساس این ایده، آزمایش میلگرم است آزمایشی برای سنجش میزان فرمانبداری افراد از اقتدار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
شکل 2- مثالی از روش k-Shell. گره 8 و 9 هر دو درجهشان 8 است ولی گره 9 به دلیل اینکه در هسته قرار دارد، میتواند گسترش نفوذ بیشتری داشته باشد.
| (6) |
Algorithm 1:ICIM-GREEDY | ||||||||||||||||||||||||||||||||||||||||||||||||||||
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 4: 5: 6: if( 7: 8: count 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 نسبت به الگوریتم حریصانه عمومی از لحاظ زمان اجرا بهتر میشود. در این الگوریتم باید توجه شود، نودهایی که گسترش نفوذ مناسبی ندارند، باعث ایجاد سربار محاسباتی میشوند. به همین دلیل برای کاهش سربار محاسباتی گسترش نفوذ باید نودهایی که گسترش نفوذ مناسبی ندارند در محاسبات گسترش نفوذ نادیده گرفته شوند. بدین ترتیب، برای محاسبات گسترش نفوذ، الگوریتم 1 تنها یکبار اجرا میشود تا بردار PID را مشخص کند. بردار PID قدرت نفوذ را برای هر نود ارائه میدهد. بردار PID بهعنوان ورودی برای الگوریتم NewGreedyWC است. بنابراین پیچیدگی کلی الگوریتمNewGreedyWC برابر است با O(kTn) بطوریکه k تعداد نودهای seed است و m تعداد یالها است. در واقع T=5 است زیرا برآورد خوبی از گسترش نفوذ را میدهد. برای محاسبه بردار PID نیاز به محاسبه
|