25573

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

دكتري

مهندسي كامپيوتر گرايش نرم‌افزار

1400

27 مهر 1400

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

مهندسي كامپيوتر

دامنه گسترده برنامه‌هاي كاربردي، تأثير مدل‌سازي و تحليل تحولات جوامع در شبكه‌هاي اجتماعي را به‌عنوان بخش مهمي از فرآيند تصميم‌گيري افزايش داده است. تجزيه‌وتحليل تغيير ساختار جوامع سبب درك الگوهاي تحولات و عواملي كه سبب اين تحولات مي‌گردند خواهد شد. آزمايش‌ها نشان مي‌دهد كه در واقعيت اغلب شاهد تحولات جزئي هستيم و يك جامعه شايد نتيجه يك رويداد جزئي باشد به‌عنوان‌مثال يك جز از يك جامعه با جزئي از يك جامعه ديگر تركيب شود و يك جامعه جديد تشكيل دهد. در اين رساله بر مبناي آنچه در واقعيت رخ مي‌د‌هد يك مجموعه بزرگ‌تر براي تحولات جوامع ارائه‌شده است. براي تشكيل زنجيرهاي تحولات جوامع، جوامع در پنجره‌هاي زماني مختلف با يكديگر مقايسه مي‌شوند. در اين رساله رويكردي ارائه‌شده است كه با استفاده از ساختار داده درهم ساز-نگاشت تطابق جوامع را بررسي مي‌كند. درنتيجه براي هر جامعه آن جامعه را فقط با جوامع مرتبط در پنجره‌هاي زماني قبلي مقايسه خواهد كرد، راه‌حل پيشنهادي زمان ردگيري تحولات جوامع را به طرز چشمگيري كاهش مي‌دهد، زيرا پيچيدگي زماني آن در حالت متوسط O(|رئوس|) است درحالي‌كه روش‌هاي رايج پيچيدگي زماني O(|رئوس|^2) دارند. همچنين روشي جديد براي بررسي انواع مختلف مشخصه‌هاي ساختاري جوامع و پيدا كردن زيرمجموعه‌اي مناسب از مشخصه‌هاي مهم جوامع به‌منظور پيش‌بيني آينده تحولات جوامع ارائه‌شده است. روش پيشنهادي دو مفهوم كليدي را براي يافتن ويژگي‌هاي برجسته تركيب مي‌كند: (1) اولويت‌بندي ويژگي‌ها بر اساس همبستگي سپيرمن آن‌ها با ساير ويژگي‌ها، اين مؤلفه ما را قادر مي‌سازد تا ويژگي‌هايي را بشناسيم كه مي‌توانند نمايانگر بقيه باشند و كشف كنيم كه كدام ويژگي‌ها در مقايسه با ديگران منحصربه‌فرد هستند. (2) آموزش يك يادگيرنده تقويت‌كننده و اولويت‌بندي ويژگي‌ها بر اساس فراواني استفاده از آن‌ها در فرآيند يادگيري براي درك اينكه كدام ويژگي‌ها ارزشمندتر هستند. درنهايت، ويژگي‌هاي مهم توسط رده‌بند جنگل تصادفي تعيين مي‌شود. درنتيجه براي پنجره‌هاي زماني بعدي مي‌توان فقط همين مشخصه‌هاي مهم و كاربردي را محاسبه كرد و به‌طور قابل‌توجهي هزينه محاسبه ويژگي‌ها را كاهش داد. راه‌حل پيشنهادي ازنظر تحليل آماري موردبررسي قرار گرفت و طبق آزمون رتبه فريدمن به همراه آزمون پسين مقايسه‌هاي چندگانه بونفروني نتايج به‌دست‌آمده با سطح اطمينان 95 درصد برتري راه‌حل پيشنهادي را نشان مي‌دهند. درنهايت شايان‌ذكر است كه در اين رساله تحولات جوامع در شبكه‌هاي اجتماعي مورد تجزيه‌وتحليل قرارگرفته است و روش‌هايي كاربردي براي كاهش زمان موردنياز براي شناسايي و پيش‌بيني تحولات جوامع ارائه‌شده است.

1400/09/08

An approach for identification and prediction of community evolution in dynamic social networks

10/19/2022 12:00:00 AM

The expanded domain of expert system applications has risen the impact of modeling and analysis of community evolution in social networks as an important part of the decision-making process. The analysis of community evolution will lead to an understanding of factors that cause these changes. Upon experimentation, we observed that a considerable portion of community evolution is partial events such as partial merge. Therefore, we define a broader set of community evolution to include partial events. Furthermore, we introduce ICEM, a novel method for Identification of Community Evolution by Mapping. ICEM determines community evolution by tracking community members, implemented with a hash-map. As a result, for each community, it will only be compared with the related communities in previous time windows. The proposed solution significantly reduces the time to follow the evolution of communities, because its time complexity is O(V), while the common methods have O(V^2) time complexity. Moreover, we present AFIF, Automatically Finding Important Features, an efficient solution to examine communities’ structural features and also to find a proper subset of promising features in order to predict the upcoming changes of social networks. AFIF combines two key concepts to find prominent features: (i)Prioritization of attributes based on their Spearman’s correlation with other features. This enables us to know the features that can represent the rest and to explore which features are unique compared to others. (ii)Training a boosting learner and prioritizing attributes based on their usage frequency in learning process to realize which features are more valuable. Eventually, important features are determined by random forest classifier. As a result, for the next time windows, only these important features can be calculated and the cost of calculating the properties can be significantly reduced. The AFIF results are statistically significant. The comparison of the prediction results gained by N algorithms for M datasets was carried out according to the Friedman rank test. In addition, an ad-hoc comparison was carried out, and the Bonferroni’s post-hoc multiple comparisons test was used (with 95% confidence level). Finally, it is worth mentioning that in this dissertation, the evolution of communities in social networks have been analyzed and practical methods to reduce the time complexity to identify and predict the developments of societies have been presented.

شبكه‌هاي اجتماعي پويا , شناسايي تحولات جوامع , پيش‌بيني تحولات جوامع

Dynamic social network , Identification of community evolution , Community evolution prediction