Combined Estimating Influence Probabilities for an Influence Maximization Problem in Social Networks and Its Application in the Power Industry

Subject Areas : Computer Engineering and IT

Sohameh Mohammadi ¹ , .Mohammad H Nadimi-Shahraki ² , Zahra Beheshti ³ , kamran zamanifar ⁴

1 - Department of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran
2 - Islamic Azad University of Najafabad & Torrens University Australia
3 - دانشکده مهندسی کامپیوتر- واحد نجف آباد، دانشگاه آزاد اسلامی، نجف آباد، ایران
4 - Kamran Zamanifar Department of Computer Engineering,University of Isfahan Isfahan, Iran

Received: 2023-10-09 Accepted : 2023-12-01 Published : 2023-12-19

Keywords: Social networks, influence maximization, information diffusion modeling, influence Probabilities,

Abstract :

Nowadays, online social networks have an inseparable connection with the daily life of many people in the world. The applications of social networks are increasing in businesses for advertising, marketing, and recommender systems, as well as in resource and energy consumption management systems. One of the most important problems in the information diffusion process of social networks is the influence maximization. In recent years, some research has been conducted to improve the prediction quality of information diffusion models in this problem. In a review of existing models, the influence probabilities among users are estimated unrealistically. In this research, a new method has been proposed to determine the influence probabilities among social network users. This method is a combination of two main approaches in the calculation of influence probabilities, including the use of an action log table and the uniform method with a predetermined value. The performance of the proposed method was evaluated and compared with competitive methods on different real-world social network data sets. The results of the experiments show that the proposed method can increase the efficiency of the predictions in solving the influence maximization problems.

References:

[1] C. Aslay, L. V. Lakshmanan, W. Lu, and X. Xiao, "Influence maximization in online social networks," in Proceedings of the eleventh ACM international conference on web search and data mining, 2018, pp. 775-776.
[2] Y. Li, W. Chen, Y. Wang, and Z.-L. Zhang, "Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships," in Proceedings of the sixth ACM international conference on Web search and data mining, 2013, pp. 657-666.
[3] N. Girdhar and K. Bharadwaj, "Signed social networks: a survey," in International Conference on Advances in Computing and Data Sciences, 2016, pp. 326-335: Springer.
[4] M. Kaya, J. Kawash, S. Khoury, and M.-Y. Day, Social network based big data analysis and applications. Springer, 2018.
[5] S. Peng, S. Yu, and P. Mueller, "Social networking big data: Opportunities, solutions, and challenges," vol. 86, ed: Elsevier, 2018, pp. 1456-1458.
[6] M. Richardson and P. Domingos, "Mining knowledge-sharing sites for viral marketing," in Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, 2002, pp. 61-70.
[7] E. Even-Dar and A. Shapira, "A note on maximizing the spread of influence in social networks," Information Processing Letters, vol. 111, no. 4, pp. 184-187, 2011.
[8] S. Kumar, A. Mallik, A. Khetarpal, and B. Panda, "Influence maximization in social networks using graph embedding and graph neural network," Information Sciences, 2022.
[9] K. Senanayaka, "Impact of Social Network Advertising towards Consumer Purchase Intention (Special Reference to Apparel Products Advertising in Facebook)," Uva Wellassa University of Sri Lanka, 2017.
[10] H. Wu, S. Wang, and H. Fang, "LP-UIT: A Multimodal Framework for Link Prediction in Social Networks," in 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), 2021, pp. 742-749: IEEE.
[11] M. H. Nadimi-Shahraki and M. Adami-Dehkordi, "K-indicators Method for Community Detection in Social Networks," Int. J. Advance Soft Compu. Appl, vol. 8, no. 3, pp. 137-159, 2016.
[12] J. Yang, C. Yao, W. Ma, and G. Chen, "A study of the spreading scheme for viral marketing based on a complex network model," Physica A: Statistical Mechanics and its Applications, vol. 389, no. 4, pp. 859-870, 2010.
[13] M. Alshahrani, Z. Fuxi, A. Sameh, S. Mekouar, and S. Huang, "Efficient Algorithms based on Centrality Measures for Identification of Top-K Influential Users in Social Networks," Information Sciences, 2020.
[14] J. Cheriyan and G. Sajeev, "Spreadmax: a scalable cascading model for influence maximization in social networks," in 2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2018, pp. 1290-1296: IEEE.
[15] C. Wang, Y. Liu, X. Gao, and G. Chen, "A Reinforcement Learning Model for Influence Maximization in Social Networks," in International Conference on Database Systems for Advanced Applications, 2021, pp. 701-709: Springer.
[16] O. Gil-Or, "The potential of Facebook in creating commercial value for service companies," Advances in Management, vol. 3, no. 2, pp. 20-25, 2010.
[17] Ö. OKAT and K. KADİRHAN, "ARTIFICIAL INTELLIGENCE-ASSISTED PROGRAMMATIC ADVERTISING," New Communication Approaches in the Digitalized World, p. 87, 2020.
[18] 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.
[19] 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.
[20] J. Zhang and P. S. Yu, "Information diffusion," in Broad Learning Through Fusions: Springer, 2019, pp. 315-349.
[21] D. Kempe, J. Kleinberg, and É. Tardos, "Influential nodes in a diffusion model for social networks," in International Colloquium on Automata, Languages, and Programming, 2005, pp. 1127-1138: Springer.
[22] Y. Ni, L. Xie, and Z.-Q. Liu, "Minimizing the expected complete influence time of a social network," Information Sciences, vol. 180, no. 13, pp. 2514-2527, 2010.
[23] A. Goyal, F. Bonchi, and L. V. Lakshmanan, "Learning influence probabilities in social networks," in Proceedings of the third ACM international conference on Web search and data mining, 2010, pp. 241-250.
[24] M. Hosseini-Pozveh, K. Zamanifar, and A. R. Naghsh-Nilchi, "Assessing information diffusion models for influence maximization in signed social networks," Expert Systems with Applications, vol. 119, pp. 476-490, 2019.
[25] S. Ahmed and C. Ezeife, "Discovering influential nodes from trust network," in Proceedings of the 28th annual acm symposium on applied computing, 2013, pp. 121-128.
[26] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian, "Rev2: Fraudulent user prediction in rating platforms," in Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 2018, pp. 333-341.
[27] S. Kumar, F. Spezzano, V. Subrahmanian, and C. Faloutsos, "Edge weight prediction in weighted signed networks," in 2016 IEEE 16th International Conference on Data Mining (ICDM), 2016, pp. 221-230: IEEE.

Full-Text:



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

سهامه محمدی1، محمد حسین ندیمی شهرکی2¹، زهرا بهشتی3، کامران زمانی‌فر4

1- دانشکده مهندسی کامپيوتر، واحد نجف‌آباد، دانشگاه آزاد اسلامی، نجف‌آباد، ایران

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

[e-mail] 

2- دانشکده مهندسی کامپيوتر، واحد نجف‌آباد، دانشگاه آزاد اسلامی، نجف‌آباد، ایران

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

[e-mail] 

3- دانشکده مهندسی کامپيوتر، واحد نجف‌آباد، دانشگاه آزاد اسلامی، نجف‌آباد، ایران

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

[e-mail] 

4- دانشکده مهندسی کامپیوتر، دانشگاه اصفهان، اصفهان، ایران

[e-mail] 

چکیده: امروزه شبکه‌های اجتماعی آنلاین ارتباط ناگسستنی با زندگی روزمره بسیاری از مردم جهان دارند. کاربرد شبکه‌های اجتماعی در کسب و کارها جهت تبلیغات، بازاریابی، سیستم‌های پیشنهاد دهنده و همچنین در سیستم‌های مدیریت مصرف منابع و انرژی رو به افزایش می‌باشد. یکی از مهم‌ترین مسائل مطرح شده در رابطه با فرایند انتشار اطلاعات در شبکه‌های اجتماعی، مسأله بیشینه‌سازی گسترش تأثیر می‌باشد. در سال‌های اخیر، تحقیق‌هایی برای بهبود کیفیت پیش‌بینی مدل‌های انتشار اطلاعات در این مسأله انجام شده است. طی بررسی‌های انجام شده در مدل‌های موجود، تخمین احتمالات تأثیر کاربران بر روی یکدیگر به طور غیر واقعی محاسبه می‌شود. در این پژوهش با هدف بررسی و بهینه‌سازی فرایند گسترش تأثیر در شبکه‌های اجتماعی، روش جدیدی برای تعیین احتمالات تأثیر در میان کاربران پیشنهاد شده است. این روش تلفیقی از دو رویکرد اصلی محاسبه احتمالات تأثیر شامل بهره‌گیری از جدول لاگ فعالیت و روش یکنواخت مقدار از پیش تعیین شده است. عملکرد روش پیشنهادی بر روی مجموعه داده‌های مختلفی از شبکه‌های اجتماعی دنیای واقعی با روش‌های رقیب مورد ارزیابی و مقایسه قرار گرفت. نتایج حاصل از آزمایش­ها نشان می‌دهد روش پیشنهادی می‌تواند باعث افزایش کارایی پیش­بینی‌های مورد نظر جهت حل مسائل بیشینه‌سازی گسترش تأثیر گردد. 

