barycenter#

barycenter(G, weight=None, attr=None, sp=None)[source]#

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

The barycenter 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. The barycenter is also called the median. See [West01], p. 78.

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 barycenter of G.

Raises:
NetworkXNoPath

If G is disconnected. G may appear disconnected to barycenter() 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

Examples

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