يك روش هرس جديد براي شناسايي گره‌هاي موثر در شبكه‌هاي اجتماعي

A New Pruning Method for Identifying Influential Nodes in Social Networks

شناسايي گره‌هاي موثر در شبكه‌هاي اجتماعي به منظور بيشينه سازي انتشار از اهميت بالايي برخوردار است. شبكه‌هاي اجتماعي، نوعي از داده‌هاي گرافي هستند كه در آنها هر گره معرف يك فرد و هر يال معرف ارتباط ميان دو فرد است. با توجه به آنكه افراد مرتبط در شبكه‌هاي اجتماعي، تحت تاثير يكديگر هستند و حجم اطلاعات وسيع روزانه توسط كاربران مختلف در شبكه‌هاي اجتماعي ارسال مي‌شود، تعيين افراد تاثير گذار در توليد و انتشار اطلاعات بسيار مهم است. استخراج كاربران موثر، به به صورت مسئله بيشينه سازي انتشار مدل مي‌شود. در اين مقاله، يك روش هرس پيشنهاد شده است تا بتوان در گراف كوچكتري به طور كاراتري گره‌هاي موثر را شناسايي كرد. بنابراين، پس از استخراج داده‌هاي شبكه‌هاي اجتماعي، يالهاي گراف توسط معيار مركزيت بينابيني يال وزن دار شده و سپس يالهايي كه وزني كمتر از ميانگين دارند هرس شده و با استفاده از معيارهاي مركزيت گره‌هاي موثر در گراف هرس شده انتخاب مي‌شوند. به منظور ارزيابي روش پيشنهادي، با استفاده از مدل انتشار آستانه خطي، زمان اجرا و متوسط تعداد گره‌هاي فعال شده براساس مجموعه‌اي از گره‌هاي فعال اوليه در مقايسه با الگوريتم‌هاي پايه مبتني بر مركزيت گزارش شده است. نتايج شبيه سازي حاكي از بهبود نسبي در نتايج بدست آمده است.

Identifying influential nodes to influence maximization plays an important role in social networks. Social networks are a type of graph data in which each node represents one person, and each edge represents a relationship between two people. Based on the relationship and interaction among people in social networks, they are influenced by each other, and different users in social networks propagate a large amount of information daily. Thus, it is essential to identify the influential people in spreading information. Identifying influential users is modeled as a problem of influence maximization. This paper proposes a pruning method to identify influential nodes effectively in a smaller graph. Therefore, after extracting the social network data, the edges of the graph are weighted by the edge betweenness centrality measure, and then the edges that weigh less than the average weight are pruned, and the influential nodes in the pruned graph are selected using any centrality measure. To evaluate the proposed pruning method, using the LTM diffusion model, the running time and the average number of activated nodes based on a set of initial active nodes compared to the baseline algorithms based on the centrality algorithm have been reported. The simulation results show a relative improvement in the results obtained.