واژه های کلیدی: شبکه‌های اجتماعی، بیشینه‌سازی تأثیر، مدلسازی انتشار اطلاعات، احتمالات تأثیر

Combined Estimating Influence Probabilities for an Influence Maximization Problem in Social Networks and Its Application in the Power Industry

Sohameh Mohammadi1, Mohammad H. Nadimi-Shahraki2*, Zahra Beheshti3, Kamran Zamanifar4

1 Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

 Big Data Research Center, Najafabad Branch, Islamic Azad University, Najafabad, Iran

[e-mail]

2 Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

 Big Data Research Center, Najafabad Branch, Islamic Azad University, Najafabad, Iran

[e-mail] 

3 Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

 Big Data Research Center, Najafabad Branch, Islamic Azad University, Najafabad, Iran

[e-mail] 

4 Department of Software Engineering, University of Isfahan, Isfahan, Iran

[e-mail] 

Abstract: 

Nowadays, online social networks have an inseparable connection with the daily life of many people in the world. The applications of social networks are increasing in businesses for advertising, marketing, and recommender systems, as well as in resource and energy consumption management systems. One of the most important problems in the information diffusion process of social networks is the influence maximization. In recent years, some research has been conducted to improve the prediction quality of information diffusion models in this problem. In a review of existing models, the influence probabilities among users are estimated unrealistically. In this research, a new method has been proposed to determine the influence probabilities among social network users. This method is a combination of two main approaches in the calculation of influence probabilities, including the use of an action log table and the uniform method with a predetermined value. The performance of the proposed method was evaluated and compared with competitive methods on different real-world social network data sets. The results of the experiments show that the proposed method can increase the efficiency of the predictions in solving the influence maximization problems.

Keywords: Social networks, influence maximization, information diffusion modeling, influence Probabilities

DOI: 00.00000/0000		نوع مقاله: پژوهشی
تاریخ چاپ مقاله: 28/09/1402	تاریخ پذیرش مقاله: 10/09/1402	تاریخ ارسال مقاله: 17/07/1402

 

---

[1] * نویسنده مسئول

 

1-        مقدمه

در حال حاضر، شبکه­های اجتماعی آنلاین آنچنان نقش و جایگاه مهمی در جنبه­های مختلف زندگی مردم پیدا کرده است که زندگی بدون آن­ها دشوار است [1]. یک شبکه اجتماعی، ساختاری متشکل از افراد یا شرکت­ها و ارتباطات اجتماعی بین آن­ها می­باشد. بر اساس نوع شبکه، ارتباطات مختلف بین اعضای شبکه می­تواند بیانگر رابطه­های دوستی، همکاری، پیروی، ارتباط علمی، دشمنی، رقابت یا سایر موارد باشد [2, 3]. امروزه با فراگیر شدن و توسعه شبکه­های اجتماعی، حجم بسیار کلانی از داده­ها فراهم شده است که تجزیه و تحلیل آن­ها می­تواند در شناخت خصوصیات شبکه­های اجتماعی و اثرات آن­ها بر روابط بین افراد و پاسخگویی به بسیاری از سؤال­های آموزشی، اقتصادی، سیاسی، فرهنگی و اجتماعی کمک کننده باشد. پاسخگویی به این نوع سؤالات مستلزم پردازش مجموعه داده­های شبکه­های اجتماعی و استفاده از تکنیک­های یادگیری ماشین و داده­کاوی برای استخراج دانش و الگوهای پنهان از مجموعه داده­ها می­باشد [4, 5]. از اینرو در سال­های اخیر تحلیل شبکه­های اجتماعی به عنوان یک زیر شاخه از علم داده مورد توجه بسیاری از محققان قرار گرفته است. در تحلیل شبکه­های اجتماعی برای نمایش هر شبکه از ساختار گراف استفاده می­شود. در این گراف مجموعه گره­ها¹ نشان­دهنده کاربران و مجموعه یال­ها² بیانگر ارتباطات بین آن­ها می­باشند [6, 7]. 

تحلیل شبکه­های اجتماعی از جنبه­های متنوعی می­تواند مورد بررسی قرارگیرد. بنابراین حوزه­های تحقیقاتی مختلفی در این زیرشاخه گسترش یافته است که از جمله می­توان به گسترش تأثیر³ [8]، تبلیغات و تحلیل بازار [9]، پیش­بینی ارتباط⁴ [10] و تشخیص انجمن⁵ [11] اشاره نمود. بهینه­سازی گسترش تأثیر یکی از حوزه­های تحقیقاتی مهم و در حال رشد در تحلیل شبکه­های اجتماعی می­باشد. در حوزه بهینه­سازی گسترش تأثیر، ابتدا لازم است تعداد کاربران فعال شده اولیه که به عنوان مجموعه هسته⁶ نام­گذاری می­گردند در شروع فرایند گسترش انتشار تأثیر مشخص شوند. در ادامه فرایند، کاربران فعال این مجموعه بر کاربران دیگر شبکه تأثیر گذاشته و منجر به فعال شدن سایر کاربران و گسترش انتشار اطلاعات می­گردند. در نهایت، گسترش مورد انتظار یا پوشش شبکه که نشان­دهنده تعداد کاربران فعال شده مورد انتظار در انتهای فرایند گسترش تأثیر می­باشد تعیین می­شود [12]. با توجه به کاربرد شبکه­های اجتماعی می­توان توابع هدف متفاوتی برای بهینه­سازی گسترش تأثیر مشخص نمود. یکی از مهم‌ترین اهداف در بهینه­سازی گسترش، پیدا کردن مجموعه هسته اولیه با یک بودجه محدود و تحت یک مدل انتشار اطلاعات⁷ معین می­باشد به طوریکه این مجموعه حداکثر گسترش یا پوشش مورد انتظار را در شبکه ایجاد نماید. این مسأله به عنوان بیشینه­سازی گسترش تأثیر نام­گذاری شده است [6, 13]. 

کاربردهای گوناگونی [14, 15] برای مسأله بیشینه­سازی گسترش تأثیر در شبکه­های اجتماعی می­توان ارائه کرد. به عنوان نمونه از مهم‌ترین آن‌ها می‌توان به ذکر کاربرد در صنعت برق کشور اشاره نمود. این صنعت در ماه­های گرم سالیان اخیر با چالش مصرف زیاد برق توسط مشترکین خانگی و تجاری مواجه بوده که منجر به قطعی­های گسترده برق یا کاهش زمان کار ادارات و کارخانجات گردیده است. شرکت برق در راستای فرهنگ­سازی و جلب مشارکت شهروندان در مدیریت مصرف برق می­تواند از ظرفیت‌های فضای مجازی و روش­های نوینی مانند بازاریابی ویروسی⁸ در بستر شبکه­های اجتماعی استفاده کند. در این روش، اطلاع رسانی اصول صحیح بهره­وری انرژی بر اساس گروهی منتخب از مشتریان در یک شبکه اجتماعی که بیشترین تأثیر در انتشار اطلاعیه ها و فرهنگ­سازی مصرف برق را داشته باشند تکیه خواهد داشت. در این راستا یک فرد پس از دریافت آموزش­های لازم، از طریق ارتباطات شبکه­ای، تجربیات خود در این زمینه را با سایر دوستان به اشتراک می­گذارد. با توجه به اینکه یکی از عوامل مهم تأثیرگذار در نگرش افراد جهت رعایت اصول صحیح بهره‌وری انرژی، دریافت توصیه از دوستان مورد اعتماد است؛ لذا این روش کارایی و اثرگذاری بالایی در کاهش هزینه‌ها و توسعه فرهنگ مصرف صحیح انرژی برق در میان آحاد جامعه خواهد داشت. با وجود اینکه این روش در سال­های اخیر مورد توجه بسیاری از شرکت­های خدماتی در سطح بین­المللی قرار گرفته [16, 17]، اما متاسفانه در کشور ما به دلیل عدم آشنایی به­طور مناسب به­کار گرفته نشده است. در این مقاله به ارائه روشی نوین در جهت بهبود عملکرد مدل­های کاربردی انتشار اطلاعات برای بیشینه­سازی گسترش تأثیر پرداخته می‌شود. 

