بخشی از مقاله
چکیده
شبکه های اجتماعی در روزگار اخیر از اهمیت ویژه ای برخوردار هستند. کاربران می توانند با استفاده از تلفن های همراه هوشمند و یا سایر وسائل ارتباطی به این شبکه ها متصل شده و داده های خود را با آن ها تبادل کند. از آنجایی که حجم داده های موجود در این شبکه ها نسبتا بزرگ است لذا فرایند جستجو و تبادل داده در این شبکه ها با مشکلاتی همراه است. برای غلبه بر این مشکلات می توان داده های موجود در این شبکه ها را خوشه بندی نمود. در این مقاله خوشه بندی شبکه های اجتماعی با استفاده از شبکه پرسپترون چند لایه بررسی شده و نتایج حاصل از آن با برخی از سایر روش های موجود در این زمینه مقایسه شده است. بررسی نتایج نشان می دهد الگوریتم پیشنهادی این مقاله از دقت بیشتری در خوشه بندی شبکه های اجتماعی برخوردار است.
کلمات کلیدی شبکه های اجتماعی، خوشه بندی شبکه های اجتماعی, شبکه عصبی، پرسپترون چند لایه
-1 مقدمه
در طول دهه گذشته، تعداد شبکه های اجتماعی1 به سرعت افزایش یافته است و میلیون ها نفر در شبکه های اجتماعی از قبیل فیس بوک2 و توییتر3 عضویت دارند.[1] فیس بوک به طور ویژه، بیش از یک میلیارد کاربر فعال در سال 2012 داشته است. همانطور که تعداد کاربران افزایش می یابد، پیچیدگی نیز هنگامی که ارزیابی شبکه های اجتماعی بیشتر می شود، بالا می رود. علاوه بر آن حوزه شبکه های اجتماعی نیز گسترده تر می شود.[2]
هدف عمده شبکه های اجتماعی اتصال افراد است تا هر کاربر در شبکه اجتماعی بتواند یک لینک هدفمند در شبکه های اجتماعی برقرار کند. این اتصالات و ارتباطات در شبکه های اجتماعی تحت عنوان یک گراف G مدل سازی می شود که به عنوان یک مجموعه G = - V, E - تعریف می شود که V یک مجموعه از N نود - V = {V1, V2, … , Vn} - و E ⊆ V × V مجموعه یال هایی است که نود Vi و Vj را به هم متصل می کند.[2 ,1] به عبارت دیگر V×V یک ماتریس مجاورتE = [Eij] 4 ، i, j ∈ V است که Vij ∈ {0,1} قابلیت دسترسی یک یال از نود i به نود j را نشان می دهد. وزن یال Eij > 0، شدت تعامل5 را نشان می دهد و گراف در این مورد یک گراف وزن دار6 نامیده می شود.
گراف، اگر Eij ≠ Eji، برای همه i, j ∈ V، غیر جهت دار است.[1] اکثر شبکه های اجتماعی، قابلیت هایشان را رایگان در اختیار کاربران قرار می دهند، اگرچه برای دسترسی به تمام قابلیت ها موجود در بعضی از شبکه های اجتماعی نیاز است تا کاربران فرایند ثبت نام در آن شبکه را طی کنند. اطلاعات شخصی درباره هر کاربر در پروفایل وی ذخیره می شود که یک پروفایل مجموعه ای از اطلاعات کاربر است که هویت فرد7 و ویژگی های شخصی دیگر را از قبیل علایق اش را شکل می دهد.[3]
هدف اصلی شبکه های اجتماعی، ارتباط افراد است بنابراین هر کاربر در شبکه اجتماعی می تواند یک لینک با کاربران دیگر در شبکه برقرار کند. شکل - 1 - انواع ارتباط هایی را که در شبکه های اجتماعی رخ می دهد نشان می دهد. یک مثال مفهوم »مرا دنبال کن8« در توییتر باشد که یک کاربر - ایجاد کننده - می تواند کاربران دیگر - هدف - را دنبال9 کند.[4 ,3] یک ارتباط کامل بین ایجاد کننده و هدف در صورتی که هر دو یکدیگر را دنبال کنند، برقرار می شود. در مثال توییتر، یک اتصال کامل قابلیت های اضافی از قبیل توانایی ارسال پیام خصوصی بین کاربران را امکان پذیر می کند. کاربران این ارتباط ها را - به ویژه آن ها علائق مشترک داشته باشند- برقرار می کنند تا مشارکت یکدیگر را دنبال کنند .[4]
شکل - 1 - نمونه ای از ساختار ارتباطی در شبکه های اجتماعی بسیاری از شبکه های اجتماعی اجازه می دهند تا هر کاربری پروفایل کاربران دیگر را ببیند، اگرچه برخی شبکه های اجتماعی از قبیل فیس بوک کاربرانی با سطح خصوصی 10 ایجاد می کند که به آن ها اجازه می دهد تا فقط به گروه خاصی از پروفایل ها دسترسی داشته باشند.[5] در این مقاله قصد داریم تا پس از تعریف خوشه بندی شبکه های اجتماعی، الگوریتمی مبتنی بر شبکه عصبی پرسپترون چند لایه جهت انجام این کار ارائه داده و خروجی های ناشی از آن را با برخی از روش های موجود در این زمینه مقایسه کنیم. لذا در ادامه مقاله ابتدا مفهوم خوشه بندی را معرفی کرده و سپس برخی از کارهای صورت گرفته در این زمینه را بررسی می کنیم.
بعد از آن الگوریتم پیشنهادی را معرفی کرده و دیتاستی که از آن جهت ارزیابی الگوریتم پیشنهادی استفاده می کنیم را تشریح می کنیم. در نهایت خروجی های الگوریتم پیشنهادی را ارزیابی کرده و نتایج حاصل از الگوریتم پیشنهادی را نشان می دهیم. تقسیم بندی افراد در گروه های مختلف در ذات بشر است. در گذشته افراد، خوشه بندی را به منظور مطالعه پدیده ها11 و مقایسه آن ها با یکدیگر براساس مجموعه خاصی از قوانین، به کار می برند.
خوشه بندی به گروه بندی اشیاء شبیه یکدیگر اطلاق می شود.[7 ,6] هر گروه یک خوشه نامیده می شود. هر خوشه از اشیایی تشکیل می شود که شباهت های مشترک دارند و به اشیاء موجود در گروه شبیه هستند. اکثر تعاریف برای خوشه بندی پارتیشن بندی داده ها در گروه ها براساس معیارهای معین است که این داده های گروه بندی شده در خوشه باید مشترک باشند. این معیارها شامل شباهت های مشترک است که با استفاده از اندازه گیری فاصله محاسبه شده است. می توان مفهوم خوشه بندی را در شبکه های اجتماعی دنیای واقعی با گروه بندی افراد با ارتباط دوستانه بالا از نظر درونی و پراکنده شده از نظر بیرونی، تعریف کرد.[8 ,1] در ادامه معیار شباهت و فاصله درخوشه بندی شبکه های اجتماعی معرفی می شود سپس انواع روش های خوشه بندی در شبکه های اجتماعی معرفی می شود و هریک به اختصار مورد بررسی قرار خواهد گرفت.[9]
-1-2 معیارهای شباهت و فاصله
چکیده مقاله باید بطور صریح موضوع و نتایج کار پژوهشی انجام شده را بیان کند. در چکیده تنها باید به اصل موضوع مقاله توجه شود و در آن از ذکرجزییات کار، شکلها، جدولها، فرمولها، و مراجع خودداری شود. چکیده را حداکثر در 200 کلمه و در یک یا دو بند - پاراگراف - تهیه کنید. عنوان چکیده باید با سبک Heading 0 نوشته شود. برای نوشتن متن چکیده از سبک Abstract استفاده کنید. در صورتی که چکیده دارای بند دوم است، آن را با سبک Abstract2 بنویسید. هر الگوریتم خوشه بندی یک فاکتور شباهت - ماتریس مجاورت - 12 دارد تا اشیا مشابه را با یکدیگر سازماندهی کند. درک معیار تشابه بسیار مهم است.سوالات زیر در این رابطه معنای بسیار پیدا می کند.
· چه چیزی دو خوشه را به هم وصل می کند؟
· چه چیزی شباهت دو نقطه را محاسبه می کند؟
· چگونه می توان این فاصله - شباهت - را محاسبه کرد؟ دینالد واش و همکاران13، تابع شباهت یا فاصله روی یک مجموعه داده X در مقالاتشان روی الگوریتم های خوشه بندی تعریف کردند. آن ها
یک ماتریس مجاورت متقارن n×n برای یک مجموعه داده n عضوی ارائه کردند که عنصر - i,i - ام تشابه یا عدم تشابه عنصر iام و jام را نشان می دهد.[10] خانواده فاصله های مینکوسکی14 دسته ای بسیار متداول از توابع فاصله است و می تواند به صورت زیر نشان داده شود:
-2-2 انواع خوشه بندی
انواع زیادی از الگوریتم های خوشه بندی وجود دارد. این الگوریتم ها براساس ساختار خوشه بندی - سلسله مراتبی، پارتیشنی - و ساختار و انواع داده ای - عددی و دسته ای - یا سایز داده ها - مجموعه داده های بزرگ - می توان دسته بندی کرد.[11] به طور کلی، روش های خوشه بندی می تواند به چهار نوع سلسله مراتبی 18، پارتیشنی19، کنترل شده فراجستجویی20 و مبتنی بر تراکم21 تقسیم می شوند. در خوشه بندی سلسله مراتبی، خوشه ها به عنوان یک درخت نمایش داده می شود که دندروگرام22 نامیده می شود. این الگوریتم ها می توانند با بالا- پایین23 - تقسیم کننده - 24 یا پایین- بالا25 - جمع کننده - 26 باشند.
اکثر این الگوریتم ها به پارامتر حد آستانه نیاز دارند که تا هنگام توقف جستجوی زیرگروه ها را اعلام کند. در خوشه بندی سلسله مراتبی تقسیم کننده، این الگوریتم از خوشه های سراسری27 شروع می شود که شامل همه عناصر است و سپس داده ها به زیرخوشه ها تقسیم می شوند. باید مشخص شود که کدام خوشه به دو قسمت تقسیم می شود و چگونه تقسیم انجام می شود. در حالیکه در خوشه بندی سلسله مراتبی جمع کننده، این الگوریتم از یک خوشه شروع می شود و سپس هر دو خوشه با یکدیگر ادغام می شوند تا یک خوشه سراسری حاصل شود .[12 , 6] ایده اصلی پشت خوشه بندی، یافتن معیار تشابه/ فاصله بین هر دو نقطه از قبیل فاصله اقلیدسی28 یا فاصله کسینوسی29 و ... است.
این الگوریتم با استفاده از یک ماتریس مجاورت ارائه می شود که فرض می شود متقارن 30 است . [12] الگوریتم های پارتشینی، تعداد ثابتی خوشه دارند که داده ها به تعداد زیر مجموعه ها تقسیم می شوند. متداول ترین مثال، الگوریتم K-means است که O - tkn - دارد که t تعداد تکرارها است و k تعداد خوشه ها و n سایز داده هایی که خوشه بندی می شوند را نشان می دهد.[13] در الگوریتم های مبتنی بر تراکم، خوشه یک منطقه متراکم از داده هاست. تراکم نقاط درون خوشه ها بیشتر از بیرون خوشه هاست. این الگوریتم زمانی استفاده می شود که شکل خوشه ها نامنظم است و داده ها پراکنده و نویز دارد.[14 , 12] خوشه بندی کنترل شده فراجستجویی، با خوشه ها به عنوان یک مسئله بهینه سازی برخورد می کند که یک هدف نهایی حداقل یا حداکثر شدن می باشد. اگرچه این الگوریتم ها انعطاف پذیری را فراهم می کنند اما زمان اجرای آنها به طور غیرقابل قبولی بالاست.
-3 بررسی کارهای پیشین
الگوریتم خوشه بندی به نام الگوریتم اسکن31 توسط گروه تحقیقی یو32 معرفی شد. این الگوریتم اختلاف های ساختاری یک دیاگرام شبکه را بررسی می کند تا خوشه بندی را انجام دهد و دو نقش ویژه تعریف می کند: یک هاب که دو خوشه یا بیشتر را به هم متصل می کند و داده های پراکنده 33 که ادغام سطح پایین تری با اعضای دیگر در یک خوشه دارند.[16 ,15] الگوریتم های گروه بندی یا خوشه بندی خودکار که برای شبکه های اجتماعی استفاده می شوند، در کار تحقیقی گروه اسلامی مورد بحث قرار گرفته اند.
در این تحقیق، محققان پیشنهاد می کنند که خوشه بندی متقابل سربار کاربران شبکه های اجتماعی هستند. بنابراین کاربران شبکه اجتماعی مورد نظر از الگوریتم های خوشه بندی خودکار برای انجام گروه بندی سریع دوستان شبکه های اجتماعی استفاده می کنند.[18 ,17] یکی از رایج ترین ابزارها که لیست هوشمند فیس بوک34 نامیده می شود، توسط گروه تحقیقی جاو 35 پیشنهاد شد. لیست هوشمند فیس بوک مکانیسم مبتنی بر توصیه 36 است که می تواند به طور کارا توسط کاربران فیس بوک برای گروه بندی خودکار دوستان استفاده شود. در یک آزمایش که توسط سیمون جونز37 انجام شد، فاکتورهایی که توسط اشخاص مورد آزمایش بررسی می شوند، هنگام خوشه بندی دوستان، تعیین می شود، محققان اطلاعات متناظر با همه دوستان فیس بوکی پانزده نفر را جمع آوری می کنند و از افراد خواسته می شود تا دوستانشان را با استفاده از متد ذخیره سازی کارت38 که توسط گروه تحقیقی کلی39 پیشنهاد شده است، خوشه بندی کنند.
این افراد به چندین سوال قبل از آزمایش پاسخ داده اند. با استفاده از دو متد فوق الذکر، محققان معیار اندازه ای را که برای خوشه بندی دوستان کاربران می تواند استفاده شود، به طور خلاصه بیان کرده اند. این دسته ها بصورت دسته ها و گروه های اجتماعی40، دوام رابطه41، اپیزودهای موقتی42، مکان های جغرافیایی43، نقش های عملکردی44 و مرزهای سازمانی45 هستند.[19 ,18] در میان این فاکتورها، متداول ترین معیار استفاده شده، دسته ها و گروه های اجتماعی و بعد از آن دوام رابطه می باشد. بعد از اینکه وظیفه ذخیره سازی کارت تکمیل شد، از الگوریتم اسکن برای خوشه بندی داده ها از فیس بوک استفاده می شود. در نهایت، شباهت نتایج حاصل با استفاده از متد ذخیره سازی کارت و متد اسکن با هم مقایسه می شوند.[20]
در چندین پژوهش دیگر گروه های تحقیقاتی بارات46 و فان بین47 و جلداستن دویستین48 آنالیزهای شبکه وزن دار را ارائه کردند و سه تایی باز49 که از دو لبه تشکیل می شود و سه تایی بسته50 که متشکل از سه لبه است را تعریف کرده اند. راه های زیادی برای محاسبه وزن هر سه تایی وجود دارد که شامل میانگین حسابی51 و میانگین هندسی52، ماکزیمم و مینیمم است.[21] هر چند که بیشتر محققان از میانگین هندسی استفاده می کنند.[22 ,21] سیستم توصیه گروهی 53 - GRS - که توسط گروه باتارجاو54 معرفی شده است، یک متد دیگر
