Package networkx :: Module centrality
[hide private]
[frames] | no frames]

Module centrality

source code

Centrality measures.


Author: Aric Hagberg (hagberg@lanl.gov) Pieter Swart (swart@lanl.gov) Sasha Gutfraind (ag362@cornell.edu)

Functions [hide private]
 
brandes_betweenness_centrality(G, normalized=True, weighted_edges=False)
Compute the betweenness centrality for nodes in G: the fraction of number of shortests paths that pass through each node.
source code
 
newman_betweenness_centrality(G, v=None, cutoff=None, normalized=True, weighted_edges=False)
"Load" centrality for nodes.
source code
 
_node_betweenness(G, source, cutoff=False, normalized=True, weighted_edges=False)
Node betweenness helper: see betweenness_centrality for what you probably want.
source code
 
betweenness_centrality(G, normalized=True, weighted_edges=False)
Compute the betweenness centrality for nodes in G: the fraction of number of shortests paths that pass through each node.
source code
 
load_centrality(G, v=None, cutoff=None, normalized=True, weighted_edges=False)
"Load" centrality for nodes.
source code
 
betweenness_centrality_source(G, normalized=True, weighted_edges=False, sources=None)
Enchanced version of the method in centrality module that allows specifying a list of sources (subgraph).
source code
 
edge_betweenness(G, normalized=True, weighted_edges=False, sources=None)
Edge betweenness centrality.
source code
 
_brandes_betweenness_helper(G, root, weighted_edges)
Helper for betweenness centrality and edge betweenness centrality.
source code
 
edge_load(G, nodes=False, cutoff=False)
Edge Betweenness
source code
 
_edge_betweenness(G, source, nodes, cutoff=False)
Edge betweenness helper.
source code
 
degree_centrality(G, v=None)
Degree centrality for nodes (fraction of nodes connected to).
source code
 
closeness_centrality(G, v=None, weighted_edges=False)
Closeness centrality for nodes (1/average distance to all nodes).
source code
 
_test_suite() source code
Function Details [hide private]

brandes_betweenness_centrality(G, normalized=True, weighted_edges=False)

source code 

Compute the betweenness centrality for nodes in G: the fraction of number of shortests paths that pass through each node.

The keyword normalized (default=True) specifies whether the betweenness values are normalized by b=b/(n-1)(n-2) where n is the number of nodes in G.

The keyword weighted_edges (default=False) specifies whether to use edge weights (otherwise weights are all assumed equal).

The algorithm is from 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

newman_betweenness_centrality(G, v=None, cutoff=None, normalized=True, weighted_edges=False)

source code 

"Load" centrality for nodes.

This actually computes 'load' and not betweenness. See https://networkx.lanl.gov/ticket/103

The fraction of number of shortests paths that go through each node counted according to the algorithm in

Scientific collaboration networks: II. Shortest paths, weighted networks, and centrality, M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).

Returns a dictionary of betweenness values keyed by node. The betweenness is normalized to be between [0,1].

If normalized=False the resulting betweenness is not normalized.

If weighted_edges is True then use Dijkstra for finding shortest paths.

_node_betweenness(G, source, cutoff=False, normalized=True, weighted_edges=False)

source code 

Node betweenness helper: see betweenness_centrality for what you probably want.

This actually computes "load" and not betweenness. See https://networkx.lanl.gov/ticket/103

This calculates the load of each node for paths from a single source. (The fraction of number of shortests paths from source that go through each node.)

To get the load for a node you need to do all-pairs shortest paths.

If weighted_edges is True then use Dijkstra for finding shortest paths. In this case a cutoff is not implemented and so is ignored.

betweenness_centrality(G, normalized=True, weighted_edges=False)

source code 

Compute the betweenness centrality for nodes in G: the fraction of number of shortests paths that pass through each node.

The keyword normalized (default=True) specifies whether the betweenness values are normalized by b=b/(n-1)(n-2) where n is the number of nodes in G.

The keyword weighted_edges (default=False) specifies whether to use edge weights (otherwise weights are all assumed equal).

The algorithm is from 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

load_centrality(G, v=None, cutoff=None, normalized=True, weighted_edges=False)

source code 

"Load" centrality for nodes.

This actually computes 'load' and not betweenness. See https://networkx.lanl.gov/ticket/103

The fraction of number of shortests paths that go through each node counted according to the algorithm in

Scientific collaboration networks: II. Shortest paths, weighted networks, and centrality, M. E. J. Newman, Phys. Rev. E 64, 016132 (2001).

Returns a dictionary of betweenness values keyed by node. The betweenness is normalized to be between [0,1].

If normalized=False the resulting betweenness is not normalized.

If weighted_edges is True then use Dijkstra for finding shortest paths.

betweenness_centrality_source(G, normalized=True, weighted_edges=False, sources=None)

source code 

Enchanced version of the method in centrality module that allows specifying a list of sources (subgraph).

weighted_edges:: consider edge weights by running Dijkstra's algorithm (no effect on unweighted graphs).

sources:: list of nodes to consider as subgraph

See Sec. 4 in 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

This algorithm does not count the endpoints, i.e. a path from s to t does not contribute to the betweenness of s and t.

edge_betweenness(G, normalized=True, weighted_edges=False, sources=None)

source code 

Edge betweenness centrality.

weighted_edges:: consider edge weights by running Dijkstra's algorithm (no effect on unweighted graphs).

sources:: list of nodes to consider as subgraph

_brandes_betweenness_helper(G, root, weighted_edges)

source code 

Helper for betweenness centrality and edge betweenness centrality.

Runs single-source shortest path from root node.

weighted_edges:: consider edge weights

Finds:

S=[] list of nodes reached during traversal P={} predecessors, keyed by child node D={} distances sigma={} indexed by node, is the number of paths to root going through the node

edge_load(G, nodes=False, cutoff=False)

source code 

Edge Betweenness

WARNING:

This module is for demonstration and testing purposes.

degree_centrality(G, v=None)

source code 

Degree centrality for nodes (fraction of nodes connected to).

Returns a dictionary of degree centrality values keyed by node.

The degree centrality is normalized to the maximum possible degree in the graph G.

closeness_centrality(G, v=None, weighted_edges=False)

source code 

Closeness centrality for nodes (1/average distance to all nodes).

Returns a dictionary of closeness centrality values keyed by node. The closeness centrality is normalized to be between 0 and 1.