یکی از پارامترهای مهم و بنیادی در مدل­سازی فرایند انتشار اطلاعات، احتمال تأثیر⁹ یک کاربر بر روی کاربر دیگر می­باشد. طی بررسی­های انجام شده در مدل­های انتشار اطلاعات موجود، تخمین احتمالات تأثیر کاربران بر روی یکدیگر به طور غیر واقعی محاسبه می­گردد. در این پژوهش به منظور سازگار نمودن رابطه­های محاسبه احتمالات تأثیر با کاربردهای دنیای واقعی، روش جدیدی برای تعیین احتمالات تأثیر در میان کاربران شبکه اجتماعی ارائه شده است. این روش تلفیقی از دو رویکرد اصلی محاسبه احتمالات تأثیر است. در رویکرد اول به دلیل نبود دانش و اطلاعات لازم در شبکه، کلیه احتمالات تأثیر برابر با مقداری از پیش مشخص شده به طور یکنواخت در نظر گرفته می­شوند؛ در حالی که در رویکرد دوم، با وجود دانش و اطلاعات لازم در شبکه و با بهره­گیری از جدولی موسوم به لاگ فعالیت، فرایند یادگیری احتمالات تأثیر میان کاربران محاسبه می‌شود. 

در ادامه ساختار مقاله بدین شرح ﺗﻨﻈﯿﻢ ﺷﺪه اﺳﺖ. در بخش 2 به مرور ادبیات و پیشینه پژوهش پرداخته شده است. در بخش 3 روش پیشنهادی با جزئیات ارائه شده است. سپس در بخش 4 روش پیشنهادی از طریق طراحی آزمایشات مختلف و پیاده­سازی آن­ها بر روی شبکه­های اجتماعی دنیای واقعی مورد ارزیابی و مقایسه قرار گرفته است. در نهایت بخش 5 به بحث و نتیجه­گیری اختصاص دارد. 

2-       ادبیات و پیشینه پژوهش

مسأله بیشینه­سازی گسترش تأثیر، برای بهبود در عملکرد بازاریابی ویروسی برای اولین بار توسط دومینگوس و ریچاردسون [6, 18] در بستر شبکه­های اجتماعی مطرح گردید. هدف از حل این مسأله، تعیین یک زیرمجموعه کوچک از کاربران یک شبکه اجتماعی در شروع فرآیند انتشار اطلاعات است به نحوی که در شبکه، بیشترین میزان گسترش تأثیر منطبق بر اهداف بازاریابی ایجاد شود. لازم به ذکر است که اندازه مجموعه اولیه کاربران با توجه به محدودیت­های بودجه تبلیغات کسب و کارها مقداری ثابت است که به صورت از پیش تعریف شده، به عنوان ورودی مسأله داده خواهد شد. در تحقیقات دومینگوس و ریچاردسون [6, 18] مدل­سازی مسأله بیشینه­سازی گسترش تأثیر، با استفاده از میدان تصادفی مارکوف انجام شده است. علی­رغم اینکه روش ارائه شده توسط آن­ها قادر به حل این مسأله و بالطبع افزایش قابل توجه سود کسب و کار در بازار هدف می­باشد، اما در مدل­سازی انجام شده نحوه تأثیرگذاری کاربران شبکه اجتماعی بر روی همدیگر و همچنین نحوه گسترش انتشار اطلاعات به وضوح تعیین نشده است.

مدل­های انتشار اطلاعات به مدل­سازی چگونگی انتشار تأثیر، اخبار و عقاید در بستر شبکه­های اجتماعی می­پردازد. در این مدل­ها بررسی میزان تأثیر افراد منتخب جهت انتشار اطلاعات در جامعه ممکن می­گردد [19, 20]. به طورکلی برای گسترش تأثیر، مدل­های انتشار اطلاعات را می­توان به دو نوع مدل­های متقارن¹⁰ و پیش­رونده¹¹ طبقه­بندی کرد. در هر دو طبقه، وضعیت هر کاربر در یک شبکه اجتماعی به صورت فعال به معنی پذیرش تأثیر و یا غیر فعال به معنی عدم پذیرش تأثیر در نظر گرفته می­شود. در مدل­های متقارن، فرض بر این است که اگر فردی تأثیر را پذیرفت، ممکن است این تأثیر در او پایدار نباشد، بنابراین کاربران شبکه می­توانند از حالت غیرفعال به فعال و یا بر عکس تغییر حالت دهند. اما در مدل­های پیش­رونده، کاربران تنها می­توانند از حالت غیر فعال به حالت فعال تغییر وضعیت دهند و این تأثیر در آن­ها پایدار خواهد بود. در بیشتر کاربردهای دنیای واقعی مدل­های پیشرونده برای تشریح نحوه انتشار اخبار گزینه مناسب­تری هستند [21, 22]. لذا تمرکز این پژوهش بر روی مدل­های انتشار پیش­رونده می­باشد. در ادامه به معرفی تعدادی از مدل­های انتشار مطرح برای مدل کردن فرایند پخش اطلاعات می­پردازیم.

اولین تعریف رسمی از مسأله بیشینه­سازی گسترش تأثیر در یک شبکه اجتماعی توسط کمپ و همکاران [19] به عنوان یک مسأله بهینه­سازی گسسته و بر مبنای مدل­های انتشار اطلاعات ارائه شد. همچنین آن­ها اثبات نمودند که مسأله بیشینه­سازی گسترش تأثیر در حالت کلی جزء مسائل اِن­پی­سخت¹² می­باشد. یکی از معروف­ترین مدل­های انتشار اطلاعات، مدل آبشاری مستقل¹³ است که توسط کمپ و همکاران [19] ارائه گردید. در این مدل، کاربران در یکی از دو حالت فعال یا غیر فعال قرار دارند. همچنین به هر کاربر فعال، احتمالی برای فعال کردن هریک از همسایه­های غیرفعالش اختصاص داده می­شود. اگر کاربر  یکی از همسایگان غیرفعال کاربر  باشد، احتمال موفقیت کاربر  در فعالسازی  با  نشان داده می­شود. در مدل آبشاری مستقل، فعال شدن یک کاربر غیرفعال، مستقل از فعالیت­های گذشته دیگر کاربران فعال بر روی این کاربر می­باشد. فرایند انتشار تأثیر با فعال کردن مجموعه اولیه از کاربران آغاز می­شود. وقتی که کاربر  در گام زمانی گسسته  فعال می­شود، آنگاه برای فعال کردن هر همسایه غیرفعال خود یک فرصت خواهد داشت. اگر چند کاربر فعال به طور همزمان بخواهند کاربر  را فعال کنند، یک جایگشت تصادفی از آن­ها انتخاب و بر اساس این جایگشت فرایند فعالسازی انجام می­شود. مدل حد آستانه خطی¹⁴ [19]، یکی دیگر از مدل­های انتشار اطلاعات معروف و پایه­ای است که در آن کاربران در یکی از دو حالت فعال یا غیر فعال قرار دارند. هر کاربر غیرفعال  از هرکاربر همسایه خود  به مقدار وزن  تأثیر می­گیرد مشروط به آنکه فرمول زیر برقرار باشد:

