Centrality
==========

>>> from networkx import *

>>> K=krackhardt_kite_graph()
>>> P3=path_graph(3)
>>> P4=path_graph(4)
>>> K5=complete_graph(5)
>>> C4=cycle_graph(4)
>>> T=balanced_tree(r=2, h=2)
>>> Gb = Graph()
>>> Gb.add_edges_from([(0,1), (0,2), (1,3), (2,3), (2,4), (4,5), (3,5)])


>>> F=Graph() # Florentine families
>>> F.add_edge('Acciaiuoli','Medici')
>>> F.add_edge('Castellani','Peruzzi')
>>> F.add_edge('Castellani','Strozzi')
>>> F.add_edge('Castellani','Barbadori')
>>> F.add_edge('Medici','Barbadori')
>>> F.add_edge('Medici','Ridolfi')
>>> F.add_edge('Medici','Tornabuoni')
>>> F.add_edge('Medici','Albizzi')
>>> F.add_edge('Medici','Salviati')
>>> F.add_edge('Salviati','Pazzi')
>>> F.add_edge('Peruzzi','Strozzi')
>>> F.add_edge('Peruzzi','Bischeri')
>>> F.add_edge('Strozzi','Ridolfi')
>>> F.add_edge('Strozzi','Bischeri')
>>> F.add_edge('Ridolfi','Tornabuoni')
>>> F.add_edge('Tornabuoni','Guadagni')
>>> F.add_edge('Albizzi','Ginori')
>>> F.add_edge('Albizzi','Guadagni')
>>> F.add_edge('Bischeri','Guadagni')
>>> F.add_edge('Guadagni','Lamberteschi')


Load
----
>>> b=load_centrality(K5)
>>> for v in K5:
...     print "%0.2d %5.3f"%(v,b[v])
00 0.000
01 0.000
02 0.000
03 0.000
04 0.000

>>> b=load_centrality(P3)
>>> for v in P3:
...     print "%0.2d %5.3f"%(v,b[v])
00 0.000
01 1.000
02 0.000


>>> b=load_centrality(K)
>>> for v in K:
...     print "%0.2d %5.3f"%(v,b[v])
00 0.023
01 0.023
02 0.000
03 0.102
04 0.000
05 0.231
06 0.231
07 0.389
08 0.222
09 0.000


>>> b=load_centrality(F)
>>> for v in sorted(F):
...     print "%-13s %5.3f"%(v,b[v])
Acciaiuoli    0.000
Albizzi       0.211
Barbadori     0.093
Bischeri      0.104
Castellani    0.055
Ginori        0.000
Guadagni      0.251
Lamberteschi  0.000
Medici        0.522
Pazzi         0.000
Peruzzi       0.022
Ridolfi       0.117
Salviati      0.143
Strozzi       0.106
Tornabuoni    0.090


Unnormalized

>>> b=load_centrality(K5,normalized=False)
>>> for v in K5:
...     print "%0.2d %5.3f"%(v,b[v])
00 0.000
01 0.000
02 0.000
03 0.000
04 0.000

>>> b=load_centrality(P3,normalized=False)
>>> for v in P3:
...     print "%0.2d %5.3f"%(v,b[v])
00 0.000
01 2.000
02 0.000


>>> b=load_centrality(K,normalized=False)
>>> for v in K:
...     print "%0.2d %5.3f"%(v,b[v])
00 1.667
01 1.667
02 0.000
03 7.333
04 0.000
05 16.667
06 16.667
07 28.000
08 16.000
09 0.000



>>> b=load_centrality(F,normalized=False)
>>> for v in sorted(F):
...     print "%-13s %5.3f"%(v,b[v])
Acciaiuoli    0.000
Albizzi       38.333
Barbadori     17.000
Bischeri      19.000
Castellani    10.000
Ginori        0.000
Guadagni      45.667
Lamberteschi  0.000
Medici        95.000
Pazzi         0.000
Peruzzi       4.000
Ridolfi       21.333
Salviati      26.000
Strozzi       19.333
Tornabuoni    16.333

Difference Between Load and Betweenness
---------------------------------------
The smallest graph that shows the difference between
load and betweenness is G=ladder_graph(3) (Graph B below)

Graph A and B are from Tao Zhou, Jian-Guo Liu, Bing-Hong Wang:
Comment on ``Scientific collaboration networks. II. Shortest paths,
weighted networks, and centrality". http://arxiv.org/pdf/physics/0511084

Notice that unlike here, their calculation adds to 1 to the betweennes
of every node i for every path from i to every other node.  This is
exactly what it should be, based on Eqn. (1) in their paper: the eqn
is B(v) = \sum_{s\neq t, s\neq v}{\frac{\sigma_{st}(v)}{\sigma_{st}}},
therefore, they allow v to be the target node.

We follow Brandes 2001, who follows Freeman 1977 that make the sum for
betweenness of v exclude paths where v is either the source or target
node.  To agree with their numbers, we must additionally, remove edge
(4,8) from the graph, see AC example following (there is a mistake
in the figure in their paper - personal communication).

>>> A = Graph()
>>> A.add_edges_from([(0,1), (1,2), (1,3), (2,4), (3,5), (4,6), (4,7), (4,8), (5,8), (6,9), (7,9), (8,9)])
>>> B = Graph() # ladder_graph(3)
>>> B.add_edges_from([(0,1), (0,2), (1,3), (2,3), (2,4), (4,5), (3,5)])

>>> b = load_centrality(B,normalized=False)
>>> for v in B:
...     print "%0.2d %5.3f"%(v,b[v])
00 1.750
01 1.750
02 6.500
03 6.500
04 1.750
05 1.750


Edge Load
---------
>>> b = edge_load(C4)
>>> for v in C4.edges():
...     print "(%0.2d, %0.2d) %5.3f"%(v[0], v[1], b[v])
(00, 01) 6.000
(00, 03) 6.000
(01, 02) 6.000
(02, 03) 6.000

>>> b = edge_load(P4)
>>> for v in P4.edges():
...     print "(%0.2d, %0.2d) %5.3f"%(v[0], v[1], b[v])
(00, 01) 6.000
(01, 02) 8.000
(02, 03) 6.000

>>> b = edge_load(K5)
>>> for v in K5.edges():
...     print "(%0.2d, %0.2d) %5.3f"%(v[0], v[1], b[v])
(00, 01) 5.000
(00, 02) 5.000
(00, 03) 5.000
(00, 04) 5.000
(01, 02) 5.000
(01, 03) 5.000
(01, 04) 5.000
(02, 03) 5.000
(02, 04) 5.000
(03, 04) 5.000

>>> b = edge_load(T)
>>> for v in T.edges():
...     print "(%0.2d, %0.2d) %5.3f"%(v[0], v[1], b[v])
(00, 01) 24.000
(00, 02) 24.000
(01, 03) 12.000
(01, 04) 12.000
(02, 05) 12.000
(02, 06) 12.000