0
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ It would help if you could give us the full definition of $Rank_u(v)$. $\endgroup$ May 29, 2015 at 14:44
  • $\begingroup$ Still not clear: how are ties resolved? $\endgroup$ May 30, 2015 at 16:51
  • $\begingroup$ You can assume that there is no ties. $\endgroup$
    – Mike
    May 30, 2015 at 17:50

1 Answer 1

0
$\begingroup$

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)<Rank_u(w)$ iff $d(u,v)<d(u,w)$.

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<i$,
  • $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<j}\frac{1}{Rank_{v_i}(v_j)Rank_{v_j}(v_i)} = 2\sum_{i<j}\frac{1}{j(1+i)} = 2\sum_{j=2}^n(\frac{j-1}{j}\sum_{i=1}^{j-1}\frac{1}{i})$;

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

$\endgroup$
0

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .