Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / centrality / tests / test_current_flow_betweenness_centrality.py @ 5cef0f13

History | View | Annotate | Download (7.88 KB)

1
#!/usr/bin/env python
2
import networkx as nx
3
from nose.tools import assert_almost_equal
4
from nose import SkipTest
5
from nose.plugins.attrib import attr
6
from networkx import edge_current_flow_betweenness_centrality \
7
    as edge_current_flow
8
from networkx import approximate_current_flow_betweenness_centrality \
9
    as approximate_cfbc
10

    
11

    
12
class TestFlowBetweennessCentrality(object):
13
    numpy = 1  # nosetests attribute, use nosetests -a 'not numpy' to skip test
14

    
15
    @classmethod
16
    def setupClass(cls):
17
        global np
18
        try:
19
            import numpy as np
20
            import scipy
21
        except ImportError:
22
            raise SkipTest('NumPy not available.')
23

    
24
    def test_K4_normalized(self):
25
        """Betweenness centrality: K4"""
26
        G = nx.complete_graph(4)
27
        b = nx.current_flow_betweenness_centrality(G, normalized=True)
28
        b_answer = {0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25}
29
        for n in sorted(G):
30
            assert_almost_equal(b[n], b_answer[n])
31
        G.add_edge(0, 1, weight=0.5, other=0.3)
32
        b = nx.current_flow_betweenness_centrality(G, normalized=True, weight=None)
33
        for n in sorted(G):
34
            assert_almost_equal(b[n], b_answer[n])
35
        wb_answer = {0: 0.2222222, 1: 0.2222222, 2: 0.30555555, 3: 0.30555555}
36
        b = nx.current_flow_betweenness_centrality(G, normalized=True, weight='weight')
37
        for n in sorted(G):
38
            assert_almost_equal(b[n], wb_answer[n])
39
        wb_answer = {0: 0.2051282, 1: 0.2051282, 2: 0.33974358, 3: 0.33974358}
40
        b = nx.current_flow_betweenness_centrality(G, normalized=True, weight='other')
41
        for n in sorted(G):
42
            assert_almost_equal(b[n], wb_answer[n])
43

    
44
    def test_K4(self):
45
        """Betweenness centrality: K4"""
46
        G = nx.complete_graph(4)
47
        for solver in ['full', 'lu', 'cg']:
48
            b = nx.current_flow_betweenness_centrality(G, normalized=False,
49
                                                       solver=solver)
50
            b_answer = {0: 0.75, 1: 0.75, 2: 0.75, 3: 0.75}
51
            for n in sorted(G):
52
                assert_almost_equal(b[n], b_answer[n])
53

    
54
    def test_P4_normalized(self):
55
        """Betweenness centrality: P4 normalized"""
56
        G = nx.path_graph(4)
57
        b = nx.current_flow_betweenness_centrality(G, normalized=True)
58
        b_answer = {0: 0, 1: 2. / 3, 2: 2. / 3, 3: 0}
59
        for n in sorted(G):
60
            assert_almost_equal(b[n], b_answer[n])
61

    
62
    def test_P4(self):
63
        """Betweenness centrality: P4"""
64
        G = nx.path_graph(4)
65
        b = nx.current_flow_betweenness_centrality(G, normalized=False)
66
        b_answer = {0: 0, 1: 2, 2: 2, 3: 0}
67
        for n in sorted(G):
68
            assert_almost_equal(b[n], b_answer[n])
69

    
70
    def test_star(self):
71
        """Betweenness centrality: star """
72
        G = nx.Graph()
73
        nx.add_star(G, ['a', 'b', 'c', 'd'])
74
        b = nx.current_flow_betweenness_centrality(G, normalized=True)
75
        b_answer = {'a': 1.0, 'b': 0.0, 'c': 0.0, 'd': 0.0}
76
        for n in sorted(G):
77
            assert_almost_equal(b[n], b_answer[n])
78

    
79
    def test_solers(self):
80
        """Betweenness centrality: alternate solvers"""
81
        G = nx.complete_graph(4)
82
        for solver in ['full', 'lu', 'cg']:
83
            b = nx.current_flow_betweenness_centrality(G, normalized=False,
84
                                                       solver=solver)
85
            b_answer = {0: 0.75, 1: 0.75, 2: 0.75, 3: 0.75}
86
            for n in sorted(G):
87
                assert_almost_equal(b[n], b_answer[n])
88

    
89

    
90
class TestApproximateFlowBetweennessCentrality(object):
91
    numpy = 1  # nosetests attribute, use nosetests -a 'not numpy' to skip test
92

    
93
    @classmethod
94
    def setupClass(cls):
95
        global np
96
        global assert_allclose
97
        try:
98
            import numpy as np
99
            import scipy
100
            from numpy.testing import assert_allclose
101
        except ImportError:
102
            raise SkipTest('NumPy not available.')
103

    
104
    def test_K4_normalized(self):
105
        "Approximate current-flow betweenness centrality: K4 normalized"
106
        G = nx.complete_graph(4)
