Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (11.2 KB)

1
#!/usr/bin/env python
2
from nose.tools import *
3
import networkx as nx
4

    
5

    
6
class TestLoadCentrality:
7

    
8
    def setUp(self):
9

    
10
        G = nx.Graph()
11
        G.add_edge(0, 1, weight=3)
12
        G.add_edge(0, 2, weight=2)
13
        G.add_edge(0, 3, weight=6)
14
        G.add_edge(0, 4, weight=4)
15
        G.add_edge(1, 3, weight=5)
16
        G.add_edge(1, 5, weight=5)
17
        G.add_edge(2, 4, weight=1)
18
        G.add_edge(3, 4, weight=2)
19
        G.add_edge(3, 5, weight=1)
20
        G.add_edge(4, 5, weight=4)
21
        self.G = G
22
        self.exact_weighted = {0: 4.0, 1: 0.0, 2: 8.0, 3: 6.0, 4: 8.0, 5: 0.0}
23
        self.K = nx.krackhardt_kite_graph()
24
        self.P3 = nx.path_graph(3)
25
        self.P4 = nx.path_graph(4)
26
        self.K5 = nx.complete_graph(5)
27

    
28
        self.C4 = nx.cycle_graph(4)
29
        self.T = nx.balanced_tree(r=2, h=2)
30
        self.Gb = nx.Graph()
31
        self.Gb.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3),
32
                                (2, 4), (4, 5), (3, 5)])
33
        self.F = nx.florentine_families_graph()
34
        self.LM = nx.les_miserables_graph()
35
        self.D = nx.cycle_graph(3, create_using=nx.DiGraph())
36
        self.D.add_edges_from([(3, 0), (4, 3)])
37

    
38
    def test_not_strongly_connected(self):
39
        b = nx.load_centrality(self.D)
40
        result = {0: 5. / 12,
41
                  1: 1. / 4,
42
                  2: 1. / 12,
43
                  3: 1. / 4,
44
                  4: 0.000}
45
        for n in sorted(self.D):
46
            assert_almost_equal(result[n], b[n], places=3)
47
            assert_almost_equal(result[n], nx.load_centrality(self.D, n), places=3)
48

    
49
    def test_weighted_load(self):
50
        b = nx.load_centrality(self.G, weight='weight', normalized=False)
51
        for n in sorted(self.G):
52
            assert_equal(b[n], self.exact_weighted[n])
53

    
54
    def test_k5_load(self):
55
        G = self.K5
56
        c = nx.load_centrality(G)
57
        d = {0: 0.000,
58
             1: 0.000,
59
             2: 0.000,
60
             3: 0.000,
61
             4: 0.000}
62
        for n in sorted(G):
63
            assert_almost_equal(c[n], d[n], places=3)
64

    
65
    def test_p3_load(self):
66
        G = self.P3
67
        c = nx.load_centrality(G)
68
        d = {0: 0.000,
69
             1: 1.000,
70
             2: 0.000}
71
        for n in sorted(G):
72
            assert_almost_equal(c[n], d[n], places=3)
73
        c = nx.load_centrality(G, v=1)
74
        assert_almost_equal(c, 1.0)
75
        c = nx.load_centrality(G, v=1, normalized=True)
76
        assert_almost_equal(c, 1.0)
77

    
78
    def test_p2_load(self):
79
        G = nx.path_graph(2)
80
        c = nx.load_centrality(G)
81
        d = {0: 0.000,
82
             1: 0.000}
83
        for n in sorted(G):
84
            assert_almost_equal(c[n], d[n], places=3)
85

    
86
    def test_krackhardt_load(self):
87
        G = self.K
88
        c = nx.load_centrality(G)
89
        d = {0: 0.023,
90
             1: 0.023,
91
             2: 0.000,
92
             3: 0.102,
93
             4: 0.000,
94
             5: 0.231,
95
             6: 0.231,
96
             7: 0.389,
97
             8: 0.222,
98
             9: 0.000}
99
        for n in sorted(G):
100
            assert_almost_equal(c[n], d[n], places=3)
101

    
102
    def test_florentine_families_load(self):
103
        G = self.F
104
        c = nx.load_centrality(G)
105
        d = {'Acciaiuoli':    0.000,
106
             'Albizzi':       0.211,
107
             'Barbadori':     0.093,
108
             'Bischeri':      0.104,
109
             'Castellani':    0.055,
110
             'Ginori':        0.000,
111
             'Guadagni':      0.251,
112
             'Lamberteschi':  0.000,
113
             'Medici':        0.522,
114
             'Pazzi':         0.000,
115
             'Peruzzi':       0.022,
116
             'Ridolfi':       0.117,
117
             'Salviati':      0.143,
118
             'Strozzi':       0.106,
119
             'Tornabuoni':    0.090}
