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

بخشی از مقاله

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

واژگان کلیدی:شبکه های اجتماعی، پیش بینی لینک، خوشه بندی، داده کاوی، تشخیص جوامع

-1 مقدمه

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

-2 تکنیک خوشه بندی گراف

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

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

- ویژگی های آن ها یکسان یا نزدیک به هم است.

- با یکی از اعضای همان خوشه روابط یا تماس هایی داشته باشد.

- به روشنی از مجموعه های مکمل (مجموعه اعضای خوشه دیگر) جدا پذیر باشد.

æ خوشه بندی، بیانگر گروه بندی نمونه ها یا مشاهدات، درون کلاس هایی از اشیاء مشابه می باشد.

-3 تشخیص جوامع در شبکه های اجتماعی

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

1

-1-3 گراف دو قسمتی و unipartite

یک گراف نشان دهنده مجموعه ای از افراد که به آنها رئوس گفته می شود، که برخی از آنها از طریق لینک به هم متصل شده اند. ارتباط افراد از طریق لینک نمایش داده می شود که به آن یال گفته می شود . چنین ساختار ریاضی ممکن است unipartite نامیده شود. یک نوع گراف شناخته شده باشگاه کاراته ذاکاری است [1] و در شکل 1 نشان داده شده است.

دنبال تقسیم افراد بین جوامع هستند که لبه ها بیش از حد غیر متقاطع هستند. بعضی نویسنده ها تلاش می کنند جوامع هم پوشا پیدا کنند که hypergraph متصل باشد. شکل 2مثالی از Hypergraph را نشان می دهد.

شکل :2 مثالی از [2]Hypergraph

Galiois lattice -3-3

شکل.1تصویری از گراف باشگاه کاراته ذاکاری[1]

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

Hypergraph -2-3

در ریاضیات، hypergraph یک گرافی است که در آن یک یال می تواند به هر تعداد راس متصل باشد. بعبارت دیگر، hypergraph یک جفت H (X , E) است که در آن X مجموعه ای از عناصر به نام گره یا راس است، و E مجموعه ای از زیر مجموعه های غیر تهی از X به نام یال ها می باشد. Hypergraph می تواند حاوی تعداد دلخواهی گره باشد مجموعه ای از جوامع را می توان به صورت یک گراف بزرگ نشان داد که رئوس افراد هستند و مجموعه یال ها جوامع را تشکیل می دهد. اکثر محققان در زمینه تشخیص جوامع به

2

فریمن [3] اولین شخصی بود که از گالیوس به منظور نشان دادن شبکه داده استفاده کرد. فرض اساسی این است که افراد مشترک بین جوامع، زیر مجموعه ای از خصوصیات یک جامعه را معرفی می کند. روش انتخاب شده شامل موارد زیر است: افراد ، ویژگی ها و مجموعه ای از ارتباطات بین افراد. این مجموعه از روابط می تواند با یک ماتریس مجاورت باینری نشان داد که به موجب آن افراد ستون ها، خصوصیات سطرها هستند. با توجه به سلسله مراتبی گالیوس یک شئ می تواند در تمامی مفاهیم نشان دهد که: مجموعه ای از ویژگی ها را با دیگر افراد به اشتراک بگذارد. شکل 3 یک مثال ساده از شبکه گالیوس را نشان می دهد که در آن چندین نفر چندین عکس را به اشتراک گذاشته اند.