Theoretical Tools for Network Analysis: Game Theory, Graph Centrality, and Statistical Inference

A computer-driven data explosion has made the difficulty of interpreting large datasets even more salient. My work focuses on theoretical tools for summarizing, analyzing, and understanding network datasets, or datasets of things and their pairwise connections. I present four results which improve our ability to use networks from a variety of domains.

I first show that the sophistication of game theoretic agent decision making is crucial in network cascades, in that differing decision making assumptions can lead to dramatically different cascade outcomes. This highlights the importance of diligence when making assumptions about agent behavior on networks and in general. I next analytically demonstrate a significant irregularity in the popular eigenvector centrality, and propose a new spectral centrality measure, nonbacktracking centrality, showing that it avoids the irregularity. This tool contributes a more robust way of ranking nodes, as well as an additional mathematical understanding of the effects of network localization. I next give a new model for uncertain networks, networks in which one has no access to true network data but instead observes only probabilities of edge existence. I give a fast maximum likelihood algorithm for recovering edges and communities in this model, and show that it outperforms a typical approach of thresholding to an unweighted network. This model gives a better tool for understanding and analyzing real-world uncertain networks such as those arising in the experimental sciences. Lastly, I give a new lens for understanding scientific literature, specifically as a hybrid coauthorship and citation network. I use this for exploratory analysis of the Physical Review journal over a hundred-year period, and I make new observations about the interplay between these two networks and how this relationship has changed over time.