Essays on network data analysis through the bag-of-paths framework

Courtain, Sylvain [UCL]

Since the rapid growth of the Internet and the advent of social networks in the 2000s, the amount of available network data is quickly increasing, leading to the development of new network analysis methods. Nowadays, these network analysis methods have spread to various fields, including, among others, marketing, supply chain, finance, and biology, as essential analysis and prediction tools. This thesis focuses on the development of one of these methods, called the bag-of-paths framework. This framework has the specificity to define a family of dissimilarity measures between nodes of the network that extrapolate between an optimal exploitation of the graph structure (optimal behavior - shortest path distance) and a random exploration of the graph (random behavior - commute time distance) via a parameter that controls the desired degree of randomness/exploration. Throughout this thesis, we propose several theoretical and practical extensions of the bag-of-paths framework. Regarding the theoretical contributions, we incorporate capacity constraints on edges, marginal constraints on input and output flows, and a Poisson distribution weighting and constraining path lengths, into the bag-of-paths framework. Furthermore, we expose the applicability of this framework through graph-based semi-supervised classification tasks and a real-life fraud detection case.