B0446
Title: Community recovery from temporal and higher-order network interactions
Authors: Lasse Leskela - Aalto University (Finland) [presenting]
Konstantin Avrachenkov - Inria Sophia-Antipolis (France)
Maximilien Dreveton - EPFL (France)
Abstract: Community recovery is the task of learning a latent community structure from interactions in a population of N nodes. Efficient algorithms for sparse binary pairwise interaction data are well known, and so are their consistency properties with respect to data sampled from the stochastic block model (SBM), the canonical model for network data with a community structure. Instead of a binary variable indicating whether or not an interaction occurs, a category, value, or shape of an interaction is often also observed. This motivates the definition of a generalised SBM in which interactions can be of arbitrary type, including categorical, numeric, and vector-valued, and not excluding even more general objects such as Markov chains or Poisson processes. For this model, information-theoretic bounds are discussed which characterise the existence of consistent estimators in terms of data sparsity, statistical similarity between intra- and inter-block interaction distributions, and the shape and size of the interaction space. Temporal networks with time-correlated interaction patterns of length T provide an important model instance, for which consistency can be analysed with respect to either N or T, or both, approaching infinity. Time permitting, recent findings and open problems related to data sets are also highlighted, involving higher-order interactions which can be modelled using hypergraph stochastic block models.
