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

دكتري تخصصي

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

194226

دانشگاه علم و صنعت ايران

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

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