Kitware TechTip 04-03-2013 Part 2: Computing fine-structure graph features

kw-techtip-04-03-2013-p2.py

"""kw-techtip-04-03-2013-p2.py

Fine-structure analysis of a graph.

Usage
-----
    
Assuming that the file "graph.txt" generated by kw-techtip-04-03-2013-p1.py
resides in "/tmp", run
    
$ python kw-techtip-04-03-2013-p2.py

to see what the feature matrix for the graph looks like.
"""


import pickle
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt


def visualize_subgraph(g, n):
    """Writes subgraph to .png file.
    """
    
    plt.title("Subgraph (Node: %.4d)" % n)
    colors = ['white'] * len(sg)
    colors[np.where(np.asarray(sg.nodes()) == n)[0]] = 'b'
    nx.draw(g, node_color=colors)
    plt.savefig("/tmp/sg-%.4d.pdf" % n)
    plt.close()


# Define the graph features
attr_list = [ #Average vertex degree
             lambda g : np.mean([e for e in g.degree().values()]),                 
             # Spectral radius (i.e., largest eigenvalue of adjacency matrix)
             lambda g : np.abs(nx.adjacency_spectrum(g))[0]]
 
# Load graph from disk
G = pickle.load(open("/tmp/graph.txt"))
 
# Run All-Shortest path algorithm
sps = nx.floyd_warshall_numpy(G)

# Consider all neighbors reachable via 2 hops
hops = 2 

V = np.zeros([len(G),len(attr_list)])
for n in G.nodes():
    # Select n-th row in shortest-path matrix
    nth_row = np.array(sps[n,:]).ravel()
    # Get all neighbors within the specified number of hops
    within_radius = np.where(nth_row <= hops)
    # Extract subgraph centered on n-th vertex
    sg = G.subgraph(within_radius[0])
    # Compute subragph features
    V[n,:] = np.asarray([attr_fun(sg) for attr_fun in attr_list]) 
    # Visualize the subgraph
    visualize_subgraph(sg, n)

print V
print "Feature matrix shape: (%d,%d)" % V.shape