شناسایی گره‌های مؤثر در شبکه‌های اجتماعی با ترکیب روش‌های مرکزیت و فعالیت گره

کریمی, علی; بسطامی, اسماعیل; نعمتی, مهران; صالح اصفهانی, محمود

شناسایی گره‌های مؤثر در شبکه‌های اجتماعی با ترکیب روش‌های مرکزیت و فعالیت گره

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

نویسندگان

¹ دانشگاه جامع امام حسین (ع)

² مربی و پژوهشگر دانشگاه جامع امام حسین (ع)

³ دانشجوی کارشناسی ارشد دانشگاه جامع امام حسین(ع)

⁴ عضو هیات علمی دانشگاه جامع امام حسین (ع)

چکیده

دنیای امروز تبدیل به یک محیط رقابتی در همه زمینه‌ها مانند سیاست، اقتصاد، مسائل اجتماعی، عقاید و مانند این‌ها شده است که برای پیشبرد اهداف خود از ابزار شبکه‌های اجتماعی استفاده می‌کنند. محققین برای رسیدن به این اهداف توسط شبکه‌های اجتماعی از بیشینه‌سازی نفوذ (IM) بهره می‌برند. وظیفه بیشینه‌سازی، شناسایی گره‌های مؤثری است که تحت عنوان گره‌های آغازگر شناخته می‌شوند و یک راهبرد برای رسیدن به بیشترین انتشار اطلاعات و یا کمترین اپیدمی با کمترین هزینه است. بیشینه‌سازی یک مسئله NP-hard است. محققان برای شناسایی گره‌های مؤثر به دنبال روش‌هایی برای کاهش پیچیدگی و دقت شناسایی قابل قبولی هستند؛ بنابراین در این تحقیق برای فائق آمدن به پیچیدگی مسئله و در عین حال بالا بردن دقت شناسایی، روشی جدید با ترکیب مرکزیت - فعالیت ارائه می‌شود. در این روش به‌صورت سراسری محدودیتی بر روی گراف شبکه برای استخراج گره‌ها توسط روش مرکزیت ایجاد می‌شود در ادامه، تحلیل گراف توسط روش فعالیت بروی گره‌های محلی استخراج شده صورت می‌گیرد. امتیاز تحلیل فعالیت با امتیاز روش مرکزیت ترکیب می‌شود که منتج به نمایش گره‌های مؤثر می‌شود. روش پیشنهادی با روش‌هایی نظیر Page Rank و مرکزیت نزدیکی مقایسه می‌شود و نتایج حاکی از آن است که روش پیشنهادی از نظر دقت در نقاط پایین بهتر از هر دو عمل کرده است و از طرفی توانسته است پیچیدگی پایین‌تری نسبت به هر دو داشته باشد. در آینده برای بالا بردن دقت در نقاط بالا می‌توان در مرحله تحلیل فعالیت از مفاهیم امتیازدهی تکراری استفاده نمود.

کلیدواژه‌ها

20.1001.1.23224347.1399.8.3.1.5

عنوان مقاله [English]

Identifying Influential Nodes in Social Networks by Integrating the Centrality Method and Node Activity

نویسندگان [English]

A. Karimi ¹
E. Bastami ²
M. Nemati ³
M. Saleh Esfehani ⁴

¹ ihu

² ihu

³ ihu

⁴ ihu

چکیده [English]

Nowadays, social networks have become a strong tool among researchers in addition to their social functions. This tool has many applications in identifying crimes, criminals and terrorists, solving epidemic problems, successful marketing and other topics in various fields. The researchers are using the influence maximization (IM) to achieve these goals. The task of maximization is to identify the influential nodes that are known as the seed nodes. It is a strategy to achieve the maximum information diffusion or minimum epidemy with minimal cost. Since maximization is an NP-hard problem, researchers are looking for ways to reduce the complexity and acceptable identification accuracy by identifying influential nodes. Therefore, to overcome the complexity and increase the identification accuracy, in this research a new method with activity-centrality combination is proposed. In this approach, to extract nodes by the centrality method a total constraint is constructed on the network graph in order to proceed to the local nodes extracted from the node activity analysis. The results of analyzing the activity of each node are combined with its centrality method score which ultimately leads to the identification of influential nodes. The proposed method is compared with other methods such as PageRank and Closeness Centrality methods, and the evaluation results show that whilst having a lower complexity, the proposed method is better than both in terms of accuracy. In the future, the concepts of repetitive scoring can be used to further enhance the accuracy of the activity analysis phase.

