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?