لینک گیت هاب پروژه
گروه‌های دوستان در شبکه‌ی اجتماعی برای نیاز به تعریف و توضیح ندارد. چیزی شبیه به همان «حلقه‌های» و یا لیست دوستان در فیسبوک و توئیتر که به شما در سازمان‌دهی روابط خود با افراد در شبکه‌های اجتماعی کمک می‌کنند. این حلقه‌ها ممکن است کاملا جدا از هم باشند، و یا این که با هم هم‌پوشانی داشته باشند، و یا حتی به صورت تو در تو و سلسله مراتبی با هم ارتباط داشته باشند.
هدف از این پروژه بدست آوردن خودکار حلقه‌های دوستان در شبکه اجتماعی است. در واقع شما لیستی از کاربران در شبکه اجتماعی را به عنوان ورودی در اختیار خواهید گرفت، و با روش و الگوریتمی که در طول پروژه توسعه می‌دهید، برای هر کدام از این کاربران حلقه‌‌ای از دوستان احتمالی در شبکه اجتماعی را پیدا می‌کنید.
برای اطلاعات بیشتر و دریافت مجموعه داده به این صفحه مراجعه کنید.

۱. مقدمه

امروزه شبکه های اجتماعی ما بسیار گسترده و بهم ریخته شده اند و درحال حاضر هیچ راه مناسبی برای مدیریت و دسته بندی آن ها وجود ندارد. البته بعضی از شبکه های اجتماعی به کاربران این امکان را داده اند تا خودشان دوستانشان را در حلقه های اجتماعی ( مانند حلقه ها در google+ و لیست دوستان در facebook و twitter ) دسته بندی کنند. بهرحال این روش راهی مناسب به نظر نمی رسد چرا که با اضافه شدن افراد دیگر به دوستان باید این حلقه ها توسط کاربران بروزرسانی گردند.
پس ما به دنبال طراحی سیستمی هستیم که قابلیت یادگیری و شناسایی افراد را داشته باشد و بتواند به صورت خودکار حلقه های اجتماعی را تشکیل داده و آن ها را بروز رسانی کند.
در این پروژه ما اطلاعات یک شخص و دوستان وی در یک شبکه اجتماعی را داریم و هدف ما پیدا کردن حلقه های اجتماعی شخص مورد نظر است که هر حلقه زیر مجموعه ای از دوستان شخص می باشد.
همان طور که در شکل زیر مشاهده می شود شخص با u و دوستان وی با v مشخص گردیده اند و هدف ما پیدا کردن حلقه های نمایش داده شده است.

۱.۱. شرح مسئله

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

۲. کارهای مرتبط

۲.۱. Clustering

در روش خوشه بندی یا clustering مدلی برای ایجاد حلقه ها با ویژگی های زیر تعریف می شود:

1. راس هایی که در یک حلقه قرار دارند باید ویژگی ها یا جنبه های یکسانی داشته باشند

2. حلقه های مختلف باید براساس ویژگی های متفاوتی شکل گرفته باشند مثلا حلقه ی خانوادگی یا حلقه ی افراد یک دانشگاه

3. حلقه ها می توانند با یکدیگر تداخل داشته باشند و همچنین حلقه های قوی تر نیز میتوانند داخل حلقه های ضعیف تر شکل بگیرند

ورودی این مدل برای هر کاربر مجوعه V که رئوس متصل به u ( کاربر مورد نظر ) و مجموعه E که شامل تمام یال هایی می باشد که میان مجموعه V وجود دارد به همراه پروفایل تمام اعضای مجموعه V است.
هدف این روش پیش بینی کردن مجموعه نهایی C ( حلقه های کاربر ) میباشد

و همچنین مشخص کردن پارامتر
که نمایش دهنده این می باشد که حلقه بر اساس چه ویژگی یا جنبه هایی تشکیل شده است.
همچنین از پارامتر
به عنوان نمایش دادن میزان شباهت پروفایل دو کاربر x و y استفاده شده است.
در قدم اول ابتدا هر یک از رئوس گراف را یک خوشه در نظر میگیریم و سپس از فرمولی که در زیر آمده برای تشخیص اینکه آیا دو خوشه میتوانند با هم ترکیب شوند و یا خیر استفاده میشود. این روش را تا جایی که مجموعه C تغییری نکند انجام میدهیم.