کلیدواژه‌ها [English]

Influence
Influential Nodes
Influence Maximization (IM)
Centrality
Activity

مراجع

[1] Z. Sun, et al., “Identifying influential nodes in complex networks based on weighted formal concept analysis,” IEEE Access, vol. 5, pp. 3777-3789, 2017.##

[2] K. Taha and P. D. Yoo, “Using the spanning tree of a criminal network for identifying its leaders,” IEEE Transactions on Information Forensics and Security, vol. 12, no. 2, pp. 445-453, 2016.##

[3] A.-L. Barabási, “Scale-free networks: a decade and beyond,” science, vol. 325(5939), pp. 412-413. 2009.##

[4] Y. Sun, et al, “Key nodes discovery in large-scale logistics network based on MapReduce,” In 2015 IEEE International Conference on Systems, Man, and Cybernetics, IEEE, 2015.##

[5] S. Singh, N. Mishra, and S. Sharma, “Survey of various techniques for determining influential users in social networks,” In 2013 IEEE International Conference on Emerging Trends in Computing, Communication and Nanotechnology (ICECCN), IEEE, 2013.##

[6] R. Rabade, N. Mishra, and S. Sharma, “Survey of influential user identification techniques in online social networks,” In Recent advances in intelligent informatics, Springer, pp. 359-370, 2014.##

[7] G. Spadon, et al., “Behavioral Characterization of Criminality Spread in Cities,” In ICCS, 2017.##

[8] J. Kim, S. Rasouli, and H. J. Timmermans, “Social networks, social influence and activity-travel behaviour: a review of models and empirical evidence,” Transport Reviews, vol. 38, no. 4, pp. 499-523, 2018.##

[9] T. Bian, J. Hu, and Y. Deng, “Identifying influential nodes in complex networks based on AHP,” Physica A: Statistical Mechanics and its Applications, vol. 479, pp. 422-436, 2017.##

[10] F. Kazmi, W. H. Butt, and A. Saeed, “Evaluation of Role Detection Approaches in Terrorist Networks. in Proceedings of the 2018 2nd International Conference on Management Engineering,” Software Engineering and Service Sciences, 2018.##

[11] M. Doo and L. Liu “Extracting top-k most influential nodes by activity analysis,” In Proceedings of the 2014 IEEE 15th International Conference on Information Reuse and Integration (IEEE IRI 2014), IEEE, 2014.##

[12] M. Nouh and J. R. Nurse, “Identifying key-players in online activist groups on the facebook social network,” In 2015 IEEE International Conference on Data Mining Workshop (ICDMW), IEEE, 2015.##

[13] P. Hu and T. Mei, “Ranking influential nodes in complex networks with structural holes,” Physica A: Statistical Mechanics and its Applications, vol. 490, pp. 624-631, 2018.##

[14] R. C. Gunasekara, “Identification of key players in networks using multi-objective optimization and its applications,” 2016.##

[15] R. Albert and A.-L. Barabási, “Statistical mechanics of complex networks. Reviews of modern physics,” vol. 74, no. 1, p. 47, 2002.##

[16] A. Bickle, “The k-cores of a graph,” 2010.##

[17] V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” Physical review letters, vol. 87, no. 19, p. 198701, 2001.##

[18] A. N. Langville and C. D. Meyer, “Google's PageRank and beyond: The science of search engine rankings,” Princeton university press, 2011.##

[19] L. C. Freeman, “A set of measures of centrality based on betweenness,” Sociometry, pp. 35-41, 1977.##

[20] P. Bonacich, “Some unique properties of eigenvector centrality,” Social networks, vol. 29, no. 4, pp. 555-564, 2007.##

[21] Z.-M. Han, et al., “Ranking key nodes in complex networks by considering structural holes, Acta physica sinica,” vol. 64, no. 5, p. 058902, 2015.##

[22] S. Brin and L. Page, “The anatomy of a large-scale hypertextual web search engine,” 1998.##

[23] Dataset: http://www.delicious.com, ACM, New York, NY, USA, 2011.##