Obtain the PageRank distribution of a static graph (in MTX format).
In this experiment, we measure the PageRank distribution of a number of
static graph datasets. As with degrees, logging all the rank value of a
graph is not feasible. Therefore, we compress the rank distribution into
blocks (or bins) such that there are a total of 256 blocks, starting
from 0 to the MAX_RANK of a vertex in the graph (this is a value smaller
than 1). The PageRank distribution is then measured by counting the number of
nodes in each block.
The results show that web graphs have a significantly skewed dual power-law PageRank distribution, i.e., as with the degree distribution, the PageRank distribution follows a power-law distribution in the low-rank region and another power-law distribution in the moderate-rank region. The transition point between the two power-law regions can be called the knee of the PageRank distribution. Very few vertices in the web graphs have a high PageRank value, and they appear to be randomly sprinkled. The PageRank distribution in social networks is less skewed, and the knee is less pronounced.
The PageRank distribution is however completely different in road networks and protein k-mer graphs. Here, we appear to be forming mountain ranges, with sharp peaks, steep slopes on the left side, and a long tail on the right side. This likely due to such real-world graphs being undirected (along with social networks), as well as being unformly connected overall (in contrast to digital-world web graphs). Does this mean that digital networks exaggerate the rich vs poor divide?
All outputs are saved in a gist and a small part of the output is listed here. Some charts are also included below, generated from sheets.
