Search

We explore methods that allow us to change an existing network's structure to achieve a desired PageRank. Being able to change the ranking of the nodes is desirable for any network for which the PageRank determines the importance of the nodes. We search for a perturbation to the original network that when added will give the desired ranking. We derive multiple algorithms to solving this Inverse PageRank problem using both constrained optimization techniques and root finding approaches. In these approaches, we ensure that the answer we find satisfies the conditions for an adjacency matrix of an undirected graph, and we explore techniques that promote sparsity of the final solution. We want sparse solutions so that we only have to change a fraction of the existing edges. We develop a general approach that can be applied to any network. We describe C++ implementations for a set of algorithms, the best of which is scalable to thousands of vertices and much faster than Matlab-based approaches we have tried. This same set of algorithms is subjected to a number of tests designed to study the relationship between the initial guess and the final solution. Our ultimate goal is to solve the inverse PageRank problem on a social network of over 6000 venture capitalists to try and reproduce the top 10 list from a previously published set of rankings. Using a root-finding algorithm where nonnegativity constraints are handled implicitly, we are able to find a highly sparse solution to this inverse problem. 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.

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.