I am trying to understand an algorithm  presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is presented on page 7, in pseudocode.)As I understand it, the idea of the algorithm is to identify densely connected communities (basically, subgraphs) in a graph, such that any subset of vertices in the community has more connections (that is, edges pointing to another vertex) inside the community than to any other community in the graph.Below I've cited the part of the algorithm I'm having trouble with:For all vertices v_i in network N that are not in any stable community    Create a subset S of v_i and its neighbors          For each neighbor n_j            ...            Identify y_j, the subset of external neighbors             which are all within distance k of each otherI take external neighbors to mean the neighbours of $n_j$ that aren't in $S$, and where the distance between them is also never measured through $S$ (as otherwise, they would never be more than two hops apartthrough $n_j$).The authors state the following about the complexity of this part:...the average degree of a vertex is $d$......the complexity for computing $y_j$ for all possible values of $k$ is $O(d^3)$.On the next page, the authors make some more statements about the complexity of this part, including that the values of the shortest paths between external vertices can be reused for many neighbours and that setting $k$ to small values (24) is sufficient in most cases. I'm not sure if these considerations are already factored in, however I'm a bit stuck on all possible values of $k$ in the above quotation.My question is: what assumptions are necessary for the complexity result $O(d^3)$ to hold, with $d$ being the average degree of a vertex? How is the subset found in this case?
Complexity of finding a subset of vertices within distance k of each other, given a set of vertices
graph theory;time complexity