# Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion
## 3 Proposed Method  
In this section, we first describe the general method. We then explain in details the exploration rules in Section 3.1, with the different parameters and their influence on the sampling. We introduce names for samplings with particular parameter values, to better distinguish them in the rest of the paper. Finally, we show the connection with the main sampling methods found in the literature in Section 3.2. Let \(\mathcal{L}_{0}\) denote the set of initial nodes from where the sampling starts. This is the initial layer. The algorithm is based on the exploration of the graph in successive layers \(\mathcal{L}_{1},\mathcal{L}_{2},\mathcal{L}_{3}\dots\), built around the initial one and expanding along the graph edges. Each layer is a set of nodes, that have been obtained from the expansion process applied at the previous layer. Different parameters set the expansion rules, selecting subsets of edges to follow, from one layer to the next. The expansion rules are the crucial ingredient that determines the final properties of the sampled graph. The main algorithm is shown on Algorithm 1. In the case of an attributed graph, the exploration may depend on the graph structure as well as the properties associated to the nodes and edges of the graph. ```
Data: Initial set of nodes \(\mathcal{L}_{0}\), number of layers \(K\), graph to sample \(G\) Result: A graph \(G_{s}\) sampled from \(G\) initialization \(\mathcal{L}_{k}\leftarrow\mathcal{L}_{0}\), \(G_{s}\leftarrow\varnothing\), \(\mathcal{L}_{T}\leftarrow\mathcal{L}_{0}\); for\(k\gets 0\)to \(K-1\)do nodes-info \(\leftarrow\)GetNodesInfo (\(\mathcal{L}_{k}\)); \(E_{k}\leftarrow\)GetNeighbors (\(\mathcal{L}_{k}\)); \(E_{k}^{(\text{in})},E_{k}^{(\text{out})}\leftarrow\)FilterEdges (\(E_{k}\), \(\mathcal{L}_{T}\)); \(\mathcal{L}_{k+1},E^{\text{sampled}}\leftarrow\)SampleEdges (\(E_{k}^{(\text{out})}\), nodes-info); \(G_{s}\leftarrow\)AddToGraph (\(G_{s}\), \(\mathcal{L}_{k}\), \(E_{k}^{(\text{in})}\), \(E^{\text{sampled}}\),nodes-info); \(\mathcal{L}_{T}\leftarrow\)Union(\(\mathcal{L}_{T}\), \(\mathcal{L}_{k+1}\));  end for
```  
**Algorithm 1**Spikyball algorithm. The first two functions of the algorithm access and collect the information from the network. The function GetNodesInfo is the one retrieving the information associated to the nodes within each layer \(\mathcal{L}_{k}\). This information may be required when dealing with an attributed graph, in the case where the sampling is guided by the attributes. While this algorithm concerns the general case of graphs having attributes, it can be used without modifications when no attributes are present. In this case, the GetNodesInfo will always return an empty set. The function GetNeighbors collect the edges incident to the nodes in \(\mathcal{L}_{k}\) as well as the data attached to these edges if available. Both functions (GetNodesInfo and GetNeighbors) will make \(|\mathcal{L}_{k}|\) requests, with \(|\mathcal{L}_{k}|\) being the number of nodes in \(\mathcal{L}_{k}\). In many cases, for graphs without attributes or for some networks allowing to join node and edge requests, GetNodesInfo is not needed and the number of requests will be divided by 2. We assume that the information about the neighbors is not collected, except their node id which is encoded in the edges. Indeed, collecting information from the neighbors would require an additional query for each neighbor, which can be quickly prohibitive and limited in the case of a social network. When the raw data has been collected from the network, it is further processed by three different functions. The edges are sorted by FilterEdges between edges connecting the source nodes to nodes already collected in previous layers \(E_{k}^{(\text{in})}\) and the edges pointing to new nodes \(E_{k}^{(\text{out})}\). Furthermore, this function can be used to remove edges according to some criteria, for example, if the weight of an edge is smaller than a given value set by the user.