The first part of this thesis explores issues surrounding the manipulation of PageRank, a popular link-analysis based reputation system for the web. PageRank is an essential part of web search, but it is also subject to manipulation by selfish web authors. We develop an alternative to PageRank, based on expected hitting time in a random walk, that is provably robust to manipulation by outlinks. We then study the effects of manipulation on the network itself by analyzing the stable outcomes of the PageRank Game, a network-formation model where web pages place outlinks strategically to maximize PageRank. The second part of the thesis explores probabilistic inference algorithms for a family of models called collective hidden Markov models. These generalize hidden Markov models (HMMs) to the situation in which one views partial information about many indistinguishable objects that all behave according to the same Markovian dynamics. Collective HMMs are motivated by an important problem in ecology: inferring bird migration paths from a large database of observations.