بخشی از مقاله
خلاصه
هر تجزیه و تحلیل شبکه اجتماعی، با وجود فراگیر بودن مطالب رسانههای اجتماعی، صفحات وب و سنسورها دستخوش تغییرات زیادی شده است. این محتوا یک منبع داده غنی برای ساخت و تجزیه و تحلیل شبکههای اجتماعی است، اما عظمت و طبیعت بدون ساختار آن نیز در حال حاضر چالشهای متعددی به وجود میآورد. از جمله چالشها، مشکلات در ساخت شبکهها از دادههای بدون ساختار، تجزیه و تحلیل ساختار جامعه یک شبکه و برگرفتن اطلاعات از شبکهها میباشد. تجزیه و تحلیل گرافی ثابت کرده است که ابزار باارزشی در حل این چالشها است. در این مقاله هدف ما بررسی چالشهای مطرح شده و تلاش برای حل آنها و نیز بررسی ضرورت و امکان بهبود مدیریت اطلاعات در شبکههای اجتماعی است.
کلمات کلیدی: پایگاه داده، گراف، شبکههای اجتماعی برخط، الگوریتم نمونهبرداری
-1 مقدمه
اندازه بزرگ گرافهای شبکه اجتماعی محققان را از فهم بهتر این گرافها باز میدارد. از یکسو به دست آوردن گراف کامل شبکه کار آسانی نیست. تا زمانی که مدیران شبکه تمایلی به ارائه دادههای خود به محققان را نداشته باشند، تهیه گراف کامل از این شبکههای اجتماعی همیشه غیر ممکن است به خصوص با درنظر گرفتن مجموعه قوانین دسترسی مشخص شده توسط شبکهها و میزان زمان لازم. از سوی دیگر، حتی باوجود مجموعه دادههای در دسترس این شبکهها، پردازش آنها گروههای کامپیوتری گران قیمت و مجهز را میطلبد، به علاوه زمان زیاد و محا سبات ا ضافه. متناوباً، گراف نمونه راهحل مؤثر و در عین حال گرانی را فراهم میکند. با انتخاب یک نماینده از زیرمجموعه گراف اصلی، نمونه گراف میتواند گراف کوچک را بسازد، درحالیکه ویژگیهای گراف اجتماعی اصلی را نگهداشته است.
چندین الگوریتم نمونهبرداری برای گراف نمونه پیشنهاد شده است. الگوریتم نمونهبرداری جستجوی اول سطح - BFS - و سیر تصادفی - RW - معروفترین الگوریتمها هستند و در سرزمینهای زیادی مورد استفاده قرار میگیرند. هرچند مطالعات اخیر ن شان میدهند که ج ستجوی اول سطح - BFS2 - و سیر ت صادفی - RW3 - برای گرههایی با میزان بالا منا سب ه ستند. MHRW4 برای به د ست آوردن نمونه در گرافهای اجتماعی بدون جهت به کار گرفته شده ا ست، به این معنی که نگهداری توزیع درجه گره گراف ا صلی بدون تغییر ا ست. USDSG5 الگوریتم MHRW را در گرافهای اجتماعی جهتدار با درنظرگرفتن همه یالهای یکطرفه به عنوان یالهای دوطرفه قابل اجرا میسازد در این مقاله ما سعی میکنیم که چگونگی عملکرد الگوریتمهای موجود را در حفظ ویژگیهای مختلف و مهم گرافهای اجتماعی اصلی دریابیم. تمام مجموعه دادههایی که انتخاب شدهاند گرافهای اجتماعی واقعی دنیا هستند و به طور گسترده در بسیاری از تحقیقات دیگر به رسمیت شناخته شدهاند.[1]
-2 پیشزمینه
1؛2 تعاریف و فرضیات
گرافهای اجتماعی که در آنها تعاملات کاربر یک طرفه - جهتدار - انجام میگیرد، میتوانند به صورت گرافهای جهتدار Gd = - V, Ed - مدلسازی شوند که در آن V مجموعهای از گرهها - کاربران - است و Ed مجموعهای از یالهای جهتدار - تعاملات بین کاربران - است. - u,v - , u,v ∈ V نشاندهنده یال بین u و v - اعمال کاربران - است. درجه ورودی گره v است که تعداد یالهای - u; v - ; u ∈ V در Ed میباشد. درجه خروجی گره v است که تعداد یالهای درحالیکه برخی الگوریتمها اطلاعات مربوط به جهت یالها را نیاز دارند گاهی اوقات آنها چندان مهم نیستند. در این وضعیت ما میتوانیم گرافهای متقارن را از گرافهای جهتدار Gd تولید کنیم. G = - V, E - گراف متقارن Gd است درحالیکه: ما kv را درجه گره v در G تعریف میکنیم که تعداد یالهای متصل به گره v است.. [2]
2؛2 ویژگیهای گراف
در این مقاله ما دو ویژگی کلی گراف را در ذیل درنظرگرفتهایم:
توزیع درجه گره : - NDD6 -
NDD یکی از مهمترین ویژگیهای یک گراف ا ست. در یک گراف جهتدار، یک گره درجه ورودی یا خروجی دارد که تعدادی از گرهها تو سط یال ورودی یا خروجی به این گره واب ستهاند. در یک گراف اجتماعی درجه گره تعداد کاربرانی که آن یک کاربر با آنها در ارتباط است را نشان میدهد. این یک نکته بسیار مهم برای مطالعه رفتار کاربر است. ما از برای نشان دادن بخشی از گرهها با درجه - ورودی یا خروجی - کمتر یا مساوی با k استفاده میکنیم. ما خطای مربعی میانگین نرمال - 7NMSE - را برای درجهی گره k به صورت معادله - 1 - تعریف میکنیم: که اصلی روی نمونه گراف است. ما از NMSE - k - برای نشان دادن تفاوت بین توزیع درجه نمونه تخمینی از گرافها و گرافهای اصلی استفاده میکنیم.
