Very large graphs

MaRDI QIDQ3645674zbMATH OpenFDO

Authors László Lovász

Publication date 18 November 2009

Full work available at URL https://arxiv.org/abs/0902.0132, https://projecteuclid.org/euclid.cdm/1254748656

zbMATH Keywords

dense graphsgraphonneighborhood samplingproperty testingsparse graphssubgraph samplingvery large finite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Internet topics (68M11) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Abstract: In the last decade it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks: separable elements, with connections (or interactions) between certain pairs of them. These huge networks pose exciting challenges for the mathematician. Graph Theory (the mathematical theory of networks) faces novel, unconventional problems: these very large networks (like the Internet) are never completely known, in most cases they are not even well defined. Data about them can be collected only by indirect means like random local sampling. Dense networks (in which a node is adjacent to a positive percent of others nodes) and sparse networks (in which a node has a bounded number of neighbors) show very different behavior. From a practical point of view, sparse networks are more important, but at present we have more complete theoretical results for dense networks. The paper surveys relations with probability, algebra, extrema graph theory, and analysis.

Recommendations

• scientific article; zbMATH DE number 1792102
• scientific article; zbMATH DE number 1241385
• scientific article; zbMATH DE number 1559556
• Testing properties of graphs and functions
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing

Cited in

(32)

• Reciprocity in directed networks
• Extremal graph theory and finite forcibility
• Testing goodness of fit of random graph models
• On finding common neighborhoods in massive graphs.
• The analytic evolution of Dyson-Schwinger equations via homomorphism densities
• Edgeworth expansions for network moments
• Bootstrapping exchangeable random graphs
• Non-perturbative graph languages, halting problem and complexity
• Replica symmetry in upper tails of mean-field hypergraphs
• The dynamics of non-perturbative phases via Banach bundles
• Asymptotic structure of constrained exponential random graph models
• Asymptotics of visibility in the hyperbolic plane
• Emergent structures in large networks
• The number of cliques in graphs of given order and size
• A deterministic algorithm for the Frieze-Kannan regularity lemma
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Implementing Huge Sparse Random Graphs
• On an anti-Ramsey threshold for random graphs
• scientific article; zbMATH DE number 1792102 (Why is no real title available?)
• MegaMenger Graphs
• An equation-free approach to coarse-graining the dynamics of networks
• Asymptotic structure and singularities in constrained directed graphs
• Large-scale graph generation and big data: an overview on recent results
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Finitely forcible graphons with an almost arbitrary structure
• Analytic representations of large graphs
• On the phase transition curve in a directed exponential random graph model
• Graphs with many large degrees
• An approximate version of Sidorenko's conjecture
• A sharp lower bound for the number of mappings of a linear graph into an arbitrary graph and an inequality of A. F. Sidorenko
• An analytic approach to stability
• Matrix and discrepancy view of generalized random and quasirandom graphs

This page was built for publication: Very large graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3645674)