({{, (RefLink[BernoulliGraphDistribution, paclet:ref/BernoulliGraphDistribution])[n,p] 
represents a Bernoulli graph distribution for n-vertex graphs with edge probability p.}})

OpenersNotesSection(Spacer1)Details and Options

The Bernoulli graph is constructed starting with the complete graph with n vertices and selecting each edge independently through a Bernoulli trial with probability p.

The following options can be given:

(RefLink[BernoulliGraphDistribution, paclet:ref/BernoulliGraphDistribution]) can be used with such functions as (RefLink[RandomGraph, paclet:ref/RandomGraph]) and (RefLink[GraphPropertyDistribution, paclet:ref/GraphPropertyDistribution]).

OpenersPrimaryExamplesSection(Spacer1)Examples  (18)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Generate a pseudorandom graph:

RandomGraph[BernoulliGraphDistribution[10,0.6]]

Distribution of the number of edges:

𝒟[n_,p_]=GraphPropertyDistribution[EdgeCount[g],g\[Distributed]BernoulliGraphDistribution[n,p]]

Probability density function:

PDF[𝒟[n,p],m]

DiscretePlot[Evaluate @ Table[PDF[𝒟[n,1/2],m],{n,3,12,3}],{m,0,50},PlotRange->All,ExtentSize->1/2]

OpenersExampleSection1(Spacer1)Scope  (4)

Generate simple undirected graphs:

RandomGraph[BernoulliGraphDistribution[5,0.6]]

Simple directed graphs:

RandomGraph[BernoulliGraphDistribution[5,0.6,DirectedEdges->True]]

Generate a set of pseudorandom graphs:

RandomGraph[BernoulliGraphDistribution[5,0.8],4]

Compute probabilities and statistical properties:

𝒟=GraphPropertyDistribution[GlobalClusteringCoefficient[g],g\[Distributed]BernoulliGraphDistribution[5,0.4]];

N[Mean[𝒟]]

OpenersExampleSection2(Spacer1)Options  (2)

OpenersExampleSubsection0(Spacer1)DirectedEdges  (2)

By default, a Bernoulli graph is undirected:

RandomGraph[BernoulliGraphDistribution[10,0.3]]

UndirectedGraphQ[%]

With the setting (RefLink[DirectedEdges, paclet:ref/DirectedEdges])->(RefLink[True, paclet:ref/True]), directed Bernoulli graphs are generated:

RandomGraph[BernoulliGraphDistribution[10,0.3,DirectedEdges->True]]

DirectedGraphQ[%]

OpenersExampleSection3(Spacer1)Applications  (3)

After 20 children have spent their first week in kindergarten, the probability that two children have made friends is 0.2:

𝒢=BernoulliGraphDistribution[20,0.2];

RandomGraph[𝒢]

Find the probability that the social network is connected:

NProbability[x==1,x\[Distributed]GraphPropertyDistribution[Boole[ConnectedGraphQ[g]],g\[Distributed]𝒢]]

In a snowball fight with 15 participants, and everybody throwing snowballs at everyone else, the probability of being hit by any given participant is 0.4:

𝒢=BernoulliGraphDistribution[15,0.4,DirectedEdges->True];

RandomGraph[𝒢]

Find the size of the largest group where everybody has been hit by everyone else:

Length[First[FindClique[%]]]

Find the largest component fraction when the mean vertex degree is β:

𝒟[n_,β_]:=GraphPropertyDistribution[Length[First[ConnectedComponents[g]]]/n,g\[Distributed]BernoulliGraphDistribution[n,β/(n-1)]]

Table[RandomVariate[𝒟[10,β]],{β,0,3}]

Average the result over 100 runs and plot it for different numbers of vertices:

Table[Plot[Mean[RandomVariate[𝒟[10,β],100]],{β,0,3},MaxRecursion->2,PlotLabel->n],{n,{10,100}}]

OpenersExampleSection4(Spacer1)Properties & Relations  (6)