107
        b = nx.current_flow_betweenness_centrality(G, normalized=True)
108
        epsilon = 0.1
109
        ba = approximate_cfbc(G, normalized=True, epsilon=0.5 * epsilon)
110
        for n in sorted(G):
111
            assert_allclose(b[n], ba[n], atol=epsilon)
112

    
113
    def test_K4(self):
114
        "Approximate current-flow betweenness centrality: K4"
115
        G = nx.complete_graph(4)
116
        b = nx.current_flow_betweenness_centrality(G, normalized=False)
117
        epsilon = 0.1
118
        ba = approximate_cfbc(G, normalized=False, epsilon=0.5 * epsilon)
119
        for n in sorted(G):
120
            assert_allclose(b[n], ba[n], atol=epsilon * len(G)**2)
121

    
122
    def test_star(self):
123
        "Approximate current-flow betweenness centrality: star"
124
        G = nx.Graph()
125
        nx.add_star(G, ['a', 'b', 'c', 'd'])
126
        b = nx.current_flow_betweenness_centrality(G, normalized=True)
127
        epsilon = 0.1
128
        ba = approximate_cfbc(G, normalized=True, epsilon=0.5 * epsilon)
129
        for n in sorted(G):
130
            assert_allclose(b[n], ba[n], atol=epsilon)
131

    
132
    def test_grid(self):
133
        "Approximate current-flow betweenness centrality: 2d grid"
134
        G = nx.grid_2d_graph(4, 4)
135
        b = nx.current_flow_betweenness_centrality(G, normalized=True)
136
        epsilon = 0.1
137
        ba = approximate_cfbc(G, normalized=True, epsilon=0.5 * epsilon)
138
        for n in sorted(G):
139
            assert_allclose(b[n], ba[n], atol=epsilon)
140

    
141
    def test_seed(self):
142
        G = nx.complete_graph(4)
143
        b = approximate_cfbc(G, normalized=False, epsilon=0.05, seed=1)
144
        b_answer = {0: 0.75, 1: 0.75, 2: 0.75, 3: 0.75}
145
        for n in sorted(G):
146
            assert_allclose(b[n], b_answer[n], atol=0.1)
147

    
148
    def test_solvers(self):
149
        "Approximate current-flow betweenness centrality: solvers"
150
        G = nx.complete_graph(4)
151
        epsilon = 0.1
152
        for solver in ['full', 'lu', 'cg']:
153
            b = approximate_cfbc(G, normalized=False, solver=solver,
154
                                 epsilon=0.5 * epsilon)
155
            b_answer = {0: 0.75, 1: 0.75, 2: 0.75, 3: 0.75}
156
            for n in sorted(G):
157
                assert_allclose(b[n], b_answer[n], atol=epsilon)
158

    
159

    
160
class TestWeightedFlowBetweennessCentrality(object):
161
    pass
162

    
163

    
164
class TestEdgeFlowBetweennessCentrality(object):
165
    numpy = 1  # nosetests attribute, use nosetests -a 'not numpy' to skip test
166

    
167
    @classmethod
168
    def setupClass(cls):
169
        global np
170
        try:
171
            import numpy as np
172
            import scipy
173
        except ImportError:
174
            raise SkipTest('NumPy not available.')
175

    
176
    def test_K4(self):
177
        """Edge flow betweenness centrality: K4"""
178
        G = nx.complete_graph(4)
179
        b = edge_current_flow(G, normalized=True)
180
        b_answer = dict.fromkeys(G.edges(), 0.25)
181
        for (s, t), v1 in b_answer.items():
182
            v2 = b.get((s, t), b.get((t, s)))
183
            assert_almost_equal(v1, v2)
184

    
185
    def test_K4_normalized(self):
186
        """Edge flow betweenness centrality: K4"""
187
        G = nx.complete_graph(4)
188
        b = edge_current_flow(G, normalized=False)
189
        b_answer = dict.fromkeys(G.edges(), 0.75)
190
        for (s, t), v1 in b_answer.items():
191
            v2 = b.get((s, t), b.get((t, s)))
192
            assert_almost_equal(v1, v2)
193

    
194
    def test_C4(self):
195
        """Edge flow betweenness centrality: C4"""
196
        G = nx.cycle_graph(4)
197
        b = edge_current_flow(G, normalized=False)
198
        b_answer = {(0, 1): 1.25, (0, 3): 1.25, (1, 2): 1.25, (2, 3): 1.25}
199
        for (s, t), v1 in b_answer.items():
200
            v2 = b.get((s, t), b.get((t, s)))
201
            assert_almost_equal(v1, v2)
202

    
203
    def test_P4(self):
204
        """Edge betweenness centrality: P4"""
205
        G = nx.path_graph(4)
206
        b = edge_current_flow(G, normalized=False)
207
        b_answer = {(0, 1): 1.5, (1, 2): 2.0, (2, 3): 1.5}
208
        for (s, t), v1 in b_answer.items():
209
            v2 = b.get((s, t), b.get((t, s)))
210
            assert_almost_equal(v1,  v2)