یافتن موثرترین مجموعه ی K عضوی از گره ها در شبکه های اجتماعی با استفاده از مجموعه ی غالب

شبکه های اجتماعی یک ساختار اجتماعی از افراد و روابط میان آنها هستند که امروزه نقش مهمی در گسترش و انتقال اطلاعات میان افراد ایفا میکنند. یکی از مباحثی که در دهه های اخیر در این زمینه اهمیت ویژه ای یافته است، یافتن موثرترین افراد در این شبکه هاست. افرادی که بواسطه ی روابط و یا جایگاه اجتماعی شان، می توانند تاثیرات عمده ای بر دیگر افراد داشته باشند. با توجه به اینکه تعداد کاربران شبکه های اجتماعی و درپی آن اندازه ی این شبکه ها به سرعت در حال گسترش میباشند نیاز به الگوریتم هایی که بتوانند افراد موثر را در کمترین زمان ممکن به دست آورند بیش از پیش احساس میگردد. در صورتی که شبکه ی اجتماعی را به صورت یک گراف تصور کنیم، گره های این گراف نشان دهنده ی افراد و یالهای آن، نشان دهنده ی روابط میان این افراد هستند. یافتن موثرترین گره ها در گراف شبکه ی اجتماعی به روشهای مختلفی امکان پذیر میباشد. یکی از این روشها، استفاده از مجموعه ی غالب است.در این مقاله پس از بررسی و مطالعه ی الگوریتم های مطرح شده در زمینه ی یافتن مجموعه ی غالب، دو الگوریتم جدید ارایه شده است: در ابتدا با بهبود یکی از الگوریتم های موجود، الگوریتمی ارایه گردیده است که در حداقل زمان اجرای ممکن نسبت به سایر الگوریتم ها، موفق به یافتن کوچکترین مجموعه غالب گردیده است و دومین الگوریتم به گونه ای طراحی شده است که برای هر عدد صحیح K، یک مجموعهی غالب با حداکثر اندازهی K به دست خواهد آمد، که بیشترین تعداد از ریوس را مغلوب خواهد گرداند.

کلیدواژه ها:

گره های موثر ، مجموعه ی غالب ، شبکه های اجتماعی