استاد: دکتر صادق علیاکبری
دانشجو: مجتبی خانلوشندی
دانشکده مهندسی کامپیوتر دانشگاه شهید بهشتی تهران
ترم پاییز ۱۴۰۳
در دنیای بههمپیوسته امروزه، شبکهها همهجا هستند. از مسیرهای پیچیده اینترنت گرفته تا تعاملات پیچیده سیستمهای اجتماعی و زیستی، شبکهها ستون فقرات بسیاری از سیستمهای دنیای واقعی را تشکیل میدهند. شبکههای پیچیده، به طور خاص، ویژگیهای توپولوژیکی غیر بدیهی دارند که آنها را از شبکههای سادهتر متمایز میکند [۱، ۳].
در بسیاری از منابع از لفظ شبکه پیچیده برای اطلاق به شبکه استفاده نشده، اما این شبکه ویژگیهای غیر بدیهی شبکههای پیچیده را دارا میباشد. مواردی مثل شبکههای اجتماعی و شبکه تورنت از جمله مواردی هستند که ویژگیهای غیر بدیهی و پویایی بالای شبکههای پیچیده و پویا را دارا هستند اما در منابع با لفظ شبکه پیچیده مواجه نیستیم. در این بررسی ما این گونه شبکهها را نیز در نظر گرفتهایم.
چالش جستجو در شبکه پیچیده:
یکی از چالشهای اساسی در این شبکهها، مسئله جستجو است: چالش جستجو در شبکههای پیچیده شامل یافتن اطلاعات، منابع یا گرههای خاص در این شبکهها است [۴]. رویکردهای متمرکز، با تکیه بر ایندکسها یا سرورهای مرکزی، در مواجهه با مقیاس وسیع و تغییرات سریع این شبکهها، ناکارآمد یا حتی غیرقابل اجرا میشوند [۴]. از این رو، تمرکز این مطالعه بر جستجوی غیرمتمرکز در شبکههای پیچیده است.
جستجوی غیرمتمرکز، به فرآیندی اطلاق میشود که در آن، گرههای منفرد، بدون نیاز به یک کنترلکننده مرکزی، به صورت محلی و با استفاده از دانش محدود خود از ساختار شبکه و همسایگانشان، به جستجوی اطلاعات یا منابع میپردازند. این رویکرد، به ویژه در شبکههایی که به دلیل حجم زیاد و تغییرات گرهها به و عدم داشتن دانش سراسری از شبکه غیر عملی است، از اهمیت ویژهای برخوردار است [۵].
در این مقاله، پیچیدگیهای جستجوی غیرمتمرکز در شبکههای پیچیده را با تمرکز بر پرسشهای کلیدی زیر بررسی خواهیم کرد:
با پرداختن به این پرسشها، هدف این مقاله، ارائه یک آشنایی اولیه از چالشها و رویکردهای موجود در زمینه جستجوی غیرمتمرکز در شبکههای پیچیده و همچنین بیان چالشهای موجود و موضوعات باز تحقیقاتی در این باره است.
در ادامه بخش اصطلاحات قبلی، توضیحات بیشتر و موارد دیگری برای درک بهتر مفاهیم ارائه میشود:
برای یافتن تحقیقات انجام گرفته در این زمینه اقدام به جستجو در ایندکس Scopus و Google Scholar کرده و از کلمات کلیدی "search" و "complex networks" استفاده شد ولی نتایج حاصله امیدوار کننده نبودند و بسیاری از موارد قدیمی و موارد جدیدتر در رابطه با خود مساله جستجو در شبکه پیچیده نبودند و همین مساله یکی از چالشهایی است که میتواند در تحقیقات دیگری به آن پرداخته و روشهایی نوین و جدید مختص به جستجو در شبکههای پیچیده و پویا با رویکردهای کلیتر ارائه کرد. بنابراین روش جستجوی منابع با استفاده از کلمات کلیدی به جستجو در سایت connected papers و براساس مقالات مشابه تغییر پیدا کرد.
در سایت connected papers با جستجوی عبارت "search in complex networks"، یک مقاله انتخاب شده و براساس این مقاله لیستی از مقالات مشابه نمایش داده شده و پس از مطالعه خلاصه مقاله اقدام به انتخاب مقالات مختص و یا مرتبط با جستجو در شبکههای پیچیده شد.
در حین جستجو به موردی برخوردیم که شایان ذکر است و آن اینکه منابعی بودند که دارای کلمه کلیدی "complex networks" نبودند ولی در رابطه با شبکهای بودند که بسیاری از ویژگیهای شبکههای پیچیده و پویا را داشت، شبکه تورنت و یا شبکههای اجتماعی. ما منابعی درباره جستجو در این شبکهها بودند را نیز اضافه کردیم و به طور کلی توصیه میکنیم که در جستجوی منابع برای موضوعات مرتبط با شبکههای پیچیده این نکته را در نظر بگیرید که الزاما منابع از کلمه کلیدی "complex networks" برای اطلاق به شبکهی مورد نظر خود استفاده نمیکنند.
الگوریتمهای جستجوی غیرمتمرکز برای پیمایش شبکههای پیچیده و پویا که دارای پویایی زیاد بوده و تغییرات زیادی رخ میدهد و ایجاد یک ایندکس مرکزی غیرعملی است، ضروری هستند. این الگوریتمها باید به طور کارآمد و بدون تکیه بر یک سازوکار مرکزی، بتوانند جستجو را انجام دهند. الگوریتمهای جستجوی غیرمتمرکز میتوانند به طور موثر با تغییرات زیاد در شبکههای پیچیده بدون نیاز به ایندکسهای مرکزی سازگار شوند. این امر از طریق به کارگیری راهکارهایی که از اطلاعات محلی و ویژگیهای شبکه بهره میبرند، امکانپذیر است. در اینجا نحوه عملکرد آن آمده است:
مکانیزمهای جستجوی هوشمند همتا(peer): همتاها [گرهها] میتوانند به طور مستقل تصمیم بگیرند که کدام همتاهای همسایه به احتمال زیاد به یک پرس و جوی مشخص پاسخ میدهند. این کار با ایجاد یک پروفایل از همتاهای خود و استفاده از آن برای تصمیمگیری در مورد محل ارسال پرس و جو انجام میشود. این پروفایل بر اساس رفتار گذشته و اطلاعات جمعآوری شده در زمان واقعی ساخته میشود. این امر به الگوریتم اجازه میدهد تا به خوبی با اندازه شبکه مقیاسپذیر شود، زیرا کاملاً توزیعشده است [۱].
جستجوی اول سطح (BFS) اصلاحشده: با گسترش پروتکلهای فعلی مانند Gnutella، جستجو با کلمات کلیدی و در عین حال به حداقل رساندن تعداد پیامهای مورد نیاز قابل دستیابی است. این مکانیزم میتواند به صورت محلی بر روی هر همتا اجرا شود، که به طور خودکار زیرمجموعهای تصادفی از همسایگان را برای ارسال هر پیام پرس و جو انتخاب میکند [۱].
بهرهگیری از ساختار شبکه: استراتژیهای جستجوی محلی که از ساختار شبکههای قانون توانی بهره میبرند، قابل استفاده هستند. الگوریتمهایی که ابتدا گرههای با اتصال بالا را با استفاده از مکانیزم جستجوی عمق اول جهتدار کاوش میکنند، میتوانند موثر باشند [۱].
اختلال تصادفی: برای جلوگیری از گیر افتادن پیامهای جستجو در یک چرخه، یک زیرمجموعه تصادفی کوچک از همتاها میتواند به مجموعه بهترین همتاها برای هر پرس و جو اضافه شود. این امر احتمال اینکه مکانیزم بخش بزرگتری از شبکه را کاوش کند و در مورد محتویات همتاهای اضافی اطلاعات کسب کند را افزایش میدهد [۱].
فشردهسازی مسیر: ذخیره اطلاعات مسیرهای مفید برای کاهش مراحل جستجو و جریان پرس و جو میتواند کارایی جستجو را بهبود بخشد. با ذخیره مسیرهای بازدید شده در مرحله اولیه هر جستجو، الگوریتم میتواند از مسیرهای ذخیره شده برای کاهش مراحل غیرضروری استفاده کند [۲].
منطق فازی برای بهینهسازی آشیانه: در شبکههای اجتماعی پویا، استفاده از بهینهسازی جستجوی فاخته با تکنیکهای فازیسازی برای بهروزرسانی آشیانه میزبان بر اساس مقدار تناسب آن و ویژگیهای ساختاری گره میتواند موثر باشد. استفاده از مرکزیت درجه و مرکزیت نزدیکی به همراه قدرت نفوذ گرهها میتواند منجر به کشف موثر مجموعه بذر شود [۳].
الگوریتمهای تطبیقی: به کارگیری الگوریتمهای تطبیقی به اجتناب از روشهای محاسبه مجدد و اندازهگیری مکرر تمام موارد و تغییرات در هر تصویر لحظهای در شبکههای اجتماعی آنلاین (OSN) پویا و پیچیده کمک میکند. الگوریتم تطبیقی به غلبه بر مشکلاتی مانند داشتن زمان اجرای پرهزینه، به دام افتادن در راهحلهای بهینه محلی و دریافت واکنشهای مشابه به تغییرات جزئی در جوامع محلی غیرفعال در شبکههای اجتماعی آنلاین پویا کمک میکند [۴].
این رویکردها با تکیه بر تصمیمگیری غیرمتمرکز و بهرهگیری از دانش محلی، امکان سازگاری موثر با تغییرات شبکه را فراهم میکنند و در عین حال از هزینهها و انعطافناپذیری مرتبط با کنترل مرکزی اجتناب میکنند.
ویژگیهای خاص شبکه، مانند توزیع درجه، ضریب خوشهبندی، ویژگی دنیای کوچک، ویژگی مقیاس-آزاد و درهمتنیدگی شبکه، به طور قابل توجهی بر عملکرد و مقیاسپذیری الگوریتمهای جستجو در شبکههای پیچیده، هم به صورت جداگانه و هم به صورت جمعی، تأثیر میگذارند. درک این تأثیرات برای طراحی استراتژیهای جستجوی کارآمد متناسب با ساختارهای شبکه خاص بسیار مهم است.
توزیع درجه:
ضریب خوشهبندی:
ویژگیهای دنیای کوچک:
درهمتنیدگی شبکه:
چندگانگی:
شبکههای پویا:
ساختار جامعه:
شبکههای علامتدار:
مبادله بین دقت، سرعت و هزینه:
به طور خلاصه، تعامل بین این ویژگیهای شبکه و الگوریتمهای جستجو، نیاز به الگوریتمهایی را برجسته میکند که تطبیقی، غیرمتمرکز و قادر به بهرهبرداری از ویژگیهای خاص شبکه برای دستیابی به عملکرد و مقیاسپذیری بهینه باشند [۳، ۱۰].
در طراحی الگوریتمهای جستجو برای شبکههای پیچیده، مبادلههای اساسی بین دقت، سرعت و هزینه نیازمند مدیریت دقیق و متناسب با کاربردهای خاص دنیای واقعی است. منابع تاکید میکنند که بهینهسازی این مبادلهها شامل ایجاد تعادل بین ویژگیهای شبکه و طراحی الگوریتم است [۵، ۸].
جنبههای کلیدی این مبادلهها و مدیریت آنها عبارتند از:
دقت در مقابل سرعت:
هزینه در مقابل بار شبکه:
پیچیدگی و مقیاسپذیری الگوریتم:
انطباقپذیری در شبکههای پویا:
بهرهبرداری از ویژگیهای شبکه:
نمونههای کاربرد دنیای واقعی:
به طور خلاصه، مدیریت موثر مبادلهها بین دقت، سرعت و هزینه نیازمند رویکردی ظریف است که ویژگیهای خاص شبکه و خواستههای کاربرد را در نظر بگیرد. الگوریتمها باید تطبیقی، غیرمتمرکز و قادر به بهرهبرداری از ویژگیهای شبکه برای دستیابی به عملکرد بهینه باشند [۵، ۱۵].
در این مقاله، به بررسی چالشها و رویکردهای موجود در زمینه جستجوی غیرمتمرکز در شبکههای پیچیده پرداختیم. ابتدا به اهمیت جستجوی غیرمتمرکز در شبکههای پیچیده و پویایی که دارای پویایی زیاد بوده و تغییرات زیادی رخ میدهد و ایجاد یک ایندکس مرکزی غیرعملی است، پرداختیم. سپس به بررسی چگونگی سازگاری الگوریتمهای جستجوی غیرمتمرکز با تغییرات پویای شبکههای پیچیده بدون داشتن یک ایندکس یا سازوکار جستجوی متمرکز پرداختیم و راهکارهایی از جمله مکانیزمهای جستجوی هوشمند همتا، جستجوی اول سطح اصلاحشده، بهرهگیری از ساختار شبکه، اختلال تصادفی، فشردهسازی مسیر و منطق فازی برای بهینهسازی آشیانه را مورد بحث قرار دادیم. در ادامه، تأثیر ویژگیهای خاص شبکه، از جمله توزیع درجه، ضریب خوشهبندی، ویژگی دنیای کوچک، ویژگی مقیاس-آزاد و سایر ویژگیهای شبکههای پیچیده و پویا، به صورت مجزا و ترکیبی بر عملکرد و مقیاسپذیری الگوریتمهای جستجوی مختلف در شبکههای پیچیده را بررسی کردیم. در نهایت، به مبادله بنیادین بین دقت، سرعت و هزینه در طراحی الگوریتمهای جستجو برای شبکههای پیچیده و چگونگی بهینهسازی این هزینه-فایده و مدیریت آن متناسب با کاربردهای مختلف در دنیای واقعی پرداختیم و مواردی از جمله الگوریتمهای ابتکاری، تقریب، ساختارهای متمرکز و غیرمتمرکز، پیچیدگی و مقیاسپذیری الگوریتم، انطباقپذیری در شبکههای پویا، بهرهبرداری از ویژگیهای شبکه و نمونههای کاربرد دنیای واقعی را مورد بحث قرار دادیم.
با بررسی این پرسشها، به درک عمیقتری از چالشها و رویکردهای موجود در زمینه جستجوی غیرمتمرکز در شبکههای پیچیده دست یافتیم. نتایج این بررسی نشان میدهد که طراحی الگوریتمهای جستجوی کارآمد در شبکههای پیچیده، نیازمند توجه به ویژگیهای خاص شبکه، مبادله بین دقت، سرعت و هزینه، و همچنین توانایی سازگاری با تغییرات پویای شبکه است.
امیدواریم که این مقاله، گامی در جهت آشنایی با چالشها و رویکردهای موجود در زمینه جستجوی غیرمتمرکز در شبکههای پیچیده باشد و زمینهای را برای تحقیقات آینده در این زمینه فراهم کند.
[1] Kalogeraki, V., Gunopulos, D., & Zeinalipour-Yazti, D. (2002). A local search mechanism for peer-to-peer networks. In Proceedings of the eleventh international conference on Information and knowledge management (pp. 300–307). CIKM02: Eleventh ACM International Conference on Information and Knowledge Management. ACM. 10.1145/584792.584842
[2] Shishavan, S. T., & Gharehchopogh, F. S. (2022). An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks. In Multimedia Tools and Applications (Vol. 81, Issue 18, pp. 25205–25231). Springer Science and Business Media LLC. 10.1007/s11042-022-12409-x
[3] Kumar Meena, S., Sheshar Singh, S., & Singh, K. (2024). Cuckoo Search Optimization-Based Influence Maximization in Dynamic Social Networks. In ACM Transactions on the Web (Vol. 18, Issue 4, pp. 1–25). Association for Computing Machinery (ACM). 10.1145/3690644
[4] Complex Networks & Their Applications XII. (2024). In H. Cherifi, L. M. Rocha, C. Cherifi, & M. Donduran (Eds.), Studies in Computational Intelligence. Springer Nature Switzerland. 10.1007/978-3-031-53503-1
[5] De Leo, D., Banuelos, J., & Parvez, I. (2024). An Analysis of Informed Search Algorithms Applied on Road Networks. 2024 Intermountain Engineering, Technology and Computing (IETC), 69-73.
[6] Shishavan, S. T., & Gharehchopogh, F. S. (2022). An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks. Multimedia Tools and Applications, 81(18), 25205-25231.
[7] Zhong, N., Guo, R., & Li, W. (2009, September). Local search in weighted and directed social networks: The case of enron email networks. In 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (Vol. 1, pp. 12-19). IEEE.
[8] Arenas, A., Cabrales, A., Díaz-Guilera, A., Guimerà, R., & Vega-Redondo, F. (2003). Search and Congestion in Complex Networks. In Lecture Notes in Physics (pp. 175–194). Springer Berlin Heidelberg. 10.1007/978-3-540-44943-0_11
[9] Yuan, Y., Chen, W., Feng, M., & Qu, H. (2013, December). An Improved Search Algorithm Based on Path Compression for Complex Network. In 2013 IEEE 11th International Conference on Dependable, Autonomic and Secure Computing (pp. 308-313). IEEE.
[10] Saha, S., & Ghrera, S. P. (2015). Nearest neighbor search in complex network for community detection. arXiv preprint arXiv:1511.07210.
[11] Huang, Y., Wang, H., Ren, X. L., & Lü, L. (2024). Identifying key players in complex networks via network entanglement. Communications Physics, 7(1), 19.
[12] Yang, F., Ma, H., Yan, C., Li, Z., & Chang, L. (2023). Polarized communities search via co-guided random walk in attributed signed networks. ACM Transactions on Internet Technology, 23(4), 1-22.
[13] Malkov, Y. A., & Yashunin, D. A. (2018). Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4), 824-836.
[14] Tang, Y., Li, J., Haldar, N. A. H., Guan, Z., Xu, J., & Liu, C. (2022). Reliable community search in dynamic networks. arXiv preprint arXiv:2202.01525.
[15] Aoyama, K., Saito, K., Yamada, T., & Ueda, N. (2009). Fast similarity search in small-world networks. In Complex Networks: Results of the 2009 International Workshop on Complex Networks (CompleNet 2009) (pp. 185-196). Springer Berlin Heidelberg.
