ارائه مدلی بهینه جهت یافتن کوتاهترین مسیرهای تخمینی با پوشش کامل گراف

نوع مقاله : مقاله پژوهشی فارسی

نویسندگان

1 گروه مهندسی کامپیوتر، دانشگاه یزد، یزد، ایران

2 دانشیار، دانشکده مهندسی برق و کامپیوتر، دانشگاه یزد، یزد، ایران

چکیده

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

کلیدواژه‌ها


[1]    درودی، ا.، برادران هاشمی، ه.، آل احمد، ا.، زارع بیدکی، ع. م.، حبیبیان، ا. ح.، مهدیخانی، ف.، شاکری، آ.، و رهگذر، م. (۱۳۸۷). مجموعه محک استاندارد برای تحقیقات بازیابی اطلاعات وب فارسی. (شماره گزارش: DBRG-TR-138702). گروه تحقیقاتی پایگاه داده: دانشگاه تهران.
[2]          Madkour, A., Aref, W. G., Rehman, F. U., Rahman, M. A., & Basalamah, S. (2017). A survey of shortest-path algorithms. arXiv preprint arXiv:1705.02044.
[3]          Potamias, M., Bonchi, F., Castillo, C., & Gionis, A. (2009, November). Fast shortest path distance estimation in large networks. In Proceedings of the 18 th ACM conference on Information and knowledge management (pp. 867-876). ACM.
[4]          Goldberg, A. V., & Harrelson, C. (2005, January). Computing the shortest path: A search meets graph theory. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms (pp.156-165(. Society for Industrial and Applied Mathematics.
[5]          Goldberg, A. V. (2007, January). Point-to-point shortest path algorithms with preprocessing. In International Conference on Current Trends in Theory and Practice of Computer Science (pp. 88-102). Springer, Berlin, Heidelberg.
[6]          Grant, K., & Mould, D. (2008, July). LPI: Approximating shortest paths using landmarks. In Workshop on Artificial Intelligence in Games (p. 45).
[7]          Gubichev, A., Bedathur, S., Seufert, S., & Weikum, G. (2010). Fast and accurate estimation of shortest paths in large networks. In 19th ACM Conference on Information and Knowledge Management (pp. 499-508). ACM.‏
[8]          Cao, L., Zhao, X., Zheng, H., & Zhao, B. Y. (2011). Atlas: Approximating shortest paths in social graphs. Computer Science Department, U. C. Santa Barbara.
[9]          Qiao, M., Cheng, H., Chang, L., & Yu, J. X. (2012). Approximate shortest distance computing: A query-dependent local landmark scheme. IEEE Transactions on Knowledge and Data Engineering, 26(1), 55-68.
[10]        Floreskul, V., Tretyakov, K., & Dumas, M. (2014, May). Memory-efficient fast shortest path estimation in large social networks. In Eighth International AAAI Conference on Weblogs and Social Media.
[11]        Feng, C., & Deng, T. (2018, October). More Accurate Estimation of Shortest Paths in Social Networks. In 2018 International Symposium on Distributed Computing and Applications for Business Engineering and Science (DCABES) (pp. 314-317). IEEE.
[12]        Dong, Q., Lakhotia, K., Zeng, H., Karman, R., Prasanna, V., & Seetharaman, G. (2018, September). A Fast and Efficient Parallel Algorithm for Pruned Landmark Labeling. In 2018 IEEE High Performance extreme Computing Conference (HPEC)(pp.1-7) . IEEE.
[13]        J. Leskovec, K. Lang, A. Dasgupta, M. Mahoney. (2009). Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics 6(1) 29--123.