Article Free Access Share on A random graph model for massive graphs Authors: William Aiello AT&T Labs, Florham Park, New Jersey JerseyView Profile , Fan Chung University of California, San Diego DiegoView Linyuan Lu Authors Info & Claims STOC '00: Proceedings the thirty-second annual ACM symposium Theory computingMay 2000 Pages 171–180https://doi.org/10.1145/335305.335326Published:01 May 2000Publication History 511citation3,291DownloadsMetricsTotal Citations511Total Downloads3,291Last 12...

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 random graphs with given expected degrees average distance almost surely order log nlog d, where d weighted sum squares degrees. Of particular interest power law in which number vertices degree k proportional 1kbeta some fixed exponent beta. For case beta > 3, we prove d. However, many Internet, social, and...

In the study of spectra power-law graphs, there are basically two competing approaches. One is to prove analogues Wigner's semicircle law, whereas other predicts that eigenvalues follow a distribution. Although law and power have nothing in common, we will show both approaches essentially correct if one considers appropriate matrices. We (under certain mild conditions) (normalized) Laplacian random graph spectrum adjacency matrix obeys law. Our results based on analysis graphs with given...

We examine a number of generalized and extended versions concentration inequalities martingale inequalities. These are effective for analyzing processes with quite general conditions as illustrated in an example infinite Polya process web graphs.

We propose a random graph model which is special case of sparserandom graphs with given degree sequences satisfy power law. This involves only small number paramo eters, called logsize and log-log growth rate. These parameters capture some universal characteristics massive graphs. From these parameters, various properties the can be derived. For example, for certai n ranges we wi II compute expected distribution sizes connected components almost surely occur high probability. illustrate...

We modify the definition of Ricci curvature Ollivier Markov chains on graphs to study properties general graphs, Cartesian product random and some special class graphs.

Are biological networks different from other large complex networks? Both and nonbiological exhibit power-law graphs (number of nodes with degree k, N(k)~k-β), yet the exponents, β, fall into ranges. This may be because duplication information in genome is a dominant evolutionary force shaping (like gene regulatory protein-protein interaction networks) fundamentally mechanisms thought to dominate growth most (such as Internet). The preferential choice models used for like web can only...

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 random graphs with given expected degrees, average distance almost surely order log _n_/ log_d̃_ where _d̃_ weighted sum squares degrees. Of particular interest power law in which number vertices degree _k_ proportional 1/_k_^β some fixed exponent _β_. For case _β_ > 3, we prove _d̃_. However, many...

In the study of spectra power law graphs, there are basically two competing approaches. One is to prove analogues Wigner's semicircle while other predicts that eigenvalues follow a distributions. Although and have nothing in common, we will show both approaches essentially correct if one considers appropriate matrices. We (under certain conditions) (normalized) Laplacian random graph spectrum adjacency matrix obeys law. Our results based on analysis graphs with given expected degrees their...

Many massive graphs (such as the WWW graph and Call graphs) share certain universal characteristics which can be described by so-called "power law." In this paper, we, examine three important aspects of power law graphs, (1) evolution (2) asymmetry in-degrees out-degrees, (3) "scale invariance" graphs. particular, we give increasingly general directed models one undirected model for generating adding at most node possibly or more edges a time. We show that any given edge density desired laws...

Abstract Meyniel conjectured that the cop number c ( G ) of any connected graph on n vertices is at most for some constant C . In this article, we prove Meyniel's conjecture in special cases has diameter 2 or a bipartite 3. For general graphs, , improving best previously known upper‐bound O / ln due to Chiniforooshan.

We develop a coupling technique for analyzing online models by using offline models. This method is especially effective growth-deletion model that generalizes and includes the preferential attachment generating large complex networks which simulate numerous realistic networks. By with random power law graphs, we derive strong bounds number of graph properties including diameter, average distances, connected components, spectral bounds. For example, prove generated almost surely has diameter...

We consider the random graph model $G(\mathbf{w})$ for a given expected degree sequence ${\mathbf w} =(w_1, w_2, \ldots, w_n)$. If average is strictly greater than 1, then almost surely giant component in G of $G({\mathbf w})$ has volume (i.e., sum weights vertices component) equal to $\lambda_0 {\rm Vol}(G) + O(\sqrt{n}\log^{3.5} n)$, where $\lambda_0$ unique nonzero root equation \[ \sum_{i=1}^n w_i e^{-w_i\lambda} = (1-\lambda) w_i, \] and ${\rm Vol}(G)=\sum_i w_i.$

Let ⊂ 2 [ n ] be a family of subsets {1, 2,. . ., }. For any poset H , we say is -free if does not contain subposet isomorphic to Katona and others have investigated the behaviour La( ), which denotes maximum size families Here use new approach, apply methods from extremal graph theory probability identify classes posets for ) can determined asymptotically as → ∞ various including two-end-forks, up-down trees, cycles C 4 k on two levels.

Let $G$ be a random graph on the vertex set $\{1,2,\ldots, n\}$ such that edges in are determined by independent indicator variables, while probabilities $p_{ij}$ for $\{i,j\}$ being an edge not assumed to equal. Spectra of adjacency matrix and normalized Laplacian recently studied Oliveira Chung-Radcliffe. $A$ $G$, $\bar A={\rm E}(A)$, $\Delta$ maximum expected degree $G$. first proved asymptotically almost surely $\|A-\bar A\|=O(\sqrt{\Delta \ln n})$ provided $\Delta\geq C n$ some constant...