<p>There is this quasi-linear time approximation algorithm based on <a href="https://en.wikipedia.org/wiki/HyperLogLog" rel="nofollow noreferrer">HyperLogLog</a>: <a href="https://papers-gamma.link/paper/187" rel="nofollow noreferrer">https://papers-gamma.link/paper/187</a></p>

CC BY-SA 4.0
2020-12-31T12:40:07.283Z
2021-01-02T23:01:36.000Z
2021-01-02T23:01:36.000Z
maxdan94
<p>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$.  </p>

<p>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.</p>

<p>Is there a fast, perhaps randomized,  way of solving this problem?  </p>

CC BY-SA 3.0
2012-09-13T19:02:13.527Z
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.
Sasho Nikolov
CC BY-SA 3.0
2012-09-14T08:02:11.107Z
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?
Simd
CC BY-SA 3.0
2012-09-16T15:23:08.317Z
@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.
Simd
CC BY-SA 3.0
2012-09-17T19:40:54.917Z
@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.
Sasho Nikolov
CC BY-SA 3.0
2012-09-17T19:44:54.897Z
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.
Sasho Nikolov
CC BY-SA 3.0
2012-09-18T12:31:20.010Z
@Sasho Nikolov, Thanks. It would be interesting if there was a reduction from matrix multiplication or from some other famous problem. Out of interest, why does the BFS method not take $O(\sqrt{n}^2)$ time per node giving $O(n^2)$ time in total when the degrees are $O(\sqrt{n})$?
Lipoff
CC BY-SA 3.0
2012-09-18T12:59:58.933Z
I might just be dense: where does this $O(\sqrt{n}^2)$ come from? Couldn't BFS examine in the worst case each edge once, giving time $O(m) = O(n^{3/2})$ per node? Am I missing some trick?
Sasho Nikolov
<ds.algorithms><graph-algorithms><randomized-algorithms>
Count $k$-hop neighborhood for every vertex
Lipoff
# Count $k$-hop neighborhood for every vertex

(Asked by: username_0 on 2012-09-13)

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?

**Tags:** ds.algorithms, graph-algorithms, randomized-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_2**: @username_1, 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.  
> **username_1**: @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.  
> **username_1**: username_0, 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.  
> **username_0**: @username_1, Thanks. It would be interesting if there was a reduction from matrix multiplication or from some other famous problem. Out of interest, why does the BFS method not take $O(\sqrt{n}^2)$ time per node giving $O(n^2)$ time in total when the degrees are $O(\sqrt{n})$?  
> **username_1**: I might just be dense: where does this $O(\sqrt{n}^2)$ come from? Couldn't BFS examine in the worst case each edge once, giving time $O(m) = O(n^{3/2})$ per node? Am I missing some trick?  

---

## 1 answers

### Answer by username_3 on 2020-12-31. Score: 2

There is this quasi-linear time approximation algorithm based on [HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog): <https://papers-gamma.link/paper/187>


---

