Tail Index Estimation of PageRanks in Evolving Random Graphs

Natalia Markovich (), Maksim Ryzhov and Marijus Vaičiulis
Additional contact information
Natalia Markovich: V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 117997 Moscow, Russia
Maksim Ryzhov: V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 117997 Moscow, Russia
Marijus Vaičiulis: Institute of Data Science and Digital Technologies, Vilnius University, Akademijos St. 4, LT-08663 Vilnius, Lithuania

Mathematics, 2022, vol. 10, issue 16, 1-26

Abstract: Random graphs are subject to the heterogeneities of the distributions of node indices and their dependence structures. Superstar nodes to which a large proportion of nodes attach in the evolving graphs are considered. In the present paper, a statistical analysis of the extremal part of random graphs is considered. We used the extreme value theory regarding sums and maxima of non-stationary random length sequences to evaluate the tail index of the PageRanks and max-linear models of superstar nodes in the evolving graphs where existing nodes or edges can be deleted or not. The evolution is provided by a linear preferential attachment. Our approach is based on the analysis of maxima and sums of the node PageRanks over communities (block maxima and block sums), which can be independent or weakly dependent random variables. By an empirical study, it was found that tail indices of the block maxima and block sums are close to the minimum tail index of representative series extracted from the communities. The tail indices are estimated by data of simulated graphs.

Keywords: random graph; evolution; PageRank; max-linear model; tail index; block maximum; block sum; community; preferential attachment (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/16/3026/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/16/3026/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:16:p:3026-:d:894730

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().