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 Examples
290 --------
291 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
292 >>> dict(nx.eccentricity(G))
293 {1: 2, 2: 3, 3: 2, 4: 2, 5: 3}
295 >>> dict(
296 ... nx.eccentricity(G, v=[1, 5])
297 ... ) # This returns the eccentricity of node 1 & 5
298 {1: 2, 5: 3}
300 """
301 # if v is None: # none, use entire graph
302 # nodes=G.nodes()
303 # elif v in G: # is v a single node
304 # nodes=[v]
305 # else: # assume v is a container of nodes
306 # nodes=v
307 order = G.order()
308 e = {}
309 for n in G.nbunch_iter(v):
310 if sp is None:
311 length = nx.shortest_path_length(G, source=n, weight=weight)
313 L = len(length)
314 else:
315 try:
316 length = sp[n]
317 L = len(length)
318 except TypeError as err:
319 raise nx.NetworkXError('Format of "sp" is invalid.') from err
320 if L != order:
321 if G.is_directed():
322 msg = (
323 "Found infinite path length because the digraph is not"
324 " strongly connected"
325 )
326 else:
327 msg = "Found infinite path length because the graph is not connected"
328 raise nx.NetworkXError(msg)
330 e[n] = max(length.values())
332 if v in G:
333 return e[v] # return single value
334 return e
337@nx._dispatchable(edge_attrs="weight")
338def diameter(G, e=None, usebounds=False, weight=None):
339 """Returns the diameter of the graph G.
341 The diameter is the maximum eccentricity.
343 Parameters
344 ----------
345 G : NetworkX graph
346 A graph
348 e : eccentricity dictionary, optional
349 A precomputed dictionary of eccentricities.
351 usebounds : bool, optional
352 If `True`, use extrema bounding (see Notes) when computing the diameter
353 for undirected graphs. Extrema bounding may accelerate the
354 distance calculation for some graphs. `usebounds` is ignored if `G` is
355 directed or if `e` is not `None`. Default is `False`.
357 weight : string, function, or None
358 If this is a string, then edge weights will be accessed via the
359 edge attribute with this key (that is, the weight of the edge
360 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
361 such edge attribute exists, the weight of the edge is assumed to
362 be one.
364 If this is a function, the weight of an edge is the value
365 returned by the function. The function must accept exactly three
366 positional arguments: the two endpoints of an edge and the
367 dictionary of edge attributes for that edge. The function must
368 return a number.
370 If this is None, every edge has weight/distance/cost 1.
372 Weights stored as floating point values can lead to small round-off
373 errors in distances. Use integer weights to avoid this.
375 Weights should be positive, since they are distances.
377 Returns
378 -------
379 d : integer
380 Diameter of graph
382 Notes
383 -----
384 When ``usebounds=True``, the computation makes use of smart lower
385 and upper bounds and is often linear in the number of nodes, rather than
386 quadratic (except for some border cases such as complete graphs or circle
387 shaped-graphs).
389 Examples
390 --------
391 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
392 >>> nx.diameter(G)
393 3
395 See Also
396 --------
397 eccentricity
398 """
399 if usebounds is True and e is None and not G.is_directed():
400 return _extrema_bounding(G, compute="diameter", weight=weight)
401 if e is None:
402 e = eccentricity(G, weight=weight)
403 return max(e.values())
406@nx._dispatchable(edge_attrs="weight")
407def harmonic_diameter(G, sp=None, *, weight=None):
408 """Returns the harmonic diameter of the graph G.
410 The harmonic diameter of a graph is the harmonic mean of the distances
411 between all pairs of distinct vertices. Graphs that are not strongly
412 connected have infinite diameter and mean distance, making such
413 measures not useful. Restricting the diameter or mean distance to
414 finite distances yields paradoxical values (e.g., a perfect match
415 would have diameter one). The harmonic mean handles gracefully
416 infinite distances (e.g., a perfect match has harmonic diameter equal
417 to the number of vertices minus one), making it possible to assign a
418 meaningful value to all graphs.
420 Note that in [1] the harmonic diameter is called "connectivity length":
421 however, "harmonic diameter" is a more standard name from the
422 theory of metric spaces. The name "harmonic mean distance" is perhaps
423 a more descriptive name, but is not used in the literature, so we use the
424 name "harmonic diameter" here.
426 Parameters
427 ----------
428 G : NetworkX graph
429 A graph
431 sp : dict of dicts, optional
432 All-pairs shortest path lengths as a dictionary of dictionaries
434 weight : string, function, or None (default=None)
435 If None, every edge has weight/distance 1.
436 If a string, use this edge attribute as the edge weight.
437 Any edge attribute not present defaults to 1.
438 If a function, the weight of an edge is the value returned by the function.
439 The function must accept exactly three positional arguments:
440 the two endpoints of an edge and the dictionary of edge attributes for
441 that edge. The function must return a number.
443 Returns
444 -------
445 hd : float
446 Harmonic diameter of graph
448 References
449 ----------
450 .. [1] Massimo Marchiori and Vito Latora, "Harmony in the small-world".
451 *Physica A: Statistical Mechanics and Its Applications*
452 285(3-4), pages 539-546, 2000.
453 <https://doi.org/10.1016/S0378-4371(00)00311-3>
454 """
455 order = G.order()
457 sum_invd = 0
458 for n in G:
459 if sp is None:
460 length = nx.single_source_dijkstra_path_length(G, n, weight=weight)
461 else:
462 try:
463 length = sp[n]
464 L = len(length)
465 except TypeError as err:
466 raise nx.NetworkXError('Format of "sp" is invalid.') from err
468 for d in length.values():
469 # Note that this will skip the zero distance from n to itself,
470 # as it should be, but also zero-weight paths in weighted graphs.
471 if d != 0:
472 sum_invd += 1 / d
474 if sum_invd != 0:
475 return order * (order - 1) / sum_invd
476 if order > 1:
477 return math.inf
478 return math.nan
481@nx._dispatchable(edge_attrs="weight")
482def periphery(G, e=None, usebounds=False, weight=None):
483 """Returns the periphery of the graph G.
485 The periphery is the set of nodes with eccentricity equal to the diameter.
487 Parameters
488 ----------
489 G : NetworkX graph
490 A graph
492 e : eccentricity dictionary, optional
493 A precomputed dictionary of eccentricities.
495 usebounds : bool, optional
496 If `True`, use extrema bounding (see Notes) when computing the periphery
497 for undirected graphs. Extrema bounding may accelerate the
498 distance calculation for some graphs. `usebounds` is ignored if `G` is
499 directed or if `e` is not `None`. Default is `False`.
501 weight : string, function, or None
502 If this is a string, then edge weights will be accessed via the
503 edge attribute with this key (that is, the weight of the edge
504 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
505 such edge attribute exists, the weight of the edge is assumed to
506 be one.
508 If this is a function, the weight of an edge is the value
509 returned by the function. The function must accept exactly three
510 positional arguments: the two endpoints of an edge and the
511 dictionary of edge attributes for that edge. The function must
512 return a number.
514 If this is None, every edge has weight/distance/cost 1.
516 Weights stored as floating point values can lead to small round-off
517 errors in distances. Use integer weights to avoid this.
519 Weights should be positive, since they are distances.
521 Returns
522 -------
523 p : list
524 List of nodes in periphery
526 Notes
527 -----
528 When ``usebounds=True``, the computation makes use of smart lower
529 and upper bounds and is often linear in the number of nodes, rather than
530 quadratic (except for some border cases such as complete graphs or circle
531 shaped-graphs).
533 Examples
534 --------
535 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
536 >>> nx.periphery(G)
537 [2, 5]
539 See Also
540 --------
541 barycenter
542 center
543 """
544 if usebounds is True and e is None and not G.is_directed():
545 return _extrema_bounding(G, compute="periphery", weight=weight)
546 if e is None:
547 e = eccentricity(G, weight=weight)
548 diameter = max(e.values())
549 p = [v for v in e if e[v] == diameter]
550 return p
553@nx._dispatchable(edge_attrs="weight")
554def radius(G, e=None, usebounds=False, weight=None):
555 """Returns the radius of the graph G.
557 The radius is the minimum eccentricity.
559 Parameters
560 ----------
561 G : NetworkX graph
562 A graph
564 e : eccentricity dictionary, optional
565 A precomputed dictionary of eccentricities.
567 usebounds : bool, optional
568 If `True`, use extrema bounding (see Notes) when computing the radius
569 for undirected graphs. Extrema bounding may accelerate the
570 distance calculation for some graphs. `usebounds` is ignored if `G` is
571 directed or if `e` is not `None`. Default is `False`.
573 weight : string, function, or None
574 If this is a string, then edge weights will be accessed via the
575 edge attribute with this key (that is, the weight of the edge
576 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
577 such edge attribute exists, the weight of the edge is assumed to
578 be one.
580 If this is a function, the weight of an edge is the value
581 returned by the function. The function must accept exactly three
582 positional arguments: the two endpoints of an edge and the
583 dictionary of edge attributes for that edge. The function must
584 return a number.
586 If this is None, every edge has weight/distance/cost 1.
588 Weights stored as floating point values can lead to small round-off
589 errors in distances. Use integer weights to avoid this.
591 Weights should be positive, since they are distances.
593 Returns
594 -------
595 r : integer
596 Radius of graph
598 Notes
599 -----
600 When ``usebounds=True``, the computation makes use of smart lower
601 and upper bounds and is often linear in the number of nodes, rather than
602 quadratic (except for some border cases such as complete graphs or circle
603 shaped-graphs).
605 Examples
606 --------
607 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
608 >>> nx.radius(G)
609 2
611 """
612 if usebounds is True and e is None and not G.is_directed():
613 return _extrema_bounding(G, compute="radius", weight=weight)
614 if e is None:
615 e = eccentricity(G, weight=weight)
616 return min(e.values())
619@nx._dispatchable(edge_attrs="weight")
620def center(G, e=None, usebounds=False, weight=None):
621 """Returns the center of the graph G.
623 The center is the set of nodes with eccentricity equal to radius.
625 Parameters
626 ----------
627 G : NetworkX graph
628 A graph
630 e : eccentricity dictionary, optional
631 A precomputed dictionary of eccentricities.
633 usebounds : bool, optional
634 If `True`, use extrema bounding (see Notes) when computing the center
635 for undirected graphs. Extrema bounding may accelerate the
636 distance calculation for some graphs. `usebounds` is ignored if `G` is
637 directed or if `e` is not `None`. Default is `False`.
639 weight : string, function, or None
640 If this is a string, then edge weights will be accessed via the
641 edge attribute with this key (that is, the weight of the edge
642 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
643 such edge attribute exists, the weight of the edge is assumed to
644 be one.
646 If this is a function, the weight of an edge is the value
647 returned by the function. The function must accept exactly three
648 positional arguments: the two endpoints of an edge and the
649 dictionary of edge attributes for that edge. The function must
650 return a number.
652 If this is None, every edge has weight/distance/cost 1.
654 Weights stored as floating point values can lead to small round-off
655 errors in distances. Use integer weights to avoid this.
657 Weights should be positive, since they are distances.
659 Returns
660 -------
661 c : list
662 List of nodes in center
664 Notes
665 -----
666 When ``usebounds=True``, the computation makes use of smart lower
667 and upper bounds and is often linear in the number of nodes, rather than
668 quadratic (except for some border cases such as complete graphs or circle
669 shaped-graphs).
671 Examples
672 --------
673 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
674 >>> list(nx.center(G))
675 [1, 3, 4]
677 See Also
678 --------
679 :func:`~networkx.algorithms.tree.distance_measures.center` : tree center
680 barycenter
681 periphery
682 :func:`~networkx.algorithms.tree.distance_measures.centroid` : tree centroid
683 """
684 if usebounds is True and e is None and not G.is_directed():
685 return _extrema_bounding(G, compute="center", weight=weight)
686 if e is None and weight is None and not G.is_directed() and nx.is_tree(G):
687 return nx.tree.center(G)
688 if e is None:
689 e = eccentricity(G, weight=weight)
690 radius = min(e.values())
691 p = [v for v in e if e[v] == radius]
692 return p
695@nx._dispatchable(edge_attrs="weight", mutates_input={"attr": 2})
696def barycenter(G, weight=None, attr=None, sp=None):
697 r"""Calculate barycenter of a connected graph, optionally with edge weights.
699 The :dfn:`barycenter` a
700 :func:`connected <networkx.algorithms.components.is_connected>` graph
701 :math:`G` is the subgraph induced by the set of its nodes :math:`v`
702 minimizing the objective function
704 .. math::
706 \sum_{u \in V(G)} d_G(u, v),
708 where :math:`d_G` is the (possibly weighted) :func:`path length
709 <networkx.algorithms.shortest_paths.generic.shortest_path_length>`.
710 The barycenter is also called the :dfn:`median`. See [West01]_, p. 78.
712 Parameters
713 ----------
714 G : :class:`networkx.Graph`
715 The connected graph :math:`G`.
716 weight : :class:`str`, optional
717 Passed through to
718 :func:`~networkx.algorithms.shortest_paths.generic.shortest_path_length`.
719 attr : :class:`str`, optional
720 If given, write the value of the objective function to each node's
721 `attr` attribute. Otherwise do not store the value.
722 sp : dict of dicts, optional
723 All pairs shortest path lengths as a dictionary of dictionaries
725 Returns
726 -------
727 list
728 Nodes of `G` that induce the barycenter of `G`.
730 Raises
731 ------
732 NetworkXNoPath
733 If `G` is disconnected. `G` may appear disconnected to
734 :func:`barycenter` if `sp` is given but is missing shortest path
735 lengths for any pairs.
736 ValueError
737 If `sp` and `weight` are both given.
739 Examples
740 --------
741 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
742 >>> nx.barycenter(G)
743 [1, 3, 4]
745 See Also
746 --------
747 center
748 periphery
749 :func:`~networkx.algorithms.tree.distance_measures.centroid` : tree centroid
750 """
751 if weight is None and attr is None and sp is None:
752 if not G.is_directed() and nx.is_tree(G):
753 return nx.tree.centroid(G)
755 if sp is None:
756 sp = nx.shortest_path_length(G, weight=weight)
757 else:
758 sp = sp.items()
759 if weight is not None:
760 raise ValueError("Cannot use both sp, weight arguments together")
761 smallest, barycenter_vertices, n = float("inf"), [], len(G)
762 for v, dists in sp:
763 if len(dists) < n:
764 raise nx.NetworkXNoPath(
765 f"Input graph {G} is disconnected, so every induced subgraph "
766 "has infinite barycentricity."
767 )
768 barycentricity = sum(dists.values())
769 if attr is not None:
770 G.nodes[v][attr] = barycentricity
771 if barycentricity < smallest:
772 smallest = barycentricity
773 barycenter_vertices = [v]
774 elif barycentricity == smallest:
775 barycenter_vertices.append(v)
776 if attr is not None:
777 nx._clear_cache(G)
778 return barycenter_vertices
781@not_implemented_for("directed")
782@nx._dispatchable(edge_attrs="weight")
783def resistance_distance(G, nodeA=None, nodeB=None, weight=None, invert_weight=True):
784 """Returns the resistance distance between pairs of nodes in graph G.
786 The resistance distance between two nodes of a graph is akin to treating
787 the graph as a grid of resistors with a resistance equal to the provided
788 weight [1]_, [2]_.
790 If weight is not provided, then a weight of 1 is used for all edges.
792 If two nodes are the same, the resistance distance is zero.
794 Parameters
795 ----------
796 G : NetworkX graph
797 A graph
799 nodeA : node or None, optional (default=None)
800 A node within graph G.
801 If None, compute resistance distance using all nodes as source nodes.
803 nodeB : node or None, optional (default=None)
804 A node within graph G.
805 If None, compute resistance distance using all nodes as target nodes.
807 weight : string or None, optional (default=None)
808 The edge data key used to compute the resistance distance.
809 If None, then each edge has weight 1.
811 invert_weight : boolean (default=True)
812 Proper calculation of resistance distance requires building the
813 Laplacian matrix with the reciprocal of the weight. Not required
814 if the weight is already inverted. Weight cannot be zero.
816 Returns
817 -------
818 rd : dict or float
819 If `nodeA` and `nodeB` are given, resistance distance between `nodeA`
820 and `nodeB`. If `nodeA` or `nodeB` is unspecified (the default), a
821 dictionary of nodes with resistance distances as the value.
823 Raises
824 ------
825 NetworkXNotImplemented
826 If `G` is a directed graph.
828 NetworkXError
829 If `G` is not connected, or contains no nodes,
830 or `nodeA` is not in `G` or `nodeB` is not in `G`.
832 Examples
833 --------
834 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
835 >>> round(nx.resistance_distance(G, 1, 3), 10)
836 0.625
838 Notes
839 -----
840 The implementation is based on Theorem A in [2]_. Self-loops are ignored.
841 Multi-edges are contracted in one edge with weight equal to the harmonic sum of the weights.
843 References
844 ----------
845 .. [1] Wikipedia
846 "Resistance distance."
847 https://en.wikipedia.org/wiki/Resistance_distance
848 .. [2] D. J. Klein and M. Randic.
849 Resistance distance.
850 J. of Math. Chem. 12:81-95, 1993.
851 """
852 import numpy as np
854 if len(G) == 0:
855 raise nx.NetworkXError("Graph G must contain at least one node.")
856 if not nx.is_connected(G):
857 raise nx.NetworkXError("Graph G must be strongly connected.")
858 if nodeA is not None and nodeA not in G:
859 raise nx.NetworkXError("Node A is not in graph G.")
860 if nodeB is not None and nodeB not in G:
861 raise nx.NetworkXError("Node B is not in graph G.")
863 G = G.copy()
864 node_list = list(G)
866 # Invert weights
867 if invert_weight and weight is not None:
868 if G.is_multigraph():
869 for u, v, k, d in G.edges(keys=True, data=True):
870 d[weight] = 1 / d[weight]
871 else:
872 for u, v, d in G.edges(data=True):
873 d[weight] = 1 / d[weight]
875 # Compute resistance distance using the Pseudo-inverse of the Laplacian
876 # Self-loops are ignored
877 L = nx.laplacian_matrix(G, weight=weight).todense()
878 Linv = np.linalg.pinv(L, hermitian=True)
880 # Return relevant distances
881 if nodeA is not None and nodeB is not None:
882 i = node_list.index(nodeA)
883 j = node_list.index(nodeB)
884 return Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
886 elif nodeA is not None:
887 i = node_list.index(nodeA)
888 d = {}
889 for n in G:
890 j = node_list.index(n)
891 d[n] = Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
892 return d
894 elif nodeB is not None:
895 j = node_list.index(nodeB)
896 d = {}
897 for n in G:
898 i = node_list.index(n)
899 d[n] = Linv.item(i, i) + Linv.item(j, j) - Linv.item(i, j) - Linv.item(j, i)
900 return d
902 else:
903 d = {}
904 for n in G:
905 i = node_list.index(n)
906 d[n] = {}
907 for n2 in G:
908 j = node_list.index(n2)
909 d[n][n2] = (
910 Linv.item(i, i)
911 + Linv.item(j, j)
912 - Linv.item(i, j)
913 - Linv.item(j, i)
914 )
915 return d
918@not_implemented_for("directed")
919@nx._dispatchable(edge_attrs="weight")
920def effective_graph_resistance(G, weight=None, invert_weight=True):
921 """Returns the Effective graph resistance of G.
923 Also known as the Kirchhoff index.
925 The effective graph resistance is defined as the sum
926 of the resistance distance of every node pair in G [1]_.
928 If weight is not provided, then a weight of 1 is used for all edges.
930 The effective graph resistance of a disconnected graph is infinite.
932 Parameters
933 ----------
934 G : NetworkX graph
935 A graph
937 weight : string or None, optional (default=None)
938 The edge data key used to compute the effective graph resistance.
939 If None, then each edge has weight 1.
941 invert_weight : boolean (default=True)
942 Proper calculation of resistance distance requires building the
943 Laplacian matrix with the reciprocal of the weight. Not required
944 if the weight is already inverted. Weight cannot be zero.
946 Returns
947 -------
948 RG : float
949 The effective graph resistance of `G`.
951 Raises
952 ------
953 NetworkXNotImplemented
954 If `G` is a directed graph.
956 NetworkXError
957 If `G` does not contain any nodes.
959 Examples
960 --------
961 >>> G = nx.Graph([(1, 2), (1, 3), (1, 4), (3, 4), (3, 5), (4, 5)])
962 >>> round(nx.effective_graph_resistance(G), 10)
963 10.25
965 Notes
966 -----
967 The implementation is based on Theorem 2.2 in [2]_. Self-loops are ignored.
968 Multi-edges are contracted in one edge with weight equal to the harmonic sum of the weights.
970 References
971 ----------
972 .. [1] Wolfram
973 "Kirchhoff Index."
974 https://mathworld.wolfram.com/KirchhoffIndex.html
975 .. [2] W. Ellens, F. M. Spieksma, P. Van Mieghem, A. Jamakovic, R. E. Kooij.
976 Effective graph resistance.
977 Lin. Alg. Appl. 435:2491-2506, 2011.
978 """
979 import numpy as np
981 if len(G) == 0:
982 raise nx.NetworkXError("Graph G must contain at least one node.")
984 # Disconnected graphs have infinite Effective graph resistance
985 if not nx.is_connected(G):
986 return float("inf")
988 # Invert weights
989 G = G.copy()
990 if invert_weight and weight is not None:
991 if G.is_multigraph():
992 for u, v, k, d in G.edges(keys=True, data=True):
993 d[weight] = 1 / d[weight]
994 else:
995 for u, v, d in G.edges(data=True):
996 d[weight] = 1 / d[weight]
998 # Get Laplacian eigenvalues
999 mu = np.sort(nx.laplacian_spectrum(G, weight=weight))
1001 # Compute Effective graph resistance based on spectrum of the Laplacian
1002 # Self-loops are ignored
1003 return float(np.sum(1 / mu[1:]) * G.number_of_nodes())
1006@nx.utils.not_implemented_for("directed")
1007@nx._dispatchable(edge_attrs="weight")
1008def kemeny_constant(G, *, weight=None):
1009 """Returns the Kemeny constant of the given graph.
1011 The *Kemeny constant* (or Kemeny's constant) of a graph `G`
1012 can be computed by regarding the graph as a Markov chain.
1013 The Kemeny constant is then the expected number of time steps
1014 to transition from a starting state i to a random destination state
1015 sampled from the Markov chain's stationary distribution.
1016 The Kemeny constant is independent of the chosen initial state [1]_.
1018 The Kemeny constant measures the time needed for spreading
1019 across a graph. Low values indicate a closely connected graph
1020 whereas high values indicate a spread-out graph.
1022 If weight is not provided, then a weight of 1 is used for all edges.
1024 Since `G` represents a Markov chain, the weights must be positive.
1026 Parameters
1027 ----------
1028 G : NetworkX graph
1030 weight : string or None, optional (default=None)
1031 The edge data key used to compute the Kemeny constant.
1032 If None, then each edge has weight 1.
1034 Returns
1035 -------
1036 float
1037 The Kemeny constant of the graph `G`.
1039 Raises
1040 ------
1041 NetworkXNotImplemented
1042 If the graph `G` is directed.
1044 NetworkXError
1045 If the graph `G` is not connected, or contains no nodes,
1046 or has edges with negative weights.
1048 Examples
1049 --------
1050 >>> G = nx.complete_graph(5)
1051 >>> round(nx.kemeny_constant(G), 10)
1052 3.2
1054 Notes
1055 -----
1056 The implementation is based on equation (3.3) in [2]_.
1057 Self-loops are allowed and indicate a Markov chain where
1058 the state can remain the same. Multi-edges are contracted
1059 in one edge with weight equal to the sum of the weights.
1061 References
1062 ----------
1063 .. [1] Wikipedia
1064 "Kemeny's constant."
1065 https://en.wikipedia.org/wiki/Kemeny%27s_constant
1066 .. [2] Lovász L.
1067 Random walks on graphs: A survey.
1068 Paul Erdös is Eighty, vol. 2, Bolyai Society,
1069 Mathematical Studies, Keszthely, Hungary (1993), pp. 1-46
1070 """
1071 import numpy as np
1072 import scipy as sp
1074 if len(G) == 0:
1075 raise nx.NetworkXError("Graph G must contain at least one node.")
1076 if not nx.is_connected(G):
1077 raise nx.NetworkXError("Graph G must be connected.")
1078 if nx.is_negatively_weighted(G, weight=weight):
1079 raise nx.NetworkXError("The weights of graph G must be nonnegative.")
1081 # Compute matrix H = D^-1/2 A D^-1/2
1082 A = nx.adjacency_matrix(G, weight=weight)
1083 n, m = A.shape
1084 diags = A.sum(axis=1)
1085 with np.errstate(divide="ignore"):
1086 diags_sqrt = 1.0 / np.sqrt(diags)
1087 diags_sqrt[np.isinf(diags_sqrt)] = 0
1088 DH = sp.sparse.dia_array((diags_sqrt, 0), shape=(m, n)).tocsr()
1089 H = DH @ (A @ DH)
1091 # Compute eigenvalues of H
1092 eig = np.sort(sp.linalg.eigvalsh(H.todense()))
1094 # Compute the Kemeny constant
1095 return float(np.sum(1 / (1 - eig[:-1])))