centroid

centroid(G, weight=None, attr=None, sp=None)

Calculate centroid of a connected graph, optionally with edge weights.

The centroid of a connected graph \(G\) is the subgraph induced by the set of its nodes \(v\) minimizing the objective function

\[\sum_{u \in V(G)} d_G(u, v),\]

where \(d_G\) is the (possibly weighted) path length. This quantity is also known as the barycenter or median. See [West01], p. 78.

Changed in version 3.7: centroid() is created by a renaming of barycenter(). The old name still works to call this function.

Parameters:

Gnetworkx.Graph

The connected graph \(G\).

weightstr, optional

Passed through to shortest_path_length().

attrstr, optional

If given, write the value of the objective function to each node’s attr attribute. Otherwise do not store the value.

spdict of dicts, optional

All pairs shortest path lengths as a dictionary of dictionaries

Returns:

list

Nodes of G that induce the centroid of G.

Raises:

NetworkXNoPath

If G is disconnected. G may appear disconnected to centroid() if sp is given but is missing shortest path lengths for any pairs.

ValueError

If sp and weight are both given.

See also

center

periphery

centroid()

tree centroid

Examples

>>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
>>> nx.centroid(G)
[1, 3, 4]