A bag-of-paths framework for network data analysis

General introduction Network and link analysis is a highly studied field, subject of much recent work in various areas of science: applied mathematics, computer science, social science, physics, chemistry, pattern recognition, applied statistics, data mining & machine learning, to name a few [4, 20, 30, 56, 61, 73, 96, 101]. Within this context, one key issue is the proper quantification of the structural relatedness between nodes of a network by taking both direct and indirect connections into account. This problem is faced in all disciplines involving networks in various types of problems such as link prediction, community detection, node classification, and network visualization to name a few popular ones. Preprint submitted to Elsevier January 2, 2018 The main contribution of this paper is in presenting in detail the bag-ofpaths (BoP) framework and defining relatedness as well as distance measures between nodes from this framework. The BoP builds on and extends previous work dedicated to the exploratory analysis of network data [54, 53, 67, 104]. The introduced distances are constructed to capture the global structure of the graph by using paths on the graph as a building block. In addition to relatedness/distance measures, various other quantities of interest can be derived within the probabilistic BoP framework in a principled way, such as betweenness measures quantifying to which extent a node is in between two sets of nodes [60], extensions of the modularity criterion for, e.g., community detection [26], measures capturing the criticality of the nodes or robustness of the network, graph cuts based on BoP probabilities, and so on.