[Lowerbounds, Upperbounds]

Title: PageRank and the Random Surfer Model
Speaker: Páll Melsted
When: September 20, 16:30-17:30pm
Where: Wean Hall 5302

Abstract:
In recent years there has been considerable interest in analyzing random graph models for the Web. We consider two such models - the Random Surfer model introduced by Blum et al. and the PageRank-based selection model proposed by Pandurangan et al. It has been observed that search engines influence the growth of the Web. The PageRank-based selection model tries to capture the effect that these search engines have on the growth of the Web by adding new links according to Pagerank. The PageRank algorithm is used in the Google search engine for ranking search results.

We show the equivalence of the two random graph models and carry out the analysis in the Random Surfer model, since it is easier to work with. We analyze the expected in-degree of vertices and show that it follows a powerlaw. We also analyze the expected PageRank of vertices and show that it also follows the same powerlaw as the expected degree.

We show that in both models the expected degree and the PageRank of the first vertex, the root of the graph, follow the same powerlaw. However the power undergoes a phase-transition as we vary the parameter of the model. This peculiar behavior of the root has not been observed in previous analysis and simulations of the two models.

This is joint work with Prasad Chebolu.

Who: Dan Golovin
Where: NSH 1507
When: 9/19/2007, Noon

Title: Stochastic Packing-Market Planning

Abstract:

In traditional mechanism design problems, the mechanism receives its inputs from various strategic players, and must select an outcome and payment scheme with the goal of providing the proper incentives to the selfish players to achieve an optimal outcome, for various objective functions. A well-studied special case of this problem is to design mechanisms for combinatorial auctions to maximize social welfare. We consider a variant of this problem in which there is probabilistic demand and participants associate some cost with participating (e.g., by waiting until their demand is sampled and then attending the auction, they incur some opportunity cost). We call this the Stochastic Packing-Market Planning problem (SPMP), which is a stochastic generalization of the Maximum k-Set Packing problem. We provide an approximation algorithm andmechanism for SPMP, and also give a linear programming based approximation for the expected weight of a maximum set packing in a random subhypergraph of a fixed hypergraph G, using techniques which may be of independent interest.