({{, (RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency])[g] 
gives the link efficiency of the graph g.}, {, (RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency])[{v->w,…}]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details

Measures how tightly connected the graph g is in relation to its number of edges.

(RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency])[g] uses the underlying simple graph of g. For a simple unweighted graph, (RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency])[g] is given by 1-(RefLink[MeanGraphDistance, paclet:ref/MeanGraphDistance])[g]/(RefLink[EdgeCount, paclet:ref/EdgeCount])[g].

OpenersPrimaryExamplesSection(Spacer1)Examples  (14)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Find the link efficiency in the graph:

GraphLinkEfficiency[]

Graph link efficiency distribution of the Watts–Strogatz graph model:

𝒟=GraphPropertyDistribution[GraphLinkEfficiency[g],g\[Distributed]WattsStrogatzGraphDistribution[50,0.1,3]];

Histogram[RandomVariate[𝒟,1000]]

OpenersExampleSection1(Spacer1)Scope  (4)

(RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency]) works with undirected graphs:

GraphLinkEfficiency[]

Directed graphs:

GraphLinkEfficiency[]

Use rules to specify the graph:

GraphLinkEfficiency[{1->2,2->3,3->1,3->4,4->5,3->5,5->2}]

(RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency]) works with large graphs:

g=GridGraph[{10,10,10,10}];

GraphLinkEfficiency[g]//Timing

OpenersExampleSection3(Spacer1)Applications  (2)

Find how tightly connected the overground line of the London Underground is with respect to the number of lines between stations:

N[GraphLinkEfficiency[]]

Analyze the distribution of link efficiency in the Watts–Strogatz graph model:

𝒢=WattsStrogatzGraphDistribution[50,0.1,3];

RandomGraph[𝒢]

Distribution of link efficiency:

𝒟=GraphPropertyDistribution[GraphLinkEfficiency[g],g\[Distributed]𝒢];

Histogram[RandomVariate[𝒟,1000]]

Expected value:

NExpectation[x,x\[Distributed]𝒟]

OpenersExampleSection4(Spacer1)Properties & Relations  (5)

(RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency]) is related to (RefLink[MeanGraphDistance, paclet:ref/MeanGraphDistance]):

g=KnightTourGraph[7,4]

GraphLinkEfficiency[g]

1-MeanGraphDistance[g]/EdgeCount[g]

The (RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency]) is always less than 1:

N[GraphLinkEfficiency[RandomGraph[{10,20}]]]

The (RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency]) of a complete graph is close to 1:

g=CompleteGraph[9]

N[GraphLinkEfficiency[g]]

Test if a graph is complete using (RefLink[CompleteGraphQ, paclet:ref/CompleteGraphQ]):

CompleteGraphQ[g]

The (RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency]) of a path graph of length 1 is 0:

PathGraph[Range[2]]

GraphLinkEfficiency[%]

The (RefLink[GraphLinkEfficiency, paclet:ref/GraphLinkEfficiency]) of a disconnected graph is -∞:

graphs={Graph[{1\[DirectedEdge]2,3\[DirectedEdge]4}],Graph[{1\[UndirectedEdge]2,3\[UndirectedEdge]4}],Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,1\[DirectedEdge]3}]}

Table[GraphLinkEfficiency[g],{g,graphs}]

Use (RefLink[ConnectedGraphQ, paclet:ref/ConnectedGraphQ]) to test for connected graphs:

Table[ConnectedGraphQ[g],{g,graphs}]

OpenersExampleSection5(Spacer1)Possible Issues  (1)

Self-loops are ignored:

g=Graph[{1\[UndirectedEdge]2,3\[UndirectedEdge]1,3\[UndirectedEdge]3}];
graphs={g,SimpleGraph[g]}

Table[GraphLinkEfficiency[g],{g,graphs}]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[GraphDistance, paclet:ref/GraphDistance])  ▪  (RefLink[MeanGraphDistance, paclet:ref/MeanGraphDistance])  ▪  (RefLink[GraphDensity, paclet:ref/GraphDensity])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Properties & Measurements, paclet:guide/GraphPropertiesAndMeasurements])}})}})