# finding "hubs" in a graph

consider the problem: given a graph and a number of vertices $n$ less than the vertices in the graph, and a distance $d$. find a set of $n$ vertices such that all vertices of the graph are within $d$ distance of the $n$ vertices (measured in edge count of the shortest path). in a sense the $n$ vertices are "hubs" of the graph. (there may be other constraints on their selection.) suspect this problem may arise in a variety of guises. am not nec. looking for an exact solution.

looking for the contexts this arises (applications) & recent literature/survey(s) on this problem, finding the "natural" "hubs" of a graph.

possibly somewhat related is finding/adding a few edges to yield "good" hubs (hub sets that are small relative to the vertices they "reach").

• seems equivalent to Dominating Set in the $d$-th power of the graph. Also search for "distance dominating set." Dec 24 '13 at 3:46
• Sounds like you should be looking at finding interesting subgraphs in social networks. In social network analysis, a $k$-clique is a maximal set of vertices that are at a distance no greater than $d$ from each other. You might also be interested in $k$-clans and $k$-clubs.
– Juho
Dec 24 '13 at 7:04
• to add to Austin's comment: the optimization problem of minimizing $n$ given $d$ and the graph is equivalent to Min Set Cover under approximation preserving reductions. So you can approximate the smallest $n$ up to $\ln N$ and no better, where $N$ is the size of the graph. Dec 24 '13 at 8:23
• agreed with austins reformulation, thx. the problem does have ties to social network analysis, marketing or finding "influencers" and also viral spreading, and transportation networks. it is not exactly the same as finding cliques in the original graph although that is similar. it may be close to finding cliques in the $d$-th power of the graph. it seems to be closely tied to the "degrees of separation" concept, small world graphs etc
– vzn
Dec 24 '13 at 16:33
• taking austins tip, a std concept/approach in this area is eg $(k,r)$-domination in graphs & there are common applications in devising wireless and power network configurations/coverages
– vzn
Dec 28 '13 at 18:32

When n is given and the objective is to minimize d, it is the well-known n-center problem.

• In particular, there's "simple" 2-approximation. Pick any vertex, pick the vertex furthest from it, pick the next one that has maximum distance from these two, and so on till you have $n$ centers. Dec 26 '13 at 1:24
• apparently a subarea of the facility location problem also called "k-center" problem but which apparently in that case is not limited to graphs ie may use more general concepts of spatial distances/distance metrics.
– vzn
Dec 28 '13 at 18:39
• also metric k-center
– vzn
Dec 28 '13 at 19:31
• The 2-approximation is also optimal under the usual assumptions.
– Juho
Dec 29 '13 at 13:50
• @Suresh thx do you know any refs for that?
– vzn
Aug 8 '14 at 16:47