1 """ 2 Load centrality. 3 4 """ 5 # Copyright (C) 2004-2010 by 6 # Aric Hagberg <hagberg (at] lanl.gov> 7 # Dan Schult <dschult (at] colgate.edu> 8 # Pieter Swart <swart (at] lanl.gov> 9 # All rights reserved. 10 # BSD license. 11 __author__ = "\n".join(['Aric Hagberg (hagberg (at] lanl.gov)', 12 'Pieter Swart (swart (at] lanl.gov)', 13 'Sasha Gutfraind (ag362 (at] cornell.edu)']) 14 15 __all__ = ['load_centrality', 16 'edge_load'] 17 18 import networkx as nx 19 20 def newman_betweenness_centrality(G,v=None,cutoff=None, 21 normalized=True, 22 weight=None): 23 """Compute load centrality for nodes. 24 25 The load centrality of a node is the fraction of all shortest 26 paths that pass through that node. 27 28 Parameters 29 ---------- 30 G : graph 31 A networkx graph 32 33 normalized : bool, optional 34 If True the betweenness values are normalized by b=b/(n-1)(n-2) where 35 n is the number of nodes in G. 36 37 weight : None or string, optional 38 If None, edge weights are ignored. 39 Otherwise holds the name of the edge attribute used as weight. 40 41 cutoff : bool, optional 42 If specified, only consider paths of length <= cutoff. 43 44 Returns 45 ------- 46 nodes : dictionary 47 Dictionary of nodes with centrality as the value. 48 49 50 See Also 51 -------- 52 betweenness_centrality() 53 54 Notes 55 ----- 56 Load centrality is slightly different than betweenness. 57 For this load algorithm see the reference 58 Scientific collaboration networks: II. 59 Shortest paths, weighted networks, and centrality, 60 M. E. J. Newman, Phys. Rev. E 64, 016132 (2001). 61 62 """ 63 if v is not None: # only one node 64 betweenness=0.0 65 for source in G: 66 ubetween = _node_betweenness(G, source, cutoff, False, weight) 67 betweenness += ubetween[v] if v in ubetween else 0 68 if normalized: 69 order = G.order() 70 if order <= 2: 71 return betweenness # no normalization b=0 for all nodes 72 betweenness *= 1.0 / ((order-1) * (order-2)) 73 return betweenness 74 else: 75 betweenness = {}.fromkeys(G,0.0) 76 for source in betweenness: 77 ubetween = _node_betweenness(G, source, cutoff, False, weight) 78 for vk in ubetween: 79 betweenness[vk] += ubetween[vk] 80 if normalized: 81 order = G.order() 82 if order <= 2: 83 return betweenness # no normalization b=0 for all nodes 84 scale = 1.0 / ((order-1) * (order-2)) 85 for v in betweenness: 86 betweenness[v] *= scale 87 return betweenness # all nodes 88 89 def _node_betweenness(G,source,cutoff=False,normalized=True,weight=None): 90 """Node betweenness helper: 91 see betweenness_centrality for what you probably want. 92 93 This actually computes "load" and not betweenness. 94 See https://networkx.lanl.gov/ticket/103 95 96 This calculates the load of each node for paths from a single source. 97 (The fraction of number of shortests paths from source that go 98 through each node.) 99 100 To get the load for a node you need to do all-pairs shortest paths. 101 102 If weight is not None then use Dijkstra for finding shortest paths. 103 In this case a cutoff is not implemented and so is ignored. 104 105 """ 106 107 # get the predecessor and path length data 108 if weight is None: 109 (pred,length)=nx.predecessor(G,source,cutoff=cutoff,return_seen=True) 110 else: 111 (pred,length)=nx.dijkstra_predecessor_and_distance(G,source,weight=weight) 112 113 # order the nodes by path length 114 onodes = [ (l,vert) for (vert,l) in length.items() ] 115 onodes.sort() 116 onodes[:] = [vert for (l,vert) in onodes if l>0] 117 118 # intialize betweenness 119 between={}.fromkeys(length,1.0) 120 121 while onodes: 122 v=onodes.pop() 123 if v in pred: 124 num_paths=len(pred[v]) # Discount betweenness if more than 125 for x in pred[v]: # one shortest path. 126 if x==source: # stop if hit source because all remaining v 127 break # also have pred[v]==[source] 128 between[x]+=between[v]/float(num_paths) 129 # remove source 130 for v in between: 131 between[v]-=1 132 # rescale to be between 0 and 1 133 if normalized: 134 l=len(between) 135 if l > 2: 136 scale=1.0/float((l-1)*(l-2)) # 1/the number of possible paths 137 for v in between: 138 between[v] *= scale 139 return between 140 141 142 load_centrality=newman_betweenness_centrality 143 144 145 def edge_load(G,nodes=None,cutoff=False): 146 """Compute edge load. 147 148 WARNING: 149 150 This module is for demonstration and testing purposes. 151 152 """ 153 betweenness={} 154 if not nodes: # find betweenness for every node in graph 155 nodes=G.nodes() # that probably is what you want... 156 for source in nodes: 157 ubetween=_edge_betweenness(G,source,nodes,cutoff=cutoff) 158 for v in ubetween.keys(): 159 b=betweenness.setdefault(v,0) # get or set default 160 betweenness[v]=ubetween[v]+b # cumulative total 161 return betweenness 162 163 def _edge_betweenness(G,source,nodes,cutoff=False): 164 """ 165 Edge betweenness helper. 166 """ 167 between={} 168 # get the predecessor data 169 #(pred,length)=_fast_predecessor(G,source,cutoff=cutoff) 170 (pred,length)=nx.predecessor(G,source,cutoff=cutoff,return_seen=True) 171 # order the nodes by path length 172 onodes = [ nn for dd,nn in sorted( (dist,n) for n,dist in length.items() )] 173 # intialize betweenness, doesn't account for any edge weights 174 for u,v in G.edges(nodes): 175 between[(u,v)]=1.0 176 between[(v,u)]=1.0 177 178 while onodes: # work through all paths 179 v=onodes.pop() 180 if v in pred: 181 num_paths=len(pred[v]) # Discount betweenness if more than 182 for w in pred[v]: # one shortest path. 183 if w in pred: 184 num_paths=len(pred[w]) # Discount betweenness, mult path 185 for x in pred[w]: 186 between[(w,x)]+=between[(v,w)]/num_paths 187 between[(x,w)]+=between[(w,v)]/num_paths 188 return between 189 190 191