120
        for n in sorted(G):
121
            assert_almost_equal(c[n], d[n], places=3)
122

    
123
    def test_les_miserables_load(self):
124
        G = self.LM
125
        c = nx.load_centrality(G)
126
        d = {'Napoleon': 0.000,
127
             'Myriel': 0.177,
128
             'MlleBaptistine': 0.000,
129
             'MmeMagloire': 0.000,
130
             'CountessDeLo': 0.000,
131
             'Geborand': 0.000,
132
             'Champtercier': 0.000,
133
             'Cravatte': 0.000,
134
             'Count': 0.000,
135
             'OldMan': 0.000,
136
             'Valjean': 0.567,
137
             'Labarre': 0.000,
138
             'Marguerite': 0.000,
139
             'MmeDeR': 0.000,
140
             'Isabeau': 0.000,
141
             'Gervais': 0.000,
142
             'Listolier': 0.000,
143
             'Tholomyes': 0.043,
144
             'Fameuil': 0.000,
145
             'Blacheville': 0.000,
146
             'Favourite': 0.000,
147
             'Dahlia': 0.000,
148
             'Zephine': 0.000,
149
             'Fantine': 0.128,
150
             'MmeThenardier': 0.029,
151
             'Thenardier': 0.075,
152
             'Cosette': 0.024,
153
             'Javert': 0.054,
154
             'Fauchelevent': 0.026,
155
             'Bamatabois': 0.008,
156
             'Perpetue': 0.000,
157
             'Simplice': 0.009,
158
             'Scaufflaire': 0.000,
159
             'Woman1': 0.000,
160
             'Judge': 0.000,
161
             'Champmathieu': 0.000,
162
             'Brevet': 0.000,
163
             'Chenildieu': 0.000,
164
             'Cochepaille': 0.000,
165
             'Pontmercy': 0.007,
166
             'Boulatruelle': 0.000,
167
             'Eponine': 0.012,
168
             'Anzelma': 0.000,
169
             'Woman2': 0.000,
170
             'MotherInnocent': 0.000,
171
             'Gribier': 0.000,
172
             'MmeBurgon': 0.026,
173
             'Jondrette': 0.000,
174
             'Gavroche': 0.164,
175
             'Gillenormand': 0.021,
176
             'Magnon': 0.000,
177
             'MlleGillenormand': 0.047,
178
             'MmePontmercy': 0.000,
179
             'MlleVaubois': 0.000,
180
             'LtGillenormand': 0.000,
181
             'Marius': 0.133,
182
             'BaronessT': 0.000,
183
             'Mabeuf': 0.028,
184
             'Enjolras': 0.041,
185
             'Combeferre': 0.001,
186
             'Prouvaire': 0.000,
187
             'Feuilly': 0.001,
188
             'Courfeyrac': 0.006,
189
             'Bahorel': 0.002,
190
             'Bossuet': 0.032,
191
             'Joly': 0.002,
192
             'Grantaire': 0.000,
193
             'MotherPlutarch': 0.000,
194
             'Gueulemer': 0.005,
195
             'Babet': 0.005,
196
             'Claquesous': 0.005,
197
             'Montparnasse': 0.004,
198
             'Toussaint': 0.000,
199
             'Child1': 0.000,
200
             'Child2': 0.000,
201
             'Brujon': 0.000,
202
             'MmeHucheloup': 0.000}
203
        for n in sorted(G):
204
            assert_almost_equal(c[n], d[n], places=3)
205

    
206
    def test_unnormalized_k5_load(self):
207
        G = self.K5
208
        c = nx.load_centrality(G, normalized=False)
209
        d = {0: 0.000,
210
             1: 0.000,
211
             2: 0.000,
212
             3: 0.000,
213
             4: 0.000}
214
        for n in sorted(G):
215
            assert_almost_equal(c[n], d[n], places=3)
216

    
217
    def test_unnormalized_p3_load(self):
218
        G = self.P3
219
        c = nx.load_centrality(G, normalized=False)
220
        d = {0: 0.000,
221
             1: 2.000,
222
             2: 0.000}
223
        for n in sorted(G):
224
            assert_almost_equal(c[n], d[n], places=3)
