<p>If I understand the requirements correctly, the answer is no. I will restate (what I understand to be) the problem:</p>

<p>We are dealing with graphs $(V,E,\delta)$ (undirected, though directed edges won't change the answer), equipped with a distance $\delta$ which generates a ranking $Rank_u$ for each node $u$. This means that there are no $u,v,w$ with $v\neq w$ and $d(u,v)=d(u,w)$; for any node $u$, $Rank_u$ is then the unique function $V\to\{1,...,|V|\}$ such that $Rank_u(v)&lt;Rank_u(w)$ iff $d(u,v)&lt;d(u,w)$.</p>

<p>I will concentrate on the case $a=b=1$, i.e. consider the sums</p>

<p>$s_1 := \sum_{v\neq u}\frac{1}{Rank_u(v)Rank_v(u)}$ and $s_2 := \sum_{v\neq u}\frac{1}{Rank_u(v)^2}$.</p>

<p>The question is whether $s_2$ can be used to approximate $s_1$. Note that for a graph with $n$ nodes, $s_2$ will always be equal to $n\sum_{i=2}^n\frac{1}{i^2}$, which is in $O(n)$, since $\sum_{i=2}^\infty\frac{1}{i^2}$ converges. It is enough to find a family $(V_n,E_n,\delta_n)$ of graphs with $|V_n|=n$ for which $s_1$ grows more quickly. Consider this example:</p>

<p>$(V_n,E_n)$ is the complete graph $K_n$ on $n$ nodes. The metric $\delta_n$ is given by $\delta_n(v_i,v_j) = 2^i+2^j$ for $i\neq j$ (and $0$ for $i=j$). The resulting ranking functions are</p>

<ul>
<li>$Rank_{v_i}(v_j) = 1+j$ for $j&lt;i$,</li>
<li>$Rank_{v_i}(v_i) = 1$,</li>
<li>$Rank_{v_i}(v_j) = j$ for $j&gt;i$.</li>
</ul>

<p>The first sum above then becomes</p>

<p>$s_1 = 2\sum_{i&lt;j}\frac{1}{Rank_{v_i}(v_j)Rank_{v_j}(v_i)} = 2\sum_{i&lt;j}\frac{1}{j(1+i)} = 2\sum_{j=2}^n(\frac{j-1}{j}\sum_{i=1}^{j-1}\frac{1}{i})$;</p>

<p>the summand is in $\Theta(\log j)$, and $s_1$ is in $\Theta(n\log n)$.</p>

CC BY-SA 3.0
2015-06-01T14:28:57.033Z
2015-06-01T16:32:02.883Z
2015-06-01T16:32:02.883Z
Klaus Draeger
<p>For arbitrary graph of n node, can I approximate $\sum_{v\neq u}\frac{1}{Rank_u(v)^a\times Rank_v(u)^b}$ with $\sum_{v\neq u}\frac{1}{Rank_u(v)^{a+b}}$ or not when n is large enough? $a,b&gt;0$, $Rank_u(v)=k$ if v is the $k$th nearest node to u. For example, $Rank_u(u)=1$, $Rank_u(u')=2$ where u' is the nearest node to u. Here approximation means something like $\Theta(n)$. Thanks a lot!</p>

CC BY-SA 3.0
2015-05-29T14:44:31.557Z
It would help if you could give us the full definition of $Rank_u(v)$.
Klaus Draeger
CC BY-SA 3.0
2015-05-30T16:51:57.377Z
Still not clear: how are ties resolved?
Sasho Nikolov
CC BY-SA 3.0
2015-05-30T17:50:21.950Z
You can assume that there is no ties.
Mike
<graph-theory><approximation>
Calculate sum of reciprocal rank in arbitrary large graph
Mike
# Calculate sum of reciprocal rank in arbitrary large graph

(Asked by: username_0 on 2015-05-29)

For arbitrary graph of n node, can I approximate $\sum\_{v\neq u}\frac{1}{Rank\_u(v)^a\times Rank\_v(u)^b}$ with $\sum\_{v\neq u}\frac{1}{Rank\_u(v)^{a+b}}$ or not when n is large enough? $a,b>0$, $Rank\_u(v)=k$ if v is the $k$th nearest node to u. For example, $Rank\_u(u)=1$, $Rank\_u(u')=2$ where u' is the nearest node to u. Here approximation means something like $\Theta(n)$. Thanks a lot!

**Tags:** graph-theory, approximation
> **Comments:**
> **username_1**: It would help if you could give us the full definition of $Rank_u(v)$.  
> **username_2**: Still not clear: how are ties resolved?  
> **username_0**: You can assume that there is no ties.  

---

## 1 answers

### Answer by username_1 on 2015-06-01. Score: 0 | Accepted answer

If I understand the requirements correctly, the answer is no. I will restate (what I understand to be) the problem:

We are dealing with graphs $(V,E,\delta)$ (undirected, though directed edges won't change the answer), equipped with a distance $\delta$ which generates a ranking $Rank\_u$ for each node $u$. This means that there are no $u,v,w$ with $v\neq w$ and $d(u,v)=d(u,w)$; for any node $u$, $Rank\_u$ is then the unique function $V\to\{1,...,|V|\}$ such that $Rank\_u(v)

I will concentrate on the case $a=b=1$, i.e. consider the sums

$s\_1 := \sum\_{v\neq u}\frac{1}{Rank\_u(v)Rank\_v(u)}$ and $s\_2 := \sum\_{v\neq u}\frac{1}{Rank\_u(v)^2}$.

The question is whether $s\_2$ can be used to approximate $s\_1$. Note that for a graph with $n$ nodes, $s\_2$ will always be equal to $n\sum\_{i=2}^n\frac{1}{i^2}$, which is in $O(n)$, since $\sum\_{i=2}^\infty\frac{1}{i^2}$ converges. It is enough to find a family $(V\_n,E\_n,\delta\_n)$ of graphs with $|V\_n|=n$ for which $s\_1$ grows more quickly. Consider this example:

$(V\_n,E\_n)$ is the complete graph $K\_n$ on $n$ nodes. The metric $\delta\_n$ is given by $\delta\_n(v\_i,v\_j) = 2^i+2^j$ for $i\neq j$ (and $0$ for $i=j$). The resulting ranking functions are

* $Rank\_{v\_i}(v\_j) = 1+j$ for $j* $Rank\_{v\_i}(v\_i) = 1$,
  * $Rank\_{v\_i}(v\_j) = j$ for $j>i$.

The first sum above then becomes

$s\_1 = 2\sum\_{i

the summand is in $\Theta(\log j)$, and $s\_1$ is in $\Theta(n\log n)$.


---

