شبیه‌سازی انتشار رفتار و بهینه‌سازی نفوذ در شبکه‌های واقعی

فاطمه رفیعی

چکیده

امروزه شبکه‌های اجتماعی به بستر اصلی برای انتشار اطلاعات، فناوری‌ها و رفتارها تبدیل شده‌اند. با این حال، دیده می‌شود که خیلی از پویش‌ها، محصولات جدید یا تغییرات رفتاری، علی‌رغم پتانسیل اولیه، در قدم اول شکست می‌خورند و هرگز فراگیر نمی‌شوند. در مقابل، بعضی دیگر با سرعت زیاد در شبکه منتشر می‌شوند. این مطالعه با هدف بررسی این موضوع و پاسخ به این پرسش که «چه ساختارهایی مانع انتشار می‌شوند و چگونه می‌توان بر آن‌ها غلبه کرد؟» انجام شده است.

در این راستا، فرآیند انتشار با استفاده از مدل آستانه خطی (Linear Threshold Model - LTM) شبیه‌سازی شده است. برخلاف مدل‌های ساده‌سازی شده، در این پژوهش از فرض آستانه‌های ناهمگن استفاده شد تا تفاوت‌های فردی در پذیرش مدل‌سازی شود و شبیه‌سازی واقع‌گرایانه باشد. آزمایش‌ها بر روی دو مجموعه داده واقعی از شبکه فیسبوک، شامل شبکه دانشگاه رایس (با حدود ۴ هزار گره) و دانشگاه میشیگان (با بیش از ۳۰ هزار گره) پیاده‌سازی شد.

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

در نهایت، برای حل مسئله NP-Hard بهینه‌سازی نفوذ (Influence Maximization)، الگوریتم حریصانه (Greedy) پیاده‌سازی و با استراتژی‌های هیوریستیک متداول (بیشترین درجه، مرکزیت بینابینی و PageRank) مقایسه شد. نتایج نشان داد که الگوریتم حریصانه نفوذی ۱۱ برابر بیشتر از روش‌های سنتی ایجاد می‌کند. همچنین، برای غلبه بر چالش زمان اجرا در مقیاس بزرگتر، نسخه بهینه‌شده الگوریتم با نام CELF پیاده‌سازی شد.

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

۱. مقدمه

در دهه‌های اخیر، گسترش شبکه‌های اجتماعی، ساختار تعاملات انسانی را به کلی تغییر داده است. پلتفرم‌هایی مثل فیسبوک، توییتر و لینکدین، فقط ابزاری برای حفظ ارتباطات نیستند؛ بلکه به بستری برای جریان اطلاعات، شکل‌گیری افکار عمومی، و گسترش نوآوری‌ها تبدیل شده‌اند. از بازاریابی برای یک محصول جدید گرفته تا کمپین‌های بهداشت عمومی (مانند واکسیناسیون) و حتی جنبش‌های سیاسی، موفقیت یا شکست یک پویش تا حد زیادی به نحوه انتشار آن در شبکه بستگی دارد.

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

۱-۱. سرایت ساده و پیچیده

برای درک انتشار، ابتدا باید بین دو نوع سرایت تمایز قائل شویم: سرایت ساده (Simple Contagion) و سرایت پیچیده (Complex Contagion).

در سرایت ساده (مانند انتشار ویروس آنفولانزا یا یک خبر)، تنها یک تماس با فرد آلوده کافی است تا ویروس یا خبر منتقل شود. در چنین حالتی، پیوندهای ضعیف (Weak Ties) یا همان آشنایان دور که گروه‌های مختلف را به هم وصل می‌کنند، نقش شاهراه‌های انتقال را بازی می‌کنند.

اما بسیاری از رفتارهای اجتماعی، از جنس سرایت ساده نیستند. پذیرش یک تکنولوژی، تغییر سبک زندگی، یا پیوستن به یک جنبش اجتماعی پرریسک، با رفتارهایی مانند گسترش ویروس متفاوت هستند. در این حالت، فرد با دیدن تنها یک نفر، قانع نمی‌شود؛ بلکه نیازمند تقویت اجتماعی (Social Reinforcement) است. شخص باید ببیند که چندین نفر از دوستان و اطرافیان مورد اعتمادش آن رفتار را انجام داده‌اند تا بر مقاومت ذهنی یا هزینه ریسک غلبه کند. این مطالعه بر روی این نوع از انتشار تمرکز دارد که دینامیک پیچیده‌تری نسبت به مدل‌های ویروسی دارد.

۱-۲. مدل آستانه خطی (LTM)

برای شبیه‌سازی دقیق این فرآیند تصمیم‌گیری، از یکی از شناخته‌شده‌ترین مدل‌های انتشار به نام مدل آستانه خطی (Linear Threshold Model) استفاده می‌شود. در این مدل، شبکه به صورت گرافی نمایش داده می‌شود که در آن گره‌ها نمایانگر افراد و یال‌ها نشان‌دهنده روابط اجتماعی هستند. برای هر گره v، یک آستانه مقاومت (theta_v) تعریف می‌شود که عددی بین ۰ و ۱ است. این عدد نشان‌دهنده میزان سرسختی یا محافظه‌کاری فرد در برابر تغییر است.

یک گره v که در ابتدا غیرفعال است، تنها زمانی فعال می‌شود (رفتار جدید را می‌پذیرد) که مجموع وزن تأثیر همسایگان فعالش، از آستانه theta_v عبور کند. اگر فرض کنیم همسایگان تأثیر برابری دارند، شرط فعال‌سازی به صورت زیر است:

active neighbors/all neighbors >= theta_v

نکته کلیدی در اینجا، استفاده از آستانه‌های ناهمگن (نابرابر) است. برخلاف برخی مطالعات که یک آستانه ثابت برای کل شبکه در نظر می‌گیرند، اینجا فرض شده است که جامعه ترکیبی از افراد زودباور (با آستانه پایین) و افراد سرسخت (با آستانه بالا) است تا شبیه‌سازی به واقعیت نزدیک‌تر باشد.

۱-۳. مسئله بهینه‌سازی نفوذ

صورت مسئله‌ای که با آن رو به رو هستیم این است که «اگر بودجه داشته باشیم که تنها k نفر را در شبکه فعال کنیم، کدام k نفر را انتخاب کنیم تا اندازه نهایی آبشار (تعداد کل افراد فعال شده) بیشینه شود؟»

