Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / centrality / betweenness_subset.py @ 5cef0f13

 1 ```# Copyright (C) 2004-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# ``` ```# Author: Aric Hagberg (hagberg@lanl.gov) ``` ```"""Betweenness centrality measures for subsets of nodes.""" ``` ```import networkx as nx ``` ```from networkx.algorithms.centrality.betweenness import\ ``` ``` _single_source_dijkstra_path_basic as dijkstra ``` ```from networkx.algorithms.centrality.betweenness import\ ``` ``` _single_source_shortest_path_basic as shortest_path ``` ```__all__ = ['betweenness_centrality_subset', 'betweenness_centrality_source', ``` ``` 'edge_betweenness_centrality_subset'] ``` ```def betweenness_centrality_subset(G, sources, targets, normalized=False, ``` ``` weight=None): ``` ``` r"""Compute betweenness centrality for a subset of nodes. ``` ``` ``` ``` .. math:: ``` ``` ``` ``` c_B(v) =\sum_{s\in S, t \in T} \frac{\sigma(s, t|v)}{\sigma(s, t)} ``` ``` ``` ``` where \$S\$ is the set of sources, \$T\$ is the set of targets, ``` ``` \$\sigma(s, t)\$ is the number of shortest \$(s, t)\$-paths, ``` ``` and \$\sigma(s, t|v)\$ is the number of those paths ``` ``` passing through some node \$v\$ other than \$s, t\$. ``` ``` If \$s = t\$, \$\sigma(s, t) = 1\$, ``` ``` and if \$v \in {s, t}\$, \$\sigma(s, t|v) = 0\$ _. ``` ``` ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` A NetworkX graph. ``` ``` ``` ``` sources: list of nodes ``` ``` Nodes to use as sources for shortest paths in betweenness ``` ``` ``` ``` targets: list of nodes ``` ``` Nodes to use as targets for shortest paths in betweenness ``` ``` ``` ``` normalized : bool, optional ``` ``` If True the betweenness values are normalized by \$2/((n-1)(n-2))\$ ``` ``` for graphs, and \$1/((n-1)(n-2))\$ for directed graphs where \$n\$ ``` ``` is the number of nodes in G. ``` ``` ``` ``` weight : None or string, optional (default=None) ``` ``` If None, all edge weights are considered equal. ``` ``` Otherwise holds the name of the edge attribute used as weight. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` nodes : dictionary ``` ``` Dictionary of nodes with betweenness centrality as the value. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` edge_betweenness_centrality ``` ``` load_centrality ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` The basic algorithm is from _. ``` ``` ``` ``` For weighted graphs the edge weights must be greater than zero. ``` ``` Zero edge weights can produce an infinite number of equal length ``` ``` paths between pairs of nodes. ``` ``` ``` ``` The normalization might seem a little strange but it is the same ``` ``` as in betweenness_centrality() and is designed to make ``` ``` betweenness_centrality(G) be the same as ``` ``` betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()). ``` ``` ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. ``` ``` Journal of Mathematical Sociology 25(2):163-177, 2001. ``` ``` http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf ``` ``` ..  Ulrik Brandes: On Variants of Shortest-Path Betweenness ``` ``` Centrality and their Generic Computation. ``` ``` Social Networks 30(2):136-145, 2008. ``` ``` http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf ``` ``` """ ``` ``` b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G ``` ``` for s in sources: ``` ``` # single source shortest paths ``` ``` if weight is None: # use BFS ``` ``` S, P, sigma = shortest_path(G, s) ``` ``` else: # use Dijkstra's algorithm ``` ``` S, P, sigma = dijkstra(G, s, weight) ``` ``` b = _accumulate_subset(b, S, P, sigma, s, targets) ``` ``` b = _rescale(b, len(G), normalized=normalized, directed=G.is_directed()) ``` ``` return b ``` ```def edge_betweenness_centrality_subset(G, sources, targets, normalized=False, ``` ``` weight=None): ``` ``` r"""Compute betweenness centrality for edges for a subset of nodes. ``` ``` ``` ``` .. math:: ``` ``` ``` ``` c_B(v) =\sum_{s\in S,t \in T} \frac{\sigma(s, t|e)}{\sigma(s, t)} ``` ``` ``` ``` where \$S\$ is the set of sources, \$T\$ is the set of targets, ``` ``` \$\sigma(s, t)\$ is the number of shortest \$(s, t)\$-paths, ``` ``` and \$\sigma(s, t|e)\$ is the number of those paths ``` ``` passing through edge \$e\$ _. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` A networkx graph. ``` ``` ``` ``` sources: list of nodes ``` ``` Nodes to use as sources for shortest paths in betweenness ``` ``` ``` ``` targets: list of nodes ``` ``` Nodes to use as targets for shortest paths in betweenness ``` ``` ``` ``` normalized : bool, optional ``` ``` If True the betweenness values are normalized by `2/(n(n-1))` ``` ``` for graphs, and `1/(n(n-1))` for directed graphs where `n` ``` ``` is the number of nodes in G. ``` ``` ``` ``` weight : None or string, optional (default=None) ``` ``` If None, all edge weights are considered equal. ``` ``` Otherwise holds the name of the edge attribute used as weight. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` edges : dictionary ``` ``` Dictionary of edges with Betweenness centrality as the value. ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` betweenness_centrality ``` ``` edge_load ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` The basic algorithm is from _. ``` ``` ``` ``` For weighted graphs the edge weights must be greater than zero. ``` ``` Zero edge weights can produce an infinite number of equal length ``` ``` paths between pairs of nodes. ``` ``` ``` ``` The normalization might seem a little strange but it is the same ``` ``` as in edge_betweenness_centrality() and is designed to make ``` ``` edge_betweenness_centrality(G) be the same as ``` ``` edge_betweenness_centrality_subset(G,sources=G.nodes(),targets=G.nodes()). ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Ulrik Brandes, A Faster Algorithm for Betweenness Centrality. ``` ``` Journal of Mathematical Sociology 25(2):163-177, 2001. ``` ``` http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf ``` ``` ..  Ulrik Brandes: On Variants of Shortest-Path Betweenness ``` ``` Centrality and their Generic Computation. ``` ``` Social Networks 30(2):136-145, 2008. ``` ``` http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf ``` ``` """ ``` ``` b = dict.fromkeys(G, 0.0) # b[v]=0 for v in G ``` ``` b.update(dict.fromkeys(G.edges(), 0.0)) # b[e] for e in G.edges() ``` ``` for s in sources: ``` ``` # single source shortest paths ``` ``` if weight is None: # use BFS ``` ``` S, P, sigma = shortest_path(G, s) ``` ``` else: # use Dijkstra's algorithm ``` ``` S, P, sigma = dijkstra(G, s, weight) ``` ``` b = _accumulate_edges_subset(b, S, P, sigma, s, targets) ``` ``` for n in G: # remove nodes to only return edges ``` ``` del b[n] ``` ``` b = _rescale_e(b, len(G), normalized=normalized, directed=G.is_directed()) ``` ``` return b ``` ```# obsolete name ``` ```def betweenness_centrality_source(G, normalized=True, weight=None, ``` ``` sources=None): ``` ``` if sources is None: ``` ``` sources = G.nodes() ``` ``` targets = list(G) ``` ``` return betweenness_centrality_subset(G, sources, targets, normalized, ``` ``` weight) ``` ```def _accumulate_subset(betweenness, S, P, sigma, s, targets): ``` ``` delta = dict.fromkeys(S, 0.0) ``` ``` target_set = set(targets) - {s} ``` ``` while S: ``` ``` w = S.pop() ``` ``` if w in target_set: ``` ``` coeff = (delta[w] + 1.0)/ sigma[w] ``` ``` else: ``` ``` coeff = delta[w] / sigma[w] ``` ``` for v in P[w]: ``` ``` delta[v] += sigma[v] * coeff ``` ``` if w != s: ``` ``` betweenness[w] += delta[w] ``` ``` return betweenness ``` ```def _accumulate_edges_subset(betweenness, S, P, sigma, s, targets): ``` ``` """edge_betweenness_centrality_subset helper.""" ``` ``` delta = dict.fromkeys(S, 0) ``` ``` target_set = set(targets) ``` ``` while S: ``` ``` w = S.pop() ``` ``` for v in P[w]: ``` ``` if w in target_set: ``` ``` c = (sigma[v] / sigma[w]) * (1.0 + delta[w]) ``` ``` else: ``` ``` c = delta[w] / len(P[w]) ``` ``` if (v, w) not in betweenness: ``` ``` betweenness[(w, v)] += c ``` ``` else: ``` ``` betweenness[(v, w)] += c ``` ``` delta[v] += c ``` ``` if w != s: ``` ``` betweenness[w] += delta[w] ``` ``` return betweenness ``` ```def _rescale(betweenness, n, normalized, directed=False): ``` ``` """betweenness_centrality_subset helper.""" ``` ``` if normalized: ``` ``` if n <= 2: ``` ``` scale = None # no normalization b=0 for all nodes ``` ``` else: ``` ``` scale = 1.0 / ((n - 1) * (n - 2)) ``` ``` else: # rescale by 2 for undirected graphs ``` ``` if not directed: ``` ``` scale = 0.5 ``` ``` else: ``` ``` scale = None ``` ``` if scale is not None: ``` ``` for v in betweenness: ``` ``` betweenness[v] *= scale ``` ``` return betweenness ``` ```def _rescale_e(betweenness, n, normalized, directed=False): ``` ``` """edge_betweenness_centrality_subset helper.""" ``` ``` if normalized: ``` ``` if n <= 1: ``` ``` scale = None # no normalization b=0 for all nodes ``` ``` else: ``` ``` scale = 1.0 / (n * (n - 1)) ``` ``` else: # rescale by 2 for undirected graphs ``` ``` if not directed: ``` ``` scale = 0.5 ``` ``` else: ``` ``` scale = None ``` ``` if scale is not None: ``` ``` for v in betweenness: ``` ``` betweenness[v] *= scale ``` ``` return betweenness ```