Loading Events

Events for May 8, 2019

Events Search and Views Navigation

Event Views Navigation

2:00 pm

CESG Fishbowl Seminar: “A Structural Result for Personalized PageRank and Its Algorithmic Consequences”

May 8 @ 2:00 pm - 3:00 pm
Free

Fishbowl, Room 333, Wisenbaker Engineering Building Dr. Vijay Subramanian Associate Professor in EECS Department at the University of Michigan Abstract: Many systems, including the Internet, social networks, and the power grid, can be represented as graphs. When analyzing graphs, it is often useful to compute scores describing the relative importance or distance between nodes. One example is Personalized PageRank (PPR), which assigns to each node v a vector whose i-th entry describes the importance of the i-th node from the perspective of v. PPR has proven useful in many applications, such as recommending who users should follow on social networks (if this i-th entry is large, v may be interested in following the i-th user). Unfortunately, computing all N such PPR vectors (where n is the number of nodes) is infeasible for many graphs of interest. In this work, we argue that the situation is not so dire. Our main result shows that the dimensionality of the set of PPR vectors scales sublinearly in n with high probability, for a certain class of random graphs and for a notion of dimensionality similar to rank. Put differently, we argue that the effective dimension of this set is much less than n despite the fact that the matrix containing these vectors has rank n. Furthermore, we show this dimensionality measure relates closely to the complexity of a PPR estimation scheme that was proposed (but not analyzed) by Jeh and Widom. This allows us to argue that accurately estimating all n PPR vectors amounts to computing a vanishing fraction of the n^2 vector elements (when the technical assumptions of our main result are satisfied). Finally, we demonstrate empirically that similar conclusions hold when considering real-world networks, despite the assumptions of our theory not holding. This is joint work with Daniel Vial, University of Michigan.   Biography: Vijay Subramanian is an Associate Professor in the EECS Department at the University of Michigan since 2014. After graduating with his Ph.D. from UIUC in 1999, he did a few stints in industry, research institutes and universities in the US and Europe before his current position. His main research interests are in stochastic modeling, communications, information theory and applied mathematics. A large portion of his past work has been on probabilistic analysis of communication networks, especially analysis of scheduling and routing algorithms. In the past, he has also done some work with applications in immunology and coding of stochastic processes. His current research interests are on game theoretic and economic modeling of socio-technological systems and networks, and the analysis of associated stochastic processes.                   Light Snacks Provided

Find out more »

3:00 pm

CESG Fishbowl Seminar: “One If by Land and Two If by Sea: A Glimpse into the Value of Information in Strategic Interactions”

May 8 @ 3:00 pm - 4:00 pm
Free

Fishbowl, Room 333, Wisenbaker Engineering Building   Dr. Vijay Subramanian Associate Professor in EECS Department at the University of Michigan   Abstract: This work studies sequential social learning (also known as Bayesian observational learning) and how private communication can enable agents to avoid herding to the wrong action/state. Starting from the seminal BHW (Bikhchandani, Hirshleifer, and Welch, 1992) model where asymptotic learning does not occur, we allow agents to ask private and finite questions to a bounded subset of their predecessors. While retaining the publicly observed history of the agents and their Bayes rationality from the BHW model, we further assume that both the ability to ask questions and the questions themselves are common knowledge. Then interpreting asking questions as partitioning information sets, we study whether asymptotic learning can be achieved with finite capacity questions. Restricting our attention to the network where every agent is only allowed to query her immediate predecessor, an explicit construction shows that a 1-bit question from each agent is enough to enable asymptotic learning. This is joint work with Shih-Tang Su and Grant Schoenebeck at the University of Michigan.   Biography: Vijay Subramanian is an Associate Professor in the EECS Department at the University of Michigan since 2014. After graduating with his Ph.D. from UIUC in 1999, he did a few stints in industry, research institutes and universities in the US and Europe before his current position. His main research interests are in stochastic modeling, communications, information theory and applied mathematics. A large portion of his past work has been on probabilistic analysis of communication networks, especially analysis of scheduling and routing algorithms. In the past, he has also done some work with applications in immunology and coding of stochastic processes. His current research interests are on game theoretic and economic modeling of socio-technological systems and networks, and the analysis of associated stochastic processes.                   Light Snacks Provided

Find out more »
+ Export Events