Graphon (original) (raw)
In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs. (en) En théorie des graphes et en statistique, un graphon (aussi connu sous le terme limite de graphes) est une fonction symétrique mesurable , qui joue un rôle important dans l'étude des graphes denses. Les graphons sont à la fois une notion naturelle de limite d'une suite de graphes denses, et sont aussi les objets fondamentaux dans la définition des modèles de graphes aléatoires échangeables Les graphons sont liés aux graphes denses par la paire d'observations suivante : les modèles aléatoires définis par les graphes donnent lieu à des graphes denses presque sûrement et, par le lemme de régularité de Szemerédi, les graphes capturent la structure de graphes denses arbitraires grands. (fr) Графон — модель случайного графа, обобщение модели Эрдеша — Реньи.Графоны возникают естественным образом при изучении предельного поведения последовательности графов. (ru) 图极限（graphon），或称图极限函数（graphon function），是用统计网络分析中，用以描述一类具有顶点可交换性结构的图之结构的二元函数。概念上，图极限函数可以被理解为一个内在结构恒定的随机图，在顶点数趋于无穷时所收敛到的极限（假定其顶点已按恰当的次序排列）。 图极限函数为描述随机图的结构和渐近性质提供了基础工具，对图极限的估计和统计推断，是近年来统计网络分析的前沿课题之一。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Exchangeable_random_graph_from_graphon.png?width=300 |
| dbo:wikiPageID | 26987628 (xsd:integer) |
| dbo:wikiPageLength | 33776 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124367471 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Dense_graph dbr:Almost_surely dbr:Invariant_measure dbr:Limit_of_a_sequence dbr:Compact_space dbr:Complete_bipartite_graph dbr:Convergence_of_random_variables dbr:Measurable dbr:Graph_homomorphism dbr:Lp_space dbr:Statistics dbr:Complete_metric_space dbr:Dense_set dbr:Half_graph dbc:Probability_theory dbr:Adjacency_matrix dbr:Fan_Chung dbr:Cauchy_sequence dbr:Discrepancy_theory dbr:Graph_edit_distance dbr:Graph_theory dbr:Graphon dbr:Quotient_space_(topology) dbr:Random_variable dbr:Szemerédi_regularity_lemma dbc:Graph_theory dbr:Homomorphism_density dbr:Metric_space dbr:Stochastic_block_model dbr:Symmetric_function dbr:Extremal_graph_theory dbr:Metric_(mathematics) dbr:Exchangeable_random_variables dbr:Erdős–Rényi dbr:De_Finetti’s_representation_theorem dbr:Aldous–Hoover_theorem dbr:File:Exchangeable_random_graph_from_graphon.png dbr:Projective_(probability) |
| dbp:wikiPageUsesTemplate | dbt:Main dbt:R |
| dct:subject | dbc:Probability_theory dbc:Graph_theory |
| rdfs:comment | In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs. (en) Графон — модель случайного графа, обобщение модели Эрдеша — Реньи.Графоны возникают естественным образом при изучении предельного поведения последовательности графов. (ru) 图极限（graphon），或称图极限函数（graphon function），是用统计网络分析中，用以描述一类具有顶点可交换性结构的图之结构的二元函数。概念上，图极限函数可以被理解为一个内在结构恒定的随机图，在顶点数趋于无穷时所收敛到的极限（假定其顶点已按恰当的次序排列）。 图极限函数为描述随机图的结构和渐近性质提供了基础工具，对图极限的估计和统计推断，是近年来统计网络分析的前沿课题之一。 (zh) En théorie des graphes et en statistique, un graphon (aussi connu sous le terme limite de graphes) est une fonction symétrique mesurable , qui joue un rôle important dans l'étude des graphes denses. Les graphons sont à la fois une notion naturelle de limite d'une suite de graphes denses, et sont aussi les objets fondamentaux dans la définition des modèles de graphes aléatoires échangeables (fr) |
| rdfs:label | Graphon (en) Graphon (fr) Графон (теория графов) (ru) 图极限 (zh) |
| owl:sameAs | freebase:Graphon wikidata:Graphon dbpedia-fr:Graphon dbpedia-ru:Graphon dbpedia-zh:Graphon https://global.dbpedia.org/id/4iK7z |
| prov:wasDerivedFrom | wikipedia-en:Graphon?oldid=1124367471&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Exchangeable_random_graph_from_graphon.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Graphon |
| is dbo:wikiPageRedirects of | dbr:Cut_distance dbr:Graph_limit dbr:Graph_limits dbr:Borel_graph dbr:Analytic_graph dbr:Continuous_graph |
| is dbo:wikiPageWikiLink of | dbr:Algebraic_signal_processing dbr:List_of_graph_theory_topics dbr:Quasirandom_group dbr:Common_graph dbr:Cut_distance dbr:Forcing_graph dbr:Nina_Holden dbr:Graphon dbr:Szemerédi_regularity_lemma dbr:Counting_lemma dbr:Katalin_Vesztergombi dbr:Homomorphism_density dbr:Sofia_Olhede dbr:Grothendieck_inequality dbr:Graph_limit dbr:Graph_limits dbr:Christian_Borgs dbr:Extremal_graph_theory dbr:Turán's_theorem dbr:Sidorenko's_conjecture dbr:Borel_graph dbr:Analytic_graph dbr:Continuous_graph |
| is foaf:primaryTopic of | wikipedia-en:Graphon |
