Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Graph diameter, radius, eccentricity and other properties."""
3import math
5import networkx as nx
6from networkx.utils import not_implemented_for
8__all__ = [
9 "eccentricity",
10 "diameter",
11 "harmonic_diameter",
12 "radius",
13 "periphery",
14 "center",
15 "barycenter",
16 "resistance_distance",
17 "kemeny_constant",
18 "effective_graph_resistance",
19]
22def _extrema_bounding(G, compute="diameter", weight=None):
23 """Compute requested extreme distance metric of undirected graph G
25 Computation is based on smart lower and upper bounds, and in practice
26 linear in the number of nodes, rather than quadratic (except for some
27 border cases such as complete graphs or circle shaped graphs).
29 Parameters
30 ----------
31 G : NetworkX graph
32 An undirected graph
34 compute : string denoting the requesting metric
35 "diameter" for the maximal eccentricity value,
36 "radius" for the minimal eccentricity value,
37 "periphery" for the set of nodes with eccentricity equal to the diameter,
38 "center" for the set of nodes with eccentricity equal to the radius,
39 "eccentricities" for the maximum distance from each node to all other nodes in G
41 weight : string, function, or None
42 If this is a string, then edge weights will be accessed via the
43 edge attribute with this key (that is, the weight of the edge
44 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
45 such edge attribute exists, the weight of the edge is assumed to
46 be one.
48 If this is a function, the weight of an edge is the value
49 returned by the function. The function must accept exactly three
50 positional arguments: the two endpoints of an edge and the
51 dictionary of edge attributes for that edge. The function must
52 return a number.
54 If this is None, every edge has weight/distance/cost 1.
56 Weights stored as floating point values can lead to small round-off
57 errors in distances. Use integer weights to avoid this.
59 Weights should be positive, since they are distances.
61 Returns
62 -------
63 value : value of the requested metric
64 int for "diameter" and "radius" or
65 list of nodes for "center" and "periphery" or
66 dictionary of eccentricity values keyed by node for "eccentricities"
68 Raises
69 ------
70 NetworkXError
71 If the graph consists of multiple components
72 ValueError
73 If `compute` is not one of "diameter", "radius", "periphery", "center", or "eccentricities".
75 Notes
76 -----
77 This algorithm was proposed in [1]_ and discussed further in [2]_ and [3]_.
79 References
80 ----------
81 .. [1] F. W. Takes, W. A. Kosters,
82 "Determining the diameter of small world networks."
83 Proceedings of the 20th ACM international conference on Information and
84 knowledge management, 2011
85 https://dl.acm.org/doi/abs/10.1145/2063576.2063748
86 .. [2] F. W. Takes, W. A. Kosters,
87 "Computing the Eccentricity Distribution of Large Graphs."
88 Algorithms, 2013
89 https://www.mdpi.com/1999-4893/6/1/100
90 .. [3] M. Borassi, P. Crescenzi, M. Habib, W. A. Kosters, A. Marino, F. W. Takes,
91 "Fast diameter and radius BFS-based computation in (weakly connected)
92 real-world graphs: With an application to the six degrees of separation
93 games."
94 Theoretical Computer Science, 2015
95 https://www.sciencedirect.com/science/article/pii/S0304397515001644
96 """
97 # init variables
98 degrees = dict(G.degree()) # start with the highest degree node
99 minlowernode = max(degrees, key=degrees.get)
100 N = len(degrees) # number of nodes
101 # alternate between smallest lower and largest upper bound
102 high = False
103 # status variables
104 ecc_lower = dict.fromkeys(G, 0)
105 ecc_upper = dict.fromkeys(G, math.inf)
106 candidates = set(G)
108 # (re)set bound extremes
109 minlower = math.inf
110 maxlower = 0
111 minupper = math.inf
112 maxupper = 0
114 # repeat the following until there are no more candidates
115 while candidates:
116 if high:
117 current = maxuppernode # select node with largest upper bound
118 else:
119 current = minlowernode # select node with smallest lower bound
120 high = not high
122 # get distances from/to current node and derive eccentricity
123 dist = nx.shortest_path_length(G, source=current, weight=weight)
125 if len(dist) != N:
126 msg = "Cannot compute metric because graph is not connected."
127 raise nx.NetworkXError(msg)
128 current_ecc = max(dist.values())
130 # print status update
131 # print ("ecc of " + str(current) + " (" + str(ecc_lower[current]) + "/"
132 # + str(ecc_upper[current]) + ", deg: " + str(dist[current]) + ") is "
133 # + str(current_ecc))
134 # print(ecc_upper)
136 # (re)set bound extremes
137 maxuppernode = None
138 minlowernode = None
140 # update node bounds
141 for i in candidates:
142 # update eccentricity bounds
143 d = dist[i]
144 ecc_lower[i] = low = max(ecc_lower[i], max(d, (current_ecc - d)))
145 ecc_upper[i] = upp = min(ecc_upper[i], current_ecc + d)
147 # update min/max values of lower and upper bounds
148 minlower = min(ecc_lower[i], minlower)
149 maxlower = max(ecc_lower[i], maxlower)
150 minupper = min(ecc_upper[i], minupper)
151 maxupper = max(ecc_upper[i], maxupper)
153 # update candidate set
154 if compute == "diameter":
155 ruled_out = {
156 i
157 for i in candidates
158 if ecc_upper[i] <= maxlower and 2 * ecc_lower[i] >= maxupper
159 }
160 elif compute == "radius":
161 ruled_out = {
162 i
163 for i in candidates
164 if ecc_lower[i] >= minupper and ecc_upper[i] + 1 <= 2 * minlower
165 }
166 elif compute == "periphery":
167 ruled_out = {
168 i
169 for i in candidates
170 if ecc_upper[i] < maxlower
171 and (maxlower == maxupper or ecc_lower[i] > maxupper)
172 }
173 elif compute == "center":
174 ruled_out = {
175 i
176 for i in candidates
177 if ecc_lower[i] > minupper
178 and (minlower == minupper or ecc_upper[i] + 1 < 2 * minlower)
179 }
180 elif compute == "eccentricities":
181 ruled_out = set()
182 else:
183 msg = "compute must be one of 'diameter', 'radius', 'periphery', 'center', 'eccentricities'"
184 raise ValueError(msg)
186 ruled_out.update(i for i in candidates if ecc_lower[i] == ecc_upper[i])
187 candidates -= ruled_out
189 # for i in ruled_out:
190 # print("removing %g: ecc_u: %g maxl: %g ecc_l: %g maxu: %g"%
191 # (i,ecc_upper[i],maxlower,ecc_lower[i],maxupper))
192 # print("node %g: ecc_u: %g maxl: %g ecc_l: %g maxu: %g"%
193 # (4,ecc_upper[4],maxlower,ecc_lower[4],maxupper))
194 # print("NODE 4: %g"%(ecc_upper[4] <= maxlower))
195 # print("NODE 4: %g"%(2 * ecc_lower[4] >= maxupper))
196 # print("NODE 4: %g"%(ecc_upper[4] <= maxlower
197 # and 2 * ecc_lower[4] >= maxupper))
199 # updating maxuppernode and minlowernode for selection in next round
200 for i in candidates:
201 if (
202 minlowernode is None
203 or (
204 ecc_lower[i] == ecc_lower[minlowernode]
205 and degrees[i] > degrees[minlowernode]
206 )
207 or (ecc_lower[i] < ecc_lower[minlowernode])
208 ):
209 minlowernode = i
211 if (
212 maxuppernode is None
213 or (
214 ecc_upper[i] == ecc_upper[maxuppernode]
215 and degrees[i] > degrees[maxuppernode]
216 )
217 or (ecc_upper[i] > ecc_upper[maxuppernode])
218 ):
219 maxuppernode = i
221 # print status update
222 # print (" min=" + str(minlower) + "/" + str(minupper) +
223 # " max=" + str(maxlower) + "/" + str(maxupper) +
224 # " candidates: " + str(len(candidates)))
225 # print("cand:",candidates)
226 # print("ecc_l",ecc_lower)
227 # print("ecc_u",ecc_upper)
228 # wait = input("press Enter to continue")
230 # return the correct value of the requested metric
231 if compute == "diameter":
232 return maxlower
233 if compute == "radius":
234 return minupper
235 if compute == "periphery":
236 p = [v for v in G if ecc_lower[v] == maxlower]
237 return p
238 if compute == "center":
239 c = [v for v in G if ecc_upper[v] == minupper]
240 return c
241 if compute == "eccentricities":
242 return ecc_lower
243 return None
246@nx._dispatchable(edge_attrs="weight")
247def eccentricity(G, v=None, sp=None, weight=None):
248 """Returns the eccentricity of nodes in G.
250 The eccentricity of a node v is the maximum distance from v to
251 all other nodes in G.
253 Parameters
254 ----------
255 G : NetworkX graph
256 A graph
258 v : node, optional
259 Return value of specified node
261 sp : dict of dicts, optional
262 All pairs shortest path lengths as a dictionary of dictionaries
264 weight : string, function, or None (default=None)
265 If this is a string, then edge weights will be accessed via the
266 edge attribute with this key (that is, the weight of the edge
267 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
268 such edge attribute exists, the weight of the edge is assumed to
269 be one.
271 If this is a function, the weight of an edge is the value
272 returned by the function. The function must accept exactly three
273 positional arguments: the two endpoints of an edge and the
274 dictionary of edge attributes for that edge. The function must
275 return a number.
277 If this is None, every edge has weight/distance/cost 1.
279 Weights stored as floating point values can lead to small round-off
280 errors in distances. Use integer weights to avoid this.
282 Weights should be positive, since they are distances.
284 Returns
285 -------
286 ecc : dictionary
287 A dictionary of eccentricity values keyed by node.
289 Raises
290 ------
291 NetworkXPointlessConcept
292 If G is a null graph.
294 Examples
295 --------
296 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
297 >>> dict(nx.eccentricity(G))
298 {1: 2, 2: 3, 3: 2, 4: 2, 5: 3}
300 >>> dict(
301 ... nx.eccentricity(G, v=[1, 5])
302 ... ) # This returns the eccentricity of node 1 & 5
303 {1: 2, 5: 3}
305 """
306 # if v is None: # none, use entire graph
307 # nodes=G.nodes()
308 # elif v in G: # is v a single node
309 # nodes=[v]
310 # else: # assume v is a container of nodes
311 # nodes=v
313 if len(G) == 0:
314 raise nx.NetworkXPointlessConcept(
315 "Cannot compute eccentricity of a null graph."
316 )
318 order = G.order()
319 e = {}
320 for n in G.nbunch_iter(v):
321 if sp is None:
322 length = nx.shortest_path_length(G, source=n, weight=weight)
324 L = len(length)
325 else:
326 try:
327 length = sp[n]
328 L = len(length)
329 except TypeError as err:
330 raise nx.NetworkXError('Format of "sp" is invalid.') from err
331 if L != order:
332 if G.is_directed():
333 msg = (
334 "Found infinite path length because the digraph is not"
335 " strongly connected"
336 )
337 else:
338 msg = "Found infinite path length because the graph is not connected"
339 raise nx.NetworkXError(msg)
341 e[n] = max(length.values())
343 if v in G:
344 return e[v] # return single value
345 return e
348@nx._dispatchable(edge_attrs="weight")
349def diameter(G, e=None, usebounds=False, weight=None):
350 """Returns the diameter of the graph G.
352 The diameter is the maximum eccentricity.
354 Parameters
355 ----------
356 G : NetworkX graph
357 A graph
359 e : eccentricity dictionary, optional
360 A precomputed dictionary of eccentricities.
362 usebounds : bool, optional
363 If `True`, use extrema bounding (see Notes) when computing the diameter
364 for undirected graphs. Extrema bounding may accelerate the
365 distance calculation for some graphs. `usebounds` is ignored if `G` is
366 directed or if `e` is not `None`. Default is `False`.
368 weight : string, function, or None
369 If this is a string, then edge weights will be accessed via the
370 edge attribute with this key (that is, the weight of the edge
371 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
372 such edge attribute exists, the weight of the edge is assumed to
373 be one.
375 If this is a function, the weight of an edge is the value
376 returned by the function. The function must accept exactly three
377 positional arguments: the two endpoints of an edge and the
378 dictionary of edge attributes for that edge. The function must
379 return a number.
381 If this is None, every edge has weight/distance/cost 1.
383 Weights stored as floating point values can lead to small round-off
384 errors in distances. Use integer weights to avoid this.
386 Weights should be positive, since they are distances.
388 Returns
389 -------
390 d : integer
391 Diameter of graph
393 Raises
394 ------
395 NetworkXError
396 If G has multiple components.
397 NetworkXPointlessConcept
398 If G is a null graph.
400 Notes
401 -----
402 When ``usebounds=True``, the computation makes use of smart lower
403 and upper bounds and is often linear in the number of nodes, rather than
404 quadratic (except for some border cases such as complete graphs or circle
405 shaped-graphs).
407 Examples
408 --------
409 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
410 >>> nx.diameter(G)
411 3
413 See Also
414 --------
415 eccentricity
416 """
417 if usebounds is True and e is None and not G.is_directed():
418 return _extrema_bounding(G, compute="diameter", weight=weight)
419 if e is None:
420 e = eccentricity(G, weight=weight)
421 return max(e.values())
424@nx._dispatchable(edge_attrs="weight")
425def harmonic_diameter(G, sp=None, *, weight=None):
426 """Returns the harmonic diameter of the graph G.
428 The harmonic diameter of a graph is the harmonic mean of the distances
429 between all pairs of distinct vertices. Graphs that are not strongly
430 connected have infinite diameter and mean distance, making such
431 measures not useful. Restricting the diameter or mean distance to
432 finite distances yields paradoxical values (e.g., a perfect match
433 would have diameter one). The harmonic mean handles gracefully
434 infinite distances (e.g., a perfect match has harmonic diameter equal
435 to the number of vertices minus one), making it possible to assign a
436 meaningful value to all graphs.
438 Note that in [1] the harmonic diameter is called "connectivity length":
439 however, "harmonic diameter" is a more standard name from the
440 theory of metric spaces. The name "harmonic mean distance" is perhaps
441 a more descriptive name, but is not used in the literature, so we use the
442 name "harmonic diameter" here.
444 Parameters
445 ----------
446 G : NetworkX graph
447 A graph
449 sp : dict of dicts, optional
450 All-pairs shortest path lengths as a dictionary of dictionaries
452 weight : string, function, or None (default=None)
453 If None, every edge has weight/distance 1.
454 If a string, use this edge attribute as the edge weight.
455 Any edge attribute not present defaults to 1.
456 If a function, the weight of an edge is the value returned by the function.
457 The function must accept exactly three positional arguments:
458 the two endpoints of an edge and the dictionary of edge attributes for
459 that edge. The function must return a number.
461 Returns
462 -------
463 hd : float
464 Harmonic diameter of graph
466 References
467 ----------
468 .. [1] Massimo Marchiori and Vito Latora, "Harmony in the small-world".
469 *Physica A: Statistical Mechanics and Its Applications*
470 285(3-4), pages 539-546, 2000.
471 <https://doi.org/10.1016/S0378-4371(00)00311-3>
472 """
473 order = G.order()
475 sum_invd = 0
476 for n in G:
477 if sp is None:
478 length = nx.single_source_dijkstra_path_length(G, n, weight=weight)
479 else:
480 try:
481 length = sp[n]
482 L = len(length)
483 except TypeError as err:
484 raise nx.NetworkXError('Format of "sp" is invalid.') from err
486 for d in length.values():
487 # Note that this will skip the zero distance from n to itself,
488 # as it should be, but also zero-weight paths in weighted graphs.
489 if d != 0:
490 sum_invd += 1 / d
492 if sum_invd != 0:
493 return order * (order - 1) / sum_invd
494 if order > 1:
495 return math.inf
496 return math.nan
499@nx._dispatchable(edge_attrs="weight")
500def periphery(G, e=None, usebounds=False, weight=None):
501 """Returns the periphery of the graph G.
503 The periphery is the set of nodes with eccentricity equal to the diameter.
505 Parameters
506 ----------
507 G : NetworkX graph
508 A graph
510 e : eccentricity dictionary, optional
511 A precomputed dictionary of eccentricities.
513 usebounds : bool, optional
514 If `True`, use extrema bounding (see Notes) when computing the periphery
515 for undirected graphs. Extrema bounding may accelerate the
516 distance calculation for some graphs. `usebounds` is ignored if `G` is
517 directed or if `e` is not `None`. Default is `False`.
519 weight : string, function, or None
520 If this is a string, then edge weights will be accessed via the
521 edge attribute with this key (that is, the weight of the edge
522 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
523 such edge attribute exists, the weight of the edge is assumed to
524 be one.
526 If this is a function, the weight of an edge is the value
527 returned by the function. The function must accept exactly three
528 positional arguments: the two endpoints of an edge and the
529 dictionary of edge attributes for that edge. The function must
530 return a number.
532 If this is None, every edge has weight/distance/cost 1.
534 Weights stored as floating point values can lead to small round-off
535 errors in distances. Use integer weights to avoid this.
537 Weights should be positive, since they are distances.
539 Returns
540 -------
541 p : list
542 List of nodes in periphery
544 Notes
545 -----
546 When ``usebounds=True``, the computation makes use of smart lower
547 and upper bounds and is often linear in the number of nodes, rather than
548 quadratic (except for some border cases such as complete graphs or circle
549 shaped-graphs).
551 Examples
552 --------
553 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
554 >>> nx.periphery(G)
555 [2, 5]
557 See Also
558 --------
559 barycenter
560 center
561 """
562 if usebounds is True and e is None and not G.is_directed():
563 return _extrema_bounding(G, compute="periphery", weight=weight)
564 if e is None:
565 e = eccentricity(G, weight=weight)
566 diameter = max(e.values())
567 p = [v for v in e if e[v] == diameter]
568 return p
571@nx._dispatchable(edge_attrs="weight")
572def radius(G, e=None, usebounds=False, weight=None):
573 """Returns the radius of the graph G.
575 The radius is the minimum eccentricity.
577 Parameters
578 ----------
579 G : NetworkX graph
580 A graph
582 e : eccentricity dictionary, optional
583 A precomputed dictionary of eccentricities.
585 usebounds : bool, optional
586 If `True`, use extrema bounding (see Notes) when computing the radius
587 for undirected graphs. Extrema bounding may accelerate the
588 distance calculation for some graphs. `usebounds` is ignored if `G` is
589 directed or if `e` is not `None`. Default is `False`.
591 weight : string, function, or None
592 If this is a string, then edge weights will be accessed via the
593 edge attribute with this key (that is, the weight of the edge
594 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
595 such edge attribute exists, the weight of the edge is assumed to
596 be one.
598 If this is a function, the weight of an edge is the value
599 returned by the function. The function must accept exactly three
600 positional arguments: the two endpoints of an edge and the
601 dictionary of edge attributes for that edge. The function must
602 return a number.
604 If this is None, every edge has weight/distance/cost 1.
606 Weights stored as floating point values can lead to small round-off
607 errors in distances. Use integer weights to avoid this.
609 Weights should be positive, since they are distances.
611 Returns
612 -------
613 r : integer
614 Radius of graph
616 Raises
617 ------
618 NetworkXError
619 If G has multiple components.
620 NetworkXPointlessConcept
621 If G is a null graph.
623 Notes
624 -----
625 When ``usebounds=True``, the computation makes use of smart lower
626 and upper bounds and is often linear in the number of nodes, rather than
627 quadratic (except for some border cases such as complete graphs or circle
628 shaped-graphs).
630 Examples
631 --------
632 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
633 >>> nx.radius(G)
634 2
636 """
637 if usebounds is True and e is None and not G.is_directed():
638 return _extrema_bounding(G, compute="radius", weight=weight)
639 if e is None:
640 e = eccentricity(G, weight=weight)
641 return min(e.values())
644@nx._dispatchable(edge_attrs="weight")
645def center(G, e=None, usebounds=False, weight=None):
646 """Returns the center of the graph G.
648 The center is the set of nodes with eccentricity equal to radius.
650 Parameters
651 ----------
652 G : NetworkX graph
653 A graph
655 e : eccentricity dictionary, optional
656 A precomputed dictionary of eccentricities.
658 usebounds : bool, optional
659 If `True`, use extrema bounding (see Notes) when computing the center
660 for undirected graphs. Extrema bounding may accelerate the
661 distance calculation for some graphs. `usebounds` is ignored if `G` is
662 directed or if `e` is not `None`. Default is `False`.
664 weight : string, function, or None
665 If this is a string, then edge weights will be accessed via the
666 edge attribute with this key (that is, the weight of the edge
667 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
668 such edge attribute exists, the weight of the edge is assumed to
669 be one.
671 If this is a function, the weight of an edge is the value
672 returned by the function. The function must accept exactly three
673 positional arguments: the two endpoints of an edge and the
674 dictionary of edge attributes for that edge. The function must
675 return a number.
677 If this is None, every edge has weight/distance/cost 1.
679 Weights stored as floating point values can lead to small round-off
680 errors in distances. Use integer weights to avoid this.
682 Weights should be positive, since they are distances.
684 Returns
685 -------
686 c : list
687 List of nodes in center
689 Notes
690 -----
691 When ``usebounds=True``, the computation makes use of smart lower
692 and upper bounds and is often linear in the number of nodes, rather than
693 quadratic (except for some border cases such as complete graphs or circle
694 shaped-graphs).
696 Examples
697 --------
698 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
699 >>> list(nx.center(G))
700 [1, 3, 4]
702 See Also
703 --------
704 :func:`~networkx.algorithms.tree.distance_measures.center` : tree center
705 barycenter
706 periphery
707 :func:`~networkx.algorithms.tree.distance_measures.centroid` : tree centroid
708 """
709 if usebounds is True and e is None and not G.is_directed():
710 return _extrema_bounding(G, compute="center", weight=weight)
711 if e is None and weight is None and not G.is_directed() and nx.is_tree(G):
712 return nx.tree.center(G)
713 if e is None:
714 e = eccentricity(G, weight=weight)
715 radius = min(e.values())
716 p = [v for v in e if e[v] == radius]
717 return p
720@nx._dispatchable(edge_attrs="weight", mutates_input={"attr": 2})
721def barycenter(G, weight=None, attr=None, sp=None):
722 r"""Calculate barycenter of a connected graph, optionally with edge weights.
724 The :dfn:`barycenter` a
725 :func:`connected <networkx.algorithms.components.is_connected>` graph
726 :math:`G` is the subgraph induced by the set of its nodes :math:`v`
727 minimizing the objective function
729 .. math::
731 \sum_{u \in V(G)} d_G(u, v),
733 where :math:`d_G` is the (possibly weighted) :func:`path length
734 <networkx.algorithms.shortest_paths.generic.shortest_path_length>`.
735 The barycenter is also called the :dfn:`median`. See [West01]_, p. 78.
737 Parameters
738 ----------
739 G : :class:`networkx.Graph`
740 The connected graph :math:`G`.
741 weight : :class:`str`, optional
742 Passed through to
743 :func:`~networkx.algorithms.shortest_paths.generic.shortest_path_length`.
744 attr : :class:`str`, optional
745 If given, write the value of the objective function to each node's
746 `attr` attribute. Otherwise do not store the value.
747 sp : dict of dicts, optional
748 All pairs shortest path lengths as a dictionary of dictionaries
750 Returns
751 -------
752 list
753 Nodes of `G` that induce the barycenter of `G`.
755 Raises
756 ------
757 NetworkXNoPath
758 If `G` is disconnected. `G` may appear disconnected to
759 :func:`barycenter` if `sp` is given but is missing shortest path
760 lengths for any pairs.
761 ValueError
762 If `sp` and `weight` are both given.
764 Examples
765 --------
766 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
767 >>> nx.barycenter(G)
768 [1, 3, 4]
770 See Also
771 --------
772 center
773 periphery
774 :func:`~networkx.algorithms.tree.distance_measures.centroid` : tree centroid
775 """
776 if weight is None and attr is None and sp is None:
777 if not G.is_directed() and nx.is_tree(G):
778 return nx.tree.centroid(G)
780 if sp is None:
781 sp = nx.shortest_path_length(G, weight=weight)
782 else:
783 sp = sp.items()
784 if weight is not None:
785 raise ValueError("Cannot use both sp, weight arguments together")
786 smallest, barycenter_vertices, n = float("inf"), [], len(G)
787 for v, dists in sp:
788 if len(dists) < n:
789 raise nx.NetworkXNoPath(
790 f"Input graph {G} is disconnected, so every induced subgraph "
791 "has infinite barycentricity."
792 )
793 barycentricity = sum(dists.values())
794 if attr is not None:
795 G.nodes[v][attr] = barycentricity
796 if barycentricity < smallest:
797 smallest = barycentricity
798 barycenter_vertices = [v]
799 elif barycentricity == smallest:
800 barycenter_vertices.append(v)
801 if attr is not None:
802 nx._clear_cache(G)
803 return barycenter_vertices
806@not_implemented_for("directed")
807@nx._dispatchable(edge_attrs="weight")
808def resistance_distance(G, nodeA=None, nodeB=None, weight=None, invert_weight=True):
809 """Returns the resistance distance between pairs of nodes in graph G.
811 The resistance distance between two nodes of a graph is akin to treating
812 the graph as a grid of resistors with a resistance equal to the provided
813 weight [1]_, [2]_.
815 If weight is not provided, then a weight of 1 is used for all edges.
817 If two nodes are the same, the resistance distance is zero.
819 Parameters
820 ----------
821 G : NetworkX graph
822 A graph
824 nodeA : node or None, optional (default=None)
825 A node within graph G.
826 If None, compute resistance distance using all nodes as source nodes.
828 nodeB : node or None, optional (default=None)
829 A node within graph G.
830 If None, compute resistance distance using all nodes as target nodes.
832 weight : string or None, optional (default=None)
833 The edge data key used to compute the resistance distance.
834 If None, then each edge has weight 1.
836 invert_weight : boolean (default=True)
837 Proper calculation of resistance distance requires building the
838 Laplacian matrix with the reciprocal of the weight. Not required
839 if the weight is already inverted. Weight cannot be zero.
841 Returns
842 -------
843 rd : dict or float
844 If `nodeA` and `nodeB` are given, resistance distance between `nodeA`
845 and `nodeB`. If `nodeA` or `nodeB` is unspecified (the default), a
846 dictionary of nodes with resistance distances as the value.
848 Raises
849 ------
850 NetworkXNotImplemented
851 If `G` is a directed graph.
853 NetworkXError
854 If `G` is not connected, or contains no nodes,
855 or `nodeA` is not in `G` or `nodeB` is not in `G`.
857 Examples
858 --------
859 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
860 >>> round(nx.resistance_distance(G, 1, 3), 10)
861 0.625
863 Notes
864 -----
865 The implementation is based on Theorem A in [2]_. Self-loops are ignored.
866 Multi-edges are contracted in one edge with weight equal to the harmonic sum of the weights.
868 References
869 ----------
870 .. [1] Wikipedia
871 "Resistance distance."
872 https://en.wikipedia.org/wiki/Resistance_distance
873 .. [2] D. J. Klein and M. Randic.
874 Resistance distance.
875 J. of Math. Chem. 12:81-95, 1993.
876 """
877 import numpy as np
879 if len(G) == 0:
880 raise nx.NetworkXError("Graph G must contain at least one node.")
881 if not nx.is_connected(G):
882 raise nx.NetworkXError("Graph G must be strongly connected.")
883 if nodeA is not None and nodeA not in G:
884 raise nx.NetworkXError("Node A is not in graph G.")
885 if nodeB is not None and nodeB not in G:
886 raise nx.NetworkXError("Node B is not in graph G.")
888 G = G.copy()
889 node_list = list(G)
891 # Invert weights
892 if invert_weight and weight is not None:
893 if G.is_multigraph():
894 for u, v, k, d in G.edges(keys=True, data=True):
895 d[weight] = 1 / d[weight]
896 else:
897 for u, v, d in G.edges(data=True):
898 d[weight] = 1 / d[weight]
900 # Compute resistance distance using the Pseudo-inverse of the Laplacian
901 # Self-loops are ignored
902 L = nx.laplacian_matrix(G, weight=weight).todense()
903 Linv = np.linalg.pinv(L, hermitian=True)
905 # Return relevant distances
906 if nodeA is not None and nodeB is not None:
907 i = node_list.index(nodeA)
908 j = node_list.index(nodeB)
909 return Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
911 elif nodeA is not None:
912 i = node_list.index(nodeA)
913 d = {}
914 for n in G:
915 j = node_list.index(n)
916 d[n] = Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
917 return d
919 elif nodeB is not None:
920 j = node_list.index(nodeB)
921 d = {}
922 for n in G:
923 i = node_list.index(n)
924 d[n] = Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
925 return d
927 else:
928 d = {}
929 for n in G:
930 i = node_list.index(n)
931 d[n] = {}
932 for n2 in G:
933 j = node_list.index(n2)
934 d[n][n2] = (
935 Linv.item(i, i)
936 + Linv.item(j, j)
937 - Linv.item(i, j)
938 - Linv.item(j, i)
939 )
940 return d
943@not_implemented_for("directed")
944@nx._dispatchable(edge_attrs="weight")
945def effective_graph_resistance(G, weight=None, invert_weight=True):
946 """Returns the Effective graph resistance of G.
948 Also known as the Kirchhoff index.
950 The effective graph resistance is defined as the sum
951 of the resistance distance of every node pair in G [1]_.
953 If weight is not provided, then a weight of 1 is used for all edges.
955 The effective graph resistance of a disconnected graph is infinite.
957 Parameters
958 ----------
959 G : NetworkX graph
960 A graph
962 weight : string or None, optional (default=None)
963 The edge data key used to compute the effective graph resistance.
964 If None, then each edge has weight 1.
966 invert_weight : boolean (default=True)
967 Proper calculation of resistance distance requires building the
968 Laplacian matrix with the reciprocal of the weight. Not required
969 if the weight is already inverted. Weight cannot be zero.
971 Returns
972 -------
973 RG : float
974 The effective graph resistance of `G`.
976 Raises
977 ------
978 NetworkXNotImplemented
979 If `G` is a directed graph.
981 NetworkXError
982 If `G` does not contain any nodes.
984 Examples
985 --------
986 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
987 >>> round(nx.effective_graph_resistance(G), 10)
988 10.25
990 Notes
991 -----
992 The implementation is based on Theorem 2.2 in [2]_. Self-loops are ignored.
993 Multi-edges are contracted in one edge with weight equal to the harmonic sum of the weights.
995 References
996 ----------
997 .. [1] Wolfram
998 "Kirchhoff Index."
999 https://mathworld.wolfram.com/KirchhoffIndex.html
1000 .. [2] W. Ellens, F. M. Spieksma, P. Van Mieghem, A. Jamakovic, R. E. Kooij.
1001 Effective graph resistance.
1002 Lin. Alg. Appl. 435:2491-2506, 2011.
1003 """
1004 import numpy as np
1006 if len(G) == 0:
1007 raise nx.NetworkXError("Graph G must contain at least one node.")
1009 # Disconnected graphs have infinite Effective graph resistance
1010 if not nx.is_connected(G):
1011 return float("inf")
1013 # Invert weights
1014 G = G.copy()
1015 if invert_weight and weight is not None:
1016 if G.is_multigraph():
1017 for u, v, k, d in G.edges(keys=True, data=True):
1018 d[weight] = 1 / d[weight]
1019 else:
1020 for u, v, d in G.edges(data=True):
1021 d[weight] = 1 / d[weight]
1023 # Get Laplacian eigenvalues
1024 mu = np.sort(nx.laplacian_spectrum(G, weight=weight))
1026 # Compute Effective graph resistance based on spectrum of the Laplacian
1027 # Self-loops are ignored
1028 return float(np.sum(1 / mu[1:]) * G.number_of_nodes())
1031@nx.utils.not_implemented_for("directed")
1032@nx._dispatchable(edge_attrs="weight")
1033def kemeny_constant(G, *, weight=None):
1034 """Returns the Kemeny constant of the given graph.
1036 The *Kemeny constant* (or Kemeny's constant) of a graph `G`
1037 can be computed by regarding the graph as a Markov chain.
1038 The Kemeny constant is then the expected number of time steps
1039 to transition from a starting state i to a random destination state
1040 sampled from the Markov chain's stationary distribution.
1041 The Kemeny constant is independent of the chosen initial state [1]_.
1043 The Kemeny constant measures the time needed for spreading
1044 across a graph. Low values indicate a closely connected graph
1045 whereas high values indicate a spread-out graph.
1047 If weight is not provided, then a weight of 1 is used for all edges.
1049 Since `G` represents a Markov chain, the weights must be positive.
1051 Parameters
1052 ----------
1053 G : NetworkX graph
1055 weight : string or None, optional (default=None)
1056 The edge data key used to compute the Kemeny constant.
1057 If None, then each edge has weight 1.
1059 Returns
1060 -------
1061 float
1062 The Kemeny constant of the graph `G`.
1064 Raises
1065 ------
1066 NetworkXNotImplemented
1067 If the graph `G` is directed.
1069 NetworkXError
1070 If the graph `G` is not connected, or contains no nodes,
1071 or has edges with negative weights.
1073 Examples
1074 --------
1075 >>> G = nx.complete_graph(5)
1076 >>> round(nx.kemeny_constant(G), 10)
1077 3.2
1079 Notes
1080 -----
1081 The implementation is based on equation (3.3) in [2]_.
1082 Self-loops are allowed and indicate a Markov chain where
1083 the state can remain the same. Multi-edges are contracted
1084 in one edge with weight equal to the sum of the weights.
1086 References
1087 ----------
1088 .. [1] Wikipedia
1089 "Kemeny's constant."
1090 https://en.wikipedia.org/wiki/Kemeny%27s_constant
1091 .. [2] Lovász L.
1092 Random walks on graphs: A survey.
1093 Paul Erdös is Eighty, vol. 2, Bolyai Society,
1094 Mathematical Studies, Keszthely, Hungary (1993), pp. 1-46
1095 """
1096 import numpy as np
1097 import scipy as sp
1099 if len(G) == 0:
1100 raise nx.NetworkXError("Graph G must contain at least one node.")
1101 if not nx.is_connected(G):
1102 raise nx.NetworkXError("Graph G must be connected.")
1103 if nx.is_negatively_weighted(G, weight=weight):
1104 raise nx.NetworkXError("The weights of graph G must be nonnegative.")
1106 # Compute matrix H = D^-1/2 A D^-1/2
1107 A = nx.adjacency_matrix(G, weight=weight)
1108 n, m = A.shape
1109 diags = A.sum(axis=1)
1110 with np.errstate(divide="ignore"):
1111 diags_sqrt = 1.0 / np.sqrt(diags)
1112 diags_sqrt[np.isinf(diags_sqrt)] = 0
1113 DH = sp.sparse.dia_array((diags_sqrt, 0), shape=(m, n)).tocsr()
1114 H = DH @ (A @ DH)
1116 # Compute eigenvalues of H
1117 eig = np.sort(sp.linalg.eigvalsh(H.todense()))
1119 # Compute the Kemeny constant
1120 return float(np.sum(1 / (1 - eig[:-1])))