Search

Traditional approaches from statistics, pattern recognition, machine-learning, or data-mining usually assume an independent and identically-distributed (i.i.d.) sample of objects, which normally leads to a double-entry table containing features from the given sample of the population. However, in some research fields such as spatial statistics, relational learning or link analysis, it is intended to take into account - and analyze - the links between objects which could be of various types and involved in different kinds of relationships. The sample can be therefore seen as a network or a graph where nodes are objects and the links between them are the edges. Within this context, an interesting research topic consists on quantifying the proximity between the network actors from the underlying graph structure. The primary objective of this thesis is precisely the study and the development of dissimilarity measures on a graph. Three different dissimilarities are proposed here, all derived from random walk models on a graph. Roughly, a Markov chain state is associated to every node of the graph and a transition probability is defined for each edge, the measures being derived from this Markov chain. The advantage is that the defined dissimilarity measures take into account not only the length of indirect paths connecting two nodes, but also their number. The studied dissimilarities are assessed in several node clustering, classification, and network representation problems. More specifically, five clustering methods as well as a two-step procedure for the visualization of a subset of the graph nodes are proposed. (FSA 3) -- UCL, 2010

This work presents a new perspective on characterizing the similarity between elements of a database or, more generally, nodes of a weighted and undirected graph. It is based on a Markov-chain model of random walk through the database. More precisely, we compute quantities (the average commute time, the pseudoinverse of the Laplacian matrix of the graph, etc) that provide similarities between any pair of nodes, having the nice property of increasing when the number of paths connect- ing those elements increases and when the “length” of paths decreases. It turns out that the square root of the average commute time is a Eu- clidean distance and that the pseudoinverse of the Laplacian matrix is a kernel (its elements are inner products closely related to commute times). A procedure for computing the subspace projection of the node vectors of the graph that preserves as much variance as possible in terms of the commute-time distance – a principal component analysis (PCA) of the graph – is also introduced. This graph PCA provides a nice interpreta- tion to the “Fiedler vector”, widely used for graph partitioning. The model is evaluated on a collaborative-recommendation task where sug- gestions are made about which movies people should watch based upon what they watched in the past. Experimental results on the MovieLens database show that the Laplacian-based similarities (the pseudoinverse of the Laplacian matrix and the “random-forest matrix”) perform well in comparison with other methods. The model, which nicely fits into the so-called “statistical relational learning” framework, could also be usedto compute document or word similarities, and, more generally, it could be applied to machine-learning and pattern-recognition tasks involving a database.

This work presents a novel procedure for computing (1) distances between nodes of a weighted, undirected, graph, called the Euclidean Commute Time Distance (ECTD), and (2) a subspace projection of the nodes of the graph that preserves as much variance as possible, in terms of the ECTD ­ a principal components analysis of the graph. It is based on a Markov-chain model of random walk through the graph. The model assigns transition probabilities to the links between nodes, so that a random walker can jump from node to node. A quantity, called the average commute time, computes the average time taken by a random walker for reaching node j for the first time when starting from node i, and coming back to node i. The square root of this quantity, the ECTD, is a distance measure between any two nodes, and has the nice property of decreasing when the number of paths connecting two nodes increases and when the "length" of any path decreases. The ECTD can be computed from the pseudoinverse of the Laplacian matrix of the graph, which is a kernel. We finally define the Principal Components Analysis (PCA) of a graph as the subspace projection that preserves as much variance as possible, in terms of the ECTD. This graph PCA has some interesting links with spectral graph theory, in particular spectral clustering.