این مسئله از نظر محاسباتی دشوار است. برای یک شبکه با ۳۰,۰۰۰ گره، تعداد حالاتی که می‌توان k نفر را انتخاب کرد، عدد بسیار بزرگی می‌شود. کمپ، کلاینبرگ و تاردوس (۲۰۰۳) اثبات کردند که این مسئله NP-Hard است.

بنابراین این پژوهش دو وجه دارد. اول درک اینکه چرا انتشار در برخی شرایط متوقف می‌شود (نقش ساختار شبکه). دوم پیاده‌سازی الگوریتم‌هایی (مانند Greedy و CELF) که بتوانند با دقتی بسیار بالا و در زمانی کوتاه، این گره‌های طلایی را در میان ده‌ها هزار گره شناسایی کنند.

۲. ادبیات موضوع و کارهای پیشین

در این بخش، به بررسی دو موضوع می‌پردازیم که زیربنای مدل‌سازی‌های این پژوهش را تشکیل می‌دهند. نخست، نظریه کلاسیک قدرت پیوندهای ضعیف که بر نقش ساختاری روابط تمرکز دارد، و دوم، مدل‌های آستانه و آبشار که دینامیک گذار فاز در سیستم‌های پیچیده را نشان می‌دهند.

۲-۱. نظریه قدرت پیوندهای ضعیف (Mark Granovetter, 1973)

یکی از تأثیرگذارترین مقالات در زمینه جامعه‌شناسی، مقاله مارک گرانووتر با عنوان "The Strength of Weak Ties" است. گرانووتر با تحلیل شبکه‌های اجتماعی انسانی، روابط میان افراد را به دو دسته کلی تقسیم کرد:

1. پیوندهای قوی: روابطی که با صرف زمان زیاد، شدت عاطفی بالا و صمیمیت همراه هستند (مانند دوستان نزدیک و خانواده).

2. پیوندهای ضعیف: روابطی سطحی‌تر و کم‌هزینه‌تر (مانند آشنایان دور یا همکاران).

استدلال مرکزی گرانووتر بر پایه مفهوم Triadic Closure استوار است. او بیان می‌کند که اگر فرد A با B و C پیوند قوی داشته باشد، احتمال بسیار زیادی وجود دارد که B و C نیز با یکدیگر پیوند داشته باشند (دوستان صمیمی ما، معمولاً یکدیگر را می‌شناسند). این پدیده باعث می‌شود که پیوندهای قوی منجر به تشکیل خوشه‌های متراکم و جزایر جدا افتاده در شبکه شوند. در درون این خوشه‌ها، اطلاعات به سرعت می‌چرخد اما راهی به بیرون پیدا نمی‌کند.

در مقابل، پیوندهای ضعیف معمولاً نقش پل را ایفا می‌کنند. آن‌ها تنها مسیرهای ارتباطی هستند که خوشه‌های متراکم و مجزا را به یکدیگر متصل می‌کنند. گرانووتر نتیجه گرفت که برای انتشار اطلاعات جدید (مانند فرصت‌های شغلی یا اخبار)، پیوندهای ضعیف بسیار کارآمدتر از پیوندهای قوی هستند، زیرا دسترسی به بخش‌های غیرتکراری و دوردست شبکه را فراهم می‌کنند.

در ادامه خواهیم دید، اگرچه فرضیه گرانووتر برای انتشار اطلاعات (سرایت ساده) صحیح است، اما آزمایش‌های ما نشان می‌دهد که برای انتشار رفتار (سرایت پیچیده)، این پیوندهای ضعیف دچار ناکارآمدی می‌شوند.

۲-۲. آبشارهای سراسری و پایداری شبکه (Duncan Watts, 2002)

در حالی که گرانووتر بر ساختار تمرکز داشت، واتس در مقاله کلیدی خود "A Simple Model of Global Cascades on Random Networks"، دینامیک تغییر وضعیت شبکه را مدل‌سازی کرد. این مقاله، پایه‌ی اصلی مدل‌سازی ریاضی (LTM) در این مطالعه است.

واتس نشان داد که شبکه‌های اجتماعی دارای خاصیتی دوگانه هستند: مقاوم و در عین حال شکننده. او با معرفی مدل آستانه، پدیده‌ای به نام آبشارهای سراسری (Global Cascades) را تحلیل کرد. طبق این مدل، یک شوک اولیه کوچک (فعال‌سازی چند گره بذر)، معمولاً به سرعت میرا می‌شود و تأثیر محدودی دارد. اما اگر پارامترهای شبکه (مانند میانگین درجه یا توزیع آستانه‌ها) از یک حد بحرانی عبور کنند، شبکه دچار گذار فاز (Phase Transition) می‌شود.

واتس دو مفهوم کلیدی را برای توضیح این پدیده معرفی کرد. اولین مفهوم خوشه‌های آسیب‌پذیر (Vulnerable Clusters) است. انتشار سراسری تنها زمانی رخ می‌دهد که گره‌های آسیب‌پذیر یعنی گره هایی که با فعال شدن تنها یک همسایه، فعال می‌شوند، تشکیل یک خوشه همبند و نفوذکننده در سراسر شبکه بدهند.

مفهوم دوم خوشه‌های مسدودکننده (Blocking Clusters) هستند. در مقابل، واتس توضیح می‌دهد که عامل اصلی توقف انتشار، برخورد با خوشه‌هایی است که تراکم داخلی آن‌ها بسیار بالاست. اگر تراکم داخلی یک گروه از آستانه مقاومت بیشتر باشد (p > 1-q)، هیچ فشار بیرونی نمی‌تواند به درون آن نفوذ کند.

این چارچوب نظری واتس، همان ابزاری است که در بخش ارزیابی‌ها برای تفسیر نمودارهای نقطه اوج و تحلیل علت توقف انتشار در شبکه دانشگاه‌های رایس و میشیگان از آن استفاده می‌کنیم.

۲-۳. نظریه سرایت پیچیده (Centola & Macy, 2007)

