Finally I managed to compute the b-skeleton of the messages left of the campus of EPFL. The idea is to use this visualization to find the messages that are more close to the others. Additionally this graph can be sparsified, meaning that some long / irrelevant connections can be removed, clustering the zones in sub-graphs. This technique is also useful to find outliers.
Beta skeletons: A continuous family of proximity graphs proposed by Kirkpatrick and Radke [*]. These graphs are defined by a positive real parameter Beta. Lower values of Beta give denser graphs (with more edges). There are two types of Beta-skeletons: lune-based (the neighborhood is an intersection of discs), and circle-based (the neighborhood is a union of discs). For Beta=1 the skeleton is in fact the Gabriel graph, and for Beta=2 the (lune-based) skeleton is the Relative Neighborhood graph.
[*] DB Kirkpatrick and JD Radke.
A framework for computational morphology.
In GT Touissant, editor, Computational Geometry, pages 217-248. Elsevier, 1985.
Tags: