diff options
Diffstat (limited to 'lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/betweenness_subset.py')
| -rw-r--r-- | lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/betweenness_subset.py | 263 |
1 files changed, 263 insertions, 0 deletions
diff --git a/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/betweenness_subset.py b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/betweenness_subset.py new file mode 100644 index 0000000..cd4f8a2 --- /dev/null +++ b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/centrality/betweenness_subset.py @@ -0,0 +1,263 @@ +""" +Betweenness centrality measures for subsets of nodes. +""" +# Copyright (C) 2004-2011 by +# Aric Hagberg <hagberg@lanl.gov> +# Dan Schult <dschult@colgate.edu> +# Pieter Swart <swart@lanl.gov> +# All rights reserved. +# BSD license. +__author__ = """Aric Hagberg (hagberg@lanl.gov)""" + +__all__ = ['betweenness_centrality_subset', + 'edge_betweenness_centrality_subset', + 'betweenness_centrality_source'] + +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 + + +def betweenness_centrality_subset(G,sources,targets, + normalized=False, + weight=None): + """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` [2]_. + + + Parameters + ---------- + G : 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 + 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 [1]_. + + 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 + ---------- + .. [1] 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 + .. [2] 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): + """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` [2]_. + + 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 + 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 [1]_. + + 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 + ---------- + .. [1] 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 + .. [2] 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=G.nodes() + return betweenness_centrality_subset(G,sources,targets,normalized,weight) + + +def _accumulate_subset(betweenness,S,P,sigma,s,targets): + delta=dict.fromkeys(S,0) + target_set=set(targets) + while S: + w=S.pop() + for v in P[w]: + if w in target_set: + delta[v]+=(sigma[v]/sigma[w])*(1.0+delta[w]) + else: + delta[v]+=delta[w]/len(P[w]) + if w != s: + betweenness[w]+=delta[w] + return betweenness + +def _accumulate_edges_subset(betweenness,S,P,sigma,s,targets): + 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): + if normalized is True: + 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=1.0/2.0 + 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): + if normalized is True: + 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=1.0/2.0 + else: + scale=None + if scale is not None: + for v in betweenness: + betweenness[v] *= scale + return betweenness |