In [3]:
edges = set([(1, 2), (3, 1), (3, 2), (2, 4)])
In [6]:
edges = set([(1, 2), (3, 1), (3, 2), (2, 4)])
edges_list = [i[0] for i in edges] + [i[1] for i in edges]
nodes = set(edges_list)
edges_number = len(edges)
nodes_number = len(nodes)
print "Número de nodos: " + str(nodes_number)
print "Número de enlaces: " + str(edges_number)
"""Now using NetorkX"""
import networkx as nx
G = nx.Graph()
G.add_edges_from(edges)
print "Número de nodos: " + str(G.number_of_nodes())
print "Número de aristas: " + str(G.number_of_edges())
In [21]:
"""Código propio"""
import numpy as np
edges = set([(1,2), (3, 1), (3, 2), (2, 4)])
def adj_matrix_dgraph(edges):
edges_list = [i[0] for i in edges] + [i[1] for i in edges]
nodes = set(edges_list)
"""create matrix"""
matrix = np.zeros((len(nodes),len(nodes)))
for edge in edges:
matrix[edge[0] - 1,edge[1] -1] = 1
return matrix
def adj_matrix(edges):
edges_list = [i[0] for i in edges] + [i[1] for i in edges]
nodes = set(edges_list)
"""create matrix"""
matrix = np.zeros((len(nodes),len(nodes)))
for edge in edges:
i = edge[0]-1
j = edge[1]-1
matrix[i,j] = 1
matrix[j,i] = 1
return matrix
print "matriz para grafo dirigido:\n" + str(adj_matrix_dgraph(edges))
print "\n"
print "matriz para grafo no dirigido:\n" + str(adj_matrix(edges))
"""Solución con NetworkX"""
import networkx as nx
G = nx.Graph()
G.add_edges_from(edges)
matrix = nx.adjacency_matrix(G)
print matrix
DG = nx.DiGraph()
DG.add_edges_from(edges)
print "\n"
print (nx.adjacency_matrix(DG))
D## Ejercicio - Sparseness
Calcule la proporción entre número de links existentes en 3 redes reales (http://snap.stanford.edu/data/index.html) contra el número de links posibles.
In [11]:
import numpy as np
""" The entered datasets correspond to non-directed graphs"""
""" information about the dataset can be found in the following link:
http://snap.stanford.edu/data/egonets-Facebook.html """
edges1 = np.genfromtxt('0.edges', dtype="int", delimiter=" ")
edges2 = np.genfromtxt('348.edges', dtype="int", delimiter=" ")
edges3 = np.genfromtxt('414.edges', dtype="int", delimiter=" ")
def edges_to_nodes(edges):
edges_list = [i[0] for i in edges] + [i[1] for i in edges]
nodes = set(edges_list)
return nodes
def edge_rate(edges):
nodes = edges_to_nodes(edges)
n = len(nodes)
print ("len(n) = %d" %(n))
""" For a non-directed graph and excluding reflexive relations"""
possible_edges = (n*(n-1))/2
print ("possible_edges=%d" % (possible_edges))
result = float(len(edges))/possible_edges
return result
def edge_rate_dgraph(edges):
nodes = edges_to_nodes(edges)
n = len(nodes)
""" For a directed graph including reflexive relations"""
possible_edges = n**2
result = float(len(edges))/possible_edges
return result
print (edge_rate(edges1))
print (edge_rate(edges2))
print (edge_rate(edges3))
""" With networkx """
import networkx as nx
G1 = nx.read_edgelist('0.edges', delimiter=" ")
G2 = nx.read_edgelist('348.edges', delimiter=" ")
G3 = nx.read_edgelist('414.edges', delimiter=" ")
def possible_edges(graph):
nodes = graph.number_of_nodes()
return (nodes*(nodes-1))/2
print ("possible_edges(G1)=%d" % (possible_edges(G1)))
def edge_rate_nx(graph):
return float(graph.number_of_edges())/float(possible_edges(graph))
print ("\n")
print (edge_rate_nx(G1))
print (edge_rate_nx(G2))
print (edge_rate_nx(G3))
En la matriz de adyacencia de cada uno de las redes elegidas, cuantos ceros hay?
In [14]:
""" Without NetworkX """
import numpy as np
def edges_to_nodes(edges):
edges_list = [i[0] for i in edges] + [i[1] for i in edges]
nodes = set(edges_list)
print ("len(nodes)=%d" %(len(nodes)))
return nodes
""" The entered datasets correspond to non-directed graphs"""
""" information about the dataset can be found in the following link:
http://snap.stanford.edu/data/egonets-Facebook.html """
edges1 = np.genfromtxt('0.edges', dtype="int", delimiter=" ")
print (len(edges1))
edges2 = np.genfromtxt('348.edges', dtype="int", delimiter=" ")
print (len(edges2))
edges3 = np.genfromtxt('414.edges', dtype="int", delimiter=" ")
print (len(edges3))
""" Asuming there aren't repeated elements in the dataset """
def number_of_zeroes(edges):
n = len(edges_to_nodes(edges))
zeroes = n**2 - len(edges)
return zeroes
def number_of_zeroes_dgraph(edges):
n = len(edges_to_nodes(edges))
zeroes = n**2 - len(edges)
return zeroes
print ("number_of_zeroes(edges1)=%d" %(number_of_zeroes(edges1)))
print ("number_of_zeroes(edges2)=%d" %(number_of_zeroes(edges2)))
print ("number_of_zeroes(edges3)=%d" %(number_of_zeroes(edges3)))
In [12]:
""" With NetworkX """
import networkx as nx
""" The selected datasets are non-directed graphs. Therefore their adjacency matrix is simetrical """
""" For undirected graphs NetworkX stores only the edges of one of the matrix's triangles (upper or lower)"""
G1 = nx.read_edgelist('0.edges', delimiter=" ")
print (len(G1.edges()))
G2 = nx.read_edgelist('348.edges', delimiter=" ")
print (len(G2.edges()))
G3 = nx.read_edgelist('414.edges', delimiter=" ")
print (len(G3.edges()))
N1 = len(G1.nodes())
N2 = len(G2.nodes())
N3 = len(G3.nodes())
def zeroes(graph):
N = len(graph.nodes())
result = N**2 - 2*len(graph.edges())
print ("zeroes=%d" %(result))
return result
zeroes(G1)
zeroes(G2)
zeroes(G3)
Out[12]:
In [29]:
import numpy as np
network1 = set([(1,'a'),(3,'b'), (4,'d'),(5,'b'),(1,'b'), (2,'d'), (1,'d'), (3,'c')])
def projection_u(edges):
edges_list = list(edges)
result = []
for i in range(0,len(edges_list)):
for j in range(i+1, len(edges_list)):
if edges_list[i][1] == edges_list[j][1]:
tup = (edges_list[i][0], edges_list[j][0])
result.append(tup)
return set(result)
print (projection_u(network1))
def projection_v(edges):
edges_list = list(edges)
result = []
for i in range(0,len(edges_list)):
for j in range(i+1, len(edges_list)):
if edges_list[i][0] == edges_list[j][0]:
tup = (edges_list[i][1], edges_list[j][1])
result.append(tup)
return set(result)
print (projection_v(network1))
In [ ]:
Baje una red real (http://snap.stanford.edu/data/index.html) y lea el archivo
In [ ]:
Utilizando NetworkX o iGraph descubra el número de componentes
In [ ]:
Implemente el algorithmo Breadth First para encontrar el número de componentes (revise que el resultado es el mismo que utilizando la librería)
In [ ]:
In [4]:
Calcule el grado promedio
In [ ]:
In [7]:
N = 5
Cree un grafo de N nodos con el máximo diámetro posible
In [ ]:
Cree un grafo de N nodos con el mínimo diámetro posible
In [ ]:
Cree un grafo de N nodos que sea un ciclo simple
In [ ]:
In [8]:
routemap = [('St. Louis', 'Miami'),
('St. Louis', 'San Diego'),
('St. Louis', 'Chicago'),
('San Diego', 'Chicago'),
('San Diego', 'San Francisco'),
('San Diego', 'Minneapolis'),
('San Diego', 'Boston'),
('San Diego', 'Portland'),
('San Diego', 'Seattle'),
('Tulsa', 'New York'),
('Tulsa', 'Dallas'),
('Phoenix', 'Cleveland'),
('Phoenix', 'Denver'),
('Phoenix', 'Dallas'),
('Chicago', 'New York'),
('Chicago', 'Los Angeles'),
('Miami', 'New York'),
('Miami', 'Philadelphia'),
('Miami', 'Denver'),
('Boston', 'Atlanta'),
('Dallas', 'Cleveland'),
('Dallas', 'Albuquerque'),
('Philadelphia', 'Atlanta'),
('Denver', 'Minneapolis'),
('Denver', 'Cleveland'),
('Albuquerque', 'Atlanta'),
('Minneapolis', 'Portland'),
('Los Angeles', 'Seattle'),
('San Francisco', 'Portland'),
('San Francisco', 'Seattle'),
('San Francisco', 'Cleveland'),
('Seattle', 'Portland')]
Cuál es el máximo número de intercambios que tendría que hacer un pasajero en un solo viaje entre dos ciudades servidas? (suponiendo rutas óptimas)
In [ ]:
Si usted necesitara viajar mucho en esta aerolínea, cual sería el lugar óptimo para vivir? (i.e. minimizar el número de intercambios para llegar a cualquier ciudad)
In [ ]:
Visualize la red
In [ ]: