2023, Spring

Abstract: Geometric graphs are a popular object of research because they can model many different kinds of networks. However, in the case of geometric graphs clustering --- the task of identifying groups of tightly connected nodes in a graph --- can be rather difficult. For instance, the widely used method of spectral clustering is mostly inefficient for these graphs. It is based on the eigenvector of the adjacency matrix associated with the second eigenvalue. For geometric graphs such a vector provides information about the geometric structure but does not allow to recover the cluster structure.

We present an effective generalization of this method, which we call higher-order spectral clustering. It resembles in concept the classical spectral clustering method but uses for partitioning the eigenvector associated with a higher-order eigenvalue. As it will be shown, this algorithm gives the almost exact recovery of clusters for a wide class of geometric graphs which we call Soft Geometric Block Model. A small adjustment of the algorithm provides the exact recovery. We also show that our method is effective in numerical experiments even for graphs of modest size.

Video

Abstract: We consider a homogeneous Markov process with continuous time on the phase space Z_+ = {0, 1, 2, ...}, which we interpret as the motion of a particle. The process is assumed to be continuous in the sense that the particle cannot «jump» over the Z_+ points, that is, with each change in the position of the particle, its coordinate changes by one. The process is equipped with a branching mechanism. Branch sources can be located at each point Z_+. At the moment of branching, new particles appear at the branch point and then begin to evolve independently of each other (and of other particles) according to the same laws as the initial particle. Such a branching Markov process corresponds to the Jacobi matrix. In terms of orthogonal polynomials corresponding to this matrix, formulas are obtained for the average number of particles at an arbitrary fixed point Z_+ at time t > 0. The results are applied to some specific models, an exact value for the average number of particles is obtained in terms of special functions, and its asymptotic behavior is found at great times.

Video

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 simple graphs 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).

Video

Abstract: The talk will be devoted to the memory and the survey of works of Professor Larissa Afanasyeva. Her main domain of scientific interest was the queueing theory, in particular the ergodicity of various queueing systems. Her works provide necessary and sufficient conditions of ergodicity under very general assumptions on the system under consideration. To achieve the utmost generality, Prof. Afanasyeva introduced the notions of a cyclic queueing system and a regerative flow.  Among the systems for which she studied ergodicity, there were such classes as multichannel systems with non-identical servers, systems with restrictions on the sojourn time, systems with unreliable servers or repeated calls, polling models, networks of server systems, systems with clients requiring multiple servers.  It is worth noting that these results can be seen not only as a contribution of the queueing systems theory, but also as a research of recurrence of some functionals determined by point processes trajectories.

Video

Abstract: Discrete-time discrete-state finite Markov chains are versatile mathematical models for a wide range of real-life stochastic processes. One of most common tasks in studies of Markov chains is computation of the stationary distribution. We propose a new general controlled, easily distributed algorithm for this task. The algorithm includes as special cases a wide range of known, very different, and previously disconnected methods including power iterations, versions of Gauss-Southwell formerly restricted to substochastic matrices, and online distributed algorithms. We prove exponential convergence of our method, demonstrate its high efficiency, and derive straightforward control strategies that achieve convergence rates faster than state-of-the-art algorithms.

Video, Slides

Abstract: We study the probability that an AR(1) Markov chain X_n with the constant parameter 0<a<1 stays positive for a long time. We find the exact asymptotics of this probability and the weak limit of X_n conditioned to stay positive, assuming that the i.i.d. innovations of the chain take only two values +1 and -1, and a<=2/3. The limiting distribution is quasi-stationary and non-atomic; it is singular with respect to the Lebesgue measure when 1/2<a<2/3 and is uniform on the interval [0,3] when a=2/3 and the distribution of the innovations is symmetric. This is similar to the properties of Bernoulli convolutions.

It turns out that for the +1 and -1 innovations there is a close connection between X_n killed at exiting the positive half-line and the classical dynamical system defined by the piecewise linear mapping x -> x/a + 1/2 (mod 1). Exploiting this we construct an appropriate Banach space, where the transition operator of the killed chain has the compactness properties needed to apply a conventional argument of Perron--Frobenius type. The difficulty in finding such space stems from discreteness of the innovations.

Video

Abstract: The talk is based on joint works with Siva Athreya, Leonid Mytnik, and Khoa Le. It is well-known that an SDE

dX_t = b(X_t) dt +dW_t

might have a unique solution even if the corresponding noiseless ODE

dX_t =b(X_t)dt

has no or infinitely many solutions. This is called regularization by noise. While this phenomenon is quite well understood in the case of Brownian forcing, much less is known if the forcing is non-Markovian (for example, fractional Brownian) or infinite-dimensional (for example, space-time white noise). This happens not because regularization by noise is specific to the Brownian case, but rather because there are very few tools available to study this problem in other setups. We will talk about new technique, stochastic sewing, and its latest modifications, which is surprisingly effective in tackling this problem in the non-Brownian setting.

Video, Slides