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

تغییرات
ارزیابی پیاده‌سازی و گزارش نتایج

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

۱. ۱. مقدمه

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

an ego-network with labled circles

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

۳. ۲.۱. 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 استفاده شده است.
در قدم اول ابتدا هر یک از رئوس گراف را یک خوشه در نظر میگیریم و سپس از فرمولی که در زیر آمده برای تشخیص اینکه آیا دو خوشه میتوانند با هم ترکیب شوند و یا خیر استفاده میشود. این روش را تا جایی که مجموعه 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

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

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

۱۰. ۳.۲. Methods of Implementation

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

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

    communities predicted by infomap on facebook dataset

  • ۳.۲.۲. 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.
[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.

تایید شده

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

محمد غضنفری

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