3
$\begingroup$

I have a set of nodes in a very large graph which I call Cluster Points. I also have for each point in the graph, the distance from each point in the Cluster point set.

For example: node_id: 2493 is 5 hops (distance) away from the first cluster point, 2 hops from the second and 8 hops from the third.

What I would like to do is to find points which far away from the whole set. Such a point would further be added to the Cluster Point set. In essence, I am trying to distribute these cluster points evenly throughout the graph.

However, given these distances I have no idea on how to find a point far away from the current set of cluster points. Any thoughts or ideas are appreciated.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The problem of choosing a sequence of nodes in a graph in which each is approximately as far as possible from the previously chosen ones was considered in my preprint with Har-Peled and Sidiropoulos, arXiv:1507.01555. We provided a randomized $(1+\epsilon)$-approximation (that is, each point is within that factor of farthest) running in expected time $O(\epsilon^{-1}(m+n)\log n\log(n/\epsilon))$, within logarithmic factors of linear.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .