The Quality of Sampling from Geographic Networks

Abstract

We empirically investigate the factors affecting the quality of information obtained by randomly sampling nodes from a network embedded in two-dimensional space. The motivation for this work is that wireless and other physical networks do in fact have embedding of their nodes in space, although analyses of random walks on such networks often only consider the link structure while ignoring node locations. Of independent interest is the measure we propose to evaluate the quality of sampling: the rate of decrease in the area of the largest empty circle remaining.

1. Introduction

Sampling information from nodes of a network is a well-considered and important problem. The problem particularly has many applications to wireless sensor networks where it may sometimes be necessary to monitor the data of the sensor nodes (e.g., temperature sensors dispersed in a forest used to detect forest fires). In very large nonphysical networks such as online social networks random sampling is useful as a mechanism by which the social network application can gather user statistics. In the physical internet, random sampling may also be used to gather network and user statistics, which, among other applications, may help detection of suspicious activities in a subnetwork. The uses and applications of sampling (random or other) from networks (physical or other) are numerous to mention [1–5].

While nonrandom and biased sampling algorithms may perform well under certain conditions, the performance of random sampling from a network, as implemented via a random walk, is indicative of the network related factors that affect the sampling quality and has many advantages due to obliviousness. For example, random walks have no critical points of failure and are completely local, requiring no global information. Moreover, due to the lack of bias in the method, a random walk can be used as a kind of control to test how the network related factors affect the sampling quality and efficiency. The mixing time of a random walk is the analytical measure of the time it takes for a random walk to reach a truly random sample. Technically it is the worst case time taken to reach the stationary distribution from an arbitrary starting node [5,6]. For a given network, the mixing time is a property of the edge connectivity of the network's nodes, has fundamental relationships with the network's resilience and eigenvalues, and has been well-studied for many graph classes. It is well-known, for example, that graphs whose edge relationships are chosen randomly, such as Erdös-Rényi and random regular graphs, exhibit optimal mixing time [7–9] whereas graphs whose edge relationships are determined via local properties, such as grids and random geometric graphs, exhibit bad mixing time [1,2]. Therefore, in general, the randomness of the edge connectivity can be expected to ameliorate the sampling quality whenever the network is defined only via the edge connectivity matrix (called adjacency matrix) and sampling quality is measured relative to sampling of random nodes quickly.

However, many real-world networks are not defined solely by their adjacency matrix of edge connectivity but also by other relevant node-specific information, such as the location of a sensor node in space for a wireless sensor network, or user-specific information for an online social network. The importance of the location of a node should not be undermined, particularly for applications in which a physical quantity must be measured by sensor nodes. For example, if sensor nodes are distributed across a forest for an application in which a forest fire must be detected via temperature and humidity measurements, the location of the nodes from which the measurements are sampled is critical. Less critical instances of the importance of node locations may include sampling opinion data from a social network, as unintentionally ignoring a large contiguous geographic region may yield inaccurate overall predictions.

As many physical networks in general and sensor networks in particular exist on a two-dimensional surface (without loss of generality), in this work we take the location based information into particular relevance. Therefore, for geographic networks, we must reformulate the meaning of sampling quality and efficiency as sampling a node uniformly at random may no longer be the most appropriate indicator of quality sampling of the information residing in the geographic space. Rather, as motivated above, we wish to further ensure that large contiguous regions of space are not ignored as the sampling proceeds. As such, we make the reasonable assumption that there is no point in space which is of zero importance compared to any other point, which is a weaker assumption than all points in space having equal importance for the sampling. As the measure of a finite set of (visited) points is always zero compared to the measure of the space, one must yet specify what kinds of spatial regions we are taking into account in terms of unvisited regions.

