2008 AFamilyofDissimilarityMeasuresB

(Yen et al., 2008) ⇒ Luh Yen, Marco Saerens, Amin Mantrach, and Masashi Shimbo. (2008). “A Family of Dissimilarity Measures Between Nodes Generalizing Both the Shortest-path and the Commute-time Distances.” In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2008). doi:10.1145/1401890.1401984

Subject Headings:

Notes

Cited By

Quotes

Author Keywords

Abstract

This work introduces a new family of link-based dissimilarity measures between nodes of a weighted directed graph. This measure, called the randomized shortest-path (RSP) dissimilarity, depends on a parameter θ and has the interesting property of reducing, on one end, to the standard shortest-path distance when θ is large and, on the other end, to the commute-time (or resistance) distance when θ is small (near zero). Intuitively, it corresponds to the expected cost incurred by a random walker in order to reach a destination node from a starting node while maintaining a constant entropy (related to θ) spread in the graph. The parameter θ is therefore biasing gradually the simple random walk on the graph towards the shortest-path policy. By adopting a statistical physics approach and computing a sum over all the possible paths (discrete path integral), it is shown that the RSP dissimilarity from every node to a particular node of interest can be computed efficiently by solving two linear systems of n equations, where n is the number of nodes. On the other hand, the dissimilarity between every couple of nodes is obtained by inverting an n x n matrix. The proposed measure can be used for various graph mining tasks such as computing betweenness centrality, finding dense communities, etc, as shown in the experimental section.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2008 AFamilyofDissimilarityMeasuresB	Luh Yen Marco Saerens Amin Mantrach Masashi Shimbo			A Family of Dissimilarity Measures Between Nodes Generalizing Both the Shortest-path and the Commute-time Distances			http://www.isys.ucl.ac.be/staff/marco/Publications/2008 FamilyOfDissimilarityMeasures.pdf	10.1145/1401890.1401984