12
$\begingroup$

For a node $v$ of a directed unweighted graph $G$, I define the $k$-hop neighborhood of $v$ as the set of vertices that are reachable from $v$ in $k$ hops or fewer (that is following a path with $k$ edges or fewer). I would like to compute the cardinality of this $k$-hop neighborhood for very node $v$ in $G$.

One option is to simply raise the adjacency matrix of $G$ to the power $k$ using Boolean arithmetic and then sum the rows. This is however rather slow and seems wasteful (consider for example the complete graph or a very sparse graph). Another approach is to naively search from each node but this is at least $O(n d^k)$ time for a $d$-regular graph, for example. This naive method is also wasteful as it doesn't take advantage of any previous computations it has done. The sizes of the neighborhood of two adjacent nodes are surely not independent.

Is there a fast, perhaps randomized, way of solving this problem?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ just to make clear what matrix mult. gives: you can take the $k$-th power of the adjacency matrix and count the number of nonzero entries in each row. this gives $O(n^{\omega}\log k)$ using the best matrix multiplication algorithm, and $O(nm\log k)$ using sparse matrix multiplication if you have a sparse graph. $\endgroup$
    – Sasho Nikolov
    Commented Sep 13, 2012 at 19:02
  • 1
    $\begingroup$ Can you use a random walk approach? For $2$-hop I can imagine you could add the degree of the all the neighbours of $v$ to get an upper bound. Then perform repeated random walks of length $2$ starting at $v$ and count the number of times you land at the same node. Then use this as the proportion of the upper bound to get your estimate. Assuming all the nodes hold their own degree, the time is roughly proportional to the number of nodes times the number of random walks per node. Maybe the idea can be extended to $k$-hop? $\endgroup$
    – Simd
    Commented Sep 14, 2012 at 8:02
  • $\begingroup$ @Sasho Nikolov, Am I right in thinking that for $k=2$ the sparse matrix multiplication complexity is always very pessimistic? If the max degree is less than $\sqrt{n}$, say, then you are always better off doing the naive breadth first search as this takes essentially $O(n^2)$ time. However, as the OP says, this seems not to take into account the redundancies in the calculations you are doing. $\endgroup$
    – Simd
    Commented Sep 16, 2012 at 15:23
  • $\begingroup$ @Raphael how do you use BFS to solve the problem in $O(n^2)$ time when the max degree is $O(\sqrt{n})$? Starting a BFS from each node gives $O(nm + n^2)$. You are right that this bound is better than what I wrote above for sparse matrix mult. $\endgroup$
    – Sasho Nikolov
    Commented Sep 17, 2012 at 19:40
  • $\begingroup$ Lipoff, your problem is of course reducible to all pairs shortest paths on unweighted undirected graphs. the best bounds i know in that case are indeed matrix multiplication and the trivial BFS from each node. $\endgroup$
    – Sasho Nikolov
    Commented Sep 17, 2012 at 19:44

1 Answer 1

Reset to default
2
$\begingroup$

There is this quasi-linear time approximation algorithm based on HyperLogLog: https://papers-gamma.link/paper/187

Improve this answer
$\endgroup$

Your Answer

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

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