1. InvestorRank and an inverse problem for PageRank
- Author
-
Sims, Bryan
- Subjects
Mathematics. ,Algorithms. ,PageRank. - Abstract
We explore methods that allow us to change an existing network's structure to achieve adesired PageRank. Being able to change the ranking of the nodes is desirable for any network forwhich the PageRank determines the importance of the nodes. We search for a perturbation to theoriginal network that when added will give the desired ranking. We derive multiple algorithmsto solving this Inverse PageRank problem using both constrained optimization techniques androot finding approaches. In these approaches, we ensure that the answer we find satisfies theconditions for an adjacency matrix of an undirected graph, and we explore techniques thatpromote sparsity of the final solution. We want sparse solutions so that we only have to changea fraction of the existing edges. We develop a general approach that can be applied to anynetwork. We describe C++ implementations for a set of algorithms, the best of which is scalableto thousands of vertices and much faster than Matlab-based approaches we have tried. This sameset of algorithms is subjected to a number of tests designed to study the relationship betweenthe initial guess and the final solution. Our ultimate goal is to solve the inverse PageRankproblem on a social network of over 6000 venture capitalists to try and reproduce the top 10 listfrom a previously published set of rankings. Using a root-finding algorithm where nonnegativityconstraints are handled implicitly, we are able to find a highly sparse solution to this inverseproblem. This thesis consists of a draft of a research paper, co-authored by my advisor and me,that we plan to submit to a peer-reviewed journal of applied/computational mathematics.
- Published
- 2012