در حالی که نظریه قدرت پیوندهای ضعیف برای دهه‌ها روش غالب در تحلیل انتشار بود، سنتولا و میسی در سال ۲۰۰۷ با انتشار مقاله‌ای، این باور را به چالش کشیدند. آن‌ها استدلال کردند که تعمیم یافته‌های گرانووتر (که برای انتشار اطلاعات بود) به انتشار رفتارها، یک خطای بنیادی است.

آن‌ها مفهوم سرایت پیچیده (Complex Contagion) را معرفی کردند؛ رفتارهایی که پذیرش آن‌ها نیازمند تأیید یا تقویت از جانب چندین منبع است. برخلاف ویروس یا شایعه که با یک تماس منتقل می‌شود، رفتارهای پرهزینه (مانند پذیرش یک تکنولوژی جدید یا پیوستن به یک اعتراض) دارای آستانه پذیرش هستند.

سنتولا و میسی نشان دادند که برای سرایت پیچیده، پل‌های طولانی و پیوندهای ضعیف که صرفاً فواصل را کوتاه می‌کنند، ناکارآمدند. دلیل این امر نبود Social Bandwidth است؛ یک پیوند ضعیف نمی‌تواند سیگنال تقویت‌کننده لازم را منتقل کند. در مقابل، آن‌ها مفهوم پل‌های عریض (Wide Bridges) را پیشنهاد کردند؛ ساختارهایی که اگرچه ممکن است کوتاه باشند، اما دارای چندین یال موازی هستند که امکان عبور همزمان تأثیر از چند همسایه به یک فرد را فراهم می‌کنند. این نظریه، توجیه‌گر آزمایش مقایسه خوشه پل در این پژوهش است، که نشان داده می‌شود چرا شروع انتشار از درون خوشه‌های متراکم، استراتژی موفق‌تری است.

۲-۴. مسئله بهینه‌سازی نفوذ و الگوریتم حریصانه (Kempe, Kleinberg, & Tardos, 2003)

کمپ، کلاینبرگ و تاردوس در مقاله خود مسئله بهینه‌سازی نفوذ را به عنوان یک مسئله بهینه‌سازی گسسته فرمول‌بندی کردند. صورت مسئله یافتن مجموعه S با اندازه k است که تابع نفوذ sigma(S) را بیشینه کند. آن‌ها اثبات کردند که این مسئله در مدل‌های LTM و ICM، در کلاس پیچیدگی NP-Hard قرار دارد. با این حال، دستاورد بزرگ آن‌ها اثبات دو ویژگی ریاضی کلیدی برای تابع نفوذ بود.

اولین ویژگی یکنوایی ست، یعنی افزودن گره جدید به مجموعه بذر، هرگز باعث کاهش نفوذ نمی‌شود.دوم زیرپیمانه‌ای بودن (Submodularity)، این ویژگی که معادل گسسته Convexity یا قانون بازده نزولی در اقتصاد است، بیان می‌کند که ارزش افزوده‌ی یک گره خاص، با بزرگتر شدن مجموعه بذر کاهش می‌یابد.

بر اساس این ویژگی‌ها، آن‌ها نشان دادند که یک الگوریتم حریصانه ساده که در هر مرحله گره‌ای با بیشترین Marginal Gain را انتخاب می‌کند، تضمین می‌کند که به جوابی نزدیک به جواب بهینه سراسری دست یابد.

۲-۵. تسریع الگوریتم: روش CELF (Leskovec et al., 2007)

هرچند الگوریتم حریصانه دقت بالایی دارد، اما از نظر محاسباتی بسیار کند است. برای انتخاب k گره در گراف با N گره، الگوریتم باید k * N بار تابع شبیه‌ساز (Monte Carlo) را اجرا کند که برای شبکه‌های بزرگ (مانند شبکه میشیگان در این پژوهش) ساعت‌ها طول می‌کشد.

برای حل این چالش، Leskovec در سال ۲۰۰۷ الگوریتم CELF (Cost-Effective Lazy Forward) را معرفی کرد. این الگوریتم با بهره‌گیری از خاصیت Submodularity، از محاسبات غیرضروری جلوگیری می‌کند. ایده اصلی Lazy Evaluation است: از آنجا که سود نهایی یک گره در طول زمان فقط می‌تواند کاهش یابد (و هرگز افزایش نمی‌یابد)، اگر گره‌ای در دور قبل سود نهایی کمی داشته است، نیازی نیست در دور فعلی بلافاصله محاسبه شود، مگر اینکه کاندیدهای بهتر همگی بررسی و رد شوند. آزمایش‌ها نشان داده‌اند که CELF می‌تواند تا ۷۰۰ برابر سریع‌تر از الگوریتم حریصانه عمل کند، در حالی که همان مجموعه جواب را تولید می‌کند. در فاز نهایی این پژوهش، با پیاده‌سازی CELF زمان اجرا به طرز قابل توجهی کاهش یافت.

۳. روش‌شناسی پژوهش

برای بررسی تجربی نظریات مطرح شده و ارزیابی کارایی الگوریتم‌های پیشنهادی، این پژوهش بر پایه شبیه‌سازی‌های گسترده بر روی داده‌های واقعی شبکه‌های اجتماعی پیش می‌رود. در این بخش، به معرفی مجموعه داده‌های مورد استفاده، ابزارهای محاسباتی و فرآیند آماده‌سازی داده‌ها پرداخته می‌شود.

۳-۱. مجموعه Dataset

برای اطمینان از تعمیم‌پذیری نتایج، آزمایش‌ها بر روی دو شبکه اجتماعی متفاوت از لحاظ مقیاس اجرا شدند. هر دو مجموعه داده از مخزن داده‌های شبکه و زیرمجموعه socfb انتخاب شده‌اند که شبکه دوستی کاربران فیسبوک در دانشگاه‌های آمریکا در سال ۲۰۰۵ است. انتخاب این شبکه‌ها به دلیل ساختار واقعی، تراکم بالا و وجود خوشه‌های اجتماعی طبیعی (مانند خوابگاه‌ها، دانشکده‌ها و سال ورودی) است که باعث می‌شود برای مطالعه پدیده انتشار مناسب باشند.

1. شبکه کوچک (socfb-Rice31): این گراف مربوط به شبکه دوستی دانشجویان دانشگاه رایس است. با داشتن حدود ۴ هزار گره، این شبکه به عنوان محیط آزمایش اولیه مورد استفاده قرار گرفت.

