خانم معصومه خیرخواه‌زاده دانشجوی دکترای جناب آقای دکتر مرتضی آنالویی روز چهارشنبه مورخ 1398/11/16 ساعت 10:30  از رساله دکتری خود تحت عنوان "شناسایی انجمن‌ها در شبکه‌های اجتماعی با روشهای ترکیبی" دفاع خواهند نمود.

 

ارائه ­دهنده:
معصومه خیرخواه‌زاده
  استاد راهنما:
  مرتضی آنالویی
  هیات داوران:

دکتر ناصر مزینی؛ دکتر بهروز مینایی مینایی بیدگلی؛ دکتر کامبیز بدیع؛ دکتر مسعود اسدپور
زمان : چهارشنبه  16 بهمن ماه 1398

  ساعت 10:30

  مکان: دانشکده مهندسی کامپیوتر- طبقه دوم- اتاق دفاعیه دکترا

چکیده پایان نامه :

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

Abstract:
 
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.
 
keyword: Community detection, Consensus clustering, Ensemble clustering, fast projection and bipartite networks.

  دانشکده مهندسی کامپیوتر مدیریت تحصیلات تکمیلی
  از اساتید بزرگوار، دانشجویان گرامی و دیگر متخصصان و علاقه مندان به موضوع دفاعیه دعوت
می شود با حضور خود موجبات غنای علمی و ارتقای کیفی را فراهم سازند.