Network Capacity Bound for Personalized PageRank in Multimodal Networks

• Autorzy: Kłopotek Mieczysław Alojzy , Wierzchoń Sławomir , Kłopotek Robert A.

Identyfikatory

DOI

10.3233/FI-222151

• Języki publikacji: EN

Abstrakty

EN

In a former paper [1] the concept of Bipartite PageRank was introduced and a theorem on the limit of authority flowing between nodes for personalized PageRank has been generalized. In this paper we want to extend those results to multimodal networks. In particular we deal with a hypergraph type that may be used for describing multimodal network where a hyperlink connects nodes from each of the modalities. We introduce a generalisation of PageRank for such graphs and define the respective random walk model that can be used for computations. We state and prove theorems on the limit of outflow of authority for cases where individual modalities have identical and distinct damping factors.

Słowa kluczowe

EN

PageRank; random walk; ranking; multimodal networks; social networks; M-uniform M-partite hypegraphs; authority flow bounds

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 189, nr 1.
• Strony: 49--68
• Opis fizyczny: Bibliogr. 43 poz., tab.

Twórcy

autor

Kłopotek Mieczysław Alojzy

• Institute of Computer Science Polish Academy of Sciences, Warsaw, Poland

• https://orcid.org/0000-0003-4685-7045

autor

Wierzchoń Sławomir

• Institute of Computer Science Polish Academy of Sciences, Warsaw, Poland

• https://orcid.org/0000-0001-8860-392X

autor

Kłopotek Robert A.

• Institute of Computer Science Polish Academy of Sciences, Warsaw, Poland

Bibliografia

