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

[لینک گیت هاب پروژه](https://github.com/sina-bty/AI-community-detection)
گروه‌های دوستان در شبکه‌ی اجتماعی برای نیاز به تعریف و توضیح ندارد. چیزی شبیه به همان «حلقه‌های» و یا لیست دوستان در فیسبوک و توئیتر که به شما در سازمان‌دهی روابط خود با افراد در شبکه‌های اجتماعی کمک می‌کنند. این حلقه‌ها ممکن است کاملا جدا از هم باشند، و یا این که با هم هم‌پوشانی داشته باشند، و یا حتی به صورت تو در تو و سلسله مراتبی با هم ارتباط داشته باشند.
هدف از این پروژه بدست آوردن خودکار حلقه‌های دوستان در شبکه اجتماعی است. در واقع شما لیستی از کاربران در شبکه اجتماعی را به عنوان ورودی در اختیار خواهید گرفت، و با روش و الگوریتمی که در طول پروژه توسعه می‌دهید، برای هر کدام از این کاربران حلقه‌‌ای از دوستان احتمالی در شبکه اجتماعی را پیدا می‌کنید.
برای اطلاعات بیشتر و دریافت مجموعه داده به [این صفحه](https://www.kaggle.com/c/learning-social-circles) مراجعه کنید. 

# **۱. مقدمه**
امروزه شبکه های اجتماعی ما بسیار گسترده و بهم ریخته شده اند و درحال حاضر هیچ راه مناسبی برای مدیریت و دسته بندی آن ها وجود ندارد. البته بعضی از شبکه های اجتماعی به کاربران این امکان را داده اند تا خودشان دوستانشان را در **حلقه های اجتماعی** ( مانند حلقه ها در google+ و لیست دوستان در facebook و twitter ) دسته بندی کنند. بهرحال این روش راهی مناسب به نظر نمی رسد چرا که با اضافه شدن افراد دیگر به دوستان باید این حلقه ها توسط کاربران بروزرسانی گردند.
پس ما به دنبال طراحی سیستمی هستیم که قابلیت یادگیری و شناسایی افراد را داشته باشد و بتواند به صورت خودکار حلقه های اجتماعی را تشکیل داده و آن ها را بروز رسانی کند. 
در این پروژه ما اطلاعات یک شخص و دوستان وی در یک شبکه اجتماعی را داریم و  هدف ما پیدا کردن **حلقه های اجتماعی** شخص مورد نظر است که هر حلقه زیر مجموعه ای از دوستان شخص می باشد.
همان طور که در شکل زیر مشاهده می شود شخص با u و دوستان وی با v مشخص گردیده اند و هدف ما پیدا کردن حلقه های نمایش داده شده است.
![an ego-network with labled circles](https://boute.s3.amazonaws.com/145-ai.PNG)

با پیدا کردن این حلقه ها میتوانیم افرادی که در یک حلقه قرار دارند ولی با هم دوست نیستند ( راس های داخل یک حلقه که یالی میان آنان وجود ندارد ) را مانند سیستم people you may know در facebook به یکدیگر پیشنهاد دهیم.


# **۲. کارهای مرتبط**
# ۲.۱. روش خوشه بندیClustering
در روش خوشه بندی یا clustering مدلی برای ایجاد حلقه ها با ویژگی های زیر تعریف می شود:
1. راس هایی که در یک حلقه قرار دارند باید ویژگی ها یا جنبه های **یکسانی** داشته باشند
2. حلقه های مختلف باید براساس ویژگی های **متفاوتی** شکل گرفته باشند مثلا حلقه ی خانوادگی یا حلقه ی افراد یک دانشگاه
3. حلقه ها می توانند با یکدیگر **تداخل** داشته باشند و همچنین حلقه های **قوی تر** نیز میتوانند داخل حلقه های **ضعیف تر** شکل بگیرند

ورودی این مدل برای هر کاربر مجوعه V که رئوس متصل به u ( کاربر مورد نظر ) و مجموعه E که شامل تمام یال هایی می باشد که میان مجموعه V وجود دارد به همراه پروفایل تمام اعضای مجموعه V است. 
هدف این روش پیش بینی کردن مجموعه نهایی C ( حلقه های کاربر ) میباشد 
$$ C = \{ C_1\dotso C_k \}, C_k \subseteq V $$
و همچنین مشخص کردن پارامتر $$ \theta_k $$
که نمایش دهنده این می باشد که حلقه بر اساس چه ویژگی یا جنبه هایی تشکیل شده است.
همچنین از پارامتر $$ \phi(x,y) $$
به عنوان نمایش دادن میزان شباهت پروفایل دو کاربر x و y استفاده شده است. 
سپس از فرمول زیردر قدم اول ابتدا هر یک از رئوس گراف را یک خوشه در نظر میگیریم و سپس از فرمولی که در زیر آمده برای یافتنتشخیص اینکه آیا دو کاربر x و  y در یک خوشه قرار میگیرخوشه میتوانند با هم ترکیب شوند و یا خیر استفاده میشود. این روش را تا جایی که مجموعه C تغییری نکند انجام میدهیم.
$$ p((x,y) \in E) \propto exp \Bigg\{ \sum_{C_k \supseteq \{x,y\}}\langle \phi(x,y) , \theta_k \rangle  -  \sum_{C_k \nsupseteq \{x,y\}}\alpha_k \langle \phi(x,y) , \theta_k \rangle \Bigg\} $$
که سیگمای اول شامل تمام حلقه هایی است که هر دو راس در آن ها قرار میگیرند و سیگمای دوم بقیه ی حلقه ها را شامل می شود.
در این فرمول مقدار $$ \alpha_k $$
ضریب تناسبی برای متعادل کردن مقدار سیگما ها می باشد.
ایده این فرمول آن است که اگر مقدار پارامتر
$$ \langle \phi(x,y) , \theta_k \rangle $$
که نمایش دهنده میزان شباهت دو راس با یکدیگر بر اساس ویژگی مورد نظر می باشد بالا باشد یعنی هر دو راس متعلق به یک خوشه می باشند و اگر پایین باشد یعنی متعلق به خوشه ی مورد نظر نیستند.[3]

# **۳. آزمایش و نتایج**
# **۴. کارهای آینده**
# **۵. مراجع**
[1] Y.-Y. Ahn, J. Bagrow, and S. Lehmann. Link communities reveal multiscale complexity in networks.  *nature*, 2010.
[2] E. Airoldi, D. Blei, S. Fienberg, and E. Xing. Mixed membership stochastic blockmodels. JMLR, 2008.
[3] Julian McAuley, and Jure Leskovec. Learning to discover social circles in ego networks. *stanford*, 2012[1].

# ۲.۲. Infomap
در روش infomap با استفاده از روش خوشه بندی با این تفاوت نسبت به روش قبل که می تواند بر روی گراف های **جهت دار** و **وزن دار** نیز اعمال شود دو الگوریتم برای خوشه بندی داده ها ارائه می شود که به طور مختصر به شرح آن ها می پردازیم[2].
+ **الگوریتم Two-level clustering** 
هسته کاری این الگوریتم خوشه بندی براساس map equation است و ابتدا هر یک از راس های گراف را یک خوشه درنظر می گیرد و در هر مرحله هرکدام از خوشه ها که شباهت زیادی با یکدیگر دارند ادغام می کند.
این روش از این نظر مناسب نیست که هر گاه دو خوشه با یکدیگر ترکیب شوند یک خوشه ی جدید به وجود می آید و اثری از خوشه های قبلی دیگر نیست و ممکن است که اگر خوشه های قبلی با خوشه های دیگری در مراحل بعد ترکیب شوند به جواب بهتر و دارای دقت بالاتری دست پیدا کنیم[2]. 
برای رفع این مشکل دو متد زیر در نظر گرفته شده است:
**1. متد Submodule movements**
این متد به ما قابلیت تجزیه ی یک خوشه به زیر خوشه هایش که در مرحله قبل تشکیل شده اند را می دهد.
**2. متد Single-node movements**
این متد به ما قابلیت تجزیه ی خوشه و جدا کردن یک راس و درنظر گرفتن راس به عنوان خوشه ی مستقل را می دهد.
+ **الگوریتم Multi-level clustering**
 این الگوریتم مدل کامل تری از الگوریتم قبل بوده و متد هایی که در این الگوریتم تعریف می شوند می توانند به جای تجزیه ی خوشه به یک مرحله قبل خوشه را به مقدار دلخواه تجزیه کنند. 

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

# ۲.۳. Martelot
در آینده تکمیل می گردد.
# ۲.۴. Louvain
در آینده تکمیل می گردد.
# ۲.۵. 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 تعریف می شود.

ورودی آزمایش شده ابتدایی [شبکه ی کوچکی از فیسبوک](https://github.com/sina-bty/AI-community-detection/tree/master/DataSet/facebook) با 4,039 راس و 88,234 یال و از هر دو نوع فرمت Link list و Pajek می باشد. 

# ۳.۲. Methods of Implementation
در این قسمت به بررسی و انجام آزمایش الگوریتم های ارائه شده روی مجموع دادگان پرداخته شده و از کدهای موجود و آماده ی آنان استفاده شده است. ([لینک کدها](https://github.com/sina-bty/AI-community-detection/tree/master/Solutions))
روش کامپایل و اجرای هر الگوریتم در فایل readme که داخل فولدر هر کدام قرار دارد آورده شده است. 

+ ۳.۲.۱. **Infomap**
با انجام این روش بر روی دادگان facebook به نتایج و خروجی های زیر دست یافتیم که در [گیت هاب](https://github.com/sina-bty/AI-community-detection/tree/master/Results/Infomap/facebook) نیز موجود است. برای مشاهده نوع فرمت فایل های خروجی به [اینجا](http://www.mapequation.org/code.html#Output) مراجعه کنید.
تعداد ۷ انجمن پیدا شد که توسط ۱۲ یال با یکدیگر در ارتباطند. این ۷ انجمن با یکدیگر قابل ترکیب نیستند ولی توسط وزن یالی که بین آن هاست می توان تشخیص داد که چه مقدار به نسبت بقیه به یکدیگر شباهت دارند.
![communities predicted by infomap on facebook dataset](https://boute.s3.amazonaws.com/145-facebook_map.PNG)
+ ۳.۲.۲. **Combo**
پس از انجام این روش بر روی دادگان facebook زمان زیادی را برای دریافت نتایج منتظر ماندم ( در حدود ۷۰ ثانیه ). در پایان کار [نتایج و فایل خروجی](https://github.com/sina-bty/AI-community-detection/tree/master/Results/Combo/facebook) این الگوریتم فایلی متنی است که تعداد خطوط آن به تعداد رئوس گراف می باشد و در هر خط تنها یک عدد نامنفی تولید شده است که نشان دهنده تعداد انجمن هایی است که راس مورد نظر در آن مشترک است. 
تعداد انجمن ها و همچنین اعضای این انجمن ها جزو نتایج و خروجی برنامه نیست!!
+ ۳.۲.۳. **Louvain**
در آینده تکمیل می گردد.
+ ۳.۲.۴. **Martelot**
در آینده تکمیل می گردد.


# **۴. کارهای آینده**
# **۵. مراجع**
[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](http://www.mapequation.org/publications.html#Rosvall-Axelsson-Bergstrom-2009-Map-equation).
[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.