Figure1 illustrates different kinds of empty spatial regions that may be defined on the same point set. The image of Figure1(b) illustrates why restricting to convex regions is necessary, as one may always draw a huge but nonconvex space filling curve that avoids any given finite point set otherwise. The image of Figure1(a) further demonstrates why considering empty regions that are similar in both dimensions is important, as it is also otherwise very easy to embed large convex areas that are very long in one dimension but small in another dimension. Therefore, in this work, we propose a natural measure based on circular regions, as illustrated by Figure1(c), due to the convexity and symmetry of the shape in addition to the elegant computability of the related computational geometry problem via the well-studied Delaunay triangulation [10]. We rely on the empty circle property of the Delaunay triangulation: a circle that contains the three vertices of any Delaunay triangle does not contain any other points of the input set in its interior. It is an unexplored region. We take the following as a measure of the quality of the random walk based sample: the rate at which the largest empty circle area diminishes (the LEC is defined only on visited points of the sampling procedure, e.g., visited points of the simple random walk). A Delaunay triangulation with largest empty circle is illustrated in Figure2. Whereas measuring largest empty circles is a well-studied computational geometry problem with applications to meshes, we are the first to our knowledge to apply it to the measurement of sampling quality from geographic networks.

Figure 1

Given the same point set, measurements are (a) wide in one dimension and narrow in another, (b) nonconvex, and (c) possibly representative of unexplored regions.

Figure 2

The largest circle is derived from the Delaunay triangulation of a given set of points. The largest circle provides a meaningful way of quantifying the unexplored region of the triangulation.

In addition to proposing a natural new measure of sampling quality relevant to geographically embedded networks in particular, we use our measure to compare what network related factors affect the geographic sampling quality. Although our measure of sampling quality is explicitly geometrically defined, it is also dependent on purely graph-theoretic sampling properties, as the sampling process considered is still network dependent. Therefore, we evaluate the mixing time as measured via eigenvalues, to see how the edge connectivity structure affects the geographic sampling quality. We emphasize, however, that one novel aspect of this work is that we also measure how the node distribution structure affects the geographic sampling quality by performing experiments in which node locations are permuted while keeping edge connectivity the same.

The different network types we consider are parametrized with respect to connectivity and expected mixing times, with eigenvalue measurements also explicitly represented in Table1. Of course, given the desired applicability of our results, we focus on parametrized versions of geometrically defined graphs characteristic of purely wireless or hybrid sensor networks. In particular, we consider classes of K-grid graphs at one extreme, representative of the connectivity structure of purely wireless networks, and random regular graphs at the other extreme, representing randomly wired networks with good mixing properties. For the K-grids, we further consider (i) randomizing (i.e., randomly permuting) the node locations in space while keeping links unchanged and (ii) randomizing the links. We note that permuting node locations of the K-grids in space (i) is for the purpose of measuring the effect of the transformation on the quality of sampling though neither transformation (i) nor transformation (ii) results in a realistic wireless scenario. We finally analyze the quality of sampling for small world networks as described by Kleinberg [11], which are representative of hybrid networks [2,12,13], and consider which parametrization processes of such networks result in the best geographic sampling quality even when controlling for degree.

Table 1

Eigenvalue comparison for networks of 2704 nodes.

Graph type	Average degree	Spectral gap
KGrid	4	0.000896
$K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$	4	0.000896
$K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}}$	4	0.339329
$\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}{\mathrm{m}}_{\mathrm{D}\mathrm{A}\mathrm{V}\mathrm{G}4}$	4	0.137089
$\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}{\mathrm{m}}_{\mathrm{D}\mathrm{A}\mathrm{V}\mathrm{G}12}$	12	0.451385
$\mathrm{S}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{l}{\mathrm{d}}_{\text{2-0-0}}$	12	0.002406
$\mathrm{S}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{l}{\mathrm{d}}_{\text{2-6-0}}$	24	0.447815
$\mathrm{S}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{l}{\text{d}}_{\text{1-4-0}}$	12	0.436951
$\mathrm{S}\mathrm{m}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{W}\mathrm{o}\mathrm{r}\mathrm{l}{\mathrm{d}}_{\text{3-0-0}}$	24	0.004534

Thus, we are able to determine the relative effect of node distribution versus edge connectivity on the geographic sampling quality. Our results indicate that, as expected, both randomly permuting node locations and randomizing edge connectivity significantly ameliorate the geographic sampling performance even when applied separately. The effect of the random permutation of the node locations for any fixed network was also surprisingly substantial. Regarding the relative effect of the node permutation versus the randomization of edges, a small but consistent effect is seen favoring the edge randomization towards geographic sampling quality for smaller networks. In order to determine how important was the distinction in the relative effects of node distribution versus edge connectivity, we performed the same experiments on much larger networks and found the distinction amplified. These results indicate that whereas randomizing node locations for the same network indeed has a significantly positive effect in geographic sampling quality, nonetheless the edge connectivity remains the most important factor in sampling quality even when restricted to geographical measures and geographical networks.