• [1] Kłopotek MA, Wierzchoń ST, Kłopotek RA, Kłopotek EA. Network Capacity Bound for Personalized Bipartite PageRank. In: S M, J M (eds.), Challenges in Computational Statistics and Data Mining, volume Studies in Computational Intelligence, vol 605, pp. 189-204. Springer, Cham. ISBN ISBN 10.1007/978-3-319-18781-5, 2016.
• [2] Page L, Brin S, Motwani R, Winograd T. The PageRank citation ranking: bringing order to the Web. Technical Report 1999-66, Stanford InfoLab, 1999. URL: http://ilpubs.stanford.edu:8090/422/.
• [3] Brezinski C, Redivo-Zaglia M. The PageRank Vector: Properties, Computation, Approximation, and Acceleration. SIAM J. Matrix Anal. Appl., 2006. 28(2):551-575. doi:10.1137/050626612. URL https://doi.org/10.1137/050626612.
• [4] Wierzchoń ST, Kłopotek MA, Ciesielski K, Czerski1 D, Drami´nski M. Accelerating PageRank computations. Control & Cybernetics, 201. 40(2):259-274. https://yadda.icm.edu.pl/baztech/element/bwmeta1.element.baztech-article-BATC-0008-0003.
• [5] Langville AN, Meyer CD. Google’s PageRank and beyond: the science of search engine rankings. Princeton University Press, 2006.
• [6] Berkhin P. A survey on PageRank computing. Internet Mathematics, 2005. 2:73-120.
• [7] Link S. Eigenvalue-based bipartite ranking. Bachelorarbeit/bachelor thesis, Institute of Computer Science, Ludwig-Maximilians-University in Munich, 2011. URL: http://www.pms.ifi.lmu.de/publikationen/#PA_Stephan.Link.
• [8] Deng H, Lyu MR, King I. A generalized Co-HITS algorithm and its application to bipartite graphs. In: Proc. of the 15th ACM SIGKDD International Conf. on Knowledge Discovery and Data Mining, KDD’09.ACM New York, NY, USA, Paris, 2009 pp. 239-248. doi:10.1145/1557019.1557051.
• [9] Bauckhage C. Image tagging using PageRank over bipartite graphs. In: Proc. of the 30th DAGM Symposium on Pattern Recognition. Springer-Verlag, Berlin, Heidelberg, 2008 pp. 426-435. doi:10.1007/978-3-540-69321-5 43.
• [10] Korner C, Kern R, Grahsl HP, Strohmaier M. Of Categorizers and Describers: An Evaluation of Quantitative Measures for Tagging Motivation. In: Proceedings of the 21st ACM Conference on Hypertext and Hypermedia, HT ’10. ACM, New York, NY, USA. ISBN 978-1-4503-0041-4, 2010 pp. 157-166.
• [11] Chen F, Gao Y, Cao D, Ji R. Multimodal hypergraph learning for microblog sentiment prediction. In: 2015 IEEE International Conference on Multimedia and Expo, ICME 2015, Turin, Italy, June 29 - July 3, 2015. IEEE, 2015 pp. 1-6.
• [12] Grolmusz V. A Note on the PageRank of Undirected Graphs. CoRR, 2012. abs/1205.1960. 1205.1960, URL http://arxiv.org/abs/1205.1960.
• [13] Chung F. A brief survey of PageRank algorithms. IEEE Transactions on Network Science and Engineering, 2014. 1(1):38-42.
• [14] Gleich DF. PageRank Beyond the Web. SIAM Review, 2015. 57(3):321-363. doi:10.1137/140976649.
• [15] Takai Y, Miyauchi A, Ikeda M, Yoshida Y. Hypergraph Clustering Based on PageRank. CoRR, 2020. abs/2006.08302. 2006.08302, URL https://arxiv.org/abs/2006.08302.
• [16] Li P, Milenkovic O. Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering. CoRR, 2018. abs/1803.03833. 1803.03833, URL http://arxiv.org/abs/1803.03833.
• [17] Mycroft R. Packing k-partite k-uniform hypergraphs. Journal of Combinatorial Theory, Series A, 2016. 138:60-132. https://doi.org/10.1016/j.jcta.2015.09.007.
• [18] Han J, Zang C, Zhao Y. Matchings in k-partite k-uniform hypergraphs. Journal of Graph Theory, 2020. 95(1):34-58.
• [19] Schauz U. A Paintability Version of the Combinatorial Nullstellensatz, and List Colorings of k-partite k-uniform Hypergraphs. The Electronic Journal of Combinatorics, 2010. 17(R176). doi:10.37236/448.
• [20] Petrovic D. Introducing: HyperPagerank. http://dejanseo.com.au/introducing-hyperpagerank/.
• [21] Berlt K, de Moura ES, Carvalho A, Cristo M, Ziviani N, Couto T. Modeling the Web As a Hypergraph to Compute Page Reputation. Inf. Syst., 2010. 35(5):530-543. doi:10.1016/j.is.2009.02.005.
• [22] Bradley JT, de Jager DV, Knottenbelt WJ, Trifunoviæ A. Hypergraph partitioning for faster parallel PageRank computation. In: Lecture Notes in Computer Science 3670. Springer, 2005 pp. 155-171. doi:10.1007/11549970 12.
• [23] Hotho A, J¨aschke R, Schmitz C, Stumme G. Information Retrieval in Folksonomies: Search and Ranking. In: Proceedings of the 3rd European Conference on The Semantic Web: Research and Applications, ESWC’06. Springer-Verlag, Berlin, Heidelberg. ISBN 3-540-34544-2, 978-3-540-34544-2, 2006 pp. 411-426. doi:10.1007/11762256 31.
• [24] Hotho A, J¨aschke R, Schmitz C, Stumme G. FolkRank: A Ranking Algorithm for Folksonomies. In: Proc. FGIR 2006. 2006 URL http://www.kde.cs.uni-kassel.de/stumme/papers/2006/hotho2006folkrank.pdf.
• [25] Bellaachia A, Al-Dhelaan M. Random Walks in Hypergraph. In: Proceedings of the 2013 International Conference on Applied Mathematics and Computational Methods. 2013.
• [26] Cooper C, Frieze AM, Radzik T. The cover times of random walks on random uniform hypergraphs. Theor. Comput. Sci., 2013. 509:51-69. doi:10.1016/j.tcs.2013.01.020.
• [27] Neubauer N, Obermayer K. Towards Community Detection in k-Partite k-Uniform Hypergraphs. In: Proceedings of the NIPS 2009 Workshop on Analyzing Networks and Learning with Graphs. 2009 pp. 1-9. http://snap.stanford.edu/nipsgraphs2009/papers/neubauer-paper.pdf.
• [28] Xu J, Singh V, Guan Z, Manjunath BS. Unified hypergraph for image ranking in a multimodal context. In: ICASSP. IEEE. ISBN 978-1-4673-0046-9, 2012 pp. 2333-2336.
• [29] Bu J, Tan S, Chen C, Wang C, Wu H, Zhang L, He X. Music Recommendation by Unified Hypergraph: Combining Social Media Information and Music Content. In: Proceedings of the International Conference on Multimedia, MM ’10. ACM, New York, NY, USA. ISBN 978-1-60558-933-6, 2010 pp. 391-400. doi:10.1145/1873951.1874005.
• [30] Schaub MT, Benson AR, Horn P, Lippner G, Jadbabaie A. Random Walks on Simplicial Complexes and the normalized Hodge Laplacian. CoRR, 2018. abs/1807.05044. 1807.05044, URL http://arxiv.org/abs/1807.05044.
• [31] Baeza-Yates R, Boldi P, Castillo C. Generic Damping Functions for Propagating Importance in Link-Based Ranking. Internet Mathematics, 2006. 3(4):445-478. URL http://projecteuclid.org/euclid.im/1227025009.
• [32] Belazzougui D, Boldi P, Ottaviano G, Venturini R, Vigna S. Cache-Oblivious Peeling of Random Hypergraphs. ArXiv e-prints, 2013. 1312.0526.
• [33] Nivre J. Non-projective dependency parsing in expected linear time. In: Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 1, ACL ’09. Association for Computational Linguistics, 2009 pp. 351-359. doi:10.3115/1687878.1687929.
• [34] Berkhin P. A survey on PageRank computing. Internet Mathematics, 2005. 2:73-120. doi:10.1080/15427951.2005.10129098.
• [35] Langville AN. An annotated bibliography of papers about Markov chains and information retrieval, 2005. URL: http://www.cofc.edu/~langvillea/bibtexpractice.pdf.
• [36] Chung F. PageRank as a discrete Green’s function. In: International Conference to Celebrate the Birthday of Shing-Tung Yau, August 27-September 1, 2008; also Geometry and Analysis I ALM 17, 285-302 (2010). 2008.
• [37] Chung F. PageRank as a discrete Green’s function. In: Ji L (ed.), Geometry and Analysis, I, volume 17 of Advanced Lectures in Mathematics (ALM), pp. 285-302. International Press of Boston, 2011.
• [38] Bauckhage C. Image tagging using PageRank over bipartite graphs. In: Proc. of the 30th DAGM Symposium on Pattern Recognition. Springer-Verlag, Berlin, Heidelberg. ISBN 978-3-540-69320-8, 2008 pp. 426-435.
• [39] Frahm K, Georgeot B, Shepelyansky D. Universal emergence of PageRank. J. Phys. A: Math. Theor.,2011. 44:465101. Doi: 10.1088/1751-8113/44/46/465101.
• [40] Garcia E, Pedroche F, Romance M. On the localization of the personalized PageRank of complex networks. Linear Algebra and its Applications, 2013. 439:640-652.
• [41] Meghabghab G, Kandel A. Search Engines, Link Analysis, and User’s Web Behavior. A Unifying Web Mining Approach, volume 99 of Studies in Computational Intelligence. Springer, 2008.
• [42] Zachary W. An information flow model for conflict and fission in small groups. J. of Anthropological Res., 1977. 33:452-473.
• [43] Mycroft R. Packing k-partite k-uniform hypergraphs, 2014. doi:10.48550/ARXIV.1402.5643. URL https://arxiv.org/abs/1402.5643.