2. شبکه بزرگ (socfb-Michigan23): این گراف مربوط به دانشگاه میشیگان است و با داشتن بیش از ۳۰ هزار گره و ۱.۱ میلیون یال، مقیاس وسیع‌تری دارد. استفاده از این شبکه برای بررسی مقیاس‌پذیری الگوریتم‌ها و تایید نتایج در ابعاد بزرگ ضروری بود.

جدول ۱، خلاصه آماری این دو شبکه را مقایسه می‌کند. نکته حائز اهمیت، تفاوت در میانگین درجه است. شبکه کوچکتر (Rice) دارای میانگین درجه ۹۰.۴ است، در حالی که شبکه بزرگتر (Michigan) میانگین درجه ۷۸.۱ دارد. همان‌طور که در بخش نتایج نشان خواهیم داد، همین تفاوت آماری به ظاهر ساده، تأثیر عمیقی بر موقعیت نقطه اوج و آسیب‌پذیری شبکه در برابر انتشار دارد.

۳-۲. ابزارها و پیش‌پردازش داده‌ها

پیاده‌سازی با استفاده از پایتون انجام شده است. کتابخانه‌های کلیدی مورد استفاده عبارتند از NetworkX جهت ایجاد، دستکاری و تحلیل ساختاری گراف‌ها (محاسبه درجه، خوشه‌بندی، مرکزیت‌ها)؛ SciPy جهت بارگذاری بهینه ماتریس‌های Sparse از فایل‌های mtx. که برای مدیریت حافظه در شبکه بزرگ میشیگان حیاتی بود؛ NumPy برای محاسبات برداری و تولید اعداد تصادفی؛ Matplotlib جهت مصورسازی نتایج و رسم نمودارهای فاز.

فرآیند پیش‌پردازش: داده‌های خام به صورت ماتریس‌های مجاورت در فرمت mtx. بودند. در گام نخست، این ماتریس‌ها بارگذاری و به گراف‌های NetworkX تبدیل شدند. از آنجا که رابطه دوستی در فیسبوک دوطرفه است، گراف‌ها به صورت بدون جهت در نظر گرفته شدند. همچنین، برای حذف نویزهای احتمالی، مولفه‌های همبند (Connected Components) بررسی شدند؛ هرچند به دلیل ماهیت Small World شبکه‌های اجتماعی، هر دو گراف دارای یک Giant Component بودند که تقریباً تمامی گره‌ها را در بر می‌گرفت و شبیه‌سازی‌ها بر روی کل گراف اجرا شد.

۳-۳. پیاده‌سازی شبیه‌ساز انتشار

بخش مرکزی این پژوهش، یک شبیه‌ساز است که دینامیک مدل آستانه خطی را بر روی گراف اجرا می‌کند. تابع ltm_simulator سه ورودی اصلی دریافت می‌کند: ساختار گراف (G)، مجموعه گره‌های بذر اولیه (S) و توزیع آستانه‌ها (Theta).

الگوریتم شبیه‌سازی طی مراحل زیر اجرا می‌شود:

1. مقداردهی اولیه: تمام گره‌های موجود در مجموعه بذر S به عنوان فعال علامت‌گذاری می‌شوند. سایر گره‌ها در وضعیت غیرفعال قرار دارند.

2. فرآیند تکرار (Cascade Loop): شبیه‌سازی وارد یک حلقه تکرار می‌شود که معادل گام‌های زمانی (t=1, 2, ...) است.

3. ارزیابی همسایگان: در هر گام، برای هر گره غیرفعال v که حداقل یک همسایه فعال دارد، کسر نفوذ محاسبه می‌شود:

   f_v = N_active(v) / N_total(v)

   که در آن N_active(v) مجموعه همسایگان فعال گره v است.

4. شرط فعال‌سازی: مقدار f_v با آستانه گره (v_threshold) مقایسه می‌شود. اگر f_v بیشتر یا مساوی v_threshold باشد، گره v به لیست فعال‌های جدید اضافه می‌شود.

5. توقف: این حلقه تا زمانی ادامه می‌یابد که در یک گام کامل، هیچ گره جدیدی فعال نشود (وضعیت پایدار). خروجی نهایی، تعداد کل گره‌های فعال شده (sigma(S)) است.

برخلاف پیاده‌سازی‌های عادی که از یک آستانه ثابت سراسری استفاده می‌کنند، این شبیه‌ساز از آستانه‌های ناهمگن پشتیبانی می‌کند.

۳-۴. الگوریتم‌های بهینه‌سازی نفوذ

هدف نهایی، یافتن مجموعه بذر با اندازه k است که خروجی شبیه‌ساز را بیشینه کند. برای این منظور، دو الگوریتم پیاده‌سازی و مقایسه شدند:

الف) الگوریتم حریصانه: این الگوریتم بر اساس اثبات کمپ و کلاینبرگ (۲۰۰۳) مبنی بر تضمین تقریب (1 - 1/e) عمل می‌کند. منطق آن به شرح زیر است:

1. مجموعه بذر S در ابتدا تهی است.

2. برای k مرحله تکرار می‌کنیم:

• برای تمامی گره‌های v که در S نیستند (گره‌های کاندید)، نفوذ حاشیه‌ای (Marginal Gain) را محاسبه می‌کنیم.

• گره‌ای که بیشترین Delta(v) را دارد انتخاب کرده و به S اضافه می‌کنیم.

اگر گراف N گره داشته باشد، برای انتخاب بذر اول N بار، بذر دوم N-1 بار و ... شبیه‌سازی اجرا می‌شود. پیچیدگی نهایی از مرتبه O(k .N . M) است که M هزینه یک بار اجرای شبیه‌سازی است. این روش برای گراف‌های بزرگ کند است.

ب) الگوریتم CELF (Cost-Effective Lazy Forward): برای غلبه بر کندی الگوریتم حریصانه در شبکه ۳۰ هزار گره‌ای میشیگان، از الگوریتم بهینه CELF استفاده شد. این الگوریتم از خاصیت Submodularity تابع نفوذ استفاده می‌کند یعنی سود نهایی افزودن یک گره، با گذشت زمان و شلوغ‌تر شدن شبکه، همواره کاهش می‌یابد.

مکانیسم Lazy Evaluation در CELF به این صورت پیاده‌سازی شد:

