In [1]:
from graphviz import Graph
G = Graph(format='png', filename='Steiner_Tree')
G.body.extend(['layout=neato'])
#G.node_attr.update(color='lightblue2', style='filled')
nodes_v = ['v1', 'v2', 'v3', 'v4', 'v5']
nodes_u = ['u1', 'u2']
# Add nodes to the graph
for no in nodes_v+nodes_u:
G.node(no, shape='circle',fontname='Times-Italic',
xlabel=no, label='', width='0.2')
for no in nodes_v:
G.node(no, style='filled', color='black')
edges=[('v1','u1',2),
('v2','u1',2),
('v3','u2',4),
('v4','u2',3),
('v5','u2',5),
('u1','u2',1)]
# Add edges to the graph
for ed in edges:
G.edge(ed[0],ed[1],label=str(ed[2]))
G
Out[1]:
In [3]:
import numpy as np
ten_points = np.matrix([[1,1,0,0,0,0,0,1,1,1],
[1,1,1,0,0,0,1,1,1,1],
[0,1,1,1,1,1,1,1,0,0],
[0,0,1,1,1,1,1,0,0,0],
[0,0,1,1,1,1,1,0,0,0],
[0,0,1,1,1,1,1,0,0,0],
[0,1,1,1,1,1,1,1,0,0],
[1,1,1,0,0,0,1,1,1,1],
[1,1,0,0,0,0,0,1,1,1],
[1,1,0,0,0,0,0,1,1,1]])
def markov_cluster(ad_matrix, power, inflation, verbose=False):
np.fill_diagonal(ad_matrix, 1)
#Initialize variable
old_ad_matrix = np.matrix([[2]])
verbose_output = [ad_matrix]
while not((ad_matrix == old_ad_matrix).all()):
old_ad_matrix = ad_matrix
# Take matrix to the power of "power"
ad_matrix = np.linalg.matrix_power(ad_matrix, power)
# Inflation step
for cell in np.nditer(ad_matrix, op_flags = ['readwrite']):
cell[...] = cell ** inflation
# Normalization
ad_matrix = ad_matrix/np.sum(ad_matrix, axis = 0)
verbose_output.append(ad_matrix)
if verbose:
return verbose_output
else:
return ad_matrix
In [4]:
markov_cluster(ten_points, 2,2, True)[:3]
Out[4]:
In [1]:
from graphviz import Graph
G = Graph(format='png', filename='Graph')
G.body.extend(['layout=neato'])
#G.node_attr.update(color='lightblue2', style='filled')
nodes_v = ['v1', 'v2', 'v3', 'v4', 'v5']
nodes_u = ['u1', 'u2', 'u3', 'u4']
# Add nodes to the graph
for no in nodes_v+nodes_u:
G.node(no, shape='circle',fontname='Times-Italic',
xlabel=no, label='', width='0.2')
for no in nodes_v:
G.node(no, style='filled', color='black')
edges=[('v1','v2',8), ('v1','v3',9), ('v1','u3',2), ('v1','u1',2),
('v2','v5',5), ('v2','u1',2), ('v2','u4',8),
('v3','v4',8), ('v3','u2',4),('v3','u3',8),
('v4','u2',3),
('v5','u2',5), ('v5','u4',8),
('u1','u2',1)]
# Add edges to the graph
for ed in edges:
G.edge(ed[0],ed[1],label=str(ed[2]))
G
Out[1]:
In [17]:
x = markov_cluster(ten_points,2,2)
import networkx as nx
import matplotlib.pyplot as plt
g = nx.from_numpy_matrix(x)
nx.draw_networkx(g)
plt.show()
In [7]:
import networkx as nx
import matplotlib.pyplot as plt
G = nx.barabasi_albert_graph(100,2)
nx.draw(G, node_size=40)
plt.show()
In [8]:
from networkx.algorithms import (closeness_centrality,
betweenness_centrality,
google_matrix)
#Computation of closeness, betweennes and page_rank
closeness = closeness_centrality(G)
betweenness = betweenness_centrality(G)
page_rank = google_matrix(G)
x = range(100)
%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use('seaborn-ticks')
#plt.plot(x,sorted_closeness, label='closeness')
#plt.plot(x, sorted_betweenness, 'o', label='betweenness')
plt.plot(x, list(closeness.values()), 'o', label='closeness')
plt.plot(x, list(betweenness.values()), 'o', label='betweenness')
#plt.bar(x, list(closeness.values()), label='closeness')
#plt.bar(x, list(betweenness.values()), label='betweenness', color='r')
plt.legend(loc=1)
Out[8]:
In [9]:
G2 = nx.barabasi_albert_graph(10000,2)
In [10]:
from collections import Counter
counts = Counter(G2.degree().values())
x,y = zip(*sorted(counts.items()))
y= [e/10000 for e in y]
plt.style.use('seaborn-ticks')
plt.loglog(x,y,'o')
plt.xlabel('Degree')
plt.ylabel('Fraction of Nodes')
Out[10]:
The node degree distribution follows a power law.
In [11]:
from networkx.algorithms.distance_measures import diameter
import math
print('Diameter:\t{}'.format(diameter(G2)))
print('Ln(|V|):\t{}'.format(math.log(10000, math.e)))