Introducción

En ocaciones tenemos un gran cúmulo de datos que queremos trabajar. Por el otro lado tenemos tenemos toda la teoría de grafos con sus algoritmos listos para ser utilizados. Lo que haremos en este caso es transformar los datos en un grafo sobre el cual podemos aplicar algoritmos y trabajarlo.

¿Qué bibliotecas usamos?

En realidad únicamente necesitamos numpy, sin embargo, para fines didácticos vamos a visualizar estos grafos con la librería graphviz. Numpy es una biblioteca para manipular de manera eficiente matrices y vectores. Sin embargo, los datos pueden ser manipulados con otros formatos, incluso con listas.

import graphviz as gv
import numpy as np

Generar datos aleatorios

Como el programa que se presenta es únicamente experimental, generaremos los datos de manera aleatoria. En este caso se generarán dos vectores de tamaño s con una distribución uniforme, y se alinearán estos dos vectores en una matriz, para que sean usados como pares ordenados. En todo caso, es posible utilizar mas dimenciones para los datos, pero con fines de ejemplo utilizamos únicamente dos.

    def random(self, s=10):
a = np.random.uniform(size=s)
b = np.random.uniform(size=s)
self.M = np.asmatrix([a,b])
self.M = np.transpose(self.M)

Caluclar distancia entre datos

Todos los datos, tendrán una distancia entre ellos. Como las distancias pueden estar en diferentes proporciones, se normalizará esta distancia, y se guardará esta distancia  normalizada en una gran matriz. La normalización se realizará con valores entre 0 y 1. El tamaño de esta matriz será de NxN, donde es el número de elementos o nodos que conforman la base de datos sobre la cual trabajaremos.

    def d(self, X, Y):
return np.linalg.norm(X-Y)

def distances(self):
self.distM = np.zeros((len(self.M), len(self.M)))
i = 0
j = 0
for e in self.M:
j = 0
for comp in self.M:
self.distM[j][i] = self.d(e, comp)
j += 1
i += 1

La matriz generada tiene la siguiente forma:

[[ 0.          0.21379117  0.40710009  0.41951918  0.34378849  0.37930608  0.36877135  0.14890573  0.27751628  0.30984749]
[ 0.21379117 0. 0.56658621 0.60156439 0.26938347 0.28846624 0.15804788 0.34103335 0.40665657 0.13227704]
[ 0.40710009 0.56658621 0. 0.0899682 0.75087819 0.78629042 0.68109126 0.26209429 0.1667116 0.58520952]
[ 0.41951918 0.60156439 0.0899682 0. 0.7584622 0.7955392 0.72872109 0.27073779 0.22811138 0.6372304 ]
[ 0.34378849 0.26938347 0.75087819 0.7584622 0. 0.03904187 0.34568779 0.4907459 0.61428041 0.38490523]
[ 0.37930608 0.28846624 0.78629042 0.7955392 0.03904187 0. 0.34753505 0.52702771 0.6471632 0.39630257]
[ 0.36877135 0.15804788 0.68109126 0.72872109 0.34568779 0.34753505 0. 0.48303881 0.51485474 0.1014129 ]
[ 0.14890573 0.34103335 0.26209429 0.27073779 0.4907459 0.52702771 0.48303881 0. 0.1628538 0.40390833]
[ 0.27751628 0.40665657 0.1667116 0.22811138 0.61428041 0.6471632 0.51485474 0.1628538 0. 0.41851855]
[ 0.30984749 0.13227704 0.58520952 0.6372304 0.38490523 0.39630257 0.1014129 0.40390833 0.41851855 0. ]]

Utilizar un portal para generar una matriz de conexiones

 Para determinar si existe alguna relación entre un nodo y otro, utilizaremos un portal definido por nosotros. El portal es un valor arbitrario t donde toda distancia menor a este, será considerado como conectado, de lo contrario no habrá conexión.

    def threshold(self, t = .3):
print(self.distM)
self.distM[self.distM > t] = 2
self.distM[self.distM <= t] = 1
self.distM[self.distM == 2] = 0
np.fill_diagonal(self.distM, 0)
print(self.distM)

 La nueva matriz será una matriz de adjacencia. Y con ella ya habríamos generado el grafo.

[[ 0.  1.  1.  0.  0.  0.  0.  0.  1.  0.]
[ 1. 0. 0. 0. 1. 0. 1. 1. 0. 1.]
[ 1. 0. 0. 1. 0. 0. 1. 1. 0. 0.]
[ 0. 0. 1. 0. 1. 0. 0. 0. 1. 1.]
[ 0. 1. 0. 1. 0. 1. 0. 1. 1. 0.]
[ 0. 0. 0. 0. 1. 0. 1. 0. 0. 1.]
[ 0. 1. 1. 0. 0. 1. 0. 0. 1. 1.]
[ 0. 1. 1. 0. 1. 0. 0. 0. 1. 1.]
[ 1. 0. 0. 1. 1. 0. 1. 1. 0. 0.]
[ 0. 1. 0. 1. 0. 1. 1. 1. 0. 0.]]

Dibujar el grafo

 Para visualizar los datos, se puede presentar el grafo de manera visual. El resultado deberá ser parecido al siguiente ejemplo:

El código

# Licence GPL 3+
# Copyright: Jesús Mager, 2017

import graphviz as gv
import numpy as np


class GraphClass:
def __init__(self):
pass

def random(self, s=10):
a = np.random.uniform(size=s)
b = np.random.uniform(size=s)
self.M = np.asmatrix([a,b])
self.M = np.transpose(self.M)

def d(self, X, Y):
return np.linalg.norm(X-Y)

def distances(self):
self.distM = np.zeros((len(self.M), len(self.M)))
i = 0
j = 0
for e in self.M:
j = 0
for comp in self.M:
self.distM[j][i] = self.d(e, comp)
j += 1
i += 1

def threshold(self, t = .3):
print(self.distM)
self.distM[self.distM > t] = 2
self.distM[self.distM <= t] = 1
self.distM[self.distM == 2] = 0
np.fill_diagonal(self.distM, 0)
print(self.distM)

def draw(self):
used=[]
g = gv.Graph(format="svg")
for i in range(len(self.distM)):
g.node(str(self.M[i]))
for j in range(len(self.distM[i])):
if self.distM[j][i]:
if not str(self.M[i])+str(self.M[j]) in used:
used.append(str(self.M[i])+str(self.M[j]))
used.append(str(self.M[j])+str(self.M[i]))
g.edge(str(self.M[i]), str(self.M[j]))
g.render(view=True)


if __name__ == "__main__":
g = GraphClass()
g.random()
g.distances()
g.threshold()
g.draw()