Search results

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 temperatureT) 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 ann×nmatrix withnbeing 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 work develops a generic framework, called the bag-of-paths (BoP), for link and network data analysis. The central idea is to assign a probability distribution on the set of all paths in a network. More precisely, a Gibbs–Boltzmann distribution is defined over a bag of paths in a network, that is, on a representation that considers all paths independently. We show that, under this distribution, the probability of drawing a path connecting two nodes can easily be computed in closed form by simple matrix inversion. This probability captures a notion of relatedness, or more precisely accessibility, between nodes of the graph: two nodes are considered as highly related when they are connected by many, preferably low-cost, paths. As an application, two families of distances between nodes are derived from the BoP probabilities. Interestingly, the second distance family interpolates between the shortest-path distance and the commute-cost distance. In addition, it extends the Bellman–Ford formula for computing the shortest-path distance in order to integrate sub-optimal paths (exploration) by simply replacing the minimum operator by the soft minimum operator. Experimental results on semi-supervised classification tasks show that both of the new distance families are competitive with other state-of-the-art approaches. In addition to the distance measures studied in this paper, the bag-of-paths framework enables straightforward computation of many other relevant network measures.

International audience ; We present the comparison and combination of two different semi automatic classification methods: an original linguistic based analysis, named extended lexical patterns (motifs lexicaux étendus, MLE) and a machine learning approach (SVM). Classification is supervised because of the use of a thesaurus containing the definition of categories. First, both systems are used and evaluated separately on the same real dataset: law and parliament documents in French. Quite unexpectedly, MLE performs as well as a state-of-the-art method such as SVM. During the second step, the combined method gave a performance improvement which underlines the complementarities of both basis methods. ; Dans le contexte de l'indexation semi-automatique de textes, nous présentons la comparaison et la combinaison de deux méthodes de classification mettant en oeuvre des approches différentes : analyse par une méthode originale à forte composante linguistique que nous nommons motifs lexicaux étendus (MLE) d'une part et apprentissage artificiel SVM d'autre part. La classification est de type supervisée car elle exploite un ensemble de catégories définies par un thésaurus documentaire. Dans un premier temps, les deux systèmes sont appliqués et évalués séparément sur un même jeu de données réelles, des textes de type législatif et parlementaire en français. De manière quelque peu inattendue, la méthode MLE permet d'atteindre des performances tout à fait compétitives par rapport à la technique state-of-the-art que constitue SVM. Les méthodes sont ensuite combinées dans le but d'obtenir une performance finale supérieure aux performances individuelles. Le gain obtenu indique une complémentarité entre les deux méthodes.