## Mercurial > repos > shellac > sam_consensus_v3

### view env/lib/python3.9/site-packages/networkx/algorithms/efficiency_measures.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

line wrap: on

line source

"""Provides functions for computing the efficiency of nodes and graphs.""" import networkx as nx from networkx.exception import NetworkXNoPath from ..utils import not_implemented_for __all__ = ["efficiency", "local_efficiency", "global_efficiency"] @not_implemented_for("directed") def efficiency(G, u, v): """Returns the efficiency of a pair of nodes in a graph. The *efficiency* of a pair of nodes is the multiplicative inverse of the shortest path distance between the nodes [1]_. Returns 0 if no path between nodes. Parameters ---------- G : :class:`networkx.Graph` An undirected graph for which to compute the average local efficiency. u, v : node Nodes in the graph ``G``. Returns ------- float Multiplicative inverse of the shortest path distance between the nodes. Notes ----- Edge weights are ignored when computing the shortest path distances. See also -------- local_efficiency global_efficiency References ---------- .. [1] Latora, Vito, and Massimo Marchiori. "Efficient behavior of small-world networks." *Physical Review Letters* 87.19 (2001): 198701. <https://doi.org/10.1103/PhysRevLett.87.198701> """ try: eff = 1 / nx.shortest_path_length(G, u, v) except NetworkXNoPath: eff = 0 return eff @not_implemented_for("directed") def global_efficiency(G): """Returns the average global efficiency of the graph. The *efficiency* of a pair of nodes in a graph is the multiplicative inverse of the shortest path distance between the nodes. The *average global efficiency* of a graph is the average efficiency of all pairs of nodes [1]_. Parameters ---------- G : :class:`networkx.Graph` An undirected graph for which to compute the average global efficiency. Returns ------- float The average global efficiency of the graph. Notes ----- Edge weights are ignored when computing the shortest path distances. See also -------- local_efficiency References ---------- .. [1] Latora, Vito, and Massimo Marchiori. "Efficient behavior of small-world networks." *Physical Review Letters* 87.19 (2001): 198701. <https://doi.org/10.1103/PhysRevLett.87.198701> """ n = len(G) denom = n * (n - 1) if denom != 0: lengths = nx.all_pairs_shortest_path_length(G) g_eff = 0 for source, targets in lengths: for target, distance in targets.items(): if distance > 0: g_eff += 1 / distance g_eff /= denom # g_eff = sum(1 / d for s, tgts in lengths # for t, d in tgts.items() if d > 0) / denom else: g_eff = 0 # TODO This can be made more efficient by computing all pairs shortest # path lengths in parallel. return g_eff @not_implemented_for("directed") def local_efficiency(G): """Returns the average local efficiency of the graph. The *efficiency* of a pair of nodes in a graph is the multiplicative inverse of the shortest path distance between the nodes. The *local efficiency* of a node in the graph is the average global efficiency of the subgraph induced by the neighbors of the node. The *average local efficiency* is the average of the local efficiencies of each node [1]_. Parameters ---------- G : :class:`networkx.Graph` An undirected graph for which to compute the average local efficiency. Returns ------- float The average local efficiency of the graph. Notes ----- Edge weights are ignored when computing the shortest path distances. See also -------- global_efficiency References ---------- .. [1] Latora, Vito, and Massimo Marchiori. "Efficient behavior of small-world networks." *Physical Review Letters* 87.19 (2001): 198701. <https://doi.org/10.1103/PhysRevLett.87.198701> """ # TODO This summation can be trivially parallelized. efficiency_list = (global_efficiency(G.subgraph(G[v])) for v in G) return sum(efficiency_list) / len(G)