Degree Sequences of PageRank Uniform Graphs and Digraphs with Prime Outdegrees

摘要

A PageRank uniform digraph is a digraph whose vertices have all the same PageRank score. These digraphs are interesting in the scope of privacy preserving release of digraph data in environments where a dishonest analyst may have previous structural knowledge about the PageRank score of some vertices. In this paper we first characterize PageRank uniform graphs (viewed as symmetric digraphs) and their degree sequence. Next, given a sequence of prime integers S, we give necessary and sufficient conditions for S to be the outdegree sequence of a PageRank uniform digraph.