You are here: Home NEWS & EVENTS Events Calendar
Events Calendar
  • [February 27, 2018]

    Finite Markov Chains: A Universal Language for Learning, Ranking, and Decomposition of Networks

  • Speaker:
    Bernd Heidergott
    Date:
    Tuesday, February 27, 2018
    Time:
    10:30am
    Location:
    Room 512, Founder Building
    Host:
    Yijie Peng
  • Abstract
  • The research presented in this talk is motivated by the growing interest in the analysis of networks found in the world-wide-web and of social networks. A common feature of these networks is that the finite-state Markov chain modeling the influence relation between nodes typically has several (nearly) ergodic classes. This talk addresses nearly decomposable chains, and we introduce a new decomposition algorithm for Markov chains that allows splitting the graph of the Markov chain into subgraphs such that the connectivity of the chain, measured by the Kemeny constant, is maximally decreased. In other words, we discuss how the structure dormant in a nearly decomposable chain can be brought to light. We present applications to influence ranking in social networks, decomposition of social networks into subnetworks, and cluster analysis.
    We discuss in particular Google’s Page rank, and the DeGroot model for social learning.

  • Biography
  • Bernd Heidergott is the professor of Stochastic Optimization at the Department of Econometrics and Operations Research at the Vrije Universiteit Amsterdam, the Netherlands. He received his Ph.D. degree from the University of Hamburg, Germany, in 1996, and held postdoc positions at various universities before joining the Vrije Universiteit. He is the program director of the BSc and MSc Econometrics and Operations Research, and research fellow of the Tinbergen Institute and Amsterdam Business Research Institute.  His research interests are optimization and control of discrete event systems, perturbation analysis, Markov chains, max-plus algebra, and social networks.