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

CC BY-SA 3.0
2013-12-26T01:24:11.177Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-12-28T18:39:27.407Z
apparently a subarea of the [facility location problem](http://en.wikipedia.org/wiki/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
CC BY-SA 3.0
2013-12-28T19:31:29.320Z
also [metric k-center](http://en.wikipedia.org/wiki/Metric_k-center)
vzn
CC BY-SA 3.0
2013-12-29T13:50:38.790Z
The 2-approximation is also optimal under the usual assumptions.
Juho
CC BY-SA 3.0
2014-08-08T16:47:21.443Z
@Suresh thx do you know any refs for that?
vzn
CC BY-SA 3.0
2014-08-08T20:18:21.333Z
For the 2-approximation ? that's Gonzalez's algorithm: in the Kleinberg/Tardos algorithms book
Suresh Venkat
CC BY-SA 3.0
2013-12-26T00:08:17.540Z
2013-12-26T00:08:17.540Z
Bangye
<p>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.</p>

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

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

CC BY-SA 3.0
2013-12-24T03:46:21.917Z
seems equivalent to Dominating Set in the $d$-th [power of the graph](http://en.wikipedia.org/wiki/Graph_power). Also search for "distance dominating set."
Austin Buchanan
CC BY-SA 3.0
2013-12-24T07:04:03.033Z
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
CC BY-SA 3.0
2013-12-24T08:23:21.650Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-12-24T16:33:49.490Z
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"](http://en.wikipedia.org/wiki/Six_degrees_of_separation) concept, [small world graphs](http://en.wikipedia.org/wiki/Small-world_network) etc
vzn
CC BY-SA 3.0
2013-12-28T18:32:25.777Z
taking austins tip, a std concept/approach in this area is eg [$(k,r)$-domination in graphs](http://www.m-hikari.com/ijcms-2011/29-32-2011/jothilakshmiIJCMS29-32-2011-1.pdf) & there are common applications in devising wireless and power network configurations/coverages
vzn
CC BY-SA 3.0
2014-08-08T01:39:23.030Z
also known as the [(k, r) center problem](http://erikdemaine.org/papers/MapGraphs_TAlg/paper.pdf)
vzn
<reference-request><graph-theory><optimization><application-of-theory>
finding "hubs" in a graph
vzn
# finding "hubs" in a graph

(Asked by: username_0 on 2013-12-24)

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").

**Tags:** reference-request, graph-theory, optimization, application-of-theory
> **Comments:**
> **username_1**: seems equivalent to Dominating Set in the $d$-th [power of the graph](http://en.wikipedia.org/wiki/Graph_power). Also search for "distance dominating set."  
> **username_2**: 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.  
> **username_3**: 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.  
> **username_0**: 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"](http://en.wikipedia.org/wiki/Six_degrees_of_separation) concept, [small world graphs](http://en.wikipedia.org/wiki/Small-world_network) etc  
> **username_0**: taking austins tip, a std concept/approach in this area is eg [$(k,r)$-domination in graphs](http://www.m-hikari.com/ijcms-2011/29-32-2011/jothilakshmiIJCMS29-32-2011-1.pdf) & there are common applications in devising wireless and power network configurations/coverages  
> **username_0**: also known as the [(k, r) center problem](http://erikdemaine.org/papers/MapGraphs_TAlg/paper.pdf)  

---

## 1 answers

### Answer by username_4 on 2013-12-26. Score: 6 | Accepted answer

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

> **Comments:**
> **username_5**: 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.  
> **username_0**: apparently a subarea of the [facility location problem](http://en.wikipedia.org/wiki/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.  
> **username_0**: also [metric k-center](http://en.wikipedia.org/wiki/Metric_k-center)  
> **username_2**: The 2-approximation is also optimal under the usual assumptions.  
> **username_0**: @Suresh thx do you know any refs for that?  
> **username_5**: For the 2-approximation ? that's Gonzalez's algorithm: in the Kleinberg/Tardos algorithms book  

---

