Forest-Fire

Consider a node with an out-degree of 100, where each of its neighbors also has a similar out-degree. If the goal is to sample 10 nodes from the neighborhood within 3 hops, a BFS traversal will likely return 10 direct neighbors of the root node, and a DFS search will likely return the first neighbor found and 9 of that neighbor's neighbors. Therefore, neither of these methods will effectively sample nodes up to 3 hops away, nor will the sampled subgraph be representative of the broader 3-hop neighborhood structure.

Therefore, to sample representative neighborhoods in the Bitcoin graph, we developed a method that randomly selects a subset of neighbors for a root node. Then, for each of those selected nodes, it chooses a subset of their immediate neighbors, and continues this process until a termination criterion is met.

This approach aims to sample representative neighborhood subgraphs from the Bitcoin graph, addressing the limitations of BFS/DFS mentioned previously. The method follows the general principles of the Forest Fire model and is an adaptation of the Forest Fire sampling algorithm.