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

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

Keywords:

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