(1)

 مجموع وزن تأثیری که همسایگان کاربر  باید رأی فعالسازی برای این کاربر اعمال کنند با مقدار حد آستانه  نشان داده می­شود. این حد آستانه به صورت تصادفی از توزیع یکنواخت پیوسته در بازه [0،1] انتخاب می­شود. در مدل حد آستانه خطی فرایند انتشار تأثیر بدین­گونه شروع می­شود که یک مجموعه اولیه از کاربران فعال انتخاب می­شود در حالیکه مابقی کاربران شبکه غیرفعال می­باشند. فرایند انتشار اطلاعات در گام­های زمانی گسسته  انجام می­شود که در هر گام کل کاربرانی که در گام زمانی قبلی فعال بوده­اند فعال خواهند ماند و کاربرانی که مجموع وزنی تأثیر همسایگان فعال بر آن­ها بیشتر از حد آستانه  باشند به مجموعه کاربران فعال اضافه می­شوند. با این توضیحات رابطه فعال­سازی برای کاربر  عبارت است از:

(2)

مدل آبشاری عمومی¹⁵ [19] مشابه آبشاری مستقل است با این تفاوت که در آن سابقه فعالیت­های کاربران فعال دیگر بر یک کاربر غیرفعال نادیده گرفته نمی­شود. اگر  مجموعه کاربران فعال با تلاش­های ناموفق جهت فعال­سازی کاربر  باشند آنگاه احتمال فعال­سازی موفق  توسط کاربر فعال  برابر با تابع افزایشی  است. مدل آستانه عمومی¹⁶ [19] تعمیمی از مدل حد آستانه خطی است. در مدل حد آستانه خطی، تابع فعالسازی برابر با مجموع وزن­های تأثیر همسایگان فعال کاربر  در نظرگرفته شده است. در مدل حد آستانه عمومی، این تابع تأثیر به صورت کلی­تر تعریف می­شود. به عبارت دقیق­تر فعال شدن کاربر  وابسته به یک تابع تأثیر یکنواخت دلخواه  در بازه [0،1] است که در آن  مجموعه همسایگان فعال  هستند. فرایند انتشار در مدل حد آستانه عمومی، مشابه مدل حد آستانه خطی است با این تفاوت که شرط فعال­سازی به صورت  تعریف می­گردد. 

همانگونه که از مدل­های معرفی شده تا به حال مشخص است احتمالات تأثیر نقش مهمی را در مدل­سازی انتشار اطلاعات ایفا می­کنند. پژوهشگران در مدل­های فوق، فرض را بر این گذاشته­اند که اطلاعات لازم برای مشخص کردن احتمالات تأثیر در اختیار نیست. بنابراین رویکرد آن­ها در تعیین احتمالات تأثیر در نظر گرفتن مقادیر از پیش تعیین شده می­باشد. به عنوان مثال، کمپ و همکاران برای مدل آبشاری مستقل [19]، مقدار احتمالات تأثیر بین دو کاربر را مقادیر ثابت 1% تا 10% در نظر گرفتند. اما طیف قابل توجهی از شبکه­های اجتماعی وجود دارد که اطلاعات لازم برای یادگیری احتمالات تأثیر در میان کاربران شبکه ثبت شده است. در اینگونه موارد، عدم استفاده از این اطلاعات باعث کاهش دقت پیش­بینی مدل­های انتشار اطلاعات می­گردد. از اینرو گویال و همکاران [23] رویکرد دیگری را برای به­دست آوردن احتمالات تأثیر بر مبنای لاگ فعالیت کاربران معرفی نمودند. بدین منظور، مدل انتشار اطلاعات مورد نظر آن­ها حالتی از مدل حد آستانه عمومی است، که در آن تابع تأثیر برای هر کاربر  مبتنی بر احتمالات تأثیر همه کاربران فعال همسایه آن تعیین می­شود. به صورت جزئی­تر، فعالسازی کاربر u در صورتی که  باشد با موفقیت انجام می­شود. در این رابطه،  حد آستانه فعالسازی و  است که به صورت تصادفی در بازه [0،1] انتخاب می­گردد.

با توجه به رویکرد پیشنهاد شده توسط گویال و همکاران [23]، پژوهش­هایی به ارائه مدل­های انتشار اطلاعاتی مبتنی بر یادگیری احتمالات تأثیر پرداخته­اند. به عنوان نمونه، حسینی­پزوه و همکاران [24] مدل انتشار آبشاری آگاه از علامت با گره­های مسدودشونده¹⁷ که در ادامه به طور خلاصه شده اِس­سی­بی¹⁸ نامیده می­شود، معرفی کردند. مدل انتشار اِس­سی­بی تعمیم­یافته، مدل آبشاری مستقل است و در طبقه مدل­های پیش­رونده قرار دارد. در این مدل، کاربران علاوه بر حالت­های فعال و غیرفعال ممکن است در حالت مسدود قرار گیرند. کاربر مسدود، کاربری است که تأثیر را می­پذیرد اما آن را به دیگر اعضای شبکه ارسال نمی­کند. در این مدل، هنگامی که کاربر  فعال می­گردد برای فعال­سازی هر یک از همسایگان غیرفعال  خود یک فرصت خواهد داشت. اگر  ارتباط مثبت با  داشته باشد، سعی می­کند تا آن کاربر را فعال نماید. اما در صورت وجود ارتباط منفی  نسبت به ، سعی می­کند تا آن کاربر را مسدود نماید. اگر یک کاربر غیرفعال به طور همزمان توسط چند کاربر فعال برای فعال یا مسدود شدن تحت تأثیر قرار گیرد، با انتخاب یک جایگشت تصادفی از این کاربران تأثیر به ترتیب اعمال می­گردد. 

اگرچه مدل­های انتشار اطلاعات مختلفی برای بیشینه­سازی گسترش تأثیر در شبکه­های اجتماعی تعریف و تعمیم داده شده­اند که به برخی از آن­ها اشاره گردید، اما نحوه محاسبه احتمالات تأثیر بر عملکرد این مدل­ها به شدت مؤثر است. دو رویکرد فعلی محاسبات احتمالات تأثیر از جمله عواملی است که باعث شده هنوز مدل­های انتشار اطلاعات، دقت لازم را در پیش­بینی­های خود نداشته باشند. در بخش بعدی به ارائه روشی در تعیین احتمالات تأثیر جهت بهبود عملکرد مدل­های انتشار اطلاعات پرداخته می­شود. 

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

کلیه مدل­های انتشار اطلاعات برای مدل­سازی مسأله بیشینه­سازی گسترش تأثیر در شبکه­های اجتماعی بر اساس پارامتری کلیدی و پایه­ای به نام احتمال تأثیر بنیاد نهاده شده­اند. احتمال تأثیر میزان تأثیرگذاری یک کاربر شبکه بر کاربر دیگر را در صورت وجود ارتباط در فرایند گسترش تأثیر نشان می­دهد. در واقع، برای شبکه­های اجتماعی که در آن ارتباطات جهت­دار هستند یک احتمال تأثیر تعریف می­گردد. تاکنون تحقیق­های قابل توجهی برای بهبود کیفیت پیش­بینی مدل­های انتشار اطلاعات در مسأله‌ی بیشینه­سازی گسترش تأثیر انجام شده است. با توجه به بررسی­های انجام شده در مدل­های انتشار اطلاعات موجود، تخمین احتمالات تأثیر کاربران بر روی یکدیگر دقيق و درست انجام نشده است که این امر منجر به کاهش چشمگیر کیفیت پیش­بینی مدل­های انتشار می­گردد. در این مدل­ها تعیین احتمالات تأثیر بر مبنای دو رویکرد اصلی شامل عدم وجود اطلاعات [19, 21] یا وجود اطلاعات [23, 24] لازم در شبکه­های اجتماعی صورت گرفته است. با توجه به رویکردهای ارائه شده همانگونه که مشخص است در صورتی که اطلاعات لازم از فعالیت کاربران شبکه­های اجتماعی موجود باشد، استفاده از رویکرد اول باعث کاهش دقت در پیش­بینی­های انجام شده می­گردد. از طرف دیگر در شبکه­های بزرگ استفاده از اطلاعات جدول لاگ فعالیت باعث می­گردد که تعداد قابل توجهی از احتمالات تأثیر بین کاربران مقداری ناچیز و نزدیک به صفر محاسبه گردد. بنابراین ارائه رویکرد جدیدی که در آن دو رویکرد قبلی با یکدیگر ترکیب می­گردند باعث می­شود که نقاط ضعف یکدیگر را برطرف و دقت پیش­بینی به طور قابل ملاحظه­ای بهبود یابد. 

