PageRank Under Interpolation Between Undirected- and Directed Networks - A Case Study
摘要
Among centrality measures, PageRank is particularly famous due to its implementation in the Google search engine. We have recently shown that in general undirected networks, the graph-normalized PageRank of any node in the network is bounded from above by its degree. This general statement, however, is not true in directed networks, where, e.g., the directed version of the preferential attachment model exhibits heavier tails for the limiting PageRank distribution than for the limiting in-degree-distribution. In this note, we illustrate the general upper bound on PageRank in undirected networks by scatter plots of datasets from three scale-free real-world networks of different sizes. We observe and explain a concentration phenomenon within the scatter plots. Furthermore, to shed light on how the directed-ness of edges changes the relation between degrees and PageRank, we interpolate between undirected and directed graphs as follows: for each of the three networks, we construct a new - directed - network by randomly choosing a subset of the edges of prescribed size and for each of its elements deleting exactly one of the two possible directions. As a result of this procedure, some small-degree vertices will obtain a PageRank that is above their in-degree. We illustrate and explain this phenomenon for the chosen datasets by comparing to what happens in the configuration model.