MATH Seminar
| Title: Multi-commodity distribution using PageRank |
|---|
| Seminar: Combinatorics |
| Speaker: Paul Horn of Harvard University |
| Contact: Dwight Duffus, dwight@mathcs.emory.edu |
| Date: 2012-03-16 at 4:00PM |
| Venue: W306 |
| Download Flyer |
| Abstract: Discontent breaks out on a graph! Unhappiness, in the form of demand for various commodities spreads according to a variation of the contact process beginning with some initial seed. We wish to schedule shipments of goods in order to ensure that demand (and hence unhappiness) is squelched. On the other hand, shipments are expensive so we wish to limit the total amount of shipments we make and only ship to 'important' vertices. In this talk, we investigate a scheme which guarantees that all demand is met, and hence the contact process dies out, quickly (with high probability). When not all vertices are sent shipments, we get bounds on the 'escape probability' in terms of PageRank (and when there are multiple commodities, we get better bounds in terms of a vectorized version of PageRank). |
See All Seminars