1. گام اول: نفوذ تمامی گره‌ها محاسبه شده و آن‌ها در یک صف اولویت بر اساس میزان نفوذشان مرتب می‌شوند.

2. انتخاب هوشمند: در هر مرحله، گره بالای صف (u) برداشته می‌شود.

3. بررسی اعتبار: بررسی می‌کنیم که نفوذ این گره مربوط به کدام دور است. اگر نفوذ مربوط به دور فعلی باشد (یعنی با توجه به بذرهای انتخاب شده‌ی قبلی آپدیت شده باشد)، این گره قطعاً بهترین گزینه است و انتخاب می‌شود. اگر نفوذ مربوط به دورهای قبل باشد (Stale)، نفوذ حاشیه‌ای آن دوباره محاسبه می‌شود (Delta_new(u)) و با مقدار جدید به صف بازگردانده می‌شود تا با سایرین رقابت کند.

این مکانیزم باعث می‌شود به جای چک کردن همه N گره در هر دور، تنها تعداد کمی از گره‌های بالای صف بررسی شوند. نتایج نشان داد که این روش تعداد فراخوانی‌های شبیه‌ساز را تا حد زیادی کاهش می‌دهد.

۴. ارزیابی‌ها و تحلیل نتایج

در این بخش، نتایج حاصل از چهار سناریوی آزمایشی بر روی هر دو مجموعه داده Rice و Michigan تحلیل می‌شود. هدف از این آزمایش‌ها، نه تنها سنجش کارایی الگوریتم‌ها، بلکه درک دینامیک حاکم بر انتشار در شبکه‌های اجتماعی واقعی است.

۴-۱. تحلیل نقطه اوج و گذار فاز

اولین پرسش در مطالعه انتشار این است که یک جامعه تا چه حد می‌تواند در برابر یک رفتار جدید مقاومت کند قبل از اینکه تسلیم شود؟ برای پاسخ به این پرسش، پدیده نقطه اوج (Tipping Point) بررسی شد. در این آزمایش، یک مجموعه بذر اولیه ثابت شامل ۲۰ گره انتخاب شده به صورت تصادفی در نظر گرفته شد. سپس شبیه‌ساز LTM با آستانه متغیر q از ۰.۰۱ تا ۰.۵۰ با گام ۰.۰۱ اجرا شد تا اندازه نهایی آبشار (sigma(S)) سنجیده شود.

نمودار حاصل از تغییرات پارامتر q در برابر اندازه آبشار، رفتاری به‌شدت غیرخطی را در هر دو شبکه نشان می‌دهد. به عبارتی شبکه رفتاری دوگانه (All-or-Nothing) دارد:

در شبکه Rice31، برای مقادیر آستانه q <= 0.06، سیستم در حالت فوق بحرانی قرار دارد. در این ناحیه، حتی یک تحریک کوچک (۲۰ بذر اولیه معادل ۰.۵٪ شبکه) منجر به فعال‌سازی بیش از ۹۹٪ گره‌ها یعنی ۴۰۸۳ نفر می‌شود. اما به محض اینکه آستانه به q=0.07 می‌رسد، سیستم دچار یک گذار فاز می‌شود. اندازه آبشار با یک سقوط شدید، از ۴۰۸۳ گره به ۲۷ گره کاهش می‌یابد. این یعنی نقطه اوج بحرانی این شبکه در بازه q_c <= 0.07 و q_c > 0.06 قرار دارد.

آزمایش مشابه بر روی شبکه ۳۰ هزار گره‌ای میشیگان، الگوی مشابه اما با پارامترهای متفاوت را نشان داد. در این شبکه، آبشار سراسری تا آستانه q=0.11 ادامه می‌یابد (فعال‌سازی ۳۰,۱۰۶ گره). اما در q=0.12، انتشار متوقف شده و به ۳۷ گره محدود می‌شود. بنابراین، نقطه اوج در این شبکه در بازه 0.11 < q_c و q_c <= 0.12 قرار دارد.

تفاوت قابل توجه در نقطه اوج دو شبکه یعنی ۰.۰۷ برای رایس در مقابل ۰.۱۱ برای میشیگان ممکن است در نگاه اول عجیب به نظر برسد که شبکه بزرگتر (میشیگان)، در برابر انتشار آسیب‌پذیرتر است و می‌تواند رفتارهای سخت‌تر (با هزینه بیشتر) را نیز منتشر کند.

این پدیده را می‌توان با ارجاع به مدل واتس (۲۰۰۲) و تفاوت در میانگین درجه دو شبکه توضیح داد. میانگین درجه در شبکه Rice برابر با ۹۰.۴ است. میانگین درجه در شبکه Michigan برابر با ۷۸.۱ است. در مدل آستانه کسری، شرط فعال‌سازی یک گره v به صورت k_active/ k_total >= q است.

برای برقراری یک آستانه ثابت (مثلاً q=0.10) یک گره در شبکه Rice (با ۹۰ دوست) نیاز دارد که حدود ۹ دوست فعال داشته باشد. و یک گره در شبکه Michigan (با ۷۸ دوست) نیاز دارد که حدود ۷.۸ (یعنی ۸) دوست فعال داشته باشد.

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

این آزمایش نشان داد که استراتژی بذردهی تصادفی فقط برای رفتارهایی با هزینه بسیار پایین (کمتر از ۷٪ در رایس و ۱۱٪ در میشیگان) کارآمد است. برای هر رفتاری که آستانه آن بالاتر از این مقادیر باشد (که شامل اکثر نوآوری‌های تجاری و اجتماعی می‌شود)، شبکه در حالت زیر بحرانی قرار دارد و انتشار به سرعت می‌میرد. این واقعیت، ضرورت بررسی موانع ساختاری و استفاده از الگوریتم‌های هوشمند که در ادامه بررسی می‌شوند را توجیه می‌کند.

۴-۲. بررسی علت توقف و نقش خوشه‌های مسدودکننده

در آزمایش قبلی مشخص شد هرگاه آستانه مقاومت (q) از حد بحرانی فراتر می‌رود، انتشار سراسری حتی با وجود ۲۰ بذر اولیه متوقف می‌شود. به عنوان مثال، در سناریوی q=0.3، در هر دو شبکه تقریباً هیچ پیشرفتی حاصل نشد و بیش از ۹۹٪ شبکه غیرفعال باقی ماند.

