| #!/usr/bin/env python |
| from nose.tools import * |
| import networkx as nx |
| |
| def weighted_G(): |
| G=nx.Graph(); |
| G.add_edge(0,1,weight=3) |
| G.add_edge(0,2,weight=2) |
| G.add_edge(0,3,weight=6) |
| G.add_edge(0,4,weight=4) |
| G.add_edge(1,3,weight=5) |
| G.add_edge(1,5,weight=5) |
| G.add_edge(2,4,weight=1) |
| G.add_edge(3,4,weight=2) |
| G.add_edge(3,5,weight=1) |
| G.add_edge(4,5,weight=4) |
| |
| return G |
| |
| |
| class TestBetweennessCentrality(object): |
| |
| def test_K5(self): |
| """Betweenness centrality: K5""" |
| G=nx.complete_graph(5) |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False) |
| b_answer={0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0} |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_K5_endpoints(self): |
| """Betweenness centrality: K5 endpoints""" |
| G=nx.complete_graph(5) |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False, |
| endpoints=True) |
| b_answer={0: 4.0, 1: 4.0, 2: 4.0, 3: 4.0, 4: 4.0} |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| def test_P3_normalized(self): |
| """Betweenness centrality: P3 normalized""" |
| G=nx.path_graph(3) |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=True) |
| b_answer={0: 0.0, 1: 1.0, 2: 0.0} |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| def test_P3(self): |
| """Betweenness centrality: P3""" |
| G=nx.path_graph(3) |
| b_answer={0: 0.0, 1: 1.0, 2: 0.0} |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_P3_endpoints(self): |
| """Betweenness centrality: P3 endpoints""" |
| G=nx.path_graph(3) |
| b_answer={0: 2.0, 1: 3.0, 2: 2.0} |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False, |
| endpoints=True) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| def test_krackhardt_kite_graph(self): |
| """Betweenness centrality: Krackhardt kite graph""" |
| G=nx.krackhardt_kite_graph() |
| b_answer={0: 1.667,1: 1.667,2: 0.000,3: 7.333,4: 0.000, |
| 5: 16.667,6: 16.667,7: 28.000,8: 16.000,9: 0.000} |
| for b in b_answer: |
| b_answer[b]/=2.0 |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False) |
| |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| |
| def test_krackhardt_kite_graph_normalized(self): |
| """Betweenness centrality: Krackhardt kite graph normalized""" |
| G=nx.krackhardt_kite_graph() |
| b_answer={0:0.023,1:0.023,2:0.000,3:0.102,4:0.000, |
| 5:0.231,6:0.231,7:0.389,8:0.222,9:0.000} |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=True) |
| |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| |
| def test_florentine_families_graph(self): |
| """Betweenness centrality: Florentine families graph""" |
| G=nx.florentine_families_graph() |
| b_answer=\ |
| {'Acciaiuoli': 0.000, |
| 'Albizzi': 0.212, |
| 'Barbadori': 0.093, |
| 'Bischeri': 0.104, |
| 'Castellani': 0.055, |
| 'Ginori': 0.000, |
| 'Guadagni': 0.255, |
| 'Lamberteschi': 0.000, |
| 'Medici': 0.522, |
| 'Pazzi': 0.000, |
| 'Peruzzi': 0.022, |
| 'Ridolfi': 0.114, |
| 'Salviati': 0.143, |
| 'Strozzi': 0.103, |
| 'Tornabuoni': 0.092} |
| |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=True) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| |
| def test_ladder_graph(self): |
| """Betweenness centrality: Ladder graph""" |
| G = nx.Graph() # ladder_graph(3) |
| G.add_edges_from([(0,1), (0,2), (1,3), (2,3), |
| (2,4), (4,5), (3,5)]) |
| b_answer={0:1.667,1: 1.667,2: 6.667, |
| 3: 6.667,4: 1.667,5: 1.667} |
| for b in b_answer: |
| b_answer[b]/=2.0 |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| def test_disconnected_path(self): |
| """Betweenness centrality: disconnected path""" |
| G=nx.Graph() |
| G.add_path([0,1,2]) |
| G.add_path([3,4,5,6]) |
| b_answer={0:0,1:1,2:0,3:0,4:2,5:2,6:0} |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_disconnected_path_endpoints(self): |
| """Betweenness centrality: disconnected path endpoints""" |
| G=nx.Graph() |
| G.add_path([0,1,2]) |
| G.add_path([3,4,5,6]) |
| b_answer={0:2,1:3,2:2,3:3,4:5,5:5,6:3} |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False, |
| endpoints=True) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| def test_directed_path(self): |
| """Betweenness centrality: directed path""" |
| G=nx.DiGraph() |
| G.add_path([0,1,2]) |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=False) |
| b_answer={0: 0.0, 1: 1.0, 2: 0.0} |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_directed_path_normalized(self): |
| """Betweenness centrality: directed path normalized""" |
| G=nx.DiGraph() |
| G.add_path([0,1,2]) |
| b=nx.betweenness_centrality(G, |
| weight=None, |
| normalized=True) |
| b_answer={0: 0.0, 1: 0.5, 2: 0.0} |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| |
| class TestWeightedBetweennessCentrality(object): |
| |
| def test_K5(self): |
| """Weighted betweenness centrality: K5""" |
| G=nx.complete_graph(5) |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=False) |
| b_answer={0: 0.0, 1: 0.0, 2: 0.0, 3: 0.0, 4: 0.0} |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_P3_normalized(self): |
| """Weighted betweenness centrality: P3 normalized""" |
| G=nx.path_graph(3) |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=True) |
| b_answer={0: 0.0, 1: 1.0, 2: 0.0} |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| def test_P3(self): |
| """Weighted betweenness centrality: P3""" |
| G=nx.path_graph(3) |
| b_answer={0: 0.0, 1: 1.0, 2: 0.0} |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=False) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_krackhardt_kite_graph(self): |
| """Weighted betweenness centrality: Krackhardt kite graph""" |
| G=nx.krackhardt_kite_graph() |
| b_answer={0: 1.667,1: 1.667,2: 0.000,3: 7.333,4: 0.000, |
| 5: 16.667,6: 16.667,7: 28.000,8: 16.000,9: 0.000} |
| for b in b_answer: |
| b_answer[b]/=2.0 |
| |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=False) |
| |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| |
| def test_krackhardt_kite_graph_normalized(self): |
| """Weighted betweenness centrality: |
| Krackhardt kite graph normalized |
| """ |
| G=nx.krackhardt_kite_graph() |
| b_answer={0:0.023,1:0.023,2:0.000,3:0.102,4:0.000, |
| 5:0.231,6:0.231,7:0.389,8:0.222,9:0.000} |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=True) |
| |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| |
| def test_florentine_families_graph(self): |
| """Weighted betweenness centrality: |
| Florentine families graph""" |
| G=nx.florentine_families_graph() |
| b_answer=\ |
| {'Acciaiuoli': 0.000, |
| 'Albizzi': 0.212, |
| 'Barbadori': 0.093, |
| 'Bischeri': 0.104, |
| 'Castellani': 0.055, |
| 'Ginori': 0.000, |
| 'Guadagni': 0.255, |
| 'Lamberteschi': 0.000, |
| 'Medici': 0.522, |
| 'Pazzi': 0.000, |
| 'Peruzzi': 0.022, |
| 'Ridolfi': 0.114, |
| 'Salviati': 0.143, |
| 'Strozzi': 0.103, |
| 'Tornabuoni': 0.092} |
| |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=True) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| |
| def test_ladder_graph(self): |
| """Weighted betweenness centrality: Ladder graph""" |
| G = nx.Graph() # ladder_graph(3) |
| G.add_edges_from([(0,1), (0,2), (1,3), (2,3), |
| (2,4), (4,5), (3,5)]) |
| b_answer={0:1.667,1: 1.667,2: 6.667, |
| 3: 6.667,4: 1.667,5: 1.667} |
| for b in b_answer: |
| b_answer[b]/=2.0 |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=False) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n],places=3) |
| |
| def test_G(self): |
| """Weighted betweenness centrality: G""" |
| G = weighted_G() |
| b_answer={0: 2.0, 1: 0.0, 2: 4.0, 3: 3.0, 4: 4.0, 5: 0.0} |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=False) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_G2(self): |
| """Weighted betweenness centrality: G2""" |
| G=nx.DiGraph() |
| G.add_weighted_edges_from([('s','u',10) ,('s','x',5) , |
| ('u','v',1) ,('u','x',2) , |
| ('v','y',1) ,('x','u',3) , |
| ('x','v',5) ,('x','y',2) , |
| ('y','s',7) ,('y','v',6)]) |
| |
| b_answer={'y':5.0,'x':5.0,'s':4.0,'u':2.0,'v':2.0} |
| |
| b=nx.betweenness_centrality(G, |
| weight='weight', |
| normalized=False) |
| for n in sorted(G): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| class TestEdgeBetweennessCentrality(object): |
| |
| def test_K5(self): |
| """Edge betweenness centrality: K5""" |
| G=nx.complete_graph(5) |
| b=nx.edge_betweenness_centrality(G, weight=None, normalized=False) |
| b_answer=dict.fromkeys(G.edges(),1) |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_normalized_K5(self): |
| """Edge betweenness centrality: K5""" |
| G=nx.complete_graph(5) |
| b=nx.edge_betweenness_centrality(G, weight=None, normalized=True) |
| b_answer=dict.fromkeys(G.edges(),1/10.0) |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| def test_C4(self): |
| """Edge betweenness centrality: C4""" |
| G=nx.cycle_graph(4) |
| b=nx.edge_betweenness_centrality(G, weight=None, normalized=True) |
| b_answer={(0, 1):2,(0, 3):2, (1, 2):2, (2, 3): 2} |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]/6.0) |
| |
| def test_P4(self): |
| """Edge betweenness centrality: P4""" |
| G=nx.path_graph(4) |
| b=nx.edge_betweenness_centrality(G, weight=None, normalized=False) |
| b_answer={(0, 1):3,(1, 2):4, (2, 3):3} |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_normalized_P4(self): |
| """Edge betweenness centrality: P4""" |
| G=nx.path_graph(4) |
| b=nx.edge_betweenness_centrality(G, weight=None, normalized=True) |
| b_answer={(0, 1):3,(1, 2):4, (2, 3):3} |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]/6.0) |
| |
| |
| def test_balanced_tree(self): |
| """Edge betweenness centrality: balanced tree""" |
| G=nx.balanced_tree(r=2,h=2) |
| b=nx.edge_betweenness_centrality(G, weight=None, normalized=False) |
| b_answer={(0, 1):12,(0, 2):12, |
| (1, 3):6,(1, 4):6,(2, 5):6,(2,6):6} |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| class TestWeightedEdgeBetweennessCentrality(object): |
| |
| def test_K5(self): |
| """Edge betweenness centrality: K5""" |
| G=nx.complete_graph(5) |
| b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False) |
| b_answer=dict.fromkeys(G.edges(),1) |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_C4(self): |
| """Edge betweenness centrality: C4""" |
| G=nx.cycle_graph(4) |
| b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False) |
| b_answer={(0, 1):2,(0, 3):2, (1, 2):2, (2, 3): 2} |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_P4(self): |
| """Edge betweenness centrality: P4""" |
| G=nx.path_graph(4) |
| b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False) |
| b_answer={(0, 1):3,(1, 2):4, (2, 3):3} |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| |
| def test_balanced_tree(self): |
| """Edge betweenness centrality: balanced tree""" |
| G=nx.balanced_tree(r=2,h=2) |
| b=nx.edge_betweenness_centrality(G, weight='weight', normalized=False) |
| b_answer={(0, 1):12,(0, 2):12, |
| (1, 3):6,(1, 4):6,(2, 5):6,(2,6):6} |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_weighted_graph(self): |
| eList = [(0, 1, 5), (0, 2, 4), (0, 3, 3), |
| (0, 4, 2), (1, 2, 4), (1, 3, 1), |
| (1, 4, 3), (2, 4, 5), (3, 4, 4)] |
| G = nx.Graph() |
| G.add_weighted_edges_from(eList) |
| b = nx.edge_betweenness_centrality(G, weight='weight', normalized=False) |
| b_answer={(0, 1):0.0, |
| (0, 2):1.0, |
| (0, 3):2.0, |
| (0, 4):1.0, |
| (1, 2):2.0, |
| (1, 3):3.5, |
| (1, 4):1.5, |
| (2, 4):1.0, |
| (3, 4):0.5} |
| |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]) |
| |
| def test_normalized_weighted_graph(self): |
| eList = [(0, 1, 5), (0, 2, 4), (0, 3, 3), |
| (0, 4, 2), (1, 2, 4), (1, 3, 1), |
| (1, 4, 3), (2, 4, 5), (3, 4, 4)] |
| G = nx.Graph() |
| G.add_weighted_edges_from(eList) |
| b = nx.edge_betweenness_centrality(G, weight='weight', normalized=True) |
| b_answer={(0, 1):0.0, |
| (0, 2):1.0, |
| (0, 3):2.0, |
| (0, 4):1.0, |
| (1, 2):2.0, |
| (1, 3):3.5, |
| (1, 4):1.5, |
| (2, 4):1.0, |
| (3, 4):0.5} |
| |
| norm = len(G)*(len(G)-1)/2.0 |
| for n in sorted(G.edges()): |
| assert_almost_equal(b[n],b_answer[n]/norm) |
| |