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$
  • 1
    $\begingroup$ It would help if you could give us the full definition of $Rank_u(v)$. $\endgroup$ – Klaus Draeger May 29 '15 at 14:44
  • $\begingroup$ Still not clear: how are ties resolved? $\endgroup$ – Sasho Nikolov May 30 '15 at 16:51
  • $\begingroup$ You can assume that there is no ties. $\endgroup$ – Mike May 30 '15 at 17:50
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.