Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / examples / advanced / plot_parallel_betweenness.py @ 5cef0f13

History | View | Annotate | Download (2.8 KB)

1
"""
2
====================
3
Parallel Betweenness
4
====================
5

6
Example of parallel implementation of betweenness centrality using the
7
multiprocessing module from Python Standard Library.
8

9
The function betweenness centrality accepts a bunch of nodes and computes
10
the contribution of those nodes to the betweenness centrality of the whole
11
network. Here we divide the network in chunks of nodes and we compute their
12
contribution to the betweenness centrality of the whole network.
13

14
This doesn't work in python2.7.13. It does work in 3.6, 3.5, 3.4, and 3.3.
15

16
It may be related to this:
17
https://stackoverflow.com/questions/1816958/cant-pickle-type-instancemethod-when-using-multiprocessing-pool-map
18
"""
19

    
20
from multiprocessing import Pool
21
import time
22
import itertools
23

    
24
import matplotlib.pyplot as plt
25
import networkx as nx
26

    
27

    
28
def chunks(l, n):
29
    """Divide a list of nodes `l` in `n` chunks"""
30
    l_c = iter(l)
31
    while 1:
32
        x = tuple(itertools.islice(l_c, n))
33
        if not x:
34
            return
35
        yield x
36

    
37

    
38
def _betmap(G_normalized_weight_sources_tuple):
39
    """Pool for multiprocess only accepts functions with one argument.
40
    This function uses a tuple as its only argument. We use a named tuple for
41
    python 3 compatibility, and then unpack it when we send it to
42
    `betweenness_centrality_source`
43
    """
44
    return nx.betweenness_centrality_source(*G_normalized_weight_sources_tuple)
45

    
46

    
47
def betweenness_centrality_parallel(G, processes=None):
48
    """Parallel betweenness centrality  function"""
49
    p = Pool(processes=processes)
50
    node_divisor = len(p._pool) * 4
51
    node_chunks = list(chunks(G.nodes(), int(G.order() / node_divisor)))
52
    num_chunks = len(node_chunks)
53
    bt_sc = p.map(_betmap,
54
                  zip([G] * num_chunks,
55
                      [True] * num_chunks,
56
                      [None] * num_chunks,
57
                      node_chunks))
58

    
59
    # Reduce the partial solutions
60
    bt_c = bt_sc[0]
61
    for bt in bt_sc[1:]:
62
        for n in bt:
63
            bt_c[n] += bt[n]
64
    return bt_c
65

    
66

    
67
if __name__ == "__main__":
68
    G_ba = nx.barabasi_albert_graph(1000, 3)
69
    G_er = nx.gnp_random_graph(1000, 0.01)
70
    G_ws = nx.connected_watts_strogatz_graph(1000, 4, 0.1)
71
    for G in [G_ba, G_er, G_ws]:
72
        print("")
73
        print("Computing betweenness centrality for:")
74
        print(nx.info(G))
75
        print("\tParallel version")
76
        start = time.time()
77
        bt = betweenness_centrality_parallel(G)
78
        print("\t\tTime: %.4F" % (time.time() - start))
79
        print("\t\tBetweenness centrality for node 0: %.5f" % (bt[0]))
80
        print("\tNon-Parallel version")
81
        start = time.time()
82
        bt = nx.betweenness_centrality(G)
83
        print("\t\tTime: %.4F seconds" % (time.time() - start))
84
        print("\t\tBetweenness centrality for node 0: %.5f" % (bt[0]))
85
    print("")
86

    
87
    nx.draw(G_ba)
88
    plt.show()