In this paper we expand greatly on the ideas previously introduced in [14]. Section2 gives definitions and preliminaries on graphs, random walks, and connectivity. Section3 gives details of the experimental setup, and Section4 summarizes the results. Finally, conclusions are presented in Section5.

2. Definitions and Preliminaries

In talking about a network, we are referring to the graph that represents it. A general graph G is defined by its node set, V, and its edge set E, and is usually denoted as $G=(V,E)$ . For $n=\left|V\right|$ , without loss of generality we may take $V=\{\mathrm{1,2},\dots ,n-1,n\}$ . The edge set E subset of $V^2$ defines the direct connectivity relationships between the nodes. We say that node a neighbors node b or in other words that node a is adjacent to node b, iff there exists edge $\{a,b\}$ in E. We consider undirected graphs where the edge relationship is symmetric. The degree of a node in a graph is the number of nodes that are adjacent to it. A graph is regular if every node has the same degree, and if that degree is d then we can also call such a graph $d\text{-}regular$ . In the case of stochastically generated networks, it is also useful to characterize a graph which may not be regular but whose degree distribution is tightly concentrated about its average degree, and we refer to such a graph as being almost regular. A common and useful representation of graph G is by its adjacency matrix which is a matrix A such that $A[i,j]=1$ iff there exists edge $\{i,j\}$ in E and $A[i,j]=0$ otherwise.

In the case of a geographically embedded network, we may also specify the ordered set of coordinates C subset of $R^2$ . So, such a network may be denoted as $G=(V,E,C)$ with $C_1=〈x_1,y_1〉$ specifying the x and y coordinates of the first node, $C_2=〈x_2,y_2〉$ , the x and y coordinates of the second node, and so forth. Two common types of geographically embedded networks are K -grids and random geometric graphs. Two-dimensional $n\times n$   K-grid is formed by placing $n^2$ nodes exactly in integer lattice positions and directly connecting any two nodes which are at Manhattan distance at most K apart. A random geometric graph is defined by parameters n and r and is formed by distributing n nodes uniformly at random into the square region and connecting any two nodes which are distance at most r apart. Both K-grids and random geometric graphs are almost regular graphs, and both are also badly mixing (very much not rapidly mixing) except for significantly large average degree (i.e., degree at least as large as a constant root of n) [1,2].

Small world graphs are constructed against a lattice according to a formula with p, q, and α as parameters. The graphs begin as K-grids, with each node having short-range connections to all nodes within p lattice steps. The small world is characterized by the addition of q long-range connections, which are generated randomly, with probability proportional to $r^{-\alpha }$ , where r is the lattice distance between the two connected points and α is a fixed exponent [11]. Thus, longer random connections become less likely as α increases.

2.1. Random Walk and Connectivity Preliminaries

A simple random walk on a graph is a memoryless stochastic process which starts at an arbitrary initial node $v_0$ and proceeds to a uniformly randomly chosen neighbor of the current node at each time step. For d-regular graphs, the random walk process is defined by a Markov chain that is identical to the normalized adjacency matrix, namely, A multiplied by $1/d$ . Such a Markov chain is called rapidly mixing if it converges to its stationary distribution, corresponding to sampling a “truly random node” in optimal, namely, asymptotically logarithmic time [5,6]. Graphs which are known to be rapidly mixing include random edge models, such as Erdos-Renyi graphs of at least logarithmic average degree and random regular graphs for any degree at least 3 [8,9]. The size of the second largest eigenvalue of the normalized Laplacian of a graph's adjacency matrix, also referred to as the spectral gap, is well-known to be indicative of whether or not the graph is rapidly mixing, with larger spectral gaps pointing to better mixing properties [6]. We formalize the above in the following.

Let Markov chain $\mathfrak{M}=(\Omega ,P)$ correspond to the natural random walk on a graph $G=(V,E)$ . For any node $v\in V$ , let $\delta (v)$ denote the degree of v, that is, the number of neighbors of v in G, and let $P(v,u)=1/\delta (v)$ for $(v,u)\in E$ and 0 otherwise. In linear algebraic terms, the process is an application of P to the current distribution vector $v_t$ of step t, where the initial distribution vector $v_0$ is concentrated completely at an arbitrary node: $v_t=v_{t-1}P=v_0{P}^t$ .

