Plenary Speakers
Jeannette Janssen
Mathematics, Dalhousie University, Canada
- Title: Recognizing graphs formed by a spatial random process
- Abstract: A common paradigm of models for social networks and other information graphs is to see the nodes as embedded in a feature space, where nodes that are closer together are deemed to have more features in common, and thus are more likely to be linked. However, what is observable in most cases is only the link structure of the network, and not the underlying spatial reality. This leads to the question: given a large graph or sequence of graphs, how can we determine if they are likely the result of a spatial random process? For dense graphs, the theory of graph limits can help answer this question. I will present recent work which demonstrates this approach in the one-dimensional (linear) case.
- Bio: Jeannette Janssen is a professor and department Chair at Dalhousie Univerisity. She has made contributions to various areas of graph theory, especially related to graph colourings and frequency assignment, modelling and mining of complex networks, and infinite graphs. Her recent work involves an exploration of graph models for complex networks that have a natural spatial embedding. Dr. Janssen has been invited to present her work nationally and internationally, including as a guest lecturer at a summer school on Network Science at USC, as a participant of a thematic program on Discrete Structures at the IMA in Minnesota, at a workshop at CRM in Montreal, and, most recently, at a workshop at the Newton Institute in Cambridge. Dr. Janssen was director of the Atlantic Association for Research in the Mathematical Sciences (AARMS) from 2011 to 2016, and she is currently a program officer of the SIAM activity group on Discrete Mathematics.
- Web page: http://www.mscs.dal.ca/~janssen/
Jure Leskovec
Computer Science, Stanford University, USA
- Title: Higher-order analysis of networks
- Abstract: Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuro, and social sciences. Present network algorithms are almost exclusively focusing on first-order, or edge-based, structures in networks. However, what is missing from the picture are methods for analyzing higher-order organization of complex networks. We present a generalized framework for a network clustering and classification based on higher-order network connectivity patterns. This framework allows for identifying rich higher-order clusters in networks. Our framework scales to networks with billions of edges and provides mathematical guarantees on the optimality of obtained clusters. We apply our framework to networks from a variety of scientific domains with scales ranging from a few hundred to over one billion links.
- Bio: Jure Leskovec is associate professor of Computer Science at Stanford University and chief scientist at Pinterest. Computation over massive networks is at the heart of his research and has applications in computer science, social sciences, economics, marketing, and healthcare. This research has won several awards including a Lagrange Prize, Microsoft Research Faculty Fellowship, the Alfred P. Sloan Fellowship, and numerous best paper awards. Leskovec received his bachelor's degree in computer science from University of Ljubljana, Slovenia, and his PhD in in machine learning from the Carnegie Mellon University and postdoctoral training at Cornell University.
- Web page: http://cs.stanford.edu/~jure
Yuval Peres
Microsoft Research in Redmond, USA
- Title: Evolving sets, local sparse cuts, and random walks in dynamically varying graphs: A pictorial introduction
- Abstract: "Evolving sets" in a graph are a sequence of random sets that can be thought of as a discerning variant of breadth-first search. They were used by Ben Morris and the speaker (STOC 2003) to bound mixing time of random walks in graphs in terms of their expansion profile; this sharpened earlier bounds due to Kannan and Lovasz. In later joint work with Reid Andersen (STOC 2009), we used evolving sets to find sparse cuts (that approximate the optimal cut of that size) in a neighborhood of a given node in a network. These works considered static graphs; but in many applications, graphs change over time. Most standard techniques to analyze random walks (e.g., using eigenvalues) are not applicable in this setting. Concretely, suppose that edges in a finite graph are open with probability p, but refresh at given rate (This process is known as dynamical percolation.) How do the changes in the graph over time affect the mixing of random walk on it? In joint work with Stauffer and Steif, we determined mixing time for random walk on dynamical percolation in a discrete torus via coupling for low (subcritical) edge density p. However, this coupling method could not be extended to high (supercritical) p, when large connected clusters form. Recently, in joint work with Sousi and Steif, we found that (for all values of p), evolving sets are an effective tool to analyze mixing of random walks in networks that vary in time. In the talk I will describe these applications and show simulations of the resulting processes; no prior knowledge of evolving sets will be assumed.
- Bio: Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. He obtained his Ph.D. at the Hebrew University, Jerusalem in 1990, and later taught there and at the University of California, Berkeley. He has published more than 280 research papers and advised 21 Ph.D. students. He has co-authored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995, the Loeve Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Mathematicians and in the 2008 European Congress. In 2016 he was elected as a foreign associate to the U.S. National Academy of Sciences.
- Web page: http://yuvalperes.com