UniformGraphDistribution
represents a uniform graph distribution on n-vertex, m-edge graphs.
Details and Options
- The sample space is all simple graphs on n vertices and m edges.
- The following options can be given:
-
DirectedEdges False whether to generate directed edges - UniformGraphDistribution can be used with such functions as RandomGraph and GraphPropertyDistribution.
Examples
open all close allBasic Examples (2)
Generate a pseudorandom graph:
RandomGraph[UniformGraphDistribution[5, 6]]Probability density functions of the degree of a vertex:
𝒟[n_, m_] := GraphPropertyDistribution[VertexDegree[g, v], gUniformGraphDistribution[n, m]]DiscretePlot[Evaluate @ Table[PDF[𝒟[40, m], x], {m, 10, 780, 152}], {x, 0, 40}, PlotRange -> All, ExtentSize -> 1 / 2]Scope (4)
Generate simple undirected graphs:
RandomGraph[UniformGraphDistribution[5, 6]]RandomGraph[UniformGraphDistribution[5, 6, DirectedEdges -> True]]Generate a set of pseudorandom graphs:
RandomGraph[UniformGraphDistribution[5, 7], 4]Compute probabilities and statistical properties:
𝒟 = GraphPropertyDistribution[VertexDegree[g, 1], gUniformGraphDistribution[5, 7]];Expectation[x ^ 2, x𝒟]Options (2)
DirectedEdges (2)
By default, undirected graphs are generated:
RandomGraph[UniformGraphDistribution[10, 20]]UndirectedGraphQ[%]Use DirectedEdges->True to generate directed graphs:
RandomGraph[UniformGraphDistribution[10, 20, DirectedEdges -> True]]DirectedGraphQ[%]Applications (2)
On a duet night at the karaoke club, 85 songs are performed by 40 guests selected randomly. Find the expected number of people who sang at least 3 songs:
𝒢 = UniformGraphDistribution[40, 85];f[g_] := Count[VertexDegree[g], d_ /; d ≥ 3]NExpectation[x, xGraphPropertyDistribution[f[g], g𝒢]]Find the largest component fraction when the mean vertex degree is approximately 
:
𝒟[n_, β_] := GraphPropertyDistribution[Length[First[ConnectedComponents[g]]] / n, gUniformGraphDistribution[n, ⌈β n / 2⌉]]Table[RandomVariate[𝒟[10, β]], {β, 0, 3}]Average the result over 100 runs and plot it for different numbers of vertices:
Table[Plot[Mean[RandomVariate[𝒟[n, β], 100]], {β, 0, 3}, MaxRecursion -> 2, PlotLabel -> n], {n, {10, 100}}]Properties & Relations (4)
Distribution of the number of vertices:
𝒟[n_, m_] = GraphPropertyDistribution[VertexCount[g], gUniformGraphDistribution[n, m]]Distribution of the number of edges:
𝒟[n_, m_] = GraphPropertyDistribution[EdgeCount[g], gUniformGraphDistribution[n, m]]Distribution of the degree of a vertex:
𝒟[n_, m_] = GraphPropertyDistribution[VertexDegree[g, v], gUniformGraphDistribution[n, m]]DiscretePlot[Evaluate @ Table[PDF[𝒟[40, m], x], {m, 10, 780, 152}], {x, 0, 40}, PlotRange -> All, ExtentSize -> 1 / 2]The mean vertex degree is 2m/n:
Mean[𝒟[10, 30]] == 2 30 / 10Use RandomSample to simulate a UniformGraphDistribution:
uniform[n_, m_] :=
Graph[Range[n], RandomSample[EdgeList[CompleteGraph[n]], m]]uniform[7, 10]Text
Wolfram Research (2010), UniformGraphDistribution, Wolfram Language function, https://reference.wolfram.com/language/ref/UniformGraphDistribution.html.
CMS
Wolfram Language. 2010. "UniformGraphDistribution." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/UniformGraphDistribution.html.
APA
Wolfram Language. (2010). UniformGraphDistribution. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/UniformGraphDistribution.html