که سیگمای اول شامل تمام حلقه هایی است که هر دو راس در آن ها قرار میگیرند و سیگمای دوم بقیه ی حلقه ها را شامل می شود.
در این فرمول مقدار
ضریب تناسبی برای متعادل کردن مقدار سیگما ها می باشد.
ایده این فرمول آن است که اگر مقدار پارامتر

که نمایش دهنده میزان شباهت دو راس با یکدیگر بر اساس ویژگی مورد نظر می باشد بالا باشد یعنی هر دو راس متعلق به یک خوشه می باشند و اگر پایین باشد یعنی متعلق به خوشه ی مورد نظر نیستند[1].

۲.۲. Infomap

در روش infomap با استفاده از روش خوشه بندی با این تفاوت نسبت به روش قبل که می تواند بر روی گراف های جهت دار و وزن دار نیز اعمال شود دو الگوریتم برای خوشه بندی داده ها ارائه می شود که به طور مختصر به شرح آن ها می پردازیم[2].

• الگوریتم Two-level clustering
  هسته کاری این الگوریتم خوشه بندی براساس map equation است و ابتدا هر یک از راس های گراف را یک خوشه درنظر می گیرد و در هر مرحله هرکدام از خوشه ها که شباهت زیادی با یکدیگر دارند ادغام می کند.
  این روش از این نظر مناسب نیست که هر گاه دو خوشه با یکدیگر ترکیب شوند یک خوشه ی جدید به وجود می آید و اثری از خوشه های قبلی دیگر نیست و ممکن است که اگر خوشه های قبلی با خوشه های دیگری در مراحل بعد ترکیب شوند به جواب بهتر و دارای دقت بالاتری دست پیدا کنیم[2].
  برای رفع این مشکل دو متد زیر در نظر گرفته شده است:
  1. متد Submodule movements
  این متد به ما قابلیت تجزیه ی یک خوشه به زیر خوشه هایش که در مرحله قبل تشکیل شده اند را می دهد.
  2. متد Single-node movements
  این متد به ما قابلیت تجزیه ی خوشه و جدا کردن یک راس و درنظر گرفتن راس به عنوان خوشه ی مستقل را می دهد.

• الگوریتم Multi-level clustering
  این الگوریتم مدل کامل تری از الگوریتم قبل بوده و متد هایی که در این الگوریتم تعریف می شوند می توانند به جای تجزیه ی خوشه به یک مرحله قبل خوشه را به مقدار دلخواه تجزیه کنند.

توسط این دو متد می توان در هر مرحله و هر جا که یک خوشه ترکیب شد چک کنیم که آیا بهترین ترکیب برای خوشه بندی را انتخاب کرده ایم و یا خیر!

۲.۳. Martelot

روش Le Martelot نیز همانند روش های پیشین از الگوریتم های خوشه بندی اطلاعات استفاده می کند و قابل اجرا بر روی گراف های جهت دار و وزن دار می باشد.
در این روش با استفاده از [4]Newman's modularity که فرمولی برای محاسبه میزان تفاوت های یک راس یا یک خوشه با دیگر خوشه ها می باشد به خوشه بندی اطلاعات می پردازیم.
این فرمول خوشه بندی برای حل مسئله ی تشخیص گروه ها مناسب نیست چرا که در شناسایی گروه های کوچک و متداخل ضعیف عمل می کند.
برای حل این مشکل در روش Martelot ضرایب مختلفی به میزان متفاوت بودن خوشه ها با یکدیگر در ماژولاریتی داده می شود و الگوریتم خوشه بندی را چندین بار اجرا می کند و خوشه بندی بهینه را انتخاب میکند [5].

۲.۴. Louvain

متد Louvain یک متد نسبتا سریع برای پیدا کردن گروه ها در شبکه های بزرگ است.
در این متد با استفاده از روش های حریصانه بر روی ماژولاریتی [4] آن را بهینه کرده و به خوشه بندی راس های گراف می پردازد.
این بهینه سازی در 2 مرحله انجام می شود:

1. با بهینه سازی محلی متد به دنبال گروه های کوچک میگردد.

2. سپس با ادغام گروه های کوچک که توانایی ایجاد گروه های بزرگتر را دارند خوشه بندی را ادامه می دهد.

این مراحل را مرتبا تکرار می شود تا به مقدار ماکزیمم ماژولاریتی برسیم [6].

۲.۵. Combo

