Samuel Koovely

Many complex systems can be modeled by temporal networks, whose organization often evolves through distinct structural phases. Detecting the change points that delimit these phases is both important and challenging. In this work, we extend the conditional entropy of heat diffusion from static graphs to temporal networks and study its properties. We provide an upper bound and explain how discrepancies from it arise from the presence of asymmetric temporal paths. Moreover, we show that this quantity is monotone in time, yielding an information-theoretic analog of the second law of thermodynamics for inhomogeneous diffusion on temporal networks. We then introduce a local version of conditional entropy, designed to probe diffusion over finite temporal windows, and show that it provides an informative signal for change-point detection in continuous-time temporal networks. We evaluate the proposed methodology on synthetic benchmarks, including comparative experiments with existing nonparametric baselines in the snapshot setting, and then apply it to a real-world temporal contact network from a French primary school. Finally, we show how to use detected change points to perform community detection on targeted sub-intervals, improving the quality and interpretability of the clustering results.

We introduce a new sampling method for continuous-time temporal networks based on queueing processes. In particular, we focus on a Markovian version of the model where the links between nodes are Poisson distributed in time and have exponential duration. We highlight the stochastic properties of these temporal structures and leverage them to design synthetic temporal networks with a controllable level of smoothness, which follow patterns relevant for the validation and interpretation of methods for community, scale, change-point, and periodicity detection. Additionally, we show that imposing assortativity constraints on the samples leads to a continuous-time generalization of stochastic block models. Finally, we describe how variations of the model can be used to sample alternative types of structure and temporal networks, especially discrete-time ones.

The modeling of diffusion processes on graphs is the basis for many network science and machine learning approaches. Entropic measures of network-based diffusion have recently been employed to investigate the reversibility of these processes and the diversity of the modeled systems. While results about their steady state are well-known, very few exact results about their time evolution exist. Here, we introduce the conditional entropy of heat diffusion in graphs. We demonstrate that this entropic measure satisfies the first and second laws of thermodynamics, thereby providing a physical interpretation of diffusion dynamics on networks. We outline a mathematical framework that contextualizes diffusion and conditional entropy within the theories of continuous-time Markov chains and information theory. Furthermore, we obtain explicit results for its evolution on complete, path, and circulant graphs, as well as a mean-field approximation for Erdős-Rényi graphs. We also obtain asymptotic results for general networks. Finally, we experimentally demonstrate several properties of conditional entropy for diffusion over random graphs, such as the Watts-Strogatz model.

Complex systems are ubiquitous in nature, and complex networks provide a flexible framework to model many of them. Many real-world networks evolve in time, and so do their structural properties. This thesis develops a mathematical framework for the study of static and temporal graphs based on the conditional entropy of heat diffusion, establishes its main theoretical properties, and demonstrates its usefulness for the analysis and structural interpretation of time-evolving networks. The main idea is to combine Markov chain theory and information theory in order to define an entropy-like quantity for diffusion processes on graphs, thereby providing a thermodynamic perspective on network dynamics. The first part of the thesis introduces the conditional entropy of heat diffusion on static graphs and shows that it satisfies an information-theoretic analogue of the second law of thermodynamics. Explicit formulas are derived for several graph families, including complete graphs, path graphs, and circulant graphs, together with a mean-field approximation for Erdős–Rényi graphs, asymptotic results, and bounds for general networks. The second part extends the framework to temporal graphs, where diffusion is governed by an inhomogeneous Markov process. In this setting, the thesis proves a temporal monotonicity result, derives an upper bound for conditional entropy, and relates deviations from this bound to asymmetric temporal paths. A local version of conditional entropy is then introduced to study diffusion over finite temporal windows. This local quantity is used as a signal for change point detection in continuous-time temporal networks, evaluated on synthetic benchmarks, compared with nonparametric baselines, and applied to a real-world temporal contact network. The detected change points are also used to guide community detection on selected time intervals, improving the interpretability of the resulting clusters. Finally, the thesis also introduces a queueing-based sampling framework for continuous-time temporal networks. In its Markovian version, link arrivals follow a homogeneous Poisson process and link durations are exponentially distributed. Coupled with block-structured endpoint distributions, the model yields a continuous-time analogue of stochastic block models and enables the generation of temporal networks with controllable smoothness and following prescribed event patterns.

T-cells are a core component of the adaptive immune system: they play a major role in mounting an effective and tailored response to foreign pathogens, and they are also relevant in the context of cancer and cer- tain autoimmune diseases. T-cells receptors are protein complexes present on T-cells’ surface that are responsible for identifying foreign and own antigens. Given the complexity of protein-protein interactions, this identification process exhibits a quasi-stochastic behaviour that can be modeled with probabilistic and statistical models. Graphical models can represent a multivariate distribution in a convenient and transparent way as a graph. In this paper we introduce COMIC-Tree, an undirected graphical model for protein-protein interactions, and DrawCOMIC-Tree, a greedy algorithm based on conditional mutual information for learning COMIC-Tree structures. We provide a solid mathematical foundation for them, highlight some theoretical aspects, and test them empirically on a dataset of T-cell receptors.

The output of the original PC-algorithm depends on the order of the evaluated variables, and the separating sets used during its pruning process might be inconsistent with the final result. We give an overview of some variations of this method that address these shortcomings and perform a simulationstudy of these algorithms.