extrema_bounding(G, compute='diameter')

Computation is based on smart lower and upper bounds, and in practice linear in the number of nodes, rather than quadratic (except for some border cases such as complete graphs or circle shaped graphs).

Parameters

G : NetworkX graph

An undirected graph

compute : string denoting the requesting metric

"diameter" for the maximal eccentricity value, "radius" for the minimal eccentricity value, "periphery" for the set of nodes with eccentricity equal to the diameter, "center" for the set of nodes with eccentricity equal to the radius, "eccentricities" for the maximum distance from each node to all other nodes in G

Raises

NetworkXError

If the graph consists of multiple components

ValueError

If compute is not one of "diameter", "radius", "periphery", "center", or "eccentricities".

Notes

-----

This algorithm was proposed in the following papers:

F.W. Takes and W.A. Kosters, Determining the Diameter of Small World

Networks, in Proceedings of the 20th ACM International Conference on

Information and Knowledge Management (CIKM 2011), pp. 1191-1196, 2011.

doi: https://doi.org/10.1145/2063576.2063748

F.W. Takes and W.A. Kosters, Computing the Eccentricity Distribution of

Large Graphs, Algorithms 6(1): 100-118, 2013.

doi: https://doi.org/10.3390/a6010100

M. Borassi, P. Crescenzi, M. Habib, W.A. Kosters, A. Marino and F.W. Takes,

Fast Graph Diameter and Radius BFS-Based Computation in (Weakly Connected)

Real-World Graphs, Theoretical Computer Science 586: 59-80, 2015.

doi: https://doi.org/10.1016/j.tcs.2015.02.033

Returns

value : value of the requested metric

int for "diameter" and "radius" or list of nodes for "center" and "periphery" or dictionary of eccentricity values keyed by node for "eccentricities"

Compute requested extreme distance metric of undirected graph G

Examples

See :

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them

---

GitHub : /networkx/algorithms/distance_measures.py#18
type: <class 'function'>
Commit: