Black hole metric: overcoming the PageRank normalization problem

DOI10.1016/J.INS.2018.01.033MaRDI QIDQ2195459zbMATH OpenOpenAlexFDO

Authors M. Buzzanca, A. Longheu, Giuseppe Mangioni, Vincenza Carchiolo, Michele Malgeri

Publication date 8 September 2020

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.05453

zbMATH Keywords

trustsocial networksPageRank metric

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

Abstract: In network science, there is often the need to sort the graph nodes. While the sorting strategy may be different, in general sorting is performed by exploiting the network structure. In particular, the metric PageRank has been used in the past decade in different ways to produce a ranking based on how many neighbors point to a specific node. PageRank is simple, easy to compute and effective in many applications, however it comes with a price: as PageRank is an application of the random walker, the arc weights need to be normalized. This normalization, while necessary, introduces a series of unwanted side-effects. In this paper, we propose a generalization of PageRank named Black Hole Metric which mitigates the problem. We devise a scenario in which the side-effects are particularily impactful on the ranking, test the new metric in both real and synthetic networks, and show the results.

Recommendations

• Generalisation of the Damping Factor in PageRank for Weighted Networks
• Ranking nodes in general networks: a Markov multi-chain approach
• PageRank beyond the web
• Non-backtracking PageRank
• PageRank optimization by edge selection

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• A Survey on PageRank Computing
• A trust prediction framework in rating-based experience sharing social networks without a Web of Trust
• Authoritative sources in a hyperlinked environment
• Deeper Inside PageRank
• Directed scale-free graphs
• PageRank beyond the web
• PageRank problem, survey and future research directions
• Perturbation of the hyper-linked environment
• String processing and information retrieval. 9th international symposium, SPIRE 2002, Lisbon, Portugal, September 11--13, 2002. Proceedings
• Towards Google matrix of brain

Cited in

(1)

• Parametric controllability of the personalized PageRank: Classic model vs biplex approach

Describes a project that uses

Uses Software

• KONECT

This page was built for publication: Black hole metric: overcoming the PageRank normalization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2195459)