علوم رایانش و فناوری اطلاعات

الگوریتم رتبه‌صفحه غیر‌یکنواخت با استفاده از بردار‌های ویژگی و بردارهای تعبیه گره‌ها (در دست انتشار)

نویسندگان

دانشکده مهندسی کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

چکیده

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

کلیدواژه‌ها

  • [1]L. Page, S. Brin, R. Motwani, and T. Winograd, "The PageRank Citation Ranking: Bringing Order to the Web", Proceedings of the 7th International Conference on World Wide Web, Brisbane, Australia, 1998.
  • [2]S. D. Kamvar, T. H. Haveliwala, C. D. Manning, and G. H. Golub, "Exploiting the Block Structure of the Web for Computing PageRank," Tech. Rep. 2003-17, Stanford University, Stanford, California, USA, 2003.
  • [3]P. Berkhin, "A Servey on PageRank Computing," Internet Mathematics, vol. 2, no. 1, pp. 5-32, 2005.
  •  
  • [4]T. H. Haveliwala, "Topic-sensitive PageRank", Proceedings of the 11th International Conference on World Wide Web, Honolulu Hawaii USA, pp. 517-526, 2002.
  • [5]S. Chakrabarti, "Dynamic Personalized PageRank in Entity-Relation Graphs," Proceedings of the 16th International Conference on World Wide Web, Alberta, Canada, pp. 571-580, 2007.
  • [6]B. Bahmani, A. Chowdhury, and A. Goel, "Fast Incremental and Personalized PageRank," Proc. VLDB Endow., vol. 4, no. 3, pp. 173-184, 2010.
  • [7] M. H. Chehreghani, "Dynamical Algorithms for Data Mining and Machine Learning over Dynamic Graphs," WIREs Data Mining Knowl. Discov., vol. 11, no. 2, 2021.
  • [8]B. Bahmani, R. Kumar, M. Mahdian, and E. Upfal, "PageRank on an Evolving Graph," Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 24-32, 2012.
  • [9] N. Ohsaka, T. Maehara, and K. Kawarabayashi, "Efficient PageRank Tracking in Evolving Networks," Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 875-884, 2015.
  • [10] W. Guo, Y. Li, M. Sha, and K.-L. Tan, "Parallel Personalized Pagerank on Dynamic Graphs," Proc. VLDB Endow., vol. 11, no. 1, pp. 93-106, 2017.
  • [11] Z. Wei, X. He, X. Xiao, S. Wang, S. Shang, and J.-R. Wen, "TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs," Proceedings of the 2018 International Conference on Management of Data (SIGMOD Conference), pp. 441-456, 2018.
  • [12] V. Thangasamy, "Efficacious Hyperlink Based Similarity Measure Using Heterogeneous Propagation of PageRank Scores," International Journal of Information Retrieval Research, vol. 9, no. 4, pp. 36-49, 2019.
  • [13] A. Grover, and J. Leskovec, "node2vec: Scalable Feature Learning for Networks," Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 855-864, 2016.
  • [14]T. N. Kipf, and M. Wellin, "Semi-Supervised Classification with Graph Convolutional Networks," Proceedings of the 5th International Conference on Learning Representations (ICLR), arXiv: 1609.02907v4, 2017.
  • [15] J. Bar-Ilan, M. Mat-Hassan, and M. Levene, "Methods for Comparing Rankings of Search Engine Results," Comput. Networks, vol. 50, no. 10, pp. 1448-1463, 2006.
  • [16]W. L. Hamilton, Z. Ying, and Jure Leskovec, "Inductive Representation Learning on Large Graphs," Proceedings of Annual Conference on Neural Information Processing Systems (NIPS), pp. 1024-1034, 2017.
  • [17] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, "A Comprehensive Survey on Graph Neural Networks," IEEE Trans. Neural Networks Learn. Syst., vol. 32, no. 1, pp. 4-24, 2021.
  • [18]A. Boodaghian-Asl, J. Raghothama, A. Darwich, and S. Meijer, "Using PageRank and social network analysis to specify mental health factors," Proceedings of the Design Society: 23rd International Conference on Engineering Design (ICED), 2021.
  • [19] H. Nassar, A. R. Benson, and D. F. Gleich, "Neighborhood and PageRank methods for pairwise link prediction," Soc. Netw. Anal. Min., vol. 10, no. 1, article no. 63, 2020.
  • [20] H. Wang, Z. Wei, J. Gan, S. Wang, and Z. Huang, "Personalized PageRank to a Target Node, Revisited," Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pp. 657-667, 2020.
  • [21] H. Lang, C. Baykal, N. A. Samra, T. Tannous, D. Feldman, and D. Rus, "Deterministic Coresets for Stochastic Matrices with Applications to Scalable Sparse PageRank," Proceedings of the 15th Annual Conference on Theory and Applications of Models of Computation (TAMC), pp. 410-423, 2019.
  • [22] S. N. Zaware, A. Gautam, S. Nashte, and P. Khanuja, "An Effectual Approach for Calculating Cosine Similarity," International Journal of Advance Engineering and Research Development, vol. 2, no. 4, pp. 1-4, 2015.
  • [23] A. Y. Alfakih, A. K. Khandani, and H. Wolkowicz, "Solving Euclidean Distance Matrix Completion Problems via Semidefinite Programming," Computational Optimization and Applications, vol. 12, no. 1, pp. 13-30, 1999.
  • [24]J. Chen, and Y. Liu, "Locally Linear Embedding: A Survey," Artif. Intell. Rev., vol. 36, no. 1, pp. 29-48, 2011.
  • [25] P. M. Domingos, "A few useful things to know about machine learning, " Commun. ACM, vol. 55, no. 10, pp. 78-87, 2012.
علوم رایانش و فناوری اطلاعات
دوره 19، شماره 2
پاییز و زمستان
آذر 1400