In such terms, the stationary distribution of $\mathfrak{M}$ , if such exists, is the unique probability vector π such that

$$\begin{array}{cc}& \pi P=\pi .\end{array}$$

(1)

The stationary distribution being a fixed point vector that remains unchanged upon operator P is also the distribution to which the random walk converges, regardless of the starting point, given that G is connected and nonbipartite (which is guaranteed by any odd length cycle):

$$\begin{array}{cc}& \pi =\underset{t\to \infty }{\lim }{v}_0{P}^t,\hspace{1em}\forall v_0.\end{array}$$

(2)

Moreover, when the underlying graph G is regular, then the stationary distribution is the uniform distribution [15], and this statement also remains true asymptotically when G is almost regular; namely, when the degree of every node is $\Theta (f(n))$ for the same function f, then the stationary distribution is $\Theta (1/f(n))$ . Therefore, for almost regular graphs, it is clear that the random walk samples efficiently at stationarity, and the faster the random walk on a regular graph converges to stationarity, the greater its load-balancing qualities are (this refers to how fairly each node is sampled). This rate of convergence to stationarity is called the mixing time.

To define mixing time, we must first introduce the relevant notion of distance over time. Let x be the state at time $t=0$ and denote by $P^t(x,·)$ the distribution of the states at time t. The variation distance at time t with respect to the initial state x is defined to be [16]

$$\begin{array}{cc}& {\Delta }_x\left(t\right)=\underset{S\subseteq \Omega }{\max }\left|P^t\left(x,S\right)-\pi \left(S\right)\right|.\end{array}$$

(3)

Note that when the state space Ω is finite it can be verified that [1]

$$\begin{array}{cc}& {\Delta }_x\left(t\right)=\frac{1}{2}{\displaystyle \sum }_{y\in \Omega }\left|P^t\left(x,y\right)-\pi \left(y\right)\right|.\end{array}$$

(4)

Now we may formally define the mixing time as the following function [16]:

$$\begin{array}{cc}& {\tau }_x\left(ϵ\right)=\min \left\{t\mid {\Delta }_x\left(t^{\prime }\right)\le ϵ,\hspace{0.17em}\hspace{0.17em}\forall t^{\prime }\ge t\right\}.\end{array}$$

(5)

A chain $\mathfrak{M}$ is considered rapidly mixing iff ${\tau }_x(ϵ)$ is $O(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log (n/ϵ)))$ . Clearly, as the name indicates, for a random walk to be used for efficient sampling (according to its stationary distribution), it should be rapidly mixing.

As the stationary distribution π is defined to be such that $\pi P=\pi$ , it corresponds to the eigenvalue ${\lambda }_0=1$ of P. Let the rest of the eigenvalues of P in decreasing order of absolute value be $1={\lambda }_0\ge \left|{\lambda }_1\right|\ge \cdots \ge \left|{\lambda }_{n-1}\right|\ge -1$ . For a finite, connected, nonbipartite Markov chain as the type in this work, the rate of convergence to π, which as you may recall is captured by the mixing time, is governed by the difference between the first and second eigenvalues, namely, the spectral gap which is $1-{\lambda }_1$ [16]. The following theorems establishing these relationships imply that inverse polylogarithmic spectral gap establishes polylogarithmic (i.e., fast) mixing time.

Theorem 1.

For an ergodic Markov chain (ergodicity is guaranteed by the chain being finite, connected, and nonbipartite, as we have in this work), the quantity ${\tau }_x(ϵ)$ satisfies

• (i)

${\tau }_x(ϵ)\le (1-{\lambda }_1{)}^{-1}(\ln \pi (x{)}^{-1}+\ln {ϵ}^{-1})$ ,

(ii)

${\mathrm{m}\mathrm{a}\mathrm{x}}_{x\in \Omega }{\tau }_x(ϵ)\ge \left(1/2\right){\lambda }_1(1-{\lambda }_1{)}^{-1}\mathrm{l}\mathrm{n}(2ϵ{)}^{-1}$ .

As we will measure mixing properties via spectral gap, the above relationships are important.

