Tail Index Estimation of PageRanks in Evolving Random Graphs

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.

Automated summary

This paper conducts a statistical analysis of the extremal part of random graphs and evaluates the tail index of PageRanks and max-linear models of superstar nodes in evolving graphs using extreme value theory. The study finds that the tail indices of block maxima and block sums are close to the minimum tail index of representative series extracted from communities.