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

۱. ۱. مقدمه

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

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

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

۳. ۲.۱. روش خوشه بندی

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

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

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

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

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

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

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

که نمایش دهنده میزان شباهت دو راس با یکدیگر بر اساس ویژگی مورد نظر می باشد بالا باشد یعنی هر دو راس متعلق به یک خوشه می باشند و اگر پایین باشد یعنی متعلق به خوشه ی مورد نظر نیستند.[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.