Sampling networks by nodal attributes

In a social network individuals or nodes connect to other nodes by choosing one of the channels of communication at a time to re-establish the existing social links. Since available data sets are usually restricted to a limited number of channels or layers, these autonomous decision making processes by the nodes constitute the sampling of a multiplex network leading to just one (though very important) example of sampling bias caused by the behavior of the nodes. We develop a general setting to get insight and understand the class of network sampling models, where the probability of sampling a link in the original network depends on the attributes $h$ of its adjacent nodes. Assuming that the nodal attributes are independently drawn from an arbitrary distribution $\rho \left(h\right)$ and that the sampling probability $r(h_i,h_j)$ for a link $ij$ of nodal attributes $h_i$ and $h_j$ is also arbitrary, we derive exact analytic expressions of the sampled network for such network characteristics as the degree distribution, degree correlation, and clustering spectrum. The properties of the sampled network turn out to be sums of quantities for the original network topology weighted by the factors stemming from the sampling. Based on our analysis, we find that the sampled network may have sampling-induced network properties that are absent in the original network, which implies the potential risk of a naive generalization of the results of the sample to the entire original network. We also consider the case, when neighboring nodes have correlated attributes to show how to generalize our formalism for such sampling bias and we get good agreement between the analytic results and the numerical simulations.

Figure 1

A schematic diagram showing the sampling method studied in this paper. For each node $i$, a hidden variable $h_i$ is drawn randomly from $\rho \left(h\right)$. A link $ij$ in the original network is sampled with a probability $r(h_i,h_j)$, where $h_i$ and $h_j$ are the hidden variables of the nodes $i$ and $j$.

Figure 2

(a) Degree distribution $P\left(k\right)$, (b) degree correlation $k_{nn}\left(k\right)$, (c) clustering coefficient $c\left(k\right)$, (d) average neighbor hidden variable $h_{nn}\left(h\right)$ of the sampled networks. Simulation results are compared with theoretical equations in Table 1. The network is sampled from the Erdös-Rényi random graph of size $N=5000$ and the link density $p=0.03$. The parameter values for sampling are $\alpha =0.8,h_0=0.3$, and $\beta =-\infty$. Under this setting, $12\%$ of the links are sampled. Simulation results are averaged over 200 independent runs.

Figure 3

(a) The degree correlation $k_{nn}\left(k\right)$ when the original network is nonassortative, assortative, and disassortative. (b) The clustering spectrum $c\left(k\right)$ of the sampled network when the original clustering spectrum is $c_o\left(\kappa \right)\propto {\kappa }^0\text{(const)},{\kappa }^{-1}$, and ${\kappa }^{-2}$. (c) The average original degree given the sampled degree, $\overline{\kappa }\left(k\right)$. The inferred original degree $\overline{\kappa }\left(k\right)$ is just slightly below the original average degree $\langle \kappa \rangle$, depicted as a horizontal dashed line, for $k<k^{*}$. (d) The average hidden variable given sampled degree $\overline{h}\left(k\right)$. The horizontal dashed line depicts $\langle h\rangle =\int dhh\rho \left(h\right)$. The other settings are the same as described in the caption of Fig. 2.

Figure 4

(a) The original degree distribution $P_o\left(\kappa \right)$ for the case of Binomial distribution (ER random graph) and the log-normal distribution. For the log-normal distribution, $\mu =150$ and $\sigma =0.5$ are used. (b) The sampled degree distributions $P\left(k\right)$ when $P_o\left(\kappa \right)$ are the log-normal and the binomial distributions. The parameters for the sampling are the same as described in the caption of Fig. (2). (c) The average neighbor degree $k_{nn}\left(k\right)$ for the log-normal $P_o\left(\kappa \right)$. The same setting is used as in Fig. 3, except for $P_o\left(\kappa \right)$. (c) The clustering spectrum $c\left(k\right)$ for the log-normal $P_o\left(\kappa \right)$. The same setting is used as in Fig. 3, except for $P_o\left(\kappa \right)$.

Figure 5

(a) Degree distribution $P\left(k\right)$, (b) average neighbor degrees $k_{nn}\left(k\right)$, (c) clustering spectrum $c\left(k\right)$ of the sampled network for the model having vector nodal attributes $\mathbf{h}$. Simulation results are compared with the theoretically predicted lines. The network is sampled with probability given by Eq. (31) with $F=2,q=4$ and $c=2$ from an original network of Erdös-Rényi random graph with $N=50000$ and $p=0.003$. Under this setting, approximately $43\%$ of the links are sampled. The simulations results are averaged over 1000 independent runs. (d) Correlation of the hidden variables between neighbors in the sampled networks. Symbols denote the simulation results while dashed curves are theoretically predicted results.

Figure 6

(a) Degree distribution $P\left(k\right)$, (b) average neighbor degrees $k_{nn}\left(k\right)$, (c) clustering spectrum $c\left(k\right)$, (d) correlations of neighboring hidden variables in the sampled network for the model with correlated $h$. Simulation results, depicted by symbols, are compared with the theoretically predictions, depicted as dashed curves. The original network is constructed using the stochastic block model where $N=10000,C=100,p_{\mathrm{in}}=0.5$ and $p_{\mathrm{out}}=50/9900$. For each community, $h$ is drawn randomly from a distribution whose mean is dependent on the index of the community to introduce the correlation. The results are compared with a null model where the correlation is removed by shuffling $h$. The correlated case and the uncorrelated cases are denoted as CO and UC in the legend, and drawn in blue and orange, respectively. The fraction of the sampled links are $16\%$ and $15\%$ for the correlated and uncorrelated cases, respectively. The simulations results are averaged over 200 independent runs.