VertexEccentricity
VertexEccentricity[g,s]
gives the length of the longest shortest path from the source s to every other vertex in the graph g.
VertexEccentricity[{vw,…},…]
uses rules vw to specify the graph g.
Details and Options
- VertexEccentricity is also known as node eccentricity.
- VertexEccentricity[g,s] gives the vertex eccentricity for the connected component in which s is contained.
- The following options can be given:
-
EdgeWeight Automatic weight for each edge Method Automatic method to use - Possible Method settings include "BellmanFord" and "Dijkstra".
Examples
open all close allBasic Examples (1)
Scope (7)
VertexEccentricity works with undirected graphs:
VertexEccentricity[[image], 1]VertexEccentricity[[image], 1]VertexEccentricity[[image], 4]VertexEccentricity[[image], 1]VertexEccentricity[[image], 1]Use rules to specify the graph:
VertexEccentricity[{1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 5 -> 3}, 1]VertexEccentricity works with large graphs:
g = GridGraph[{10, 10, 10, 10}];VertexEccentricity[g, 1]//TimingApplications (5)
In an 
PetersenGraph, every vertex has the same eccentricity:
PetersenGraph[6, 1]Table[VertexEccentricity[%, v], {v, VertexList[%]}]Some Petersen graphs have different eccentricities for the inner and outer subgraphs:
g = PetersenGraph[9, 4]HighlightGraph[g, Table[Labeled[v, VertexEccentricity[g, v]], {v, VertexList[g]}]]Compute and highlight the vertex eccentricity for special graphs, including GridGraph:
g = GridGraph[{5, 8}, VertexSize -> 0.5];
ve = Table[VertexEccentricity[g, v], {v, VertexList[g]}];HighlightGraph[g, Table[Style[v, ColorData["TemperatureMap", ve[[VertexIndex[g, v]]] / Max[ve]]], {v, VertexList[g]}]]Package this up as a function:
EccentricityPlot[g_ ? GraphQ] :=
Module[{ve = Table[VertexEccentricity[g, v], {v, VertexList[g]}]},
HighlightGraph[g, Table[Style[v, ColorData["TemperatureMap", ve[[VertexIndex[g, v]]] / Max[ve]]], {v, VertexList[g]}]]
];Many special graphs have constant vertex eccentricity:
{EccentricityPlot[CycleGraph[15, VertexSize -> 0.5]], EccentricityPlot[HypercubeGraph[4, VertexSize -> 0.5]],
EccentricityPlot[PetersenGraph[7, 4, VertexSize -> 0.5]]}A few will have varying eccentricity, where some vertices are more centrally located:
{EccentricityPlot[CompleteKaryTree[4, VertexSize -> 0.5]], EccentricityPlot[PathGraph[Range[50], VertexSize -> 0.5]], EccentricityPlot[KnightTourGraph[8, 8, VertexSize -> 0.5]]}Most random graphs have small eccentricities:
EccentricityPlot[g_ ? GraphQ] :=
Module[{ve = Table[VertexEccentricity[g, v], {v, VertexList[g]}]},
HighlightGraph[g, Table[Style[v, ColorData["TemperatureMap", ve[[VertexIndex[g, v]]] / Max[ve]]], {v, VertexList[g]}]]
]EccentricityPlot[RandomGraph[UniformGraphDistribution[50, 75], VertexSize -> {"Scaled", 0.03}]]The Barabasi–Albert random graph:
EccentricityPlot[RandomGraph[BarabasiAlbertGraphDistribution[50, 3], VertexSize -> {"Scaled", 0.03}]]The de Solla Price random graph:
EccentricityPlot[RandomGraph[PriceGraphDistribution[50, 3, 1], VertexSize -> {"Scaled", 0.03}]]Low eccentricity indicates close relation to everybody at the family gathering. Compare Larry and Rudy:
ExampleData[{"NetworkGraph", "FamilyGathering"}]{VertexEccentricity[%, "Larry"], VertexEccentricity[%, "Rudy"]}Properties & Relations (3)
In a connected graph, the vertex eccentricity is related to GraphDistance:
g = GridGraph[{3, 4}]GraphDistance[g, 1, #]& /@ VertexList[g]//MaxVertexEccentricity[g, 1]GraphDistanceMatrix[g][[VertexIndex[g, 1], All]]//MaxThe vertex eccentricity in a connected graph is related to GraphDiameter:
g = GridGraph[{3, 4}]Max[VertexEccentricity[g, #]& /@ VertexList[g]]GraphDiameter[g]Min[VertexEccentricity[g, #]& /@ VertexList[g]]GraphRadius[g]ecc = VertexEccentricity[g, #]& /@ VertexList[g]Flatten[Position[ecc, Max[ecc]]]GraphPeriphery[g]ecc = VertexEccentricity[g, #]& /@ VertexList[g]Flatten[Position[ecc, Min[ecc]]]GraphCenter[g]Illustrate the eccentricity of two vertices in a Petersen graph:
findVertexEccentricityPath[g_ ? UndirectedGraphQ, u_] := Module[{d = GraphDistanceMatrix[g], posu, posv, vl = VertexList[g]}, posu = First@First@Position[vl, u];
posv = First@First@Position[d[[posu]], Max[d[[posu]]]];
PathGraph@FindShortestPath[g, u, vl[[posv]]]]With[{g = PetersenGraph[5, 2]}, HighlightGraph[Annotate[{g, #}, VertexSize -> Small], findVertexEccentricityPath[g, #]]& /@ {1, 6}]For a CompleteGraph, every vertex has eccentricity 1:
Table[HighlightGraph[Annotate[{g, v}, VertexSize -> Small], findVertexEccentricityPath[g, v]], {g, {CompleteGraph[3], CompleteGraph[7]}}, {v, {1, 2}}]//FlattenThe eccentricity path in a PathGraph switches halfway through:
With[{g = PathGraph[Range[6]]},
HighlightGraph[Annotate[{g, #}, VertexSize -> Small], findVertexEccentricityPath[g, #]]& /@ Range[4]]The eccentricity path in a CycleGraph measures both the GraphDiameter and GraphRadius:
Table[HighlightGraph[Annotate[{g, v}, VertexSize -> Small], findVertexEccentricityPath[g, v]], {g, {CycleGraph[6], CycleGraph[7]}}, {v, {1, 2}}]//FlattenIn a WheelGraph of size 5 or more, the eccentricity is 1 at the hub and 2 elsewhere:
Table[HighlightGraph[Annotate[{g, v}, VertexSize -> Small], findVertexEccentricityPath[g, v]], {g, {WheelGraph[5], WheelGraph[7]}}, {v, {1, 2}}]//FlattenIn a GridGraph, the eccentricity path always ends in a corner of the grid:
With[{g = GridGraph[{5, 4}]}, Table[HighlightGraph[Annotate[{g, v}, VertexSize -> Small], findVertexEccentricityPath[g, v]], {v, {1, 8, 15, 17}}]]In a CompleteKaryTree, the eccentricity path always ends in a leaf:
With[{g = CompleteKaryTree[3, 3]}, Table[HighlightGraph[Annotate[{g, v}, VertexSize -> Small], findVertexEccentricityPath[g, v]], {v, {1, 4, 5, 12}}]]Text
Wolfram Research (2010), VertexEccentricity, Wolfram Language function, https://reference.wolfram.com/language/ref/VertexEccentricity.html (updated 2015).
CMS
Wolfram Language. 2010. "VertexEccentricity." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/VertexEccentricity.html.
APA
Wolfram Language. (2010). VertexEccentricity. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/VertexEccentricity.html