1.
Robustness and Vulnerability of Scale-Free Random Graphs - Bollobás, Béla; Riordan, Oliver
Recently many new "scale-free'' random graph models have been introduced,
motivated by the power-law degree sequences observed in many large-scale,
real-world networks. Perhaps the best known, the Barabási-Albert model,
has been extensively studied from heuristic and experimental points of view.
Here we consider mathematically two basic characteristics of a precise version
of this model, the LCD model, namely robustness to random damage, and
vulnerability to malicious attack. We show that the LCD graph is much
more robust than classical random graphs with the same number of edges,
but also more vulnerable to attack. In particular, if vertices of the
n-vertex LCD graph are deleted at random, then as long...
2.
Detecting a Network Failure - Kleinberg, Jon
Measuring the properties of a large, unstructured network
can be difficult: One may not have full knowledge
of the network topology, and detailed
global measurements may be infeasible.
A valuable approach to such problems
is to take measurements from selected locations
within the network and then aggregate them
to infer large-scale properties.
One sees this notion applied in settings that range from
Internet topology discovery tools to
remote software agents that estimate the download times
of popular web pages.
Some of the most basic questions about this type of approach,
however, are largely unresolved at an analytical level.
How reliable are the results?
How much does the choice of measurement locations
affect the aggregate information one...
3.
Crawling on Simple Models of Web Graphs - Cooper, Colin; Frieze, Alan
We consider the problem of searching a randomly growing graph by a random walk. In particular we consider two simple models of "web-graphs." Thus at each time step a new vertex is added and it is connected to the current graph by randomly chosen edges. At the same time a "spider" S makes a number of steps of a random walk on the current graph. The parameter we consider is the expected proportion of vertices that have been visited by S up to time t.
4.
The Average Distance in a Random Graph with Given Expected Degrees - Chung, Fan; Lu, Linyuan
Random graph theory is used to
examine the "small-world phenomenon"---any two strangers are connected
through a short chain of mutual acquaintances.
We will show that
for certain families of
random graphs with given expected degrees, the average distance is
almost surely of order
$\log n / \log \tilde d$ where
$\tilde d$ is the weighted average of the sum of squares of the
expected degrees.
Of particular interest are
power law random graphs in which the number
of
vertices of degree k is proportional to $1/k^{\beta}$ for some fixed
exponent $\beta $. For the case of $\beta > 3$, we prove that
the average distance of
the power law graphs is almost surely of order
$\log n...
5.
Algorithmic Challenges in Web Search Engines - Henzinger, Monika R.
In this paper, we describe six algorithmic problems
that arise in web search engines and that are not or only
partially solved:
(1) Uniformly sampling of web pages; (2) modeling the web graph; (3) finding
duplicate hosts; (4) finding top gainers and losers in data streams; (5) finding large dense bipartite graphs; and (6) understanding
how eigenvectors partition the web.
6.
An Approximate Truthful Mechanism for Combinatorial Auctions with Single Parameter Agents - Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva
Mechanism design seeks algorithms whose inputs are provided by selfish agents who would lie if it were to their advantage. Incentive-compatible mechanisms compel the agents to tell the truth by making it in their self-interest to do so. Often, as in combinatorial auctions, such mechanisms involve the solution of NP-hard problems. Unfortunately, approximation algorithms
typically destroy incentive compatibility. Randomized rounding is a commonly used technique for designing approximation algorithms. We devise a version of randomized rounding that is incentive-compatible, giving a truthful mechanism for combinatorial auctions with single parameter agents (e.g., "single minded bidders'') that approximately maximizes the social value of...
7.
Smaller Explicit Superconcentrators - Alon, N.; Capalbo, M.
Using a new recursive technique, we present an explicit construction of an infinite family of N-superconcentrators of density 44. The most economical previously known explicit graphs of this type have density around 60.
8.
Admission Control to Minimize Rejections - Blum, Avrim; Kalai, Adam; Kleinberg, Jon
Admission control (call control) is a well-studied online problem. We are given a fixed graph with edge capacities, and must process a sequence of calls that arrive over time, accepting some and rejecting others in order to stay within capacity limitations of the network. In the standard theoretical formulation, this problem is analyzed as a benefit problem: The goal is to devise an online algorithm that accepts at least a reasonable fraction of the maximum number of calls that could possibly have been accepted in hindsight. This formulation, however, has the property that even algorithms with optimal competitive ratios (typically...
9.
Guessing Secrets with Inner Product Questions - Chung, Fan; Graham, Ronald; Lu, Linyuan
We suppose we are given some fixed (but unknown) subset X of a set $\Omega = {\mathbb F}_2^n$,
where ${\mathbb F}_2$ denotes the field of two elements. Our goal is to learn as much as possible about the elements of X by asking certain binary questions. Each "question" Q is just some element of $\Omega$, and the "answer" to Q is just the inner product $Q \cdot x \in {\mathbb F}_2$ for {\it some} $x \in X$. However, the choice of x is made by a truthful (but possibly malevolent) adversary A, whom we may assume is trying to choose answers...
10.
Infinite Limits of Copying Models of the Web Graph - Bonato, Anthony; Janssen, Jeanette
Several stochastic models were proposed recently to model the dynamic evolution of the web graph. We study the infinite limits of the stochastic processes proposed to model the web graph when time goes to infinity. We prove that deterministic variations of the so-called copying model can lead to several nonisomorphic limits. Some models converge to the infinite random graph R, while the convergence of other models is sensitive to initial conditions or minor changes in the rules of the model. We explain how limits of the copying model of the web graph share several properties with R that seem to...
11.
Coupling Scale-Free and Classical Random Graphs - Bollobás, Béla; Riordan, Oliver
Recently many new "scale-free'' random graph models have been introduced, motivated by the power-law degree sequences observed in many large-scale real-world networks. The most studied of these is the Barabási-Albert growth with "preferential attachment'' model, made precise as the LCD model by the present authors. Here we use coupling techniques to show that in certain ways the LCD model is not too far from a standard random graph; in particular, the fractions of vertices that must be retained under an optimal attack in order to keep a giant component are within a constant factor for the scale-free and classical
models.
12.
A Brief History of Generative Models for Power Law and Lognormal Distributions - Mitzenmacher, Michael
Recently, I became interested in a current debate over whether file size distributions are best modelled by a power law distribution or a lognormal distribution. In trying to learn enough about these distributions to settle the question, I found a rich and long history, spanning many fields. Indeed, several recently proposed models from the computer science community have antecedents in work from decades ago. Here, I briefly survey some of this history, focusing on underlying generative models that lead to these distributions. One finding is that lognormal and power law distributions connect quite naturally, and hence, it is not surprising...
13.
The Spectra of Random Graphs with Given Expected Degrees - Chung, Fan; Lu, Linyuan; Vu, Van
In the study of the spectra of power law graphs, there are basically two competing approaches. One is to prove analogues of
Wigner's semicircle law while the other predicts that the eigenvalues follow a power law distributions. Although the semicircle law and the power law have nothing in common, we will show that both approaches are essentially correct if one considers the appropriate matrices. We will show that (under certain conditions) the eigenvalues of the (normalized) Laplacian of a random power law graph follow the semicircle law while the spectrum of the adjacency matrix of a power law graph obeys the...
14.
Link Evolutions: Analysis and Algorithms - Chien, Steve; Dwork, Cynthia; Kumar, Ravi; Simon, Daniel R.; Sivakumar, D.
We anticipate that future web search techniques will exploit changes in web structure and content. As a first step in this direction, we examine the problem of integrating observed changes in link structure into static hyperlink-based ranking computations
¶ We present a very efficient algorithm to incrementally compute good approximations to Google's PageRank [Brin and Page 98], as links evolve. Our experiments reveal that this algorithm is both fast and yields excellent approximations to PageRank, even in light of large changes to the link structure
¶ Our algorithm derives intuition and partial justification from a rigorous sensitivity analysis of Markov chains. Consider...
15.
Dynamic Models for File Sizes and Double Pareto Distributions - Mitzenmacher, Michael
In this paper, we introduce and analyze a new, dynamic generative user model to explain the behavior of file size distributions. Our Recursive Forest File model combines multiplicative models that generate lognormal distributions with recent work on random graph models for the web. Unlike similar previous work, our Recursive Forest File model allows new files to be created and old files to be deleted over time, and our analysis covers problematic issues such as correlation among file sizes. Moreover, our model allows natural variations where files that are copied or modified are more likely to be copied or modified subsequently.
¶...
16.
Deeper Inside PageRank - Langville, Amy N.; Meyer, Carl D.
This paper serves as a companion or extension to the "Inside PageRank'' paper by Bianchini et al. It is a comprehensive survey of all issues associated with PageRank, covering the basic PageRank model, available and recommended solution methods, storage issues, existence, uniqueness, and convergence properties, possible alterations to the basic model, suggested alternatives to the traditional solution methods, sensitivity and conditioning, and finally the updating problem. We introduce a few new results, provide an extensive reference list, and speculate about exciting areas of future research.
17.
Graph Clustering and Minimum Cut Trees - Flake, Gary William; Tarjan, Robert E.; Tsioutsiouliklis, Kostas
In this paper, we introduce simple graph clustering methods based on minimum cuts within the graph. The clustering methods are general enough to apply to any kind of graph but are well suited for graphs where the link structure implies a notion of reference, similarity, or endorsement, such as web and citation graphs. We show that the quality of the produced clusters is bounded by strong minimum cut and expansion criteria. We also develop a framework for hierarchical clustering and present applications to real-world data. We conclude that the clustering algorithms satisfy strong theoretical criteria and perform well in practice.
18.
Coupling Online and Offline Analyses for Randome Power Law Graphs - Chung, Fan; Lu, Linyuan
We develop a coupling technique for analyzing online models by using offline models. This method is especially effective for
a growth-deletion model that generalizes and includes the preferential attachment model for generating large complex networks which simulate numerous realistic networks. By coupling the online model with the offline model for random power law graphs, we derive strong bounds for a number of graph properties including diameter, average distances, connected components, and spectral bounds. For example, we prove that a power law graph generated by the growth-deletion model almost surely has diameter $ O(\log n)$ and average distance $ O(\log \log n)$.
19.
Random Deletion in a Scale-Free Random Graph Process - Cooper, Colin; Frieze, Alan; Vera, Juan
We study a dynamically evolving random graph which adds vertices and edges using preferential attachment and deletes vertices randomly. At time $t$, with probability $\a_1>0$ we add a new vertex $u_t$ and $m$ random edges incident with $u_t$. The neighbours of $u_t$ are chosen with probability proportional to degree. With probability $\a-\a_1\geq 0$ we add $m$ random edges to existing
vertices where the endpoints are chosen with probability proportional to degree. With probability $1-\a-\a_0$ we delete a random vertex, if there are vertices left to delete. With probability $\a_0$ we delete $m$ random edges. Assuming that $\a+\a_1+\a_0>1$ and $\a_0$ is sufficently...
20.
Network Applications of Bloom Filters: A Survey - Broder, Andrei; Mitzenmacher, Michael
A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters allow false positives but the space savings often outweigh this drawback when the probability of an error is controlled. Bloom filters have been used in database applications since the 1970s, but only in recent years have they become popular in the networking
literature. The aim of this paper is to survey the ways in which Bloom filters have been used and modified in a variety of network problems, with the aim of providing a unified mathematical and practical framework...
1.
