# Spikyball Sampling: Exploring Large Networks via an Inhomogeneous Filtered Diffusion
## 3 Proposed Method
### Exploration Rules  
The edge sampling rules are encoded in the function SampleEdges which takes 2 input arguments. The first one is the list of edges with their properties, \(E_{k}^{(\text{out})}\), that connect nodes from \(\mathcal{L}_{k}\) to their neighbors not already sampled (not in \(G_{s}\)). The second one is the data associated to the nodes in \(\mathcal{L}_{k}\) that may influence the selection of the edges. Within the function is performed a selection of edges to explore, among the one in \(E_{k}^{(\text{out})}\). The target nodes of the selected edges will be the elements of \(\mathcal{L}_{k+1}\), to explore in the next step \(k+1\). Several exploration schemes can be defined with different sets of rules and different properties. The key element is a probability mass function \(p_{k}\) associated to the set of edges \(E_{k}^{(\text{out})}\) that guides the choice of edges to follow from the layer \(k\) to the next. This can also be seen as a conditional probability \(p_{k}(j|j)\) of choosing \(j\) at layer \(k+1\) if \(i\) has been collected at layer \(k\). For the Spikyball, this probability mass function depends on the properties associated to the edge and its source and target nodes. The influence of these properties can be tuned and lead to different propagation schemes. We introduce three real numbers \(\alpha,\beta,\gamma\) and three functions \(f,g,h\). These functions map the feature space of the source node, edge and target node respectively to positive real numbers. We have, at layer \(k\),  
\[p_{k}(e_{ij})=p_{k}(j|i)=\frac{f(i)^{\alpha}g(i,j)^{\beta}h(j)^{\gamma}}{s_{k}}, \tag{1}\]  
where \(s_{k}\) is the normalization depending on the number of nodes at layer \(k\) and their neighbors \(\{\mathcal{N}(i)\}_{i\in\mathcal{L}_{k}}\):  
\[s_{k}=\sum_{i\in\mathcal{L}_{k}}\sum_{j\in\mathcal{N}(i)}f(i)^{\alpha}g(i,j)^ {\beta}h(j)^{\gamma}. \tag{2}\]  
The normalization varies with the layer as there is a different number of nodes and neighbors at each step, however, the mappings from features to positive numbers are independent of the layer. In some cases, the features may depend on the layer. For example, the number of connections of a node that are not connecting it to nodes already collected in previous layers (see below). There are many possibilities for defining \(f,g,h\) and the exponents. In the present work, we focus on a few cases that are representative of the general approach, and of potential interest for the exploration of social networks. In the following, we denote by \(w_{ij}\) the weight associated to edge \(e_{ij}\) between node \(i\) and node \(j\). The weighted degree of node \(i\) is \(d_{i}\) and \(d_{i}^{(out)}\) is the sum of weighted connections from node \(i\) to nodes of \(G\) not in \(G_{s}\). We also introduce \(d_{j}^{(in)}\), the number of connections of node \(j\) from nodes in layer \(k\). Note that \(d_{i}^{(out)}\) and \(d_{j}^{(in)}\) both depend on layer \(k\), although omitted from the notation for simplicity. The number of edges in \(E_{k}^{(\text{out})}\) is denoted \(N_{k}=|E_{k}^{(\text{out})}|\). **Spikyball:** This is the general setting. A random subset of the edges is selected at each layer \(k\) following the probability mass function of Equation (1). If the graph is attributed, the probability to pick an edge can depend on the data, on the edge, and on the connected nodes via the functions \(f,g,h\). For example, in a social network, one may want to sample more edges from highly active users. The number of posts of these users could be the value (node data) influencing the probability to sample the edge.