Nonequilibrium statistical physics involves the study of many-particle systems that break time reversibility|also known as detailed balance|at some scale. For states in thermal equilibrium, which must respect detailed balance, the comprehensive theory of statistical mechanics was developed to explain how their macroscopic properties arise from interactions between their microscopic constituent particles; for nonequilibrium states no such theory exists. The study of active matter, made up of particles that individually transduce free energy to produce systematic movement, provides a paradigm in which to develop an understanding of nonequilibrium behaviours. In this thesis, we are interested in particular in the microscopic interactions that generate the clustering of active particles that has been widely observed in simulations, and may have biological relevance to the formation of bacterial assemblages known as biofilms, which are an important source of human infection. The focus of this thesis is a microscopic lattice-based model of two random walkers interacting under mutual exclusion and undergoing the run-and-tumble dynamics that characterise the motion of certain species of bacteria, notably Escherichia coli. I apply perturbative and exact analytic approaches from statistical physics to three variants of the model in order to find the probability distributions of their nonequilibrium steady states and elucidate the emergent interactions that manifest. I first apply a generating function approach to the model on a one-dimensional periodic lattice where the particles perform straight line runs randomly interspersed by instantaneous velocity reversals or tumbles, and find an exact solution to the stationary probability distribution. The distribution can be interpreted as an effective non-equilibrium pair potential that leads to a finite-range attraction in addition to jamming between the random walkers. The finite-range attraction collapses to a delta function in the limit of continuous space and time, but the combination of this jamming and attraction is suffciently strong that even in this continuum limit the particles spend a finite fraction of time next to each other. Thus, although the particles only interact directly through repulsive hard-core exclusion, the activity of the particles causes the emergence of attractive interactions, which do not arise between passive particles with repulsive interactions and dynamics respecting detailed balance. I then relax the unphysical assumption of instantaneous tumbling and extend the interacting run-and-tumble model to incorporate a finite tumbling duration, where a tumbling particle remains stationary on its site. Here the exact solution for the nonequilibrium stationary state is derived using a generalisation of the previous generating function approach. This steady state is characterised by two lengthscales, one arising from the jamming of approaching particles, familiar from the instant tumbling model, and the other from one particle moving when the other is tumbling. The first of these lengthscales vanishes in a scaling limit where continuum dynamics is recovered. However, the second, entirely new, lengthscale remains finite. These results show that the feature of a finite tumbling duration is relevant to the physics of run-and-tumble interactions. Finally, I explore the effect of walls on the interacting run-and-tumble model by applying a perturbative graph-theoretic approach to the model with reflecting boundaries. Confining the particles in this way leads to a probability distribution in the low tumble limit with a much richer structure than the corresponding limit for the model on a periodic lattice. This limiting probability distribution indicates that an interaction over a finite distance emerges not just between the particles, but also between the particles and the reflecting boundaries. Together, these works provide a potential pathway towards understanding the clustering of self-propelled particles widely observed in active matter from a microscopic perspective.

In this thesis, we propose many developments in the context of Structural Similarity. We address both node (local) similarity and graph (global) similarity. Concerning node similarity, we focus on improving the diffusive process leading to compute this similarity (e.g. Commute Times) by means of modifying or rewiring the structure of the graph (Graph Densification), although some advances in Laplacian-based ranking are also included in this document. Graph Densification is a particular case of what we call graph rewiring, i.e. a novel field (similar to image processing) where input graphs are rewired to be better conditioned for the subsequent pattern recognition tasks (e.g. clustering). In the thesis, we contribute with an scalable an effective method driven by Dirichlet processes. We propose both a completely unsupervised and a semi-supervised approach for Dirichlet densification. We also contribute with new random walkers (Return Random Walks) that are useful structural filters as well as asymmetry detectors in directed brain networks used to make early predictions of Alzheimer's disease (AD). Graph similarity is addressed by means of designing structural information channels as a means of measuring the Mutual Information between graphs. To this end, we first embed the graphs by means of Commute Times. Commute times embeddings have good properties for Delaunay triangulations (the typical representation for Graph Matching in computer vision). This means that these embeddings can act as encoders in the channel as well as decoders (since they are invertible). Consequently, structural noise can be modelled by the deformation introduced in one of the manifolds to fit the other one. This methodology leads to a very high discriminative similarity measure, since the Mutual Information is measured on the manifolds (vectorial domain) through copulas and bypass entropy estimators. This is consistent with the methodology of decoupling the measurement of graph similarity in two steps: a) linearizing the Quadratic Assignment Problem (QAP) by means of the embedding trick, and b) measuring similarity in vector spaces. The QAP problem is also investigated in this thesis. More precisely, we analyze the behaviour of $m$-best Graph Matching methods. These methods usually start by a couple of best solutions and then expand locally the search space by excluding previous clamped variables. The next variable to clamp is usually selected randomly, but we show that this reduces the performance when structural noise arises (outliers). Alternatively, we propose several heuristics for spanning the search space and evaluate all of them, showing that they are usually better than random selection. These heuristics are particularly interesting because they exploit the structure of the affinity matrix. Efficiency is improved as well. Concerning the application domains explored in this thesis we focus on object recognition (graph similarity), clustering (rewiring), compression/decompression of graphs (links with Extremal Graph Theory), 3D shape simplification (sparsification) and early prediction of AD. / Ministerio de Economía, Industria y Competitividad (Referencia TIN2012-32839 BES-2013-064482)