بر اساس قضایای اثبات شده در نظریه شبکه‌ها، یک آبشار با آستانه q، فقط در صورتی متوقف می‌شود که گره‌های باقی‌مانده (غیرفعال)، تشکیل یک خوشه مسدودکننده بدهند. یک خوشه مسدودکننده، مجموعه‌ای از گره‌هاست که هر عضو آن، بخش عمده‌ای از همسایگانش در درون همان مجموعه قرار دارند.

در این آزمایش با q=0.3، شرط مقاومت برابر با 1 - 0.3 = 0.7 است. این یعنی انتشار تنها زمانی متوقف می‌شود که تمامی گره‌های غیرفعال، در حلقه‌های دوستی متراکمی قرار گرفته باشند که بیش از ۷۰٪ دوستانشان هم غیرفعال باشند. در چنین حالتی، فشار اجتماعی از بیرون (که حداکثر ۳۰٪ است) برای شکستن مقاومت آن‌ها کافی نیست.

برای راستی‌آزمایی این تئوری، الگوریتمی توسعه داده شد که پس از توقف شبیه‌سازی، گراف باقی‌مانده‌ی گره‌های غیرفعال را استخراج و برای تک‌تک گره‌ها، تراکم همسایگان داخلی را محاسبه می‌کند. در شبکه Rice31 از مجموع ۴۰۶۵ گره غیرفعال، تعداد گره‌هایی که شرط تراکم بالا (p > 0.7) را نقض کردند، دقیقاً صفر بود. در شبکه Michigan23 نیز از مجموع ۳۰,۱۲۴ گره غیرفعال، تعداد موارد نقض شرط نیز دقیقاً صفر بود.

نتیجه‌ نشان می‌دهد که هیچ یک از دو شبکه، این تئوری را نقض نکردند. این موضوع دو واقعیت مهم را درباره ساختار شبکه‌های اجتماعی واقعی نشان می‌دهد.

موضوع اول High Modularity است، شبکه‌های اجتماعی یک توده‌ی همگن نیستند؛ بلکه از بخش‌های مستحکمی تشکیل شده‌اند (احتمالا منطبق بر ساختارهای دانشکده‌ای، خوابگاهی یا گروه‌های ورزشی). این خوشه‌ها چسبندگی داخلی بالایی دارند که نفوذ به آن‌ها از طریق انتشار طبیعی تقریباً غیرممکن است.

دومین مسئله، ناکارآمدی بذردهی پراکنده ست، وقتی ما بذرها را به صورت تصادفی در شبکه پخش می‌کنیم، آن‌ها به صورت انفرادی یا در گروه‌های کوچک در پشت دیوارهای این خوشه‌های مسدودکننده قرار می‌گیرند. از آنجا که تراکم داخلی خوشه بالای ۷۰٪ است، یک یا دو دوست فعال در بیرون دیوار، نمی‌توانند کسر نفوذ لازم (۳۰٪) را برای هیچ‌یک از اعضای داخل خوشه تأمین کنند.

این موضوع اثبات می‌کند که توقف انتشار در این شبکه‌ها، ناشی از بدشانسی در انتخاب بذرها نیست، بلکه ناشی از موانع ساختاری است. بنابراین، برای موفقیت در انتشار رفتارهای با هزینه متوسط و بالا (q >=0.3)، استراتژی ما باید از پخش تصادفی به سمت تمرکز در بخش خاصی تغییر کند؛ یعنی باید تلاش کنیم تا با انتخاب هوشمندانه بذرها، از این خوشه‌های مسدودکننده عبور کنیم.

۴-۳. آزمایش فرضیه پیوندهای ضعیف در مقایسه با سرایت پیچیده

پس از اثبات نقش بازدارنده‌ی خوشه‌های مسدودکننده، قدم بعدی یافتن استراتژی مناسب برای نفوذ به این ساختارهاست. در ادبیات کلاسیک شبکه (Granovetter, 1973)، همیشه بر اهمیت پیوندهای ضعیف یا همان پل‌های ارتباطی که گروه‌های دور از هم را به یکدیگر وصل می‌کنند، تأکید می‌شود. استدلال این است که این پل‌ها، اطلاعات را از بخش‌های تکراری شبکه خارج کرده و به مناطق جدید می‌برند. سوال این است که آیا این اصل برای انتشار رفتارهای پرهزینه با آستانه بالا همچنان صادق است؟

برای پاسخ به این مسئله، یک آزمایش طراحی شد تا کارایی دو استراتژی آغازین متفاوت را در شرایطی که رفتار نیازمند تقویت اجتماعی است (q=0.26)، مقایسه کنیم.

1. استراتژی خوشه‌محور (Cluster Strategy): انتخاب یک گروه ۵ نفره در مرکز یک خوشه متراکم (گره مرکزی با ضریب خوشه‌بندی بالا، CC = 1.0). در این گروه، اعضای بذر با یکدیگر پیوند دوستی دارند.

2. استراتژی پل‌محور (Bridge Strategy): انتخاب یک گروه ۵ نفره بر روی یک پل ارتباطی (گره مرکزی با ضریب خوشه‌بندی پایین، CC = 0.0). در این گروه، اعضای بذر همدیگر را نمی‌شناسند و هرکدام به بخش متفاوتی از شبکه متصل‌اند.

در شبکه Rice31 نتایج نشان داد که استراتژی خوشه‌محور موفق به فعال‌سازی نهایی ۸ گره شد (افزایش ۳ گره جدید)، در حالی که استراتژی پل‌محور تنها به ۷ گره رسید (افزایش ۲ گره جدید). اگرچه تفاوت کمی به نظر می‌رسد، اما جهت‌گیری آن خلاف پیش‌بینی‌های کلاسیک گرانووتر است. در شبکه Michigan23 برای حذف اثرات تصادفی و دستیابی به نتیجه‌ای قطعی، این آزمایش ۱۰۰ بار به صورت مستقل بر روی شبکه میشیگان تکرار شد. نتایج میانگین به این صورت است که میانگین نفوذ گروه پل ۵.۰۰ گره و میانگین نفوذ گروه خوشه ۵.۸۴ گره است.

