The degree distribution is one of the most fundamental properties used in the analysis of massive graphs. There is a large literature on graph sampling, where the goal is to estimate properties (especially the degree distribution) of a large graph through a small, random sample. The degree distribution estimation poses a significant challenge, due to its heavy-tailed nature and the large variance in degrees. We design a new algorithm, SADDLES, for this problem, using recent mathematical techniques from the field of sublinear algorithms. The SADDLES algorithm gives provably accurate outputs for all values of the degree distribution. For the analysis, we define two fatness measures of the degree distribution, called the h-index and the z-index. We prove that SADDLES is sublinear in the graph size when these indices are large. A corollary of this result is a provably sublinear algorithm for any degree distribution bounded below by a power law. We deploy our new algorithm on a variety of real datasets and demonstrate its excellent empirical behavior. In all instances, we get extremely accurate approximations for all values in the degree distribution by observing at most 1 of the vertices. This is a major improvement over the state-of-the-art sampling algorithms, which typically sample more than 10 of the vertices to give comparable results. We also observe that the h and z-indices of real graphs are large, validating our theoretical analysis.
On the practical side, Dasgupta, Kumar, and Sarlos study average degree estimation in real graphs, and develop alternate algorithms @cite_13 . They require the graph to have low mixing time and demonstrate that the algorithm has excellent behavior in practice (compared to implementations of Feige's and the Goldreich-Ron algorithm @cite_21 @cite_28 ). note that sampling uniform random vertices is not possible in many settings, and thus they consider a significantly weaker setting than SM or HDM. focus on sampling uniform random vertices, using only a small set of seed vertices and neighbor queries @cite_37 .
@cite_28 @cite_37 @cite_21 @cite_13
2012438382 2336754337 2121707217 2075709248
Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 Supported by Israel Internet Association (ISOC-IL). This article is dedicated in memory of Shimon Even (1935–2004). Random walk is an important tool in many graph mining applications including estimating graph parameters, sampling portions of the graph, and extracting dense communities. In this paper we consider the problem of sampling nodes from a large graph according to a prescribed distribution by using random walk as the basic primitive. Our goal is to obtain algorithms that make a small number of queries to the graph but output a node that is sampled according to the prescribed distribution. Focusing on the uniform distribution case, we study the query complexity of three algorithms and show a near-tight bound expressed in terms of the parameters of the graph such as average degree and the mixing time. Both theoretically and empirically, we show that some algorithms are preferable in practice than the others. We also extend our study to the problem of sampling nodes according to some polynomial function of their degrees; this has implications for designing efficient algorithms for applications such as triangle counting. We prove the following inequality: for every positive integer n and every collection X 1 ,..., X n of nonnegative independent random variables that each has expectation 1, the probability that their sum remains below n+1 is at least α > 0. Our proof produces a value of α = 1 13 ≅ 0.077, but we conjecture that the inequality also holds with α = 1 e ≅ 0.368.As an example for the use of the new inequality, we consider the problem of estimating the average degree of a graph by querying the degrees of some of its vertices. We show the following threshold behavior: approximation factors above 2 require far less queries than approximation factors below 2. The new inequality is used in order to get tight (up to multiplicative constant factors) relations between the number of queries and the quality of the approximation. We show how the degree approximation algorithm can be used in order to quickly find those edges in a network that belong to many shortest paths. Networks are characterized by nodes and edges. While there has been a spate of recent work on estimating the number of nodes in a network, the edge-estimation question appears to be largely unaddressed. In this work we consider the problem of estimating the average degree of a large network using efficient random sampling, where the number of nodes is not known to the algorithm. We propose a new estimator for this problem that relies on access to node samples under a prescribed distribution. Next, we show how to efficiently realize this ideal estimator in a random walk setting. Our estimator has a natural and simple implementation using random walks; we bound its performance in terms of the mixing time of the underlying graph. We then show that our estimators are both provably and practically better than many natural estimators for the problem. Our work contrasts with existing theoretical work on estimating average degree, which assume that a uniform random sample of nodes is available and the number of nodes is known.