Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals

Graphs have become extremely useful for representing a wide variety of systems in different contexts: biological, social, information... A basic attempt to study them may consist in partitioning the vertices of a graph into clusters that are more densely connected; that is commonly called community detection or graph clustering; see for instance [20, 1]. Community detection and clustering are central problems in machine learning and data science. In particular, the stochastic block model (SBM) [34, 25] has been widely used as a canonical model for community detection and as a building block for clustering with more structural assumptions. In its most general form, the SBM corresponds to a randomly weighted graph model where each node has an unobserved label and the probability of observing a given edge between two nodes depends only on the labels of the nodes under consideration.