21867

21867

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

دكتري تخصصي

هوش مصنوعي و رباتيك

1398/11/16

دكتر مرتضي آنالويي

كامپيوتر

در شبكه‌هاي اجتماعي به مجموعه‌اي از اعضا كه ارتباطات قوي‌تري با يكديگر دارند، انجمن، مجمع يا خوشه گفته مي‌شود كه اطلاعات ارزشمندي را در مورد نوع ارتباط اعضا ، نحوه انتقال اطلاعات و نحوه توزيع افراد در شبكه اجتماعي ارائه مي‌كنند. شناسايي انجمن‌ها در تحليل شبكه‌هاي اجتماعي، تجارت الكترونيكي، سيستم‌هاي توصيه‌گر، پيش‌بيني لينك، پردازش زبان طبيعي و پزشكي كاربرد دارد. تاكنون الگوريتم‌هاي انجمن‌يابي مختلفي ارائه شده است اما هيچ كدام روش ايده‌آلي براي شناسايي انجمنها نيست. بنابراين استفاده از يك روش هم‌جوشي (Fusion method) جهت بهره‌گيري از نقاط قوت روشهاي مختلف و پوشاندن نقاط ضعف اين روشها، ايده خوبي به نظر مي‌رسد. رويكرد خوشه‌بندي توافقي (Consensus clustering) نيز يك روش هم‌جوشي است كه در آن مجموعه‌اي از الگوريتم‌هاي خوشه‌بندي پايه به صورت يك توافق (اِجماع) عمل كرده و خوشه‌بندي بهتري در راستاي افزايش پايداري انجمنها ارائه مي‌كنند. نوآوري ارائه شده در اين رساله شامل دو بخش است. در بخش اول، يك روش جديد به نام "تصويرسازيِ سريع" براي تبديل شبكه‌هاي دوبخشي به يك‌بخشي ارائه شده است كه به عنوان يك پيش‌پردازش هوشمند روي گراف شبكه، منجر به شناسايي پيوندهاي پايدار و مهم و حذف داده‌هاي كم ارزش‌تر مي‌گردد. در بخش دوم با استفاده از "تصويرسازيِ سريع"، يك "رويكرد توافقي" جديد (در قالب دو الگوريتم به نامهاي Mitra و Azar) براي شناسايي انجمنها ارائه شده است. به اين ترتيب كه پس از ايجاد يك گراف توافق دوبخشي، آن را با "تصويرسازي سريع"، (با هدف تركيب و فشرده‌سازي اطلاعات و تاكيد بر ارتباطات مهم)، به يك شبكه تك-بخشي تبديل مي‌كند. سپس يكي از روشهاي خوشه‌بندي پايه، انجمنهاي شبكه يك‌بخشي را آشكار مي‌سازد. جهت ارزيابي تصويرسازي سريع و رويكرد توافقي از معيارهاي رايجي نظير اطلاعات متقابل نرمال (NMI) و پيمانگي (Modularity) استفاده كرده و به بررسي كيفيت و مقايسه كارايي روش پيشنهادي با روشهاي پايه پرداخته‌ايم. به علاوه روش خود را با يك روش توافقي ديگر كه اخيرا ارائه شده است نيز، مقايسه نموده‌ايم. نتايج حاصل از بررسي‌هاي جامع در اين رساله نشان مي‌دهد كه رويكرد ما نسبت به روشهاي پايه و روش توافقي دوم، قادر به تشخيص ساختار انجمني گوياتري براي شبكه است و در بيشتر موارد، انجمنهاي شبكه را با كارايي بسيار بهتري (به خصوص براي شبكه‌هاي بزرگ و با ساختار پيچيده) به دست مي‌آورد. پس "تصويرسازي سريع" و "الگوريتم توافقي" ما، منجر به استخراج داده‌هاي ارزشمند ارتباطي، يافتن انجمنهاي مرغوب و گره‌هاي تاثيرگذار در شبكه شده است.

1399/02/17

Community Detection in Social Networks by Fusion Methods

2/5/2020 12:00:00 AM

In social networks there’s a set of members which has more strong relationships which is called a community or a cluster which represents valuable information about the type of relations between members, the type of transferring information and the kind of distribution of these members in social networks. The usage of community detection is in social network analysis, electronic commerce, decision support systems, link prediction, natural language processing and medical sciences. Several community detection methods have been proposed for clustering networks. However, none of them is ideal method for network clustering. Therefore, it seems a good idea to apply a fusion method to get the benefit from strengths of methods and cover their weaknesses. Consensus clustering approach is a fusion method in which a set of community detection algorithms are employed as a consensus and results in a better clustering that leads to increase the stability of communities. The innovation proposed in this thesis consists of two parts. In the first part a new method called "fast projection" is presented for converting bipartite networks to unipartite ones that results in detection of stable and important links and removing the less valuable data. In the second part, a new "consensus approach" (consists of Mitra and Azar algorithms) is proposed to detect communities by employing "fast projection". In this approach a bipartite consensus graph is built then fast projection converts the bipartite network to a unipartite network (in order to combine and compress information and emphasize on important links). After that, one of the base clustering methods detects the communities of the unipartite network. To evaluate fast projection and the consensus approach some popular criteria are used (such as NMI and Modularity) and we examine the quality and performance of the proposed method and base methods. Moreover, we compare our method with another consensus method which is recently proposed. The results of our comprehensive evaluation shows our approach is able to detect a more clear community structure for networks in comparison with base methods and the other consensus method and, it finds network communities more efficiently in most cases. Therefore, our fast projection and consensus algorithm lead to extract valuable relational data, detect qualified communities and effective nodes in graphs.