از آنجا که اندازه بذر اولیه ۵ نفر بود، میانگین ۵.۰۰ به معنای شکست است. یعنی در ۱۰۰ بار آزمایش، استراتژی پل تقریباً هیچ‌گاه نتوانست حتی یک نفر جدید را در خارج از گروه اولیه فعال کند. دلیل شکست پل‌ها به ماهیت سرایت پیچیده برمی‌گردد. برای فعال‌سازی یک گره با آستانه q=0.26، فرد نیاز دارد که حدود ۲۶٪ از دوستانش فعال باشند.

در ساختار پل ۵ نفر بذر اولیه از هم دور هستند و همسایگان مشترک ندارند. وقتی سیگنال انتشار از طریق این پل‌ها به بیرون ارسال می‌شود، هر همسایه‌ی بیرونی تنها یک پیام دریافت می‌کند. یک پیام واحد برای غلبه بر آستانه ۲۶٪ کافی نیست.

در ساختار خوشه ۵ نفر بذر اولیه، دارای همسایگان مشترک زیادی هستند (ساختار مثلثی). این همسایگان مشترک، به جای دریافت یک سیگنال ضعیف، همزمان از جانب ۲ یا ۳ عضو بذر تحت فشار قرار می‌گیرند. این هم‌افزایی محلی (Local Synergy) باعث می‌شود آستانه مقاومت شکسته شده و افراد جدید فعال شوند.

این آزمایش نظریه سنتولا و میسی (۲۰۰۷) را تأیید می‌کند که برای انتشار رفتارهای پرهزینه، ما به پل‌های طولانی نیاز نداریم، بلکه به پل‌های عریض نیاز داریم؛ و خوشه‌های متراکم با فراهم کردن مسیرهای موازی، نقش همین پل‌های عریض را ایفا می‌کنند.

۴-۴. ارزیابی الگوریتم‌های بهینه‌سازی نفوذ

پس از شناخت موانع ساختاری (خوشه‌های مسدودکننده) و ناکارآمدی استراتژی‌های کلاسیک (پیوندهای ضعیف)، گام نهایی این پژوهش، حل مسئله ماکزیمم‌سازی نفوذ است. هدف در این مرحله، شناسایی مجموعه‌ای بهینه از k=10 گره شروع‌کننده ست که بتوانند در شرایط q=0.2، بیشترین گستره انتشار را در شبکه ۳۰ هزار گره‌ای میشیگان ایجاد کنند.

به منظور ارزیابی کارایی، الگوریتم بهینه‌سازی حریصانه در برابر سه استراتژی Heuristic متداول مبتنی بر مرکزیت مقایسه شد:

1. بیشترین درجه (High Degree): انتخاب ۱۰ گره محبوب شبکه.

2. مرکزیت بینابینی (Betweenness): انتخاب ۱۰ گره که بیشترین نقش پل ارتباطی را دارند.

3. رتبه صفحه (PageRank): انتخاب ۱۰ گره با بیشترین اعتبار ساختاری.

نتایج حاصل از شبیه‌سازی نهایی نشان‌دهنده یک شکاف عملکردی میان روش پیشنهادی و روش‌های سنتی است.

همان‌طور که مشاهده می‌شود، الگوریتم حریصانه با فعال‌سازی ۶۰۲ گره، عملکردی فراتر از انتظار داشته است. این میزان، بیش از ۱۱ برابر بهتر از استراتژی درجه (۵۴ گره) و تقریبا ۸ برابر بهتر از بهترین هیوریستیک یعنی مرکزیت بینابینی با ۷۴ گره است.

شکست روش‌های مبتنی بر درجه و PageRank، یک واقعیت را درباره ساختار شبکه‌های اجتماعی بیان می‌کند، اینکه پدیده افزونگی ساختاری (Structural Redundancy). گره‌هایی که بیشترین درجه را دارند (مثلا محبوب‌ترین دانشجویان)، معمولاً با یکدیگر دوست هستند و تشکیل یک Rich Club را می‌دهند. وقتی ما ۱۰ نفر اول لیست درجه را انتخاب می‌کنیم، عملاً تمامی منابع خود را در یک ناحیه متراکم از شبکه متمرکز کرده‌ایم. این بذرها، همسایگان مشترک زیادی دارند و نفوذ آن‌ها هم‌پوشانی شدیدی دارد. در نتیجه، انرژی انتشار صرف فعال‌سازی مجدد گره‌هایی می‌شود که قبلاً توسط بذر دیگری فعال شده‌اند و آبشار نمی‌تواند از مرزهای آن خوشه خارج شود.

کشف مکمل‌های استراتژیک موفقیت الگوریتم حریصانه ناشی از توانایی آن در مدیریت این هم‌پوشانی‌هاست. بررسی لاگ اجرایی الگوریتم پدیده‌ای به نام انفجارهای تأخیری را نشان می‌دهد. در گام‌های اول و دوم، الگوریتم گره‌هایی را انتخاب کرد که نفوذ متوسطی داشتند (+۲۲ و +۴۲). اما در گام سوم، الگوریتم گرهی را انتخاب کرد که ناگهان منجر به فعال‌سازی ۲۷۱ گره جدید شد. مجدداً در گام هشتم، انتخاب گرهی دیگر منجر به جهش ۱۶۴ نفری شد.

این رفتار نشان می‌دهد که الگوریتم حریصانه به دنبال قوی‌ترین فرد نمی‌گردد، بلکه به دنبال بهترین مکمل می‌گردد. گره انتخاب شده ممکن است به تنهایی قدرتمند نباشد، اما در ترکیب با بذرهای انتخاب شده در مراحل قبل، توانسته است آستانه مقاومت یک خوشه مسدودکننده بزرگ را بشکند. این هم‌افزایی میان بذرها، ویژگی منحصر‌به‌فردی است که هیچ‌یک از معیارهای مرکزیت ایستا قادر به درک آن نیستند و فقط از طریق شبیه‌سازی دینامیک (روش حریصانه) قابل شناسایی است.

۴-۵. حل چالش زمان با الگوریتم CELF

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

