Spaces:
Runtime error
Runtime error
File size: 2,678 Bytes
35b22df |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
"""
==========
Blockmodel
==========
Example of creating a block model using the quotient_graph function in NX. Data
used is the Hartford, CT drug users network::
@article{weeks2002social,
title={Social networks of drug users in high-risk sites: Finding the connections},
url = {https://doi.org/10.1023/A:1015457400897},
doi = {10.1023/A:1015457400897},
author={Weeks, Margaret R and Clair, Scott and Borgatti, Stephen P and Radda, Kim and Schensul, Jean J},
journal={{AIDS and Behavior}},
volume={6},
number={2},
pages={193--206},
year={2002},
publisher={Springer}
}
"""
from collections import defaultdict
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np
from scipy.cluster import hierarchy
from scipy.spatial import distance
def create_hc(G):
"""Creates hierarchical cluster of graph G from distance matrix"""
path_length = nx.all_pairs_shortest_path_length(G)
distances = np.zeros((len(G), len(G)))
for u, p in path_length:
for v, d in p.items():
distances[u][v] = d
# Create hierarchical cluster
Y = distance.squareform(distances)
Z = hierarchy.complete(Y) # Creates HC using farthest point linkage
# This partition selection is arbitrary, for illustrive purposes
membership = list(hierarchy.fcluster(Z, t=1.15))
# Create collection of lists for blockmodel
partition = defaultdict(list)
for n, p in zip(list(range(len(G))), membership):
partition[p].append(n)
return list(partition.values())
G = nx.read_edgelist("hartford_drug.edgelist")
# Extract largest connected component into graph H
H = G.subgraph(next(nx.connected_components(G)))
# Makes life easier to have consecutively labeled integer nodes
H = nx.convert_node_labels_to_integers(H)
# Create partitions with hierarchical clustering
partitions = create_hc(H)
# Build blockmodel graph
BM = nx.quotient_graph(H, partitions, relabel=True)
# Draw original graph
pos = nx.spring_layout(H, iterations=100, seed=83) # Seed for reproducibility
plt.subplot(211)
nx.draw(H, pos, with_labels=False, node_size=10)
# Draw block model with weighted edges and nodes sized by number of internal nodes
node_size = [BM.nodes[x]["nnodes"] * 10 for x in BM.nodes()]
edge_width = [(2 * d["weight"]) for (u, v, d) in BM.edges(data=True)]
# Set positions to mean of positions of internal nodes from original graph
posBM = {}
for n in BM:
xy = np.array([pos[u] for u in BM.nodes[n]["graph"]])
posBM[n] = xy.mean(axis=0)
plt.subplot(212)
nx.draw(BM, posBM, node_size=node_size, width=edge_width, with_labels=False)
plt.axis("off")
plt.show()
|