شکل (1) حاکی از یک ساختار سلسله مراتبی است که به­کارگیری روش پیشنهادی در حل یک مسأله بیشینه­سازی گسترش تأثیر در شبکه­های اجتماعی را نشان می­دهد. همانگونه که در این ساختار مشاهده می­شود، محاسبه احتمالات تأثیر بر اساس روش پیشنهادی بعد از مراحل جمع­آوری و پیش­پردازش داده­های شبکه اجتماعی و قبل از مراحل کاوش مجموعه هسته و مدل­سازی فرایند انتشار اطلاعات قرار می­گیرد.

در روش پیشنهادی، محاسبه احتمالات تأثیر برای ارتباطاتی در جدول لاگ فعالیت که اطلاعات کافی برای محاسبه احتمالات تأثیر وجود ندارد، مقدار ثابت از پیش تعیین شده (به عنوان احتمال تأثیر حداقلی) در نظر گرفته می­شود. اما در حالتی که جدول لاگ فعالیت، اطلاعات کافی برای محاسبه احتمالات تأثیر در بر دارد از این اطلاعات به شرح زیر جهت تعیین احتمالات تأثیر استفاده می­شود. در روش مبتنی بر جدول لاگ فعالیت، یادگیری احتمالات تأثیر بین کاربران با توجه به شبکه­های اجتماعی معمولی¹⁹ یا شبکه­های اجتماعی علامت­دار²⁰ محاسبه می­شود. شبکه­های اجتماعی معمولی تنها بر اساس روابط اعتماد پایه­گذاری شده­اند. یادگیری احتمال تأثیر برای مدل­های انتشار منطبق بر این نوع از شبکه­ها با استفاده از برآورد ماکسیمم درست­نمایی در توزیع برنولی مطابق (3) محاسبه می­گردد [23]:

(3)

که صورت کسر، نشان دهنده تعداد عملیات­هایی است که کاربر  با الهام گرفتن از کاربر  انجام داده و مخرج کسر برابر تعداد کل عملیات­های انجام شده توسط کاربر  است. از آنجایی که شبکه­های اجتماعی علامت­دار دارای هر دو روابط اعتماد و عدم اعتماد است، از اینرو لازم است برای این مدل انتشار اطلاعات (منطبق بر آن­ها)، دو نوع احتمال تأثیر مثبت و احتمال تأثیر منفی محاسبه گردد. 

 

شکل (1): مراحل حل مسأله بیشینه‌‌سازی گسترش تأثیر در شبکه‌های اجتماعی

جدول (1): مشخصات آماری مجموعه داده­ها

مشخصات	بیت­کوین OTC	بیت­کوین Alpha
تعداد گره­ها	3783	5881
تعداد یال­ها	24186	35592

 

---

[1]  Nodes

[2]  Edges

[3]  Influence propagation

[4]  Link prediction

[5]  Community detection

[6]  Seed set

[7]  Information diffusion model

[8]  Viral marketing

[9]  Influence probability

[10]  Symmetric

[11]  Progressive

[12]  NP-hard 

[13]  Independent Cascade (IC) Model

[14]  Linear threshold Model

[15]  General Cascade Model

[16]  General threshold Model

[17]  Sign-aware cascade including blocking nodes

[18]  SC-B

[19]  Typical social networks (TSN)

[20]  Signed social networks (SSN)

در شبکه‌های اجتماعی علامت­دار چنانچه رابطه بین دو کاربر بر پایه اعتماد باشد، احتمال تأثیر مثبت و در صورتی که روابط بین آن­ها از نوع عدم اعتماد باشد، احتمال تأثیر منفی مطرح می­گردند. این دو نوع احتمالات تأثیر، بر اساس (4-5) محاسبه می­شوند [25]:

(4)
(5)

که در (5) صورت کسر، نشان­دهنده تعداد عملیات­هایی است که توسط کاربر  انجام شده، اما پس از آن توسط کاربر  دنبال نشده است. در شکل (2) شبه­کد مربوط به روش پیشنهادی ارائه شده است. 

4-       پیاده‌سازی و ارزیابی

در این بخش به ارزیابی روش­های موجود و پیشنهادی در تعیین احتمالات تأثیر پرداخته می­شود. برای مقایسه، از مدل­های مبتنی بر انتشار آبشاری شامل مدل آبشاری مستقل [19] و مدل آبشاری آگاه از علامت با گره­های مسدود شونده [24] استفاده شده است. ارزیابی تمامی مدل­های انتشار اطلاعات منطبق بر روش­های موجود و پیشنهادی این مطالعه با زبان برنامه نویسی پایتون و با سیستم کامپیوتر شخصی با مشخصات پردازنده Intel Core i7- 3.4 GHz، حافظه موقت 8 گیگابایت و سیستم عامل ویندوز 10، 64 بیتی پیاده­سازی شده­اند. برای ارزیابی­ها از دو مجموعه داده شبکه اجتماعی واقعی بیت­کوین OTC و بیت­کوین Alpha [26, 27] استفاده شده است. این مجموعه داده­ها، شبکه­های اجتماعی علامت­داری هستند که در پلتفرم تجزیه و تحلیل شبکه استنفورد منتشر شده­اند. این شبکه­ها در برگیرنده معاملات بیت­کوین افرادی است که بر روی پلتفرم‌های بیت­کوین OTC و Alpha انجام شده است. از آنجایی که کاربران بیت­کوین ناشناس هستند، برای جلوگیری از تراکنش با کاربران متقلب و پرخطر، نیاز به حفظ سابقه شهرت کاربران وجود دارد. بدین منظور اعضای بیت­کوین OTC و Alpha یکدیگر را با نمره­ای از 10- (بی­اعتمادی کامل) تا 10+ (اعتماد کامل) رتبه بندی می­کنند. مشخصات آماری مربوط به مجموعه­ داده­های این دو شبکه در جدول (1) نشان شده است. با توجه به اینکه مدل آبشاری مستقل تنها بر اساس روابط اعتماد پایه­گذاری شده، تنها روابطی که دارای نمرات مثبت هستند لحاظ می­گردند و روابط عدم اعتماد در این مجموعه داده­ها نادیده گرفته می­شوند. 

به منظور انجام فرایند ارزیابی، لاگ فعالیت کاربران در هر مجموعه داده شبکه­های اجتماعی بر اساس اولویت زمانی به دو قسمت مجموعه آموزش و مجموعه آزمایش تقسیم می­گردد. از مجموعه داده آموزش جهت یادگیری احتمالات تأثیر بین کاربران در مدل­های انتشار اطلاعات استفاده شده است. این مجموعه شامل80% ابتدایی قسمت نمرات ارزیابی کابران از یکدیگر می­باشد. علاوه بر این مجموعه داده آزمایش برای تعیین اینکه کدام یک از روش­های مربوط به نحوه انتشار تأثیر در شبکه­های اجتماعی نسبت به دیگری توانمندی بالاتری جهت پیش­بینی کردن پذیرش تأثیر در بین کاربران را دارد. این مجموعه شامل 20% پایانی قسمت نمرات مجموعه داده است. لازم به ذکر است که در محاسبات احتمالات تأثیر زمان ایجاد روابط در بین کاربران هم لحاظ گردیده است. به بیان دیگر، هنگام نمره­دهی کاربران به یکدیگر در محاسبات لحاظ می­شود که نمره­دهی بعد از زمان تشکیل شدن اولین رابطه بین آن­ها باشد و در غیر این صورت به­کار برده نمی­شود.

کلیه آزمایشات با انتخاب تصادفی مجموعه کاربران اولیه با اندازه­های 3، 6، 9، 12، 15، 18، 21 و 24 جهت شبیه­سازی فرایند انتشار تأثیر در مدل­های انتشار اطلاعات انجام می­شود. علاوه بر این، پارامترهای ،  و  مربوط به حدود آستانه احتمالات تأثیر مسأله برای هر دو شبکه OTC و Alpha در دو حالت شامل صفر یا برابر با 1/0 لحاظ شده است. در حالت اول، پارامترهای ،  و  برای هر دو شبکه با احتمال تأثیر 01/0 تا احتمال تأثیر 07/0 با فواصل 02/0 در نظر گرفته شده که به ترتیب با نمادهای  تا  در ارزیابی روش پیشنهادی مشخص شده است. در حالت دوم احتمالات تأثیر مشمول با 1/0 جایگزین می­گردند که با نماد  نشان داده شده است.

