Estimation of the Tail Index of PageRanks in Random Graphs

Superstar nodes to which a large proportion of nodes attach in the evolving graphs are considered. We attract results of the extreme value theory regarding sums and maxima of non-stationary random length sequences to predict the tail index of the PageRanks and Max-linear models as influence measures of superstar nodes. To this end, the graphs are divided into mutually weakly dependent communities. Maxima and sums of the PageRanks over communities are used as weakly independent block-data. Tail indices of the block-maxima and block-sums and hence, of the PageRanks and the Max-linear models are found to be close to the minimum tail index of series of representative nodes taken from the communities. The graph evolution is provided by a linear preferential attachment. The tail indices are estimated by data of simulated and real temporal graphs.