1
$\begingroup$

In other words, given a graph with nodes $N=\{n_0,n_1,...,n_j\}$, and a set of nodes in the graph $M=\{n_a,n_b,...,n_k\}$ with $M\subseteq N$, I'm looking for what to call the node or nodes $n'$ which minimize:

$\sum_{m\in M}d_{min}(n',m)$

where $d_{min}(x,y)$ is the shortest distance from node $x$ to node $y$, as traditionally defined.

When $M=N$, this would be the node with the highest closeness centrality, but I'm interested in subgraphs.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Why not the vertices closest to $M$? See also graph centrality. $\endgroup$
    – Pål GD
    Aug 28, 2013 at 22:30
  • $\begingroup$ Nit-picky note: using typical conventions, your sum ranges over $a, a+1, \dots, k$ -- not what you want. I recommend you use an index set $I \subseteq [0..j]$ so that $M = \{ n_i \mid i \in I\}$. $\endgroup$
    – Raphael
    Aug 29, 2013 at 9:25
  • 1
    $\begingroup$ @Raphael Even more nits picked. No need to introduce indices at all: $\sum_{x\in M} d_\min(n',x)$. $\endgroup$
    – Hendrik Jan
    Aug 29, 2013 at 10:46
  • $\begingroup$ Thanks for the nitpicks; it's been a while since I wrote math so formally :) $\endgroup$
    – nvioli
    Aug 29, 2013 at 15:55

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.