In [5]:
# Import dependencies
import numpy as np
import pickle
import networkx as nx
import matplotlib.pyplot as plt
In [ ]:
## Undirected Unweighted Graph
G1 = nx.Graph()
G1.add_edges_from([(1, 2), (1, 3), (3, 4), (5, 6), (7, 8), (2, 5), (8, 3), (5, 8)])
plt.clf()
pos=nx.spring_layout(G1) # positions for all nodes
nx.draw(G1, pos)
nx.draw_networkx_labels(G1, pos)
plt.title('(a) Undirected Unwieghted Graph')
plt.show()
In [ ]:
## Undirected Weighted Graph
G2 = nx.MultiGraph()
G2.add_weighted_edges_from([(1, 2, 0.1), (1, 3, 0.7), (3, 4, 1.0), (5, 6, 0.4),
(7, 8, 0.3), (2, 5, 0.3), (8, 3, 1.0), (5, 8, 0.5)])
pos=nx.spring_layout(G2) # positions for all nodes
nx.draw(G2, pos)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G2.edges(data=True)])
nx.draw_networkx_edge_labels(G2,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(G2, pos)
plt.title('(b) Undirected Wieghted Graph')
plt.show()
In [ ]:
## Directed Unweighted Graph
G3 = nx.DiGraph()
G3.add_edges_from([(1, 2), (1, 3), (3, 4), (5, 6), (7, 8), (2, 5), (8, 3), (5, 8)])
pos=nx.spring_layout(G3) # positions for all nodes
nx.draw(G3, pos)
nx.draw_networkx_labels(G3, pos)
plt.title('(c) Directed Unweighted Graph')
plt.show()
In [ ]:
## Directed Weighted Graph
G4 = nx.MultiDiGraph()
G4.add_weighted_edges_from([(1, 2, 0.1), (1, 3, 0.7), (3, 4, 1.0), (5, 6, 0.4),
(7, 8, 0.3), (2, 5, 0.3), (8, 3, 1.0), (5, 8, 0.5)])
pos=nx.spring_layout(G4) # positions for all nodes
nx.draw(G4, pos)
edge_labels=dict([((u,v,),d['weight'])
for u,v,d in G4.edges(data=True)])
nx.draw_networkx_edge_labels(G4,pos,edge_labels=edge_labels)
nx.draw_networkx_labels(G4, pos)
plt.title('(d) Directed Wieghted Graph')
plt.show()
In [ ]:
## Storing these graphs as adjacency matrix and adjacency list
G = {'G1 (UD-UW)': G1, 'G2 (UD-W)': G2,'G3 (D-UW)': G3,'G4 (D-W)': G4}
adjacency_matrix = dict()
edgelist = dict()
for key in G:
adjacency_matrix[key] = nx.to_numpy_matrix(G[key])
edgelist[key] = nx.to_edgelist(G[key])
# saving
with open('ques1_stired_networks.pickle', 'w') as f:
pickle.dump([adjacency_matrix, edgelist], f)
In [99]:
## Fuction to find degree from adjacency matrix
# function definition
def print_degree(adj):
"""
This function computes the degree of each node for a given adjacency matrix
For Uniderected Graphs:
It prints node wise degree and returns it.
For Directed Graphs:
It prnts both in degree and out degree and reurns both of them.
"""
if np.allclose(adj, adj.T, atol=1e-8):
print "Undirected Graph"
deg = np.sum(adj != 0, axis=0)
print "Degree of each node: " + np.str(deg)
else:
print "Directed Graph"
deg = list()
deg.append(np.sum(adj != 0, axis=0).astype(np.int))
deg.append(np.sum(adj != 0, axis=1).astype(np.int).T)
print "In Degree of each node: " + np.str(deg[0])
print "Out Degree of each node: " + np.str(deg[1])
return deg
# loading adjacency matrix which were saved in question 1
f = open('ques1_stired_networks.pickle', 'r')
adj_matrix, edge_list = pickle.load(f)
for key in adj_matrix:
print key
print_degree(adj_matrix[key])
In [ ]:
# Computing A square for Undirected nnweighted graph G1
A = adjacency_matrix['G1 (UD-UW)']
A = A.astype(np.int)
A_square = A*A
pos=nx.spring_layout(G1) # positions for all nodes
nx.draw(G1, pos)
nx.draw_networkx_labels(G1, pos)
plt.title('Undirected Unwieghted Graph')
plt.show()
print "A_square : \n " + np.str(A_square)
Clearly, $A^2$ as computed above for the undirected unweighted graph G1 (question 1) encodes the information of the number of paths of length 2 from each node to every other node. For Example, Cosider the pair of nodes 1 and 4. There exists a path of length 2 from node 1 to node 4 via node 3, thereby giving $A^2_{(1, 4)} = 1$ . Similarly, there exists three paths of length 2 from node 8 back to node 8, via node 3, node 5 and node 7. Thus we have $A^2_{(8, 8)} = 3$. In general, $A^n_{(i, j)}$ gives the number of paths of length $n$ from node $i$ to node $j$ in the undirected unweighted graph.
In [94]:
## Reading C. Elegans neural network dataset
G_celegans = nx.read_gml('Newman_Datasets/celegansneural/celegansneural.gml')
G_celegans_adj = nx.to_numpy_matrix(G_celegans)
G_celegans_deg = print_degree(G_celegans_adj) # function written in question 2
# Plotting
plt.hist(np.asarray(G_celegans_deg[0])[0], bins='auto')
plt.title("In Degree Distribution for C. Elegans Neural Network")
plt.xlabel("Degree")
plt.ylabel("Frequency")
plt.show()
plt.hist(np.asarray(G_celegans_deg[1])[0], bins='auto')
plt.title("Out Degree Distribution for C. Elegans Neural Network")
plt.xlabel("Degree")
plt.ylabel("Frequency")
plt.show()
In [95]:
## Reading C. Elegans neural network dataset
G_adjnoun = nx.read_gml('Newman_Datasets/adjnoun/adjnoun.gml')
G_adjnoun_adj = nx.to_numpy_matrix(G_adjnoun)
G_adjnoun_deg = print_degree(G_adjnoun_adj) # function written in question 2
# Plotting
plt.hist(np.asarray(G_adjnoun_deg[0])[0], bins='auto')
plt.title("In Degree Distribution for C. Elegans Neural Network")
plt.xlabel("Degree")
plt.ylabel("Frequency")
plt.show()
In [98]:
## Random Undirected Unweighted Graph
def create_random_graph(n, e):
"""
This function creates a random adjacncy matrix for a simple
undirected unweighted graph with n nodes and e edges.
It returns the randomly computed adjacency matrix.
"""
adj = np.zeros((nodes, nodes))
edges = 0;
while edges < e:
i = np.random.randint(0, n-2)
j = np.random.randint(1, n-1)
if (adj[i][j] == 1):
continue
adj[i][j] = 1
edges = edges+1
In [97]:
?np.zeros