Search

This paper introduces a novel and well-founded betweenness measure, called the bag-of-paths (BoP) betweenness, as well as its extension, the BoP group betweenness, to tackle semisupervised classification problems on weighted directed graphs. The objective of semisupervised classification is to assign a label to unlabeled nodes using the whole topology of the graph and the labeled nodes at our disposal. The BoP betweenness relies on a BoP framework, assigning a Boltzmann distribution on the set of all possible paths through the network such that long (high-cost) paths have a low probability of being picked from the bag, while short (low-cost) paths have a high probability of being picked. Within that context, the BoP betweenness of node $j$ is defined as the sum of the a posteriori probabilities that node $j$ lies in between two arbitrary nodes $(i,k)$ when picking a path starting in $i$ and ending in $k$ . Intuitively, a node typically receives a high betweenness if it has a large probability of appearing on paths connecting two arbitrary nodes of the network. This quantity can be computed in closed form by inverting an $n\times n$ matrix where $n$ is the number of nodes. For the group betweenness, the paths are constrained to start and end in nodes within the same class, thereby defining a within-class group betweenness for each class. Unlabeled nodes are then classified according to the class showing the highest group betweenness. Experiments on various real-world datasets show that the BoP group betweenness performs competitively compared to all the tested state-of-the-art methods. The benefit of the BoP betweenness is particularly noticeable when only a few labeled nodes are available. [ABSTRACT FROM AUTHOR]