الگوریتم های جستجوی موجود برای تشخیص گروه های شبکه های اجتماعی براساس یک یا چند روش زیر کار می کنند:

1. ادغام : ادغام و ترکیب دو جامعه مشابه

2. تقسیم : تقسیم و تجزیه ی دو جامعه ی متفاوت

3. نوترکیبی : انتقال و حرکت کردن یک راس بین دو جامعه ی مجزا

الگوریتم combo با بهره گیری از هر ۳ روش بالا به حل مساله تشخیص گروه های اجتماعی می پردازد که روش انجام کار این الگوریتم را توضیح می دهیم.
پس از انتخاب شدن یک حالت اولیه از یک شبکه اجتماعی موجود ( منظور از حالت اولیه ،جوامع موجود در ابتدای برنامه است که می توانند هر جوامع تصادفی انتخاب شوند و یا در ابتدای کار تمام شبکه یک جامعه در نظر گرفته شود و در مراحل بعدی تقسیم شود و یا هر کدام از رئوس یک جامعه جدا در نظر گرفته شوند و در مراحل بعد ادغام گردند ) مراحل زیر تا زمانی که تابع هدف به امتیاز بالا و نتایج مطلوب دست پیدا کند انجام می شود[3]:

1. برای هر جامعه بهترین توزیع مجدد ممکن برای تمام رئوس به جامعه ی مقصد آن ها ( اگر جامعه ی مقصد موجود نباشد جامعه جدید ایجاد می گردد ) محاسبه می شود. به زبان ساده تر در این مرحله وضعیت یک جامعه بررسی می شود که آیا جامعه مشخص شده مستقل از بقیه ی جوامع موجود است یا نیاز دارد که تغییرات روی آن صورت بگیرد[3].

2. در این مرحله اگر جامعه نیاز به تغییر داشته باشد بهترین عمل ادغام/تقسیم/نوترکیبی انتخاب شده و اعمال می شود[3].

۳. آزمایش و نتایج

۳.۱. Data Set

مجموع دادگان ورودی این مساله یک گراف شبکه است که به صورت های مختلف می تواند تعریف شود.

1. فرمت Link list
   این نوع ورودی دارای N خط می باشد که به تعداد یال های گراف شبکه است و در هر خط هر یال به صورت source target weight تعریف می شود. که source و target رئوس مبدا و مقصد را مشخص می کنند و weight نیز نمایش دهنده وزن یال است که عددی نا منفی است و می تواند نباشد که در این صورت به صورت پیش فرض مقدار ۱ در نظر گرفته می شود.
   همان طور که مشاهده می شود توسط این نوع به سادگی می توان گراف های جهت دار و وزن دار را نیز پشتیبانی کرد.

2. فرمت Pajek
   این نوع ورودی راس ها و یال های گراف شبکه را در دو قسمت جداگانه همانند زیر در یک فایل مشخص می کند:

   *Vertices N
   1 "V1"
   2 "V2"
   3 "V3"
   ...

   *Edges M
   1 2 1
   1 5 0.33
   4 3 0.5
   2 3 1
   ...

در بخش رئوس که با Vertices N* مشخص می شود N نمایش دهنده ی تعداد رئوس گراف است و در N خط بعد در هر خط ابتدا id راس و سپس label آن می آید.
در بخش یال ها نیز که با Edges M* و یا Arcs M* مشخص می شود M نمایش دهنده ی تعداد یال های گراف است و M خط بعد همانند فرمت Link List تعریف می شود.

ورودی آزمایش شده ابتدایی شبکه ی کوچکی از فیسبوک با 4,039 راس و 88,234 یال و از هر دو نوع فرمت Link list و Pajek می باشد.

۳.۲. Methods of Implementation

در این قسمت به بررسی و انجام آزمایش الگوریتم های ارائه شده روی مجموع دادگان پرداخته شده و از کدهای موجود و آماده ی آنان استفاده شده است. (لینک کدها)
روش کامپایل و اجرای هر الگوریتم در فایل readme که داخل فولدر هر کدام قرار دارد آورده شده است.

• ۳.۲.۱. Infomap
  با انجام این روش بر روی دادگان facebook به نتایج و خروجی های زیر دست یافتیم که در گیت هاب نیز موجود است. برای مشاهده نوع فرمت فایل های خروجی به اینجا مراجعه کنید.
  تعداد ۷ انجمن پیدا شد که توسط ۱۲ یال با یکدیگر در ارتباطند. این ۷ انجمن با یکدیگر قابل ترکیب نیستند ولی توسط وزن یالی که بین آن هاست می توان تشخیص داد که چه مقدار به نسبت بقیه به یکدیگر شباهت دارند.
  

  

