Back

The extended Jaccard distance in complex networks

Eglantine Camby and Gilles Caporossi

BibTeX reference

Distance measures play an important role in data analysis, mainly for clustering purpose, but also for data representation (for instance using multidimensional scaling) or for prediction (e.g., $$k$$-nearest neighbors). If the concept is also well defined in networks, it turns out that the distance measures are either difficult to compute or are not precise enough for most analysis purpose. Furthermore, the concept of distance and its measure should be adapted depending on the application area since it does not have the same meaning in a social network, a telecommunication network or a molecule. In this paper, we propose a new distance measure that is based upon the well known Jaccard distance, but does not have the limitation that all pairs of nodes at geodesic distance strictly greater than 2 automatically have 1 as the Jaccard distance. The new distance measure is defined and analyzed according to its possible applications and in terms of computational complexity.

, 10 pages

Document

G1777.pdf (300 KB)