الگوریتم حریصانه کلاسیک برای یافتن ۱۰ گره بذر در شبکه ۳۰ هزار گره‌ای میشیگان، نیازمند ارزیابی نفوذ حاشیه‌ای تمام گره‌ها در تمام دورها بود. این فرآیند منجر به زمان اجرای بسیار طولانی (بیش از ۴.۵ ساعت) شد. چنین هزینه زمانی برای شبکه‌های واقعی امروزی یا برای سناریوهایی که نیاز به تعداد بذر بیشتر (k=50 یا k=100) دارند، قابل پذیرش نیست.

برای حل این موضوع، نسخه بهینه‌سازی شده‌ای از الگوریتم با نام CELF (Cost-Effective Lazy Forward) پیاده‌سازی شد. این الگوریتم بدون آنکه از دقت الگوریتم حریصانه کم کند، با بهره‌گیری هوشمندانه از ویژگی‌های ریاضی تابع نفوذ، زمان اجرا را به طرز چشمگیری کاهش می‌دهد.

ویژگی Submodularity بیان می‌کند که Marginal Gain افزودن یک گره خاص به مجموعه بذر، با بزرگتر شدن مجموعه بذر، هرگز افزایش نمی‌یابد.

بنابراین، اگر گره u در دور اول سود حاشیه‌ای ۱۰۰ داشته باشد و گره v سود ۹۰، در دور دوم سود u ممکن است به ۸۰ کاهش یابد، اما هرگز ۱۰۱ نخواهد شد. CELF از این واقعیت برای Lazy Evaluation استفاده می‌کند. گره‌ها در یک صف اولویت نگهداری می‌شوند و در هر دور، تنها نفوذ گره‌های بالای صف به‌روزرسانی می‌شود. اگر گره بالای صف پس از به‌روزرسانی همچنان از نفر دوم (که مقدارش مربوط به دور قبل است) بالاتر باشد، بدون نیاز به محاسبه سایرین، به عنوان برنده انتخاب می‌شود.

تفاوت جزئی در تعداد گره‌های فعال ناشی از ماهیت احتمالاتی شبیه‌سازی مونت‌کارلو است و به معنای تفاوت در منطق انتخاب نیست. پیاده‌سازی CELF توانست زمان اجرا را از حدود ۵ ساعت به کمتر از ۴۰ ثانیه کاهش دهد. تحلیل لاگ سیستم نشان می‌دهد که پس از محاسبه اولیه، الگوریتم CELF برای انتخاب ۱۰ بذر نهایی، تنها ۱۸ بار شبیه‌ساز را فراخوانی کرده است (در مقایسه با حدود ۳۰۰,۰۰۰ فراخوانی در روش حریصانه).

بررسی مجموعه بذر خروجی نشان می‌دهد که CELF موفق به شناسایی دقیق همان گره‌ها شده است. گره‌های کلیدی مانند 16995 (عامل جهش اول) و 14040 (عامل جهش دوم) دقیقاً در خروجی CELF نیز حضور دارند.

۵. جمع‌بندی

این پژوهش با هدف بررسی دینامیک انتشار در شبکه‌های اجتماعی و بهینه‌سازی نفوذ انجام شد. با عبور از مدل‌های ویروسی و پیاده‌سازی مدل آستانه خطی با پارامترهای ناهمگن بر روی دو مجموعه داده واقعی (Rice31 و Michigan23)، نتایجی حاصل شد که هم از دید نظری و هم از منظر کاربردی حائز اهمیت است.

دستاوردهای کلیدی:

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

2. آزمون‌های مقایسه‌ای نشان داد که برای سرایت پیچیده که یک رفتار پرهزینه محسوب می‌شود، تئوری کلاسیک قدرت پیوندهای ضعیف کارایی ندارد. در عوض، شروع انتشار از درون خوشه‌های متراکم به دلیل ایجاد تقویت اجتماعی و هم‌افزایی بین بذرها، استراتژی موفق‌تری است.

3. در بخش بهینه‌سازی، نشان داده شد که معیارهای سنتی مانند بیشترین درجه یا PageRank به دلیل نادیده گرفتن هم‌پوشانی نفوذ، عملکرد ضعیفی دارند. در مقابل، الگوریتم حریصانه با شبیه‌سازی دینامیک شبکه و کشف مکمل‌های استراتژیک، توانست نفوذی ۱۱ برابر بیشتر ایجاد کند.

4. با پیاده‌سازی الگوریتم CELF، نشان داده شد که می‌توان بر چالش NP-Hard بودن مسئله غلبه کرد. کاهش زمان اجرا از ۴.۵ ساعت به کمتر از ۴۰ ثانیه بدون افت دقت، امکان پیاده‌سازی این راهکار را در شبکه‌هایی با مقیاس بزرگ فراهم می‌کند.

این پژوهش می‌تواند در چند جهت توسعه یابد که به برخی از آن‌ها اشاره می‌کنیم:

• در نظر گرفتن بُعد زمان: مدل فعلی تنها نفوذ نهایی را می‌سنجد. می‌توان با افزودن پارامتر زمان، سرعت انتشار را نیز بهینه کرد.

• Adaptive Seeding: به جای انتخاب تمام k بذر در ابتدا، می‌توان بذرها را در چند مرحله انتخاب کرد تا از وضعیت جدید شبکه پس از موج اول انتشار بهره‌برداری شود.

• Competitive Diffusion: بررسی حالتی که دو رفتار متضاد (مثلاً شایعه و تکذیبیه) همزمان در شبکه منتشر می‌شوند و برای گرفتن گره‌ها رقابت می‌کنند.

منابع:

[1] Centola, D., & Macy, M. (2007). Complex Contagion and the Weakness of Long Ties. American Journal of Sociology, 113(3), 702-734.

[2] Easley, D., & Kleinberg, J. (2010). Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press. (Chapter 19: Cascading Behavior in Networks).

[3] Granovetter, M. S. (1973). The Strength of Weak Ties. American Journal of Sociology, 78(6), 1360-1380.

[4] Kempe, D., Kleinberg, J., & Tardos, É. (2003). Maximizing the spread of influence through a social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '03), 137-146.

[5] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., & Glance, N. (2007). Cost-effective outbreak detection in networks. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD '07), 420-429.

[6] Rossi, R., & Ahmed, N. (2015). The Network Data Repository with Interactive Graph Analytics and Visualization. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence.

[7] Watts, D. J. (2002). A Simple Model of Global Cascades on Random Networks. Proceedings of the National Academy of Sciences (PNAS), 99(9), 5766-5771.