| """ |
| Betweenness centrality measures. |
| """ |
| # 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. |
| import heapq |
| import networkx as nx |
| import random |
| __author__ = """Aric Hagberg (hagberg@lanl.gov)""" |
| |
| __all__ = ['betweenness_centrality', |
| 'edge_betweenness_centrality', |
| 'edge_betweenness'] |
| |
| def betweenness_centrality(G, k=None, normalized=True, weight=None, |
| endpoints=False, |
| seed=None): |
| r"""Compute the shortest-path betweenness centrality for nodes. |
| |
| Betweenness centrality of a node `v` is the sum of the |
| fraction of all-pairs shortest paths that pass through `v`: |
| |
| .. math:: |
| |
| c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|v)}{\sigma(s, t)} |
| |
| where `V` is the set of nodes, `\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 |
| A NetworkX graph |
| |
| k : int, optional (default=None) |
| If k is not None use k node samples to estimate betweenness. |
| The value of k <= n where n is the number of nodes in the graph. |
| Higher values give better approximation. |
| |
| 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. |
| |
| endpoints : bool, optional |
| If True include the endpoints in the shortest path counts. |
| |
| Returns |
| ------- |
| nodes : dictionary |
| Dictionary of nodes with betweenness centrality as the value. |
| |
| See Also |
| -------- |
| edge_betweenness_centrality |
| load_centrality |
| |
| Notes |
| ----- |
| The algorithm is from Ulrik Brandes [1]_. |
| See [2]_ for details on algorithms for variations and related metrics. |
| |
| For approximate betweenness calculations set k=#samples to use |
| k nodes ("pivots") to estimate the betweenness values. For an estimate |
| of the number of pivots needed see [3]_. |
| |
| 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. |
| |
| References |
| ---------- |
| .. [1] A Faster Algorithm for Betweenness Centrality. |
| Ulrik Brandes, |
| 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 |
| .. [3] Ulrik Brandes and Christian Pich: |
| Centrality Estimation in Large Networks. |
| International Journal of Bifurcation and Chaos 17(7):2303-2318, 2007. |
| http://www.inf.uni-konstanz.de/algo/publications/bp-celn-06.pdf |
| """ |
| betweenness=dict.fromkeys(G,0.0) # b[v]=0 for v in G |
| if k is None: |
| nodes = G |
| else: |
| random.seed(seed) |
| nodes = random.sample(G.nodes(), k) |
| for s in nodes: |
| # single source shortest paths |
| if weight is None: # use BFS |
| S,P,sigma=_single_source_shortest_path_basic(G,s) |
| else: # use Dijkstra's algorithm |
| S,P,sigma=_single_source_dijkstra_path_basic(G,s,weight) |
| # accumulation |
| if endpoints: |
| betweenness=_accumulate_endpoints(betweenness,S,P,sigma,s) |
| else: |
| betweenness=_accumulate_basic(betweenness,S,P,sigma,s) |
| # rescaling |
| betweenness=_rescale(betweenness, len(G), |
| normalized=normalized, |
| directed=G.is_directed(), |
| k=k) |
| return betweenness |
| |
| |
| def edge_betweenness_centrality(G,normalized=True,weight=None): |
| r"""Compute betweenness centrality for edges. |
| |
| Betweenness centrality of an edge `e` is the sum of the |
| fraction of all-pairs shortest paths that pass through `e`: |
| |
| .. math:: |
| |
| c_B(v) =\sum_{s,t \in V} \frac{\sigma(s, t|e)}{\sigma(s, t)} |
| |
| where `V` is the set of nodes,`\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 |
| |
| 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 algorithm is from Ulrik Brandes [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. |
| |
| References |
| ---------- |
| .. [1] A Faster Algorithm for Betweenness Centrality. Ulrik Brandes, |
| 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 |
| """ |
| betweenness=dict.fromkeys(G,0.0) # b[v]=0 for v in G |
| # b[e]=0 for e in G.edges() |
| betweenness.update(dict.fromkeys(G.edges(),0.0)) |
| for s in G: |
| # single source shortest paths |
| if weight is None: # use BFS |
| S,P,sigma=_single_source_shortest_path_basic(G,s) |
| else: # use Dijkstra's algorithm |
| S,P,sigma=_single_source_dijkstra_path_basic(G,s,weight) |
| # accumulation |
| betweenness=_accumulate_edges(betweenness,S,P,sigma,s) |
| # rescaling |
| for n in G: # remove nodes to only return edges |
| del betweenness[n] |
| betweenness=_rescale_e(betweenness, len(G), |
| normalized=normalized, |
| directed=G.is_directed()) |
| return betweenness |
| |
| # obsolete name |
| def edge_betweenness(G,normalized=True,weight=None): |
| return edge_betweenness_centrality(G,normalized,weight) |
| |
| |
| # helpers for betweenness centrality |
| |
| def _single_source_shortest_path_basic(G,s): |
| S=[] |
| P={} |
| for v in G: |
| P[v]=[] |
| sigma=dict.fromkeys(G,0.0) # sigma[v]=0 for v in G |
| D={} |
| sigma[s]=1.0 |
| D[s]=0 |
| Q=[s] |
| while Q: # use BFS to find shortest paths |
| v=Q.pop(0) |
| S.append(v) |
| Dv=D[v] |
| sigmav=sigma[v] |
| for w in G[v]: |
| if w not in D: |
| Q.append(w) |
| D[w]=Dv+1 |
| if D[w]==Dv+1: # this is a shortest path, count paths |
| sigma[w] += sigmav |
| P[w].append(v) # predecessors |
| return S,P,sigma |
| |
| |
| |
| def _single_source_dijkstra_path_basic(G,s,weight='weight'): |
| # modified from Eppstein |
| S=[] |
| P={} |
| for v in G: |
| P[v]=[] |
| sigma=dict.fromkeys(G,0.0) # sigma[v]=0 for v in G |
| D={} |
| sigma[s]=1.0 |
| push=heapq.heappush |
| pop=heapq.heappop |
| seen = {s:0} |
| Q=[] # use Q as heap with (distance,node id) tuples |
| push(Q,(0,s,s)) |
| while Q: |
| (dist,pred,v)=pop(Q) |
| if v in D: |
| continue # already searched this node. |
| sigma[v] += sigma[pred] # count paths |
| S.append(v) |
| D[v] = dist |
| for w,edgedata in G[v].items(): |
| vw_dist = dist + edgedata.get(weight,1) |
| if w not in D and (w not in seen or vw_dist < seen[w]): |
| seen[w] = vw_dist |
| push(Q,(vw_dist,v,w)) |
| sigma[w]=0.0 |
| P[w]=[v] |
| elif vw_dist==seen[w]: # handle equal paths |
| sigma[w] += sigma[v] |
| P[w].append(v) |
| return S,P,sigma |
| |
| def _accumulate_basic(betweenness,S,P,sigma,s): |
| delta=dict.fromkeys(S,0) |
| while S: |
| w=S.pop() |
| coeff=(1.0+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_endpoints(betweenness,S,P,sigma,s): |
| betweenness[s]+=len(S)-1 |
| delta=dict.fromkeys(S,0) |
| while S: |
| w=S.pop() |
| coeff=(1.0+delta[w])/sigma[w] |
| for v in P[w]: |
| delta[v] += sigma[v]*coeff |
| if w != s: |
| betweenness[w] += delta[w]+1 |
| return betweenness |
| |
| def _accumulate_edges(betweenness,S,P,sigma,s): |
| delta=dict.fromkeys(S,0) |
| while S: |
| w=S.pop() |
| coeff=(1.0+delta[w])/sigma[w] |
| for v in P[w]: |
| c=sigma[v]*coeff |
| 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,k=None): |
| 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: |
| if k is not None: |
| scale=scale*n/k |
| 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 |