Distribution of the number of vertices:

GraphPropertyDistribution[VertexCount[g],g\[Distributed]BernoulliGraphDistribution[n,p]]

Distribution of the number of edges:

𝒟[n_,p_]=GraphPropertyDistribution[EdgeCount[g],g\[Distributed]BernoulliGraphDistribution[n,p]]

Probability density function:

PDF[𝒟[n,p],m]

DiscretePlot[Evaluate @ Table[PDF[𝒟[n,0.4],x],{n,3,12,3}],{x,0,40},PlotRange->All,ExtentSize->1/2]

The mean of the number of edges:

Mean[𝒟[n,p]]

Distribution of the degree of a vertex:

𝒟[n_,p_]=GraphPropertyDistribution[VertexDegree[g,v],g\[Distributed]BernoulliGraphDistribution[n,p]]

Probability density function:

PDF[𝒟[n,p],k]

DiscretePlot[Evaluate @ Table[PDF[𝒟[n,0.3],x],{n,5,50,15}],{x,0,25},PlotRange->All,ExtentSize->1/2]

The mean of the degree of a vertex:

Mean[𝒟[n,p]]

Connectivity for large n with respect to p:

𝒟[n_,p_]:=GraphPropertyDistribution[Boole[ConnectedGraphQ[g]],g\[Distributed]BernoulliGraphDistribution[n,p]]

A Bernoulli graph is almost surely disconnected for n p<log(n):

NProbability[x==0,x\[Distributed]𝒟[500,0.01],Method->{"MonteCarlo",PrecisionGoal->1}]

A Bernoulli graph is almost surely connected for n p>log(n):

NProbability[x==1,x\[Distributed]𝒟[500,0.02],Method->{"MonteCarlo",PrecisionGoal->1}]

Use (RefLink[BernoulliDistribution, paclet:ref/BernoulliDistribution]) to simulate a (RefLink[BernoulliGraphDistribution, paclet:ref/BernoulliGraphDistribution]):

bernoulli[n_,p_]:=
Graph[Range[n],Pick[EdgeList[CompleteGraph[n]],
RandomVariate[BernoulliDistribution[p],n(n-1)/2],1]]

Pseudorandom graphs:

Table[bernoulli[10,p],{p,0.3,1,0.2}]

Edge probability 1 results in the (RefLink[CompleteGraph, paclet:ref/CompleteGraph]):

RandomGraph[BernoulliGraphDistribution[5,1]]

CompleteGraphQ[%]

Edge probability 0 results in the empty graph:

RandomGraph[BernoulliGraphDistribution[5,0]]

EmptyGraphQ[%]

OpenersExampleSection5(Spacer1)Neat Examples  (1)

Randomly colored vertices:

HighlightGraph[RandomGraph[BernoulliGraphDistribution[10^2,0.03]],Table[Style[i,RandomChoice[ColorData[45,"ColorList"]]],{i,10^2}]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[UniformGraphDistribution, paclet:ref/UniformGraphDistribution])  ▪  (RefLink[BarabasiAlbertGraphDistribution, paclet:ref/BarabasiAlbertGraphDistribution])  ▪  (RefLink[PriceGraphDistribution, paclet:ref/PriceGraphDistribution])  ▪  (RefLink[DegreeGraphDistribution, paclet:ref/DegreeGraphDistribution])  ▪  (RefLink[WattsStrogatzGraphDistribution, paclet:ref/WattsStrogatzGraphDistribution])  ▪  (RefLink[BinomialDistribution, paclet:ref/BinomialDistribution])  ▪  (RefLink[PoissonDistribution, paclet:ref/PoissonDistribution])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Random Graphs, paclet:guide/RandomGraphs])}, {▪(RefLinkPlain[Social Network Analysis, paclet:guide/SocialNetworks])}, {▪(RefLinkPlain[Derived Statistical Distributions, paclet:guide/DerivedDistributions])}})}})