هدف از شبیه­سازی­ها، پیش­بینی رفتار آینده کاربران در مجموعه داده آزمایش می­باشد. برای تحلیل نتایج و ارزیابی کارایی روش پیشنهادی از معیارهای دقت¹، فراخوانی² و امتیاز اِف³ [24] که سه معیار ارزیابی معروف در حوزه علم داده­ها هستند، استفاده شده است. از آنجایی که مجموعه کاربران اولیه به صورت تصادفی انتخاب می­شوند، آزمایشات برای هر مجموعه کاربر اولیه 10 بار تکرار می­گردد. نتایج ارزیابی بر روی مجموعه داده­های بیت­کوین OTCو Alpha در جداول (2-5) نشان داده شده است. در شکل (3) مقایسه روش پیشنهادی با روش­های پیشین بر اساس معیار ارزیابی میانگین امتیاز اِف ارائه شده است. با توجه به این نتایج، در هر دو مدل انتشار اطلاعات آبشاری مستقل و مدل آبشاری آگاه از علامت با گره­های مسدود شونده بدترین عملکرد در پیش­بینی پذیرش تأثیر در میان کاربران بر مبنای هر سه معیار دقت، فراخوانی و امتیاز اِف مربوط به روشی است که مقادیر احتمالات تأثیر تنها مبتنی بر لاگ فعالیت کاربران باشد. از طرفی این نتایج بیانگر آن است که در روش پیشنهادی برای ارتباطاتی در جدول لاگ فعالیت کاربران که اطلاعات لازم برای محاسبه احتمالات تأثیر وجود ندارد، اعمال مقدار ثابت احتمال تأثیر حداقلی به صورت کنترل شده و بر اساس نوع و کاربردهای خاص شبکه­های اجتماعی دارای اهمیت قابل توجهی است و موجب بهبود قدرت پیش­بینی مدل­های انتشار اطلاعات در شبکه اجتماعی می­گردد.

5-       نتیجه‌گیری

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

 

---

[1]  Precision

[2]  Recall

[3]  F-score

 

شکل (2): شبه کد روش پیشنهادی جهت برآورد احتمالات تأثیر 

 

جدول (2): مقایسه مدل انتشار IC با احتمالات تأثیر متفاوت در مجموعه داده OTC 

