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

امروزه اهمیت مبحث انتشار و استحکام معماری در شبکه، توجه محققین زیادی را به سمت شناسایی افراد تاثیرگذار در شبکه های اجتماعی جلب کرده است. بنابراین روشهای زیادی برای کشف گرهی تاثیرگذار ارائه شده است. با این وجود هر کدام از معیارهای ارائه شده دارای محدودیت های خاص خود هستند. الگوریتم GLS یکی از متدهای کشف و رتبه بندی گره های تاثیرگذار است. GLS با ادغام دو بعد اطلاعات سراسری و محلی گره ها، از دقت بیشتری نسبت به متدهای کلاسیک و نوین مشابه برخوردار است. GLS دارای پیچیدگی زمانی از مرتبه ی نمایی است. بنابراین استفاده از این متد برای شبکه های بزرگ هزینه ی زیادی را در بر دارد و در برخی موارد غیرممکن است. در این مقاله ساختار GLS را به منظور کاهش زمان اجرای آن تغییر داده ایم. این تغییر با در نظرگرفتن همسایه های مشترک هر گره با همسایه هایش تنها تا شعاع دو در بخش محاسبه ی تاثیر سراسری انجام شده است. الگوریتم ارائه شده در این پژوهش (NGLS) ضمن حفظ دقت GLS، دارای پیچیدگی زمانی از مرتبه ی خطی است. زمان اجرای NGLS روی ۱۵ شبکه ی دنیای واقعی حداقل %۵۰ و روی ۱۳ شبکه ی شبیه سازی شده حداقل ۸۰% نسبت به الگوریتم GLS کاهش یافته است. NGLS قابل استفاده در انواع شبکه ها با مقیاس های متفاوت است.

Keywords:

گره های تاثیرگذار , اطلاعات سراسری و محلی , شبکه های بزرگ , معیارهای مرکزیت