Search

AbstractThe recently developed bag-of-paths (BoP) framework consists in setting a Gibbs–Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature T) controlling the entropic level of the distribution. This formalism enables the computation of new distances or dissimilarities, interpolating between the shortest-path and the resistance distance, which have been shown to perform well in clustering and classification tasks. In this work, the bag-of-paths formalism is extended by adding two independent equality constraints fixing starting and ending nodes distributions of paths (margins).When the temperature is low, this formalism is shown to be equivalent to a relaxation of the optimal transport problem on a network where paths carry a flow between two discrete distributions on nodes. The randomization is achieved by considering free energy minimization instead of traditional cost minimization. Algorithms computing the optimal free energy solution are developed for two types of paths: hitting (or absorbing) paths and non-hitting, regular, paths and require the inversion of an n× nmatrix with nbeing the number of nodes. Interestingly, for regular paths on an undirected graph, the resulting optimal policy interpolates between the deterministic optimal transport policy (T→ 0+) and the solution to the corresponding electrical circuit (T→ ∞). Two distance measures between nodes and a dissimilarity between groups of nodes, both integrating weights on nodes, are derived from this framework.

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]

Abstract: This work introduces a probabilistic model allowing to compute reputation scores as close as possible to their intrinsic value, according to the model. It is based on the following, natural, consumer–provider interaction model. Consumers are assumed to order items from providers, who each has some intrinsic, latent, “quality of service” score. In the basic model, the providers supply the items with a quality following a normal law, centered on their intrinsic “quality of service”. The consumers, after the reception and the inspection of the item, rate it according to a linear function of its quality – a standard regression model. This regression model accounts for the bias of the consumer in providing ratings as well as his reactivity towards changes in item quality. Moreover, the constancy of the provider in supplying an equal quality level when delivering the items is estimated by the standard deviation of his normal law of item quality generation. Symmetrically, the consistency of the consumer in providing similar ratings for a given quality is quantified by the standard deviation of his normal law of ratings generation. Two extensions of this basic model are considered as well: a model accounting for truncation of the ratings and a Bayesian model assuming a prior distribution on the parameters. Expectation-maximization algorithms, allowing to estimate the parameters based on the ratings, are developed for all the models. The experiments suggest that these models are able to extract useful information from the ratings, are robust towards adverse behaviors such as cheating, and are competitive in comparison with standard methods. Even if the suggested models do not show considerable improvements over other competing models (such as Brockhoff and Skovgaard’s model ), they, however, also permit to estimate interesting features over the raters – such as their reactivity, bias, consistency, reliability, or expectation. [Copyright &y& Elsevier]

This work extends the randomized shortest paths (RSP) model by investigating the net flow RSP and adding capacity constraints on edge flows. The standard RSP is a model of movement, or spread, through a network interpolating between a random-walk and a shortest-path behavior (Kivimäki et al., 2014; Saerens et al., 2009; Yen et al., 2008). The framework assumes a unit flow injected into a source node and collected from a target node with flows minimizing the expected transportation cost, together with a relative entropy regularization term. In this context, the present work first develops the net flow RSP model considering that edge flows in opposite directions neutralize each other (as in electric networks), and proposes an algorithm for computing the expected routing costs between all pairs of nodes. This quantity is called the net flow RSP dissimilarity measure between nodes. Experimental comparisons on node clustering tasks indicate that the net flow RSP dissimilarity is competitive with other state-of-the-art dissimilarities. In the second part of the paper, it is shown how to introduce capacity constraints on edge flows, and a procedure is developed to solve this constrained problem by exploiting Lagrangian duality. These two extensions should improve significantly the scope of applications of the RSP framework. [ABSTRACT FROM AUTHOR]