Algorithm 1: The proposed method to estimate the influence probabilities
	Input:  (a social network directed graph  where  represents a set of users and  represents a set of edges among them); L (users' action log); Network Type (TSN, SSN);  (the acceptable minimum thresholds for the influence probabilities);  (the predetermined minimum values for the influence probabilities)
	Output:  (the graph  where the influence probabilities  among all users are determined)
	Begin
	Generate a time sequence table TST from users' action log L
	If Network Type = "TSN" then
	For each edge (, ) in E
	Calculate action patterns  and for each user pair that is in TST
	Calculate the influence probability  by using Eq. (3)
	If  then
	End if
	End for
	Else
	For each edge (, ) in E
	Calculate action patterns  and for each user pair that is in TST
	If there exists trust relationship between the users  and  then
	Calculate the positive influence probability  by using Eq. (4)
	If  then
	End if
	else
	Calculate the negative influence probability  by using Eq. (5)
	If  then
	End if
	End if
	End for
	End if
	Return
	End

معیار		دقت						فراخوانی						امتیاز اِف
کاربر#	شاخص	IC	IC(P1)	IC(P2)	IC(P3)	IC(P4)	IC(P5)	IC	IC(P1)	IC(P2)	IC(P3)	IC(P4)	IC(P5)	IC	IC(P1)	IC(P2)	IC(P3)	IC(P4)	IC(P5)
3	Avg	0.010	0.030	0.033	0.043	0.045	0.036	0.020	0.134	0.255	0.471	0.550	0.614	0.013	0.049	0.058	0.079	0.083	0.068
	Max	0.028	0.077	0.087	0.079	0.101	0.080	0.074	0.318	0.400	0.636	0.682	0.786	0.041	0.124	0.143	0.141	0.176	0.145
6	Avg	0.094	0.087	0.099	0.126	0.100	0.098	0.089	0.215	0.350	0.531	0.561	0.670	0.091	0.124	0.154	0.204	0.170	0.171
	Max	0.279	0.218	0.245	0.235	0.205	0.196	0.154	0.355	0.513	0.615	0.714	0.818	0.198	0.270	0.332	0.340	0.319	0.316
9	Avg	0.069	0.087	0.098	0.100	0.090	0.093	0.086	0.269	0.381	0.436	0.499	0.616	0.077	0.131	0.156	0.163	0.152	0.162
	Max	0.210	0.252	0.303	0.267	0.256	0.249	0.188	0.500	0.562	0.688	0.677	0.812	0.198	0.335	0.394	0.385	0.372	0.381
12	Avg	0.146	0.138	0.136	0.128	0.137	0.121	0.160	0.360	0.474	0.626	0.710	0.736	0.153	0.200	0.211	0.213	0.230	0.208
	Max	0.238	0.216	0.224	0.244	0.236	0.232	0.298	0.526	0.667	0.750	0.818	0.857	0.265	0.306	0.335	0.368	0.366	0.365
15	Avg	0.166	0.180	0.186	0.184	0.180	0.176	0.167	0.343	0.441	0.531	0.617	0.701	0.166	0.236	0.262	0.273	0.279	0.281
	Max	0.359	0.367	0.396	0.359	0.328	0.342	0.320	0.497	0.598	0.706	0.765	0.825	0.338	0.422	0.476	0.476	0.459	0.484
18	Avg	0.183	0.183	0.194	0.187	0.206	0.195	0.173	0.331	0.484	0.566	0.637	0.712	0.178	0.236	0.277	0.281	0.311	0.306
	Max	0.258	0.241	0.259	0.254	0.256	0.249	0.254	0.435	0.612	0.700	0.786	0.875	0.256	0.310	0.364	0.373	0.386	0.388
21	Avg	0.202	0.180	0.157	0.208	0.177	0.188	0.228	0.382	0.475	0.520	0.594	0.681	0.214	0.245	0.236	0.297	0.273	0.295
	Max	0.477	0.286	0.241	0.460	0.424	0.422	0.364	0.500	0.545	0.625	0.727	0.818	0.413	0.364	0.334	0.530	0.536	0.557
24	Avg	0.244	0.245	0.253	0.278	0.252	0.232	0.222	0.429	0.553	0.634	0.684	0.721	0.232	0.312	0.347	0.387	0.368	0.351
	Max	0.373	0.329	0.352	0.340	0.325	0.305	0.349	0.533	0.651	0.685	0.782	0.800	0.361	0.407	0.457	0.454	0.459	0.442
رفتار میانگین		0.139	0.141	0.145	0.157	0.148	0.142	0.143	0.308	0.427	0.539	0.607	0.681	0.141	0.192	0.213	0.237	0.233	0.230
بهترین رفتار		0.477	0.367	0.396	0.460	0.424	0.422	0.364	0.533	0.667	0.750	0.818	0.875	0.413	0.422	0.476	0.530	0.536	0.557
رتبه														6	5	4	1	2	3

 

جدول (3): مقایسه مدل انتشار IC با احتمالات تأثیر متفاوت در مجموعه داده Alpha

معیار		دقت												فراخوانی													امتیاز اِف
کاربر#	شاخص		IC		IC(P1)		IC(P2)		IC(P3)		IC(P4)		IC(P5)		IC		IC(P1)		IC(P2)		IC(P3)		IC(P4)		IC(P5)		IC		IC(P1)		IC(P2)		IC(P3)		IC(P4)		IC(P5)
3	Avg		0.058		0.027		0.039		0.049		0.043		0.047		0.085		0.104		0.218		0.397		0.441		0.519		0.069		0.043		0.066		0.087		0.078		0.086
	Max		0.090		0.072		0.108		0.149		0.094		0.167		0.208		0.250		0.417		0.625		0.667		0.792		0.126		0.112		0.172		0.241		0.165		0.276
6	Avg		0.062		0.084		0.081		0.093		0.089		0.083		0.100		0.340		0.436		0.533		0.680		0.713		0.077		0.135		0.137		0.158		0.157		0.149
	Max		0.156		0.161		0.153		0.173		0.150		0.143		0.241		0.678		0.700		0.737		0.846		0.833		0.189		0.260		0.251		0.280		0.255		0.244
9	Avg		0.090		0.104		0.097		0.086		0.091		0.087		0.106		0.282		0.401		0.432		0.646		0.724		0.097		0.152		0.156		0.143		0.160		0.155
	Max		0.250		0.233		0.244		0.276		0.246		0.223		0.208		0.485		0.576		0.667		0.750		0.900		0.227		0.315		0.343		0.390		0.370		0.357
12	Avg		0.152		0.165		0.153		0.173		0.169		0.159		0.130		0.350		0.469		0.550		0.655		0.689		0.140		0.224		0.231		0.263		0.269		0.258
	Max		0.288		0.287		0.324		0.287		0.298		0.271		0.211		0.440		0.618		0.762		0.750		0.789		0.244		0.347		0.425		0.417		0.427		0.403
15	Avg		0.184		0.201		0.214		0.240		0.229		0.223		0.130		0.301		0.408		0.551		0.604		0.675		0.152		0.241		0.281		0.334		0.332		0.335
	Max		0.304		0.362		0.391		0.381		0.373		0.354		0.255		0.403		0.488		0.633		0.717		0.867		0.277		0.381		0.434		0.476		0.491		0.503
18	Avg		0.155		0.216		0.230		0.217		0.221		0.208		0.186		0.428		0.512		0.595		0.629		0.724		0.169		0.287		0.317		0.318		0.327		0.323
	Max		0.286		0.445		0.396		0.407		0.407		0.349		0.264		0.495		0.536		0.677		0.720		0.808		0.275		0.469		0.455		0.508		0.520		0.487
21	Avg		0.277		0.263		0.260		0.260		0.250		0.230		0.241		0.462		0.543		0.584		0.677		0.745		0.258		0.335		0.352		0.360		0.365		0.351
	Max		0.476		0.393		0.260		0.260		0.385		0.350		0.370		0.604		0.543		0.584		0.746		0.830		0.416		0.476		0.351		0.360		0.508		0.492
24	Avg		0.275		0.303		0.297		0.296		0.317		0.298		0.216		0.387		0.481		0.528		0.612		0.690		0.242		0.340		0.367		0.379		0.418		0.416
	Max		0.383		0.484		0.388		0.439		0.452		0.440		0.349		0.496		0.590		0.608		0.718		0.771		0.365		0.490		0.468		0.510		0.555		0.560
رفتار میانگین		0.157		0.170		0.171		0.177		0.176		0.167		0.149		0.332		0.434		0.521		0.618		0.685		0.151		0.220		0.238		0.255		0.263		0.259
بهترین رفتار		0.476		0.484		0.396		0.439		0.452		0.440		0.370		0.678		0.700		0.762		0.846		0.900		0.416		0.490		0.468		0.510		0.555		0.560
رتبه																										6		5		4		3		1		2

 

جدول (4): مقایسه مدل انتشار SC-B با احتمالات تأثیر متفاوت در مجموعه داده OTC

معیار		دقت						فراخوانی						امتیاز اِف
کاربر#	شاخص	SC-B	SC-B (P1)	SC-B (P2)	SC-B (P3)	SC-B (P4)	SC-B (P5)	SC-B	SC-B (P1)	SC-B (P2)	SC-B (P3)	SC-B (P4)	SC-B (P5)	SC-B	SC-B (P1)	SC-B (P2)	SC-B (P3)	SC-B (P4)	SC-B (P5)
3	Avg	0.026	0.035	0.051	0.051	0.057	0.054	0.077	0.110	0.233	0.320	0.455	0.555	0.039	0.053	0.084	0.088	0.101	0.098
	Max	0.062	0.077	0.097	0.099	0.106	0.121	0.333	0.222	0.324	0.412	0.560	0.667	0.105	0.114	0.149	0.160	0.178	0.205
6	Avg	0.106	0.124	0.141	0.147	0.143	0.128	0.122	0.188	0.288	0.367	0.451	0.528	0.113	0.149	0.189	0.210	0.217	0.206
	Max	0.272	0.284	0.288	0.320	0.278	0.236	0.215	0.264	0.417	0.507	0.565	0.612	0.240	0.274	0.341	0.392	0.373	0.341
9	Avg	0.100	0.103	0.132	0.134	0.133	0.121	0.139	0.183	0.320	0.408	0.501	0.537	0.116	0.132	0.187	0.202	0.210	0.197
	Max	0.230	0.242	0.328	0.311	0.299	0.277	0.266	0.281	0.391	0.469	0.656	0.691	0.247	0.260	0.357	0.374	0.411	0.395
12	Avg	0.174	0.173	0.170	0.172	0.162	0.171	0.206	0.264	0.354	0.464	0.530	0.590	0.189	0.209	0.230	0.251	0.248	0.265
	Max	0.240	0.268	0.265	0.252	0.268	0.243	0.381	0.390	0.485	0.588	0.625	0.691	0.294	0.318	0.343	0.353	0.375	0.360
15	Avg	0.196	0.190	0.201	0.228	0.227	0.205	0.213	0.261	0.345	0.428	0.497	0.532	0.204	0.220	0.254	0.298	0.312	0.296
	Max	0.358	0.365	0.370	0.368	0.382	0.367	0.320	0.364	0.440	0.520	0.602	0.610	0.338	0.364	0.402	0.431	0.467	0.458
18	Avg	0.219	0.228	0.241	0.253	0.248	0.241	0.221	0.271	0.357	0.419	0.514	0.563	0.220	0.248	0.288	0.315	0.335	0.338
	Max	0.255	0.268	0.286	0.283	0.298	0.277	0.312	0.329	0.444	0.583	0.639	0.692	0.281	0.295	0.348	0.381	0.406	0.396
21	Avg	0.244	0.260	0.255	0.289	0.263	0.261	0.283	0.315	0.367	0.473	0.501	0.536	0.262	0.285	0.301	0.359	0.345	0.351
	Max	0.486	0.494	0.495	0.490	0.489	0.456	0.489	0.346	0.426	0.549	0.571	0.615	0.487	0.407	0.458	0.518	0.527	0.524
24	Avg	0.309	0.299	0.311	0.332	0.312	0.281	0.293	0.343	0.412	0.469	0.536	0.588	0.301	0.319	0.354	0.389	0.394	0.380
	Max	0.413	0.398	0.400	0.392	0.391	0.366	0.355	0.410	0.476	0.574	0.593	0.649	0.382	0.404	0.435	0.466	0.471	0.468
رفتار میانگین		0.172	0.177	0.188	0.201	0.193	0.183	0.194	0.242	0.335	0.419	0.498	0.554	0.181	0.202	0.236	0.264	0.270	0.266
بهترین رفتار		0.486	0.494	0.495	0.490	0.489	0.456	0.489	0.410	0.485	0.588	0.656	0.692	0.487	0.407	0.458	0.518	0.527	0.524
رتبه														6	5	4	3	1	2

 

جدول (5): مقایسه مدل انتشار SC-B با احتمالات تأثیر متفاوت در مجموعه داده Alpha 

معیار			دقت													فراخوانی													امتیاز اِف
کاربر#	شاخص	SC-B		SC-B (P1)		SC-B (P2)		SC-B (P3)		SC-B (P4)		SC-B (P5)		SC-B			SC-B (P1)		SC-B (P2)		SC-B (P3)		SC-B (P4)		SC-B (P5)		SC-B			SC-B (P1)		SC-B (P2)		SC-B (P3)		SC-B (P4)		SC-B (P5)
3	Avg	0.089		0.043		0.059		0.053		0.073		0.064		0.122			0.113		0.257		0.308		0.528		0.614		0.103			0.062		0.096		0.090		0.128		0.116
	Max	0.120		0.100		0.102		0.139		0.171		0.141		0.274			0.250		0.368		0.474		0.694		0.867		0.167			0.143		0.160		0.215		0.274		0.243
6	Avg	0.102		0.138		0.137		0.145		0.132		0.140		0.135			0.291		0.413		0.577		0.644		0.749		0.116			0.187		0.206		0.232		0.219		0.236
	Max	0.257		0.210		0.217		0.206		0.208		0.187		0.300			0.431		0.578		0.714		0.765		0.863		0.277			0.282		0.316		0.320		0.327		0.307
9	Avg	0.117		0.128		0.155		0.154		0.151		0.141		0.149			0.259		0.407		0.482		0.555		0.659		0.131			0.171		0.225		0.233		0.237		0.232
	Max	0.265		0.287		0.291		0.303		0.306		0.276		0.333			0.382		0.676		0.592		0.737		0.750		0.295			0.328		0.407		0.401		0.432		0.404
12	Avg	0.224		0.204		0.222		0.216		0.212		0.209		0.215			0.341		0.458		0.517		0.579		0.671		0.219			0.255		0.299		0.305		0.310		0.319
	Max	0.357		0.369		0.403		0.373		0.365		0.334		0.310			0.429		0.571		0.619		0.676		0.762		0.332			0.397		0.473		0.465		0.474		0.464
15	Avg	0.218		0.262		0.276		0.290		0.269		0.272		0.205			0.307		0.383		0.470		0.504		0.606		0.211			0.283		0.321		0.359		0.351		0.375
	Max	0.331		0.329		0.376		0.398		0.340		0.361		0.333			0.417		0.440		0.573		0.575		0.717		0.332			0.368		0.405		0.470		0.427		0.480
18	Avg	0.197		0.268		0.263		0.273		0.275		0.258		0.261			0.361		0.432		0.497		0.578		0.633		0.225			0.308		0.327		0.352		0.373		0.367
	Max	0.296		0.471		0.446		0.389		0.444		0.422		0.330			0.414		0.496		0.584		0.663		0.692		0.312			0.441		0.470		0.467		0.532		0.524
21	Avg	0.323		0.333		0.343		0.335		0.333		0.323		0.330			0.409		0.496		0.558		0.618		0.697		0.326			0.367		0.406		0.419		0.433		0.441
	Max	0.466		0.475		0.455		0.448		0.454		0.455		0.410			0.491		0.569		0.618		0.671		0.768		0.436			0.483		0.506		0.519		0.542		0.571
24	Avg	0.330		0.364		0.366		0.374		0.367		0.363		0.289			0.379		0.425		0.498		0.543		0.630		0.308			0.371		0.393		0.427		0.438		0.461
	Max	0.438		0.494		0.513		0.476		0.494		0.481		0.349			0.512		0.464		0.586		0.598		0.700		0.388			0.503		0.487		0.525		0.541		0.570
رفتار میانگین			0.200		0.218		0.228		0.230		0.227		0.221		0.213			0.308		0.409		0.488		0.569		0.657		0.205			0.251		0.284		0.302		0.311		0.318
بهترین رفتار			0.466		0.494		0.513		0.476		0.494		0.481		0.410			0.512		0.676		0.714		0.765		0.867		0.436			0.503		0.506		0.525		0.542		0.571
رتبه																												6			5		4		3		2		1

 

شکل (3): مقایسه کلی روش پیشنهادی با روش­های پیشین بر اساس معیار ارزیابی میانگین امتیاز اِف 

 

 

مراجع

[1] C. Aslay, L. V. Lakshmanan, W. Lu, and X. Xiao, "Influence maximization in online social networks," in Proceedings of the eleventh ACM international conference on web search and data mining, 2018, pp. 775-776.

[2] Y. Li, W. Chen, Y. Wang, and Z.-L. Zhang, "Influence diffusion dynamics and influence maximization in social networks with friend and foe relationships," in Proceedings of the sixth ACM international conference on Web search and data mining, 2013, pp. 657-666.

[3] N. Girdhar and K. Bharadwaj, "Signed social networks: a survey," in International Conference on Advances in Computing and Data Sciences, 2016, pp. 326-335: Springer.

[4] M. Kaya, J. Kawash, S. Khoury, and M.-Y. Day, Social network based big data analysis and applications. Springer, 2018.

[5] S. Peng, S. Yu, and P. Mueller, "Social networking big data: Opportunities, solutions, and challenges," vol. 86, ed: Elsevier, 2018, pp. 1456-1458.

[6] M. Richardson and P. Domingos, "Mining knowledge-sharing sites for viral marketing," in Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, 2002, pp. 61-70.

[7] E. Even-Dar and A. Shapira, "A note on maximizing the spread of influence in social networks," Information Processing Letters, vol. 111, no. 4, pp. 184-187, 2011.

[8] S. Kumar, A. Mallik, A. Khetarpal, and B. Panda, "Influence maximization in social networks using graph embedding and graph neural network," Information Sciences, 2022.

[9] K. Senanayaka, "Impact of Social Network Advertising towards Consumer Purchase Intention (Special Reference to Apparel Products Advertising in Facebook)," Uva Wellassa University of Sri Lanka, 2017.

[10] H. Wu, S. Wang, and H. Fang, "LP-UIT: A Multimodal Framework for Link Prediction in Social Networks," in 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), 2021, pp. 742-749: IEEE.

