بهبود کارایی شناسایی افراد تاثیرگذار در شبکه های اجتماعی از طریقنمونه برداری گراف

در سال های اخیر، شبکه های اجتماعی برخط رشد سریع و روزافزونی داشته اند و بستری برای تعاملات اجتماعی برخط جریانی برای هزاران میلیونکاربر در سراسر جهان به وجود آورده است . از این رو این تعاملات اجتماعی مستمر بین کاربران حجم زیادی از داده ها را تولید می کنند و تحلیل داده هارادر کل آنها دشوار می کند.از آن جایی که نمایش شبکه های اجتماعی در کامپیوتر به کمک نظریه گراف انجام می شود بنابراین تحلیل گرافمکانیزمی جهت تحلیل شبکه های اجتماعی محسوب می شود . یک شبکه اجتماعی جریانی یک گراف جریانی است که در این گراف گره ها می توانند نشان دهنده افراد موجود (کاربران) در شبکه اجتماعی باشند. در این کار برای بهبود کارایی شناسایی افراد تاثیرگذار از تلفیق دو الگوریتم PIES و PageRank استفاده و آن را پیاده سازی کردیم. برای ارزیابی روش پیشنهادی از مجموعه داده Enron استفاده شد و برای اعتبار سنجی ، روش ما با الگوریتم های شناخته شده برای شناسایی گره های تاثیرگذار مقایسه شد. نتایج عددی اثربخشی روش پیشنهادی را تایید می کند .در این پایان نامه برای یافتن افراد تاثیر گذار در شبکه های اجتماعی ابتدا به تشخیص جوامع در داخل شبکه با استفاده از الگوریتم PIES پرداختیم که اجرای این الگوریتم باعث شد جامعه ورودی به صورت خوشه بندی نمایش داده شود و داخل هر خوشه با اجرای الگوریتم PageRank به شناسایی افراد تاثیرگذار پرداختیم. در اکثر الگوریتم هایی که بر روی گراف کار می کنند از ماتریس مجاورتی برای محاسبات خود استفاده می کنند که این ساختار به دلیل اینکه ی آرایه دو بعدی است و تمام درایه های آن پویش می شود دارای پیچیدگی زمانی O(n)۲ است. که در روش ارائه شده برای کاهش این زمان به جای ماتریس مجاورتی از لیست همجواری استفاده شد و توانستیم زمان پردازش این کار را تا O( n +e ) کاهش دهیم.