21152

۲۱۱۵۲

رديابي تكامل جوامع در شبكه هاي اجتماعي پويا بر اساس مقايسه جوامع

كارشناسي ارشد

نرم افزار

۱۳۹۵-۱۳۹۸

۱۳۹۸/۲/۳

دكتر حسن نادري

كامپيوتر

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

1398/07/16

Community evolution tracking in dynamic social networks based on community comparison

4/22/2020 12:00:00 AM

Social networks and relationships within them are changing over time. Identifying these changes and extracting the structural patterns of these networks is a subject that is of interest to many researchers. Communities that are formed in a social network will change over time. These changes can include communities shrinking, growing, merging them together, or even community dissolving over the lifetime of a network. To find these changes, a community must be seen from forming until dissolving and its status must be examined in different periods of time. This issue is raised as the problem of tracking community evolution in dynamic social networks. There are many approaches to identifying group developments in dynamic social networks. This thesis presents a new approach for tracking community evolution that model dynamic social network as a sequence of static networks in sequential time series and extract communities in these time steps. Then, using a locality sensitive hashing technique, compares communities to examine the changes in groups within the network. This technique allows a community to compare with communities whose similarity is more than a certain amount rather than comparing them to all communities of earlier periods. So this technique reduces the number of comparisons and runtime. Using this method while maintaining the accuracy of the algorithm at a high level causes a significant increase in the speed of execution of the algorithm comparing with the previous methods.