Betweenness centrality for nodes in the graph. Betweenness centrality is a measure of the number of shortests paths that pass through a node. Nodes in high-density areas will get a good score.
(graph, normalized=True, directed=False)
| 884 | return [u] + _traverse(u,v) + [v] |
| 885 | |
| 886 | def brandes_betweenness_centrality(graph, normalized=True, directed=False): |
| 887 | """ Betweenness centrality for nodes in the graph. |
| 888 | Betweenness centrality is a measure of the number of shortests paths that pass through a node. |
| 889 | Nodes in high-density areas will get a good score. |
| 890 | """ |
| 891 | # Ulrik Brandes, A Faster Algorithm for Betweenness Centrality, |
| 892 | # Journal of Mathematical Sociology 25(2):163-177, 2001, |
| 893 | # http://www.inf.uni-konstanz.de/algo/publications/b-fabc-01.pdf |
| 894 | # Based on: Dijkstra's algorithm for shortest paths modified from Eppstein. |
| 895 | # Based on: NetworkX 1.0.1: Aric Hagberg, Dan Schult and Pieter Swart. |
| 896 | # http://python-networkx.sourcearchive.com/documentation/1.0.1/centrality_8py-source.html |
| 897 | W = adjacency(graph, directed=directed) |
| 898 | b = dict.fromkeys(graph, 0.0) |
| 899 | for id in graph: |
| 900 | Q = [] # Use Q as a heap with (distance, node id)-tuples. |
| 901 | D = {} # Dictionary of final distances. |
| 902 | P = {} # Dictionary of paths. |
| 903 | for n in graph: P[n]=[] |
| 904 | seen = {id: 0} |
| 905 | heappush(Q, (0, id, id)) |
| 906 | S = [] |
| 907 | E = dict.fromkeys(graph, 0) # sigma |
| 908 | E[id] = 1.0 |
| 909 | while Q: |
| 910 | (dist, pred, v) = heappop(Q) |
| 911 | if v in D: |
| 912 | continue |
| 913 | D[v] = dist |
| 914 | S.append(v) |
| 915 | E[v] += E[pred] |
| 916 | for w in W[v]: |
| 917 | vw_dist = D[v] + W[v][w] |
| 918 | if w not in D and (w not in seen or vw_dist < seen[w]): |
| 919 | seen[w] = vw_dist |
| 920 | heappush(Q, (vw_dist, v, w)) |
| 921 | P[w] = [v] |
| 922 | E[w] = 0.0 |
| 923 | elif vw_dist == seen[w]: # Handle equal paths. |
| 924 | P[w].append(v) |
| 925 | E[w] += E[v] |
| 926 | d = dict.fromkeys(graph, 0.0) |
| 927 | for w in reversed(S): |
| 928 | for v in P[w]: |
| 929 | d[v] += (1.0 + d[w]) * E[v] / E[w] |
| 930 | if w != id: |
| 931 | b[w] += d[w] |
| 932 | # Normalize between 0.0 and 1.0. |
| 933 | m = normalized and max(b.values()) or 1 |
| 934 | b = dict((id, w/m) for id, w in b.iteritems()) |
| 935 | return b |
| 936 | |
| 937 | def eigenvector_centrality(graph, normalized=True, reversed=True, rating={}, iterations=100, tolerance=0.0001): |
| 938 | """ Eigenvector centrality for nodes in the graph (cfr. Google's PageRank). |