• ۳.۲.۲. Combo
  پس از انجام این روش بر روی دادگان facebook زمان زیادی را برای دریافت نتایج منتظر ماندم ( در حدود ۷۰ ثانیه ). در پایان کار نتایج و فایل خروجی این الگوریتم فایلی متنی است که تعداد خطوط آن به تعداد رئوس گراف می باشد و در هر خط تنها یک عدد نامنفی تولید شده است که نشان دهنده تعداد انجمن هایی است که راس مورد نظر در آن مشترک است.
  تعداد انجمن ها و همچنین اعضای این انجمن ها جزو نتایج و خروجی برنامه نیست!!

• ۳.۲.۳. Louvain
  نتایج خروجی برنامه ی نوشته شده برای متد Louvain به صورت یک فایل با فرمت tree. می باشد که برای تبدیل این فرمت به clu. این قطعه کد را نوشتم. چرا که برای نمایش خروجی به فرمت clu. نیازمندیم.
  با انجام این روش بر روی دادگان facebook به تعداد 17 انجمن مختلف دست پیدا کردم که در شکل زیر قابل مشاهده می باشد.
  

  

• ۳.۲.۴. Martelot
  با اجرای متد Le Martelot بر روی دیتاست facebook به خروجی زیر دست پیدا کردیم ( گیت هاب ) .
  این روش ۱۲ انجمن بر روی این دادگان پیدا کرد که در شکل زیر نمایان است.
  

  

۴. کارهای آینده

بررسی نتایج بدست آمده

تا اینجای کار روش های موجود را بر روی دادگان فیسبوک اجرا کردیم و برای هر کدام به نتایجی رسیدیم.
برای دقیق تر شدن نتایج اقدام به بررسی دادگان توییتر (اینجا) نیز کردم که متاسفانه به دلیل بالا بودن حجم آن رم کامپیوترم پر شد و در استفاده از تمام روش ها به ارور segmentation fault برخوردم.
برای بررسی دقت الگوریتم های مختلف نیازمند یک جواب بودم که با خروجی دیگر برنامه ها مقایسه کنم و میزان صحت روش های مختلف را اندازه گیری کنم ولی متاسفانه دسترسی به جواب صحیح برای دادگان فیسبوک نداشتم. البته طبق تحقیقات دانشگاه MIT بر روی همین دادگان و مقایسه روش ها با یکدیگر به نمودار رسیده اند.

با توجه به این نمودار که از نظر کیفیت و سرعت متدهای مختلف بررسی شده اند متد Combo دارای بالاترین کیفیت و متد Martelot بالاترین سرعت را دارا بوده است.
نکته حائز اهمیت نبودن روش Infomap است که دلیلش رو نمیدونم!
با توجه به گستردگی زیاد این روش و همچنین داشتن کد بسیار قوی که از انواع فرمت های ورودی و خروجی را پشتیبانی می کند و دارای option زیادی برای اجرای آن است به همراه داکیومنت بسیار قوی و کامل ، من استفاده از روش Infomap را درحال حاضر مناسب ترین روش برای پیدا کردن گروه های دوستان در شبکه های اجتماعی می دانم و به بقیه ی دوستان پیشنهاد می کنم.

۵. مراجع

[1] J. McAuley and J. Leskovec. Learning to Discover Social Circles in Ego Networks. NIPS, 2012.
[2] M. Rosvall, D. Axelsson, and C.T. Bergstrom. The map equation. Eur. Phys. J. Special Topics 178, 13, 2009.
[3] S. Sobolevsky, R. Campari, A. Belyi, and C. Ratti "General optimization technique for high-quality community detection in complex networks" Phys. Rev. E 90, 012811 2014.
[4] Newman, M.E.J. and Girvan, M. (2004) Finding and evaluating community structure in networks. Phys. Rev. E, 69, 026113.
[5] Le Martelot, E. and Hankin, C. (2013) Fast Multi-Scale Detection of Overlapping Communities using Local Criteria. Computing, Springer, 2014.
[6] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre. Fast unfolding of communities in large networks. J. Stat. Mech. (2008) P10008.