[11] M. H. Nadimi-Shahraki and M. Adami-Dehkordi, "K-indicators Method for Community Detection in Social Networks," Int. J. Advance Soft Compu. Appl, vol. 8, no. 3, pp. 137-159, 2016.

[12] J. Yang, C. Yao, W. Ma, and G. Chen, "A study of the spreading scheme for viral marketing based on a complex network model," Physica A: Statistical Mechanics and its Applications, vol. 389, no. 4, pp. 859-870, 2010.

[13] M. Alshahrani, Z. Fuxi, A. Sameh, S. Mekouar, and S. Huang, "Efficient Algorithms based on Centrality Measures for Identification of Top-K Influential Users in Social Networks," Information Sciences, 2020.

[14] J. Cheriyan and G. Sajeev, "Spreadmax: a scalable cascading model for influence maximization in social networks," in 2018 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 2018, pp. 1290-1296: IEEE.

[15] C. Wang, Y. Liu, X. Gao, and G. Chen, "A Reinforcement Learning Model for Influence Maximization in Social Networks," in International Conference on Database Systems for Advanced Applications, 2021, pp. 701-709: Springer.

[16] O. Gil-Or, "The potential of Facebook in creating commercial value for service companies," Advances in Management, vol. 3, no. 2, pp. 20-25, 2010.

[17] Ö. OKAT and K. KADİRHAN, "ARTIFICIAL INTELLIGENCE-ASSISTED PROGRAMMATIC ADVERTISING," New Communication Approaches in the Digitalized World, p. 87, 2020.

[18] 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.

[19] 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.

[20] J. Zhang and P. S. Yu, "Information diffusion," in Broad Learning Through Fusions: Springer, 2019, pp. 315-349.

[21] D. Kempe, J. Kleinberg, and É. Tardos, "Influential nodes in a diffusion model for social networks," in International Colloquium on Automata, Languages, and Programming, 2005, pp. 1127-1138: Springer.

[22] Y. Ni, L. Xie, and Z.-Q. Liu, "Minimizing the expected complete influence time of a social network," Information Sciences, vol. 180, no. 13, pp. 2514-2527, 2010.

[23] A. Goyal, F. Bonchi, and L. V. Lakshmanan, "Learning influence probabilities in social networks," in Proceedings of the third ACM international conference on Web search and data mining, 2010, pp. 241-250.

[24] M. Hosseini-Pozveh, K. Zamanifar, and A. R. Naghsh-Nilchi, "Assessing information diffusion models for influence maximization in signed social networks," Expert Systems with Applications, vol. 119, pp. 476-490, 2019.

[25] S. Ahmed and C. Ezeife, "Discovering influential nodes from trust network," in Proceedings of the 28th annual acm symposium on applied computing, 2013, pp. 121-128.

[26] S. Kumar, B. Hooi, D. Makhija, M. Kumar, C. Faloutsos, and V. Subrahmanian, "Rev2: Fraudulent user prediction in rating platforms," in Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, 2018, pp. 333-341.

[27] S. Kumar, F. Spezzano, V. Subrahmanian, and C. Faloutsos, "Edge weight prediction in weighted signed networks," in 2016 IEEE 16th International Conference on Data Mining (ICDM), 2016, pp. 221-230: IEEE.

69

نشریه تحلیل مدارها، داده ها و سامانه ها - سال اول- شماره سوم – پاییز 1402

 

---