I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does this already have a name?). I know of an $O(N^2)$ solution: Starting at every vertex: BFS to calculate the mean distance to all other vertices, choose the minimum. But $N^2$ is too slow for a graph this size, is there any way to calculate the "mean center" in faster than $N^2$ time? Are there any good approximation algorithms? Or more efficient algorithms which find some similar "center" of a graph?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ en.m.wikipedia.org/wiki/Graph_center $\endgroup$– JuhoJan 22, 2020 at 20:17
-
1$\begingroup$ @Juho I've seen that page, but the algorithm listed there (Floyd–Warshall algorithm) appears to be $O(N^3)$ which is even worse. I'm guessing this is because they are considering graphs with arbitrary edge weights? $\endgroup$– sligockiJan 22, 2020 at 22:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it.
Pick a vertex and run BFS from it. For some small $k$, take the $k$ furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the $k$ overall furthest vertices each time. Repeat a few times.
If the graph is a tree, this is in fact guaranteed to find the longest path with $k=1$ after the second iteration! For a general graph, I don't know of any such guarantee -- but you are likely to find a reasonably long shortest path.
Once you have a sufficiently long path, pick the vertex halfway along it. (This is uniquely determined if the path has an odd number of vertices; if it has an even number, you could choose arbitrarily, or run BFS again from the middle two vertices, and pick whichever scores higher.)
answered Apr 9, 2020 at 17:46
-
$\begingroup$ Thanks. IIUC, this is better for finding the normal center of the graph (the point with the shortest max distance to other nodes), let me call this the "max center". This does not quite match my use-case which is the "mean center". Specifically, the "max center" can be highly influenced by outliers, say a string of 100 nodes added on will completely move the "max center", whereas it will minimally affect the "mean center". $\endgroup$– sligockiApr 10, 2020 at 19:14
-
$\begingroup$ Yes, it's not a perfect fit. To improve robustness for any heuristic, it may be useful to first trim off vertices that appear at or near leaves in (one or more) BFSes. BTW, your problem is equivalent to finding a vertex having minimum sum of distances to all other vertices. $\endgroup$ Apr 10, 2020 at 19:36
$\begingroup$
$\endgroup$
After a bit of reading through literature I've come upon "closeness centrality" which is the reciprocal of what I'm calculating (mean distance, which they call "farness" in the article). But I still haven't found any algorithms for finding the "closeness center" (node with maximum closeness centrality) that is faster than $O(N^2)$.
As a heuristic, I have found a very effective $O(N)$ approximation algorithm though:
- For some $k$, randomly choose $k$ start nodes from the graph.
- Run BFS simultaneously around all $k$ start nodes. For each start node $s$, build up sets $N_s(d)$ of all nodes distance $d$ or less from node $s$ (the $d$-neighborhood of $s$) iteratively starting at $d = 0$.
- For all nodes $n$, keep track of $C_n(d) = \#\{s | n \in N_s(d)\}$ the "count" of how many neighborhoods $n$ is in.
- Iteratively increase $d$ until there exists some node $n$ such that $C_n(d) > k / 2$. In other words, until you find the smallest distance $d$ such that there exists a node $n$ which is within $d$ distance from a majority of the original points.
As $k \to N$, I think this will find the "median center" (or centers). In other words the nodes with minimum (median distance to all other nodes). This tends to be similar (if not identical) to the "mean center" and is definitely close enough to my intention.
There are generally many of these points at the last step and you can test them all to find which has the min (mean distance) / max closeness centrality. And likewise can run this simulation multiple times to get more candidates to test.
Still gladly looking for any other ideas anyone else has!