# Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion
## 2 Related Work  
There are two main families of graph sampling methods adopting a neighbor exploration strategy. The first family is based on random walks (RWs). Examples are the re-weighted random walk, the Metropolis-Hasting random walk [6], CNRW and GNRW [7], CNARW [8] or Frontier Sampling [9]. The general principle is to guide random walks with probabilities assigned to edges. These probabilities define which neighbors to visit as the exploration progresses. In the re-weighted and Metropolis-Hasting RWs, the goal is to reduce potential biases toward high degree nodes and obtain a faithful reduced graph. The assessment criteria are degree distribution and graph properties such as diameter or clustering coefficient. For the CNARW, rules are introduced to push the exploration to go farther at each step, favoring a faster sampling of the graph. Frontier Sampling uses multiple RWs in parallel. The second family of graph crawling algorithms starts from an initial node or group of nodes and expands around it either with a breadth-first search (BFS) or depth-first search (DFS) approach. Examples are Snowball sampling [1; 10], where close regions around the initial starting point are densely sampled while regions that are located further away from it may not be sampled at all. Moreover, in large, densely connected, networks, snowball gets quickly surrounded by the overwhelming number of neighbors. Forest Fire [2] and the Expander graph approach [3] provide solutions for large networks. These approaches achieve scalability by following a reduced random subset of the edges during the expansion. The Spikyball approach unifies these latter samplings into a unique framework and adds new exploration options. Its tunable rules enable the preferential collection of nodes and edges with specific properties. More precisely, what distinguishes the methods within the second family are the spreading rules. The snowball sampling is a breadth-first search with a stopping parameter. At each iteration, the sampling propagates to all the neighbors and is stopped after \(N\) iterations. For the Forest Fire, the propagation takes place on a subset of the edges selected randomly. For each newly burned (or explored) node, a number \(x\) of its neighbors is selected to spread the \"fire\" further. This random number follows a geometric distribution and is independent of the number of neighbors. This independence decreases the influence of highly connected nodes (possessing many edges where the fire could propagate). This is desirable in the context of graph sampling when the sampled graph must have a degree distribution as close as possible to the one of the full graph and Forest Fire is designed for this purpose [11]. However, this random  
Figure 1: Snowball **(left)** and Spikyball **(right)** sampling example. The sampled nodes are colored in purple, pink, and green, the non-sampled ones are in grey. Starting from the central node (user defined), both samplings expand in successive hops, following neighbor connections (purple circle is 1-hop, pink circle is 2-hop, and green circle is 3-hop). The size of the nodes symbolizes their importance and the spikyball focus on collecting them in priority. This importance can be related to their degree or to some other attribute associated to them. selection may fail at collecting a set of nodes with particular properties that are considered important for the research problem at hand. In the Expander graph method [3], the subset of neighbors to spread to is selected according to the target node connections. The nodes giving the largest increase in the number of neighbors of the sampling are collected. The rationale is to maximize the chance to collect new communities. However, estimating the optimal nodes to spread to needs costly requests. For each candidate, all its connections have to be requested and this can result in a computationally intractable solution when dealing with applications that involve social media. Furthermore, this also leads to a partial sampling of the core nodes of a community.