Abstract: A classical setting of graph clustering consists of partitioning the vertices of a graph into tight-knit clusters. Nowadays, the underlying challenge is frequently called the "community detection problem" due to its numerous applications in diverse domains such as sociology, neuroscience, bibliography and recommender systems, just to name a few. A benchmark model for graph clustering problem is a Stochastic Block Model (SBM), which is an inhomogeneous version of the Erdos-Renyi random graph. In this talk I discuss several generalizations of SBM that go beyond binary interactions modelled by simple graphs. Specifically, I consider a network, where the observed interactions belong to a general measurable interaction space. This can represent categorical and vector-valued interactions, including time series or spatial point patterns. I present sharp information-theoretic criteria for the strong cluster recovery in terms of data sparsity, the statistical similarity between intra- and inter-block interaction distributions, and the shape and size of the interaction space. This general framework makes it possible to study temporal networks when both the number of nodes and the time horizon go to infinity, and when the temporal interaction patterns are correlated over time. An efficient spectral algorithm to recover clusters will be presented and demonstrated on real-life and synthetic network examples. In some applications, the framework of hypergraphs is more appropriate than the framework of simplegraphs or even graphs with weighted edges. The recovery conditions for the hypergraph clustering are also available and will be discussed if time permits.
This talk is based on a series of joint works with M. Dreveton (EPFL), K. Alaluusua and L. Leskela (Aalto University), and V. Kumar (Inria).
Short Bio: Konstantin Avrachenkov received his Master degree in Control Theory from St. Petersburg State Polytechnic University (1996), Ph.D. degree in Mathematics from University of South Australia (2000) and Habilitation from University of Nice Sophia Antipolis (2010). Currently, he is a Director of Research at Inria Sophia Antipolis, France. He is an associate editor of Probability in the Engineering and Informational Sciences, ACM TOMPECS, Stochastic Models and IEEE Network Magazine. Konstantin has co-authored two books “Analytic Perturbation Theory and its Applications”, SIAM, 2013 and “Statistical Analysis of Networks”, Now Publishers, 2022. He has won 5 best paper awards. His main theoretical research interests are Markov chains, Markov decision processes, random graphs and singular perturbations. He applies these methodological tools to the modeling and control of networks, and to design data mining and machine learning algorithms.
