بخشی از مقاله
چکیده
با افزایش روز افزون شبکههای اجتماعی و حجم بسیار وسیع کاربران آنها، لزوم ارائهی روشهای کارا که بتوانند افراد تاثیرگذار این شبکهها را انتخاب کنند بیش از پیش احساس میشود. بنابراین تاثیرگذاری و مدلهای انتشار اطلاعات درون شبکههای اطلاعاتی از بحثهای جامعهشناسی گرفته تا بازاریابی و امنیت می تواند کاربردهای گوناگونی داشته باشد. از چالشهای بزرگ پیشرو در این زمینه حجیم بودن و تراکم بالای اطلاعات موجود در شبکههای اجتماعی است که پردازش آن را بسیار پر هزینه میکند و پردازش شبکههای اجتماعی با هزینهی متناسب یکی از دغدغههای کنونی است.
الگوریتمهای نمونهبرداری یکی از این نوع الگوریتمهای قابل توجیه در کاربردهای واقعی هستند چرا که هزینه و زمان آنها در مقابل دقت، مقیاسپذیر است. در مقالهی حاضر تلاش شده است الگوریتمی با کاربرد واقعی معرفی شود که بتواند گرافی خلاصه ارائه دهد که بتوان از آن پذیرندههای اولیه و فرایند مستمر انتشار را استنباط کرد. این الگوریتم مبتنی بر روشهای مونت کارلو، نمونهبرداری تصادفی و پردازش به کمک ماتریس مارکوف است . آزمایشهای انجام شده روی گرافی با دادههای شبیهسازی شده انجام میشود تا کیفیت الگوریتم اثبات شود.
.1 مقدمه
امروزه حجم وتنوع دادههای موجود در جهان با سرعت چشمگیری در حال افزایش است. به همین دلیل، یافتن دادههای مفید از میان انبوهی از دادهها و استخراج اطلاعات و دانش مورد نیاز از میان آنها، به چالشی اساسی برای محققین در زمینههای مختلف تبدیل شده است. در همین زمینه، مسئله یافتن راهحلی مناسب برای مدلسازی، نمایش و تحلیل داده-های حجیم و متنوع نیز موضوعی بسیار مهم به شمار میرود. در میان تمام ساختارهای موجود،گرافها با توجه به خواص منحصر به فرد خود، محبوبیت خاصی در میان محققین پیدا کردهاند.
با استفاده از گراف، میتوان دادههای بسیار متنوع با پیچیدگی زیاد را به سادگی نمایش داد. سادگی و معنادار بودن گراف و همچنین قدرت این ساختار در نمایش روابط پیچیده میان موجودیتها، در کنار قابلیت انعطافپذیری و مقیاس-پذیری آن، این ساختار را به مدلی مناسب برای نمایش دادههای متنوع و حجیم با روابط پیچیده تبدیل کرده است، به گونهای که امروزه در بیشتر حوزهها، از گراف به عنوان مدل نمایش دادهها استفاده میشود.
بزرگی شبکههای اجتماعی کنونی و حجم دادههای تولید شده به اندازهای است که نمیتوان با الگوریتمهای ساده و مبتنی بر یک تکنیک خاص به نیازهای تحقیقاتی و تجاری پاسخ گفت. در این مقاله تلاش شده است با استفاده از نمونه-گیری از شبکهی اجتماعی و تشکیل زنجیرهی مارکوف از تاثیرگذاری به خلاصهای از گراف شبکهی اجتماعی برسیم که پذیرندههای اولیه برای انتشار مداوم و حداکثری را معرفی نماید. الگوریتم خلاصه سازی گراف، یک گراف عظیم الجثه را به گونهای خلاصه میکند که حاصل گرافی سادهترو کوچکتر باشد و تمامی خصوصیات و اطلاعات برجسته-ی موجود در گراف اولیه و متناسب با نیاز کاربران مختلف را حفظ کند.
به طور کلی، خلاصهسازی گراف به دو بخش ساختاری و معناگرا تقسیم میشود. الگوریتمهای معناگرا همانطور که ازاسمشان مشخص است بر روی خلاصهسازی اطلاعات درون شبکه تمرکز دارند و از یک گراف، خلاصههای مختلفی تولید میکنند. این الگوریتمها معمولا کندتر هستند و از نظر تعداد بسیار کمتر از الگوریتمهای ساختاری هستند، موضوع این مقاله هم نیستند. الگوریتمهای خلاصهسازی ساختاری گراف، بیشتر به الگوریتمهای فشردهسازی شبیه هستند. برخلاف الگوریتمهای کاوش گراف، خروجی این الگوریتمها، یک گراف خلاصهی ساخته شده از گراف اولیه است که برای بررسی مناسب-تر بوده و ذخیرهی آن نیز سادهتر است . - Navlakha et al, 2008 -
الگوریتمهای نمایش گراف را نیز میتوان نوعی از الگوریتمهای خلاصهسازی برشمرد. در واقع برخی از این الگوریتمها برای نمایش گرافها، خلاصههایی ساختاری از آنها تولید میکنند که کاربر قادر است در فرایندی محاورهای، با زیاد و کم- کردن دقت نمایش گراف، میزان جزئیات قابل نمایش را تنظیم نماید. بازاریابی ویروسی با هدف کمکردن هزینهی تبلیغات و استفاده از پتانسیل شبکهی اجتماعی هر کاربر به انتشار اطلاعات در شبکه کمک کند. این پردازشها در حالت عادی بسیار پر هزینه خواهند بود و عموم تحقیقات موجود در زمینهی بازاریابی ویروسی به شکل مستقیم و غیر مستقیم به بهینهسازی فرایند پردازش مورد نیاز آن میپردازند. ارائهی یک مدل خلاصه شده از شبکهی اجتماعی با رویکرد تاثیرگذاری هدف این مقاله است.
.2 پیشینهی تحقیق
تیان و همکاران الگوریتمی برای ساخت گراف خلاصهی مبتنی بر صفات گره در نظر گرفتند. این گراف خلاصهی تولید شده برای پاسخ به پرسوجوهای گوناگون با توجه به گراف اولیه مناسب است. اما اشکال عمدهی این الگوریتمها عدم توجه به اطلاعات مهم است که سبب صرفنظر از صفات موجود در رئوس و یالهای گراف میشود که حاوی اطلاعات مهم هستند . - Tian et al - بونچی و همکاران از تجزیهی سلسله مراتبی فضای حالت برای سادهسازی مدل مارکوف استفاده میکنند. - Bonchi et al,2009 -
الگوریتم هایی تقریبی هم برای حل مسئلهی بیشینهسازی تأثیر استفاده میشود. دربیشتر مدلهای تأثیر، الگوریتم حریصانه مجموعهای از افراد با تقریب - - - 1- 1/e انتخاب خواهد کرد که e پایهی لگاریتم طبیعی است و هر عدد حقیقی مثبت است. در الگوریتم حریصانه، ابتدا مجموعه هستهی اولیه، خالی بوده، سپس تا زمانی که تعداد گرههای انتخاب شده کمتر از تعداد موردنظر ما است، حلقه به این صورت تکرار میشود که هر بار گرهای که نسبت به گرههای دیگر دارای سود حاشیهای بالاتری1 میباشد انتخاب شده و به گرههای مجموعهی آغازین افزوده میشود. منظور از سود حاشیهای این است که افزودن آن گره به مجموعهی آغازین از افزودن هر گرهی دیگری سود بیشتر یا به تعبیر بهتر گرههای بیشتری را فعال کند.
الگوریتم حریصانهی ارائه شده توسط - - Chen and Xie, 2008 دارای دو محدودیت میباشد که منجر به عدم کارایی آن میشوند: - 1 هسته های اولیهی مختلف نیاز به محاسبهی تابع انتشار دارند که این مسئله تحت مدلهای آبشاری مستقل و آستانه خطی#p-Hard است.به همین منظور کمپ و همکارانش از شبیهسازی مونتکارلو به تعداد زیاد استفاده کردند تا گسترش تأثیر را بهدرستی تخمین بزنند که این امر نتیجه ای جز زمان محاسبهی زیاد نداشت. - 2 الگوریتم حریصانهی پیشنهادشده، در هر تکرار تمام گرههای گراف را به عنوان کاندید بالقوه برای انتخاب گره بعدی بررسی میکرد.
برای بهبود الگوریتم حریصانه، - Chen et al, 2009 - ، به ارائهی راهکاری برای بهبود زمان اجرای الگوریتم حریصانه برای دو مدل انتشار آبشاری مستقل و آبشاری وزندار پرداختهاند.در الگوریتم پیشنهادی، ابتدا تعدادی از یالها با احتمال 1-p از گراف اولیه حذف شده و یک گراف تصادفی ساخته میشود.سپس در گراف تصادفی ساخته شده،میزان دسترسپذیری هر گره با پیمایش اول عمق یا اول سطح بدست میآید. سپس به ازای هر گرهی v در گراف تصادفی که قبلا به عنوان گرهی تاثیرگذار در مجموعهیS انتخاب نشده است،مقدار SV که برابر تعداد گرههای قابل دسترسی از گرهی v است، محاسبه میشود.این کار به تعداد R دفعه برای تمامی گرهها تکرار میشود.