Finally, we must speak of some of the well-known mixing (or nonmixing) properties of some graphs considered in this work: K-grids for any constant and polylogarithmic K are known to exhibit very poor mixing properties and bad spectral gap [1,17,18]. On the other hand, random d-regular graphs are expanders w.h.p. for any $d\ge 3$ and are therefore rapidly mixing with excellent spectral gap [8,9]. The mixing properties of small world graphs vary significantly, depending to large degree on the parameters used in their construction.

3. Experimental Setup

The experiments were performed on networks of sizes (number of nodes) 2704 and 10404, respectively. For each graph type and node location distribution considered, a random walk was performed on the network, and at every 10 steps the largest empty circle (largest circular unvisited region) was calculated via Delaunay triangulation of the visited nodes. The random walk was continued until all nodes in the network were visited, and the empty circle calculations were plotted for comparisons. The results can be seen in Section4.

The graph types considered were generated as follows. Both $K\mathrm{G}\mathrm{r}\mathrm{i}\mathrm{d}$ and $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ are K-grids of two dimensions for $K=1$ and $K=2$ where indicated; however $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ permutes the location of the grid points while retaining the same link structure. $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}}$ on the other hand maintains that nodes are on the grid locations (as in K-grid) but chooses links randomly, maintaining almost regularity at an average degree of 4 for $K=1$ (and 12 for $K=2$ ). Latter constraint allows us to control for degree when comparing the networks.

The graphs labeled $\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}{\mathrm{m}}_{\mathrm{D}\mathrm{A}\mathrm{V}\mathrm{G}4}$ and $\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}{\mathrm{m}}_{\mathrm{D}\mathrm{A}\mathrm{V}\mathrm{G}12}$ are constructed by choosing both point locations and links randomly, maintaining average degrees of 4 and 12, respectively. The small worlds graphs are labeled according to their parameters p (lattice distance threshold for local links), q (number of randomly chosen distant links), and α (the fixed clustering exponent).

4. Results

Table1 compares the eigenvalues of the networks examined. Note that $K\mathrm{G}\mathrm{r}\mathrm{i}\mathrm{d}$ and $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ have identical spectral gap due to both networks having identical edge connectivity (and adjacency matrices). Note further that because experiments were performed on the normalized matrices, all spectral gaps must be less than 1. The comparative results of the table are consistent with the theoretically known facts that K-grids exhibit poor mixing time and spectral gap whereas the random edge models have significantly good spectral gap.

4.1. K-Grids, Perturbed K-Grids, and Random d-Regular Graphs

Figure3 plots the rate of decrease of the largest empty circle areas during the random walks, for the K-grid and random graphs with 2704 nodes.

Figure 3

Overall comparison of sampling quality for all graph types with 2704 nodes. The graphs with the slowest rate of decrease of largest empty circle area are the two blue lines at the top, which represent the K-grid graphs, with both $K=1$ and $K=2$ .

All networks outperform the unperturbed K-grids. Interestingly, even K-grid of $k=2$ (and average degree of 12) is significantly outperformed by the location-randomized and edge-randomized models of degree 4. In particular, there is a substantial degree of improvement in the sampling quality for the $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ model over the unperturbed K-grid though those two are the same graph. More surprising is the similarity in the performance of the $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ model with the $\mathrm{R}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}{\mathrm{m}}_{\mathrm{D}\mathrm{A}\mathrm{V}\mathrm{G}}$ model of the same average degree.

Upon closer examination of Figure3, it is also apparent that the randomization of edge choices while maintaining node location at regularly spaced grid points ( $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}}$ ) still consistently beats the $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ model in which edge selection is not randomized. In fact, further experiments reveal that the randomization of the edge connections yields higher quality of sampling in comparison to only randomization of the grid's node locations. This comparison is shown for two graphs of 10,404 nodes in Figure4.

Figure 4

Relative comparison of node versus edge effect on sampling quality for two networks of over 10000 nodes. Steps 0 to 500, $k=1$ . Performance of the $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}}$ graph is consistently superior to performance of the $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ graph.

Figure5 shows the rate of decrease of the largest empty circle areas for K-grid and random graphs with 10,404 nodes. As with the 2704-node graphs, the nonrandomized K-grids converge at a much slower rate than all other graph types.

Figure 5

Overall comparison of sampling quality for all graph types with over 10,000 nodes.

