Network analysis based on bag-of-paths : classification, node criticality and randomized policies

Network analysis and graph mining are used in many fields such as chemistry, biology, physics, human sciences and (computer) engineering, but also in everyday life from route planners to recommendation systems and social networks tools. In this context, nodes represent concepts of interest and edges represent a given relation between nodes. In this elegant abstraction, finding the shortest path is probably the most well-known problem and is common to all graphs textbooks. This problem consists in the identification of the shortest (in terms of cost or length), most effective path, between two nodes. However, the shortest path forgets about the rest of the network and therefore fails to report some important information present in this network. For example, it does not integrate the degree of connectivity between nodes. In many applications, nodes connected by many indirect paths should be considered as ''closer'' than nodes connected by only a few paths. On the other hand, measures taking connectivity into account (such as the commute-time distance) have their own drawbacks, especially when networks become large. The bag-of-paths framework defines a family of distances interpolating between the shortest path and the commute-time distances. In doing so, the framework takes into account both proximity between nodes in the network and amount of connectivity. It is also possible, via a temperature parameter, to emphasize more on network exploitation or on network exploration. This thesis is based on the bag-of-paths framework and introduces several of its applications: a new classifier based on a bag-of-paths group betweenness for graph-based semi-supervised classification, a new graph criticality measure and an algorithm to determine an optimal, mixed, policy for Markov decision processes. Other applications, closely related to the bag-of-paths framework, are also proposed.