<s> """<STR_LIT>""" <EOL> __author__ = """<STR_LIT>""" <EOL> __all__ = [ '<STR_LIT>' , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' ] <EOL> import networkx as nx <EOL> from networkx . algorithms . centrality . betweenness import _single_source_dijkstra_path_basic as dijkstra <EOL> from networkx . algorithms . centrality . betweenness import _single_source_shortest_path_basic as shortest_path <EOL> def betweenness_centrality_subset ( G , sources , targets , <EOL> normalized = False , <EOL> weight = None ) : <EOL> """<STR_LIT>""" <EOL> b = dict . fromkeys ( G , <NUM_LIT:0.0> ) <EOL> for s in sources : <EOL> if weight is None : <EOL> S , P , sigma = shortest_path ( G , s ) <EOL> else : <EOL> S , P , sigma = dijkstra ( G , s , weight ) <EOL> b = _accumulate_subset ( b , S , P , sigma , s , targets ) <EOL> b = _rescale ( b , len ( G ) , normalized = normalized , directed = G . is_directed ( ) ) <EOL> return b <EOL> def edge_betweenness_centrality_subset ( G , sources , targets , <EOL> normalized = False , <EOL> weight = None ) : <EOL> """<STR_LIT>""" <EOL> b = dict . fromkeys ( G , <NUM_LIT:0.0> ) <EOL> b . update ( dict . fromkeys ( G . edges ( ) , <NUM_LIT:0.0> ) ) <EOL> for s in sources : <EOL> if weight is None : <EOL> S , P , sigma = shortest_path ( G , s ) <EOL> else : <EOL> S , P , sigma = dijkstra ( G , s , weight ) <EOL> b = _accumulate_edges_subset ( b , S , P , sigma , s , targets ) <EOL> for n in G : <EOL> del b [ n ] <EOL> b = _rescale_e ( b , len ( G ) , normalized = normalized , directed = G . is_directed ( ) ) <EOL> return b <EOL> def betweenness_centrality_source ( G , normalized = True , weight = None , sources = None ) : <EOL> if sources is None : <EOL> sources = G . nodes ( ) <EOL> targets = G . nodes ( ) <EOL> return betweenness_centrality_subset ( G , sources , targets , normalized , weight ) <EOL> def _accumulate_subset ( betweenness , S , P , sigma , s , targets ) : <EOL> delta = dict . fromkeys ( S , <NUM_LIT:0> ) <EOL> target_set = set ( targets ) <EOL> while S : <EOL> w = S . pop ( ) <EOL> for v in P [ w ] : <EOL> if w in target_set : <EOL> delta [ v ] += ( sigma [ v ] / sigma [ w ] ) * ( <NUM_LIT:1.0> + delta [ w ] ) <EOL> else : <EOL> delta [ v ] += delta [ w ] / len ( P [ w ] ) <EOL> if w != s : <EOL> betweenness [ w ] += delta [ w ] <EOL> return betweenness <EOL> def _accumulate_edges_subset ( betweenness , S , P , sigma , s , targets ) : <EOL> delta = dict . fromkeys ( S , <NUM_LIT:0> ) <EOL> target_set = set ( targets ) <EOL> while S : <EOL> w = S . pop ( ) <EOL> for v in P [ w ] : <EOL> if w in target_set : <EOL> c = ( sigma [ v ] / sigma [ w ] ) * ( <NUM_LIT:1.0> + delta [ w ] ) <EOL> else : <EOL> c = delta [ w ] / len ( P [ w ] ) <EOL> if ( v , w ) not in betweenness : <EOL> betweenness [ ( w , v ) ] += c <EOL> else : <EOL> betweenness [ ( v , w ) ] += c <EOL> delta [ v ] += c <EOL> if w != s : <EOL> betweenness [ w ] += delta [ w ] <EOL> return betweenness <EOL> def _rescale ( betweenness , n , normalized , directed = False ) : <EOL> if normalized is True : <EOL> if n <= <NUM_LIT:2> : <EOL> scale = None <EOL> else : <EOL> scale = <NUM_LIT:1.0> / ( ( n - <NUM_LIT:1> ) * ( n - <NUM_LIT:2> ) ) <EOL> else : <EOL> if not directed : <EOL> scale = <NUM_LIT:1.0> / <NUM_LIT> <EOL> else : <EOL> scale = None <EOL> if scale is not None : <EOL> for v in betweenness : <EOL> betweenness [ v ] *= scale <EOL> return betweenness <EOL> def _rescale_e ( betweenness , n , normalized , directed = False ) : <EOL> if normalized is True : <EOL> if n <= <NUM_LIT:1> : <EOL> scale = None <EOL> else : <EOL> scale = <NUM_LIT:1.0> / ( n * ( n - <NUM_LIT:1> ) ) <EOL> else : <EOL> if not directed : <EOL> scale = <NUM_LIT:1.0> / <NUM_LIT> <EOL> else : <EOL> scale = None <EOL> if scale is not None : <EOL> for v in betweenness : <EOL> betweenness [ v ] *= scale <EOL> return betweenness </s>
