بخشی از مقاله
چکیده.
در این مقاله، با استفاده از مفهوم میانگین های ماتریسی و ماتریس های لاپلاس، الگو ریتمی برای تشخیص ساختار انجمن ها در شبکه های اجتماعی ارائه می دهیم. الگو ریتم داده شده برای گروه بندی داده ها به وسیله روش خوشه بندی طیفی بکار برده شده و برروی مجموعه داده استاندارد شبکه دلفین ها با دو روش فازی -cمیانگین و -kمیانگین اعمال شده است. در نهایت کیفیت الگو ریتم ذکر شده به کمک نتایج بدست آمده با استفاده از معیار ماژلا ریتی سنجیده شده است.
١. پیش_گفتار
یک انجمن در یک شبکه اجتماعی، از تجمع تعدادی عوامل و روابط میان آن ها تشکیل می شود که اعضای انجمن دارای بیشترین پیوند درون انجمن و کمترین پیوند بیرون آن هستند. در نظریه گراف ها، هر عامل یک گره و هر رابطه میان آنها یک یال است. این گره ها به وسیله انواع خاصی از وابستگی های متقابل مانند دوستی، خویشاندی، باورها، منافع مشترک و غیره به هم متصل شده اند.
تشخیص ساختار انجمن، به این دلیل که آنها بستری برای انتشار اطلاعات هستند، یک مساله مهم و چالش برانگیز است. یکی از الگو ریتم های شناخته شده برای تشخیص انجمن ها، روش نیومن-گیروان ]١[ است که در آن برای یافتن یال های انجمنی از مفهوم مرکزیت ارتباط استفاده می کند. الگو ریتم با وجود بهبودهای حاصل شده دارای پیچیدگی زمان زیادی می باشد. الگو ریتم دیگر برای شناسانی انجمن ها توسط نیومن ]۴[ پیشنهاد شد. این الگو ریتم برای بیشینه سازی ماژولا ریتی با قراردادن هر رأس در یک انجمن مجزا کار خود را شروع می کند و در شروع هیچ یالی وجود ندارد. با افزودن یک به یک یال ها انجمن هایی که در دوسر این یال ها قرار دارند در صورت افزایش ماژولا ریتی باهم ادغام می شوند.
روش دیگر در این راستا الگو ریتم ”عابر تصادفی”است که توسط هوگز معرفی شد. در این روش از هر رأس با توجه به یال های موجود به هر کدام از رأس های مجاور بصورت تصادفی حرکت می شود. یک روش دیگر الگو ریتم ”گسترش برچسب ها” است. در این روش، رأس ها در ابتدا با برچسب های منحصر بفردی از هم مجزا شده و سپس در هر مرحله یکبار مورد بررسی قرار می گیرند و برچسب شان با کمک برچسب رأس های اطراف مشخص می شود؛ بدین ترتیب که هر رأس برچسب خود را به برچسبی که بیشترین تعداد تکرار را در بین رأس های همسایه دارد، تغییر می دهد.
روش مورد توجه در این مقاله، الگو ریتم خوشه بندی طیفی ]٣، ۵[ است که مبنای آن استفاده از بردارهای ویژه ماتریس هایی خاص می باشد. در بخش بعد به توصیف این ماتریس ها می پردازیم.
٢. ماتریس لاپلاس اساس روش خوشه بندی طیفی بر مبنای استفاده از ماتریس هایی موسوم به ماتریس لاپلاس است. معمولا شبکه های اجتماعی را می توان به وسیله یک گراف نمایش داد.
روش های فراوانی برای معرفی شباهت بین داده ها وجود دارند. باید توجه کرد که چگونگی تعریف تشابه بین داده ها به طور مستقیم روی ساختار انجمن های به دست آمده تاثیر می گذارد. در این مقاله، تابع شباهت را براساس همسایگان مشترک معرفی می کنیم، چرا که در شبکه های اجتماعی افرادی که دوست مشترک بسیاری دارند به احتمال زیاد با یکدیگر دوست بوده و به گروه مشترکی تعلق دارند. بنابراین تابع شباهت برای الگو ریتم پیشنهادی بدین صورت تعریف می کنیم.
تعریف ٢.٣. فرض کنید k عددی صحیح و مثبت باشد. همسایگی -kفاصله برای رأس v شامل تمام رأس هایی است که فاصله آنها از v بزرگتر از k نباشد.
٣. الگو ریتم پیشنهادی
فرض می کنیم که مجموعه داده مورد نظر شامل n نقطه _ _ _ ; x n ;۱x است. تشابه بین جفت داده xi و xj را با استفاده از تابع شباهت تعریف ٢.۴ سنجیده و بصورت sij = S - xi; xj - نمایش داده می شود. ماتریس به دست آمده توسط اعداد sij که یک ماتریس مثبت و متقارن است، ماتریس شباهت نامیده می شود.
انتخاب ماتریس لاپلاس مورد استفاده در خوشه بندی طیفی از اهمیت زیادی برخوردار است بطوری که اگر گراف منظم باشد و اکثر راس های آن دارای درجه تقریبا یکسانی باشند، آنگاه تمام ماتریس های لاپلاس مشابه یکدیگر هستند و می توان از هرکدام برای خوشه بندی استفاده کرد.
اما اگر درجه رأس های گراف تفاوت زیادی با یکدیگر داشته باشند، ماتریس های لاپلاس بطور قابل توجهی متفاوت خواهند بود. استدلال های زیادی وجود دارند که تضمین می کند استفاده از ماتریس های لاپلاس نرمال به مراتب بهتر از ماتریس لاپلاس غیرنرمال می باشد.
بطور خلاصه مراحل الگو ریتم به شرح زیر است:
ورودی: گراف شبکه اجتماعی، تعداد خوشه های مورد نظر خروجی: ساختار شبکه تقسیم شده به خوشه ها
گام ١: ساخت گراف شباهت با استفاده از تعریف ٢.۴ و قراردادن آن بعنوان ماتریس وزن .
گام ٢: محاسبه میانگین لاپلاس های نرمال از طریق معادله - ٣.١ - .
گام ٣: محاسبه -kبردار ویژه متناظر با -kمقدار ویژه کوچکتر ماتریس لاپلاس.
گام ۴: محاسبه ماتریس U 2 Rn_k که ستون های آن را بردارهای ویژه تشکیل می دهند.
گام ۵: مشخص کردن بردارهای برای هر ، که همان سطرهای ماتریس هستند.
گام ۶: خوشه بندی نقاط داده با استفاده از الگو ریتم فازی -cمیانگین -k - میانگین - به دسته های : : : ; Ck ;۱.C
