Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / examples / algorithms / plot_blockmodel.py @ 5cef0f13

History | View | Annotate | Download (2.82 KB)

1
#!/usr/bin/env python
2
# encoding: utf-8
3
"""
4
==========
5
Blockmodel
6
==========
7

8
Example of creating a block model using the quotient_graph function in NX.  Data
9
used is the Hartford, CT drug users network::
10

11
    @article{weeks2002social,
12
      title={Social networks of drug users in high-risk sites: Finding the connections},
13
      url = {https://doi.org/10.1023/A:1015457400897},
14
      doi = {10.1023/A:1015457400897},
15
      author={Weeks, Margaret R and Clair, Scott and Borgatti, Stephen P and Radda, Kim and Schensul, Jean J},
16
      journal={{AIDS and Behavior}},
17
      volume={6},
18
      number={2},
19
      pages={193--206},
20
      year={2002},
21
      publisher={Springer}
22
    }
23

24
"""
25
# Authors:  Drew Conway <drew.conway@nyu.edu>, Aric Hagberg <hagberg@lanl.gov>
26

    
27
from collections import defaultdict
28

    
29
import matplotlib.pyplot as plt
30
import networkx as nx
31
import numpy
32
from scipy.cluster import hierarchy
33
from scipy.spatial import distance
34

    
35

    
36
def create_hc(G):
37
    """Creates hierarchical cluster of graph G from distance matrix"""
38
    path_length = nx.all_pairs_shortest_path_length(G)
39
    distances = numpy.zeros((len(G), len(G)))
40
    for u, p in path_length:
41
        for v, d in p.items():
42
            distances[u][v] = d
43
    # Create hierarchical cluster
44
    Y = distance.squareform(distances)
45
    Z = hierarchy.complete(Y)  # Creates HC using farthest point linkage
46
    # This partition selection is arbitrary, for illustrive purposes
47
    membership = list(hierarchy.fcluster(Z, t=1.15))
48
    # Create collection of lists for blockmodel
49
    partition = defaultdict(list)
50
    for n, p in zip(list(range(len(G))), membership):
51
        partition[p].append(n)
52
    return list(partition.values())
53

    
54

    
55
if __name__ == '__main__':
56
    G = nx.read_edgelist("hartford_drug.edgelist")
57

    
58
    # Extract largest connected component into graph H
59
    H = next(nx.connected_component_subgraphs(G))
60
    # Makes life easier to have consecutively labeled integer nodes
61
    H = nx.convert_node_labels_to_integers(H)
62
    # Create parititions with hierarchical clustering
63
    partitions = create_hc(H)
64
    # Build blockmodel graph
65
    BM = nx.quotient_graph(H, partitions, relabel=True)
66

    
67
    # Draw original graph
68
    pos = nx.spring_layout(H, iterations=100)
69
    plt.subplot(211)
70
    nx.draw(H, pos, with_labels=False, node_size=10)
71

    
72
    # Draw block model with weighted edges and nodes sized by number of internal nodes
73
    node_size = [BM.nodes[x]['nnodes'] * 10 for x in BM.nodes()]
74
    edge_width = [(2 * d['weight']) for (u, v, d) in BM.edges(data=True)]
75
    # Set positions to mean of positions of internal nodes from original graph
76
    posBM = {}
77
    for n in BM:
78
        xy = numpy.array([pos[u] for u in BM.nodes[n]['graph']])
79
        posBM[n] = xy.mean(axis=0)
80
    plt.subplot(212)
81
    nx.draw(BM, posBM, node_size=node_size, width=edge_width, with_labels=False)
82
    plt.axis('off')
83
    plt.show()