225

    
226
    def test_unnormalized_krackhardt_load(self):
227
        G = self.K
228
        c = nx.load_centrality(G, normalized=False)
229
        d = {0: 1.667,
230
             1: 1.667,
231
             2: 0.000,
232
             3: 7.333,
233
             4: 0.000,
234
             5: 16.667,
235
             6: 16.667,
236
             7: 28.000,
237
             8: 16.000,
238
             9: 0.000}
239

    
240
        for n in sorted(G):
241
            assert_almost_equal(c[n], d[n], places=3)
242

    
243
    def test_unnormalized_florentine_families_load(self):
244
        G = self.F
245
        c = nx.load_centrality(G, normalized=False)
246

    
247
        d = {'Acciaiuoli':  0.000,
248
             'Albizzi':    38.333,
249
             'Barbadori':  17.000,
250
             'Bischeri':   19.000,
251
             'Castellani': 10.000,
252
             'Ginori':     0.000,
253
             'Guadagni':   45.667,
254
             'Lamberteschi': 0.000,
255
             'Medici':     95.000,
256
             'Pazzi':      0.000,
257
             'Peruzzi':    4.000,
258
             'Ridolfi':    21.333,
259
             'Salviati':   26.000,
260
             'Strozzi':    19.333,
261
             'Tornabuoni': 16.333}
262
        for n in sorted(G):
263
            assert_almost_equal(c[n], d[n], places=3)
264

    
265
    def test_load_betweenness_difference(self):
266
        # Difference Between Load and Betweenness
267
        # --------------------------------------- The smallest graph
268
        # that shows the difference between load and betweenness is
269
        # G=ladder_graph(3) (Graph B below)
270

    
271
        # Graph A and B are from Tao Zhou, Jian-Guo Liu, Bing-Hong
272
        # Wang: Comment on "Scientific collaboration
273
        # networks. II. Shortest paths, weighted networks, and
274
        # centrality". https://arxiv.org/pdf/physics/0511084
275

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

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

    
290
        # A = nx.Graph()
291
        # A.add_edges_from([(0,1), (1,2), (1,3), (2,4),
292
        #                  (3,5), (4,6), (4,7), (4,8),
293
        #                  (5,8), (6,9), (7,9), (8,9)])
294
        B = nx.Graph()  # ladder_graph(3)
295
        B.add_edges_from([(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (4, 5), (3, 5)])
296
        c = nx.load_centrality(B, normalized=False)
297
        d = {0: 1.750,
298
             1: 1.750,
299
             2: 6.500,
300
             3: 6.500,
301
             4: 1.750,
302
             5: 1.750}
303
        for n in sorted(B):
304
            assert_almost_equal(c[n], d[n], places=3)
305

    
306
    def test_c4_edge_load(self):
307
        G = self.C4
308
        c = nx.edge_load_centrality(G)
309
        d = {(0, 1): 6.000,
310
             (0, 3): 6.000,
311
             (1, 2): 6.000,
312
             (2, 3): 6.000}
313
        for n in G.edges():
314
            assert_almost_equal(c[n], d[n], places=3)
315

    
316
    def test_p4_edge_load(self):
317
        G = self.P4
318
        c = nx.edge_load_centrality(G)
319
        d = {(0, 1): 6.000,
320
             (1, 2): 8.000,
321
             (2, 3): 6.000}
322
        for n in G.edges():
323
            assert_almost_equal(c[n], d[n], places=3)
324

    
325
    def test_k5_edge_load(self):
326
        G = self.K5
327
        c = nx.edge_load_centrality(G)
328
        d = {(0, 1): 5.000,
329
             (0, 2): 5.000,
330
             (0, 3): 5.000,
331
             (0, 4): 5.000,
332
             (1, 2): 5.000,
333
             (1, 3): 5.000,
334
             (1, 4): 5.000,
335
             (2, 3): 5.000,
336
             (2, 4): 5.000,
337
             (3, 4): 5.000}
338
        for n in G.edges():
339
            assert_almost_equal(c[n], d[n], places=3)
340

    
341
    def test_tree_edge_load(self):
342
        G = self.T
343
        c = nx.edge_load_centrality(G)
344
        d = {(0, 1): 24.000,
345
             (0, 2): 24.000,
346
             (1, 3): 12.000,
347
             (1, 4): 12.000,
348
             (2, 5): 12.000,
349
             (2, 6): 12.000}
350
        for n in G.edges():
351
            assert_almost_equal(c[n], d[n], places=3)