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

graphonsparse graphsproperty testingdense graphsneighborhood samplingsubgraph samplingvery large finite graphs

Mathematics Subject Classification ID

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

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)

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

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)