Black hole metric: overcoming the PageRank normalization problem

DOI10.1016/J.INS.2018.01.033zbMATH Open1440.68184arXiv1802.05453OpenAlexW2785637338MaRDI QIDQ2195459FDOQ2195459

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)

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.

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

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

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)

Cites Work

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

Cited In (1)

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

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)