Figure6 represents an attempt to show more clearly the results for the K-grid graphs of size 2704. We show the size of the largest unsampled area (as measured via the largest empty circle) decreasing logarithmically as the number of steps required increases. Here it is clear that the $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}}$ graphs perform the best, with $K=2$ beating all and $K=1$ second. In the case shown, the graphs with the worst sampling quality are, as expected, the simple $K\mathrm{G}\mathrm{r}\mathrm{i}\mathrm{d}$ with $K=1$ and, unexpectedly, the $K\mathrm{G}\mathrm{r}\mathrm{i}{\mathrm{d}}_{\mathrm{P}\mathrm{e}\mathrm{r}\mathrm{m}}$ with $K=1$ .

Figure 6

Steps in the random walk versus size of the largest unsampled area for different types of graphs. The size of the largest unsampled area shrinks exponentially from left to right.

4.2. Small World Graphs

It has been shown that the mixing time of geometrically embedded graphs, such as those representing purely wireless networks, is improved by the addition of sparse random links [19,20]. This results in hybrid models characteristic of small world graphs [12,13,21]. It is of interest to verify empirically that the geographic sampling quality is also improved by varying the randomness-inducing parameters of small world graphs.

For each small world graph, the degree of randomness is determined by the q and α parameters. Higher q indicates the presence of more randomly chosen links, and lower α indicates that those links will cover longer distances.

The spectral gaps for four randomly generated small world graphs are shown in Table1. The graphs are labeled by their p-q-α values. It is noticed that, as expected, larger spectral gaps are obtained by graphs with more random links, q, and longer random link distances, expressed by smaller α values.

For purposes of comparison, contrasting graphs of degrees 12 and 24 were generated in different ways. The 12-degree graphs had p, q, and α of 2-0-0 (all lattice connections, no random connections) and 1-4-0 (4 lattice and 4 random connections for each node). The 24-degree graphs had p, q, and α of 3-0-0 (we note that this case is also a K-grid) and 2-6-0. As is shown in Figure7, the 12-degree graph with more random connections exhibited even higher sampling quality than the 24-degree degree graph with no randomness. We note that the $\alpha =0$ Kleinberg model that we have taken is similar to the Watts-Strogatz small world model and allows us to test the extreme cases of adding random links versus completely geometrically defined links (where $q=0$ ).

Figure 7

Small worlds graphs. A 24-degree graph (red) converges more slowly than a 12- degree graph (light blue) with increased randomness. A high degree does not necessarily guarantee good mixing properties.

5. Conclusion

We have proposed a natural new measure of sampling quality relevant to geographically embedded networks in particular and used our measure to compare what network related factors affect the geographic sampling quality. We have demonstrated use of the rate of decline of the area of the largest empty circle to evaluate the efficiency with which a geographic network can be traversed by a random walk. A high rate of decline was generally correlated with graphs with high spectral gap and low mixing time. However, even for graphs with low mixing time, randomization of node locations while retaining identical connectivity structure also significantly affected the sampling quality. A greater amount of randomness in either node placement or edge connections resulted in a higher quality of sampling from geographic networks.

We compared the quality of sampling of geographic networks by noting the rate of shrinkage of the largest circumscribed circle of the Delaunay triangulation of the sampled points. Various types of networks were used, including completely nonrandom K-grids, node and edge based perturbations of the K-grids, random networks with regular degrees, and small world networks with varying randomness and degrees.

We started by first permuting the node locations and then randomizing the edge connections of the K-grids, to determine the relative effect of node distribution versus edge connectivity on the quality of sampling. The addition of randomness applied either way resulted in a substantially more rapid decrease in the unexplored geographic area compared to the unperturbed K-grids. Generally, the edge randomization resulted in better quality sampling than node randomization, although the differences were not necessarily great. Interestingly, the differences were greater with networks of greater size.

Spectral gap information was calculated for the examined graphs and was shown to correlate with the quality of sampling. As expected, graphs with higher spectral gaps exhibited a faster rate of largest circle decline. This was particularly important with small world graphs. The graphs with the highest amount of randomness, as represented by their q and α parameters, resulted in a better sample that was more quickly obtained via a random walk. And such graphs also had better mixing properties, as expected. In fact, a nonrandom graph of degree 24 performed significantly worse than a randomized small world graph of only degree 12.