Figura

El gráfico (gráfico) se ha convertido gradualmente en un área central importante del aprendizaje automático. Antes de comenzar el aprendizaje del marco PGL, aprendamos los conceptos básicos de la imagen, el algoritmo clásico del gráfico y el desarrollo del aprendizaje en los últimos años.

1. ¿Cuál es la imagen?

En primer lugar, importamos las necesidades del paquete

import numpy as np
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt

Definición de la figura
El diagrama representa el objeto matemático de la relación entre el objeto y el objeto, que es el objeto de investigación básico del gráfico.

Por ejemplo, una figura simple puede ser así:

El nodo (nodo) está marcado con rojo y está conectado al lado negro (EDGE).

La figura se puede utilizar para representar:

Red social
Página web
Red de bio
…
¿Qué tipo de análisis podemos realizar en el mapa?

Topología de investigación y conectividad
Detección de grupos
Nodo del centro de identificación
Predecir el nodo que falta
Predecir la falta de
…
Primero importamos el primer pre-incorporado en nuestro cuaderno:

# Load the graph
G_karate = nx.karate_club_graph()
# Find key-values for the graph
pos = nx.spring_layout(G_karate)
# Plot the graph
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

Mapa del club de karate

¿Qué es esta foto de «karate»? Wayne W. Zachary estudió una red social de un club de karate entre 1970 y 1972. La red contiene 34 miembros de este club de karate, y la conexión entre las parejas miembro los representa en el club. Durante el estudio, hubo un conflicto entre el administrador Johna y el entrenador Mr.Hi (seudónimo), que llevó al club a dos. La mitad de los miembros han formado un nuevo club alrededor del Sr.Hi, y la otra mitad encontró un nuevo entrenador o abandonó el karate. Basado en los datos recopilados, además de uno de los miembros, zachary asigna correctamente los paquetes introducidos después de la división.

Método de expresión básico

• La figura g = (v, e) consta de los siguientes elementos:
• Un conjunto de nodos (también conocido como Verticle) v = 1, …, n
• Un grupo de E⊆V × V
• Lado (i, j) ∈ e nodo conectado I y J
• I y J se denominan nodos adyacentes (vecino)
• El grado de nodo se refiere al número de nodos adyacentes

Diagrama esquemático de nodos, bordes y grados

• Si todos los nodos de una figura tienen nodos adyacentes n-1, la figura se ha completado (Complete). Es decir, todos los nodos tienen toda la conexión posible.
• El trazado de I a J se refiere a la secuencia de bordes de I a J. La longitud de la ruta es igual al número de aristas que pasan.
• El diámetro de la figura hace referencia a la longitud de la ruta máxima en todas las rutas más cortas conectadas a dos nodos cualquiera.

Por ejemplo, en este caso, podemos calcular algunas rutas más cortas que conectan dos nodos. El diámetro de la figura es 3 porque no hay longitud de la trayectoria más corta entre dos nodos más allá de 3.

Una figura de un diámetro de 3

• La ruta geodésica hace referencia a la ruta más corta entre los dos nodos.
• Si todos los nodos se pueden conectar entre sí a través de una ruta de acceso, constituyen una rama conectiva (
  Componente. Si una imagen solo tiene una rama conectiva, la figura está conectada (Conectado)

Por ejemplo, a continuación se muestra un diagrama con dos ramas de conectividad diferentes:

Un mapa con dos ramas conectivas

• Si el borde de una figura es un par secuencial, la figura es Dirigida. IN-Degree significa i
  El número de bordes, out-deterree es el número lejos del lado de I
  

Mapa

• Si puede volver a un nodo determinado, la figura es cíclica. Por el contrario, si no se puede devolver al menos un nodo, la figura es acíclica.
• La figura se puede ponderar, es decir, se aplica al nodo o a la relación.
• Esta cifra es escasa (escasa) si el número de imágenes es menor que el número de nodos. Por otro lado, si el lado entre los nodos es grande, la cifra es intensiva (densa)

El libro de NEO4J sobre el algoritmo del diagrama da un resumen claro:

Resumen (de Neo4J Graph Book)

De vuelta a nuestro mapa del club de karate

En [8]
La propiedad .deee () devuelve una lista del grado de cada nodo de la figura (el número de nodos adyacentes):

n=34
print(G_karate.degree())
degree_sequence = list(G_karate.degree())
[(0, 16), (1, 9), (2, 10), (3, 6), (4, 3), (5, 4), (6, 4), (7, 4), (8, 5), (9, 2), (10, 3), (11, 1), (12, 2), (13, 5), (14, 2), (15, 2), (16, 2), (17, 2), (18, 2), (19, 3), (20, 2), (21, 2), (22, 2), (23, 5), (24, 3), (25, 3), (26, 2), (27, 4), (28, 3), (29, 4), (30, 4), (31, 6), (32, 12), (33, 17)]

En [9]
Calcule el número de aristas, pero también calcule la métrica de la secuencia:

nb_nodes = n
nb_arr = len(G_karate.edges())
avg_degree = np.mean(np.array(degree_sequence)[:,1])
med_degree = np.median(np.array(degree_sequence)[:,1])
max_degree = max(np.array(degree_sequence)[:,1])
min_degree = np.min(np.array(degree_sequence)[:,1])

Por último, imprima toda la información:

print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))
print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))
print("Average degree : " + str(avg_degree))
print("Median degree : " + str(med_degree))
Number of nodes : 34
Number of edges : 78
Maximum degree : 17
Minimum degree : 1
Average degree : 4.588235294117647
Median degree : 3.0

En [10]
En promedio, todos en la cifra están conectados a 4,6 personas.
Podemos dibujar el histograma de estos grados:

degree_freq = np.array(nx.degree_histogram(G_karate)).astype('float')
plt.figure(figsize=(12, 8))
plt.stem(degree_freq)
plt.ylabel("Frequence")
plt.xlabel("Degre")
plt.show()

Veremos que el histograma del grado es bastante importante, que se puede utilizar para determinar el tipo de higovamos a ver.

II. ¿Cómo almacenar el gráfico?

Hay tres maneras de almacenar gráficos, dependiendo de lo que quieras hacer:

Almacenar como una lista lateral:
1 2

5 ·

1 4

2 3

0 W

…

Almacenamos el ID de cada par de nodos conectados, por ejemplo:

En [ ]
G_karate.edges()
Utilice una matriz de adyacencia, que normalmente se carga en la memoria:
Para cada emparejamiento posible de la figura, si los dos nodos están conectados, establezca en 1. Si la figura no es un mapa, A es simétrica.

Utilice la lista de adyacencia:
1 ：[2, 3, 4]

2 ：[1,3]

3 ：[2, 4]

…

Estas tres representaciones son equivalentes, podemos seleccionar el modo de almacenamiento del diagrama de acuerdo con el uso de la escena.

III. Tipo y naturaleza de la figura

El gráfico se puede clasificar de acuerdo con diferentes estándares, y estamos aquí para decir un método de clasificación, la misma composición e isómero. Más información Puede ver blogs, Figura (2) – Varios mapas

• Diagrama simple e isomerial

Dos figuras G y H son gráficos ISOMÓRFICOS, que pueden generar la Figura H re-marcando los vértices del gráfico G.

Si G y H son isórficos, entonces sus órdenes son las mismas, sus tamaños son los mismos, y los grados de sus vértices corresponden a los mismos.

El gráfico heterogéneo es un nuevo concepto correspondiente al gráfico isórfico.

Solo hay un tipo de nodo y borde en los datos tradicionales de Gráfico homogéneo. Por lo tanto, al construir una red neuronal gráfica, todos los nodos comparten los mismos parámetros de modelo y tienen el mismo espacio de entidades dimensional.

Puede haber más de un tipo de nodos y bordes en un gráfico heterogéneo, por lo que se permite que diferentes tipos de nodos tengan diferentes entidades o atributos dimensionales.

4. El algoritmo gráfico principal

Actualmente, la mayoría de los marcos (como networkx de Python o Neo4J) admiten tres categorías principales de algoritmos de gráficos:

• Pathfinding: determine la ruta óptima en función de condiciones como la disponibilidad y la calidad. También incluimos algoritmos de búsqueda en esta categoría. Esto se puede utilizar para determinar la ruta más rápida o la ruta de tráfico.
• Centralidad: determine la importancia de los nodos en la red. Esto se puede utilizar para identificar personas influyentes en las redes sociales o para identificar posibles objetivos de ataque en la red.
• Detección de comunidades: la forma de evaluar la agrupación en clústeres de grupos. Esto se puede utilizar para dividir clientes o detectar fraudes, etc.

Todos los algoritmos de networkx se pueden encontrar aquí: https://networkx.github.io/documentation/stable/reference/algorithms/index.html

Solo introduciremos los algoritmos básicos más comunes implementados en networkx.

Algoritmo de búsqueda de pathsfinding y gráficos

• El algoritmo de búsqueda de rutas de acceso es encontrar la ruta más corta entre dos nodos minimizando el número de saltos.
• El algoritmo de búsqueda no da la ruta más corta, pero explora el gráfico de acuerdo con su situación o profundidad vecina. Esto se puede usar para la recuperación de información.

1). Algoritmo de búsqueda
Hay dos algoritmos principales de búsqueda de gráficos:

• Breadth First Search (BFS): primero explore los nodos vecinos de cada nodo y, a continuación, explore los nodos vecinos de los nodos vecinos;
• Búsqueda de profundidad primero (DFS): intente profundizar lo más profundamente posible en una ruta de acceso y visite nuevos nodos vecinos si es posible.

2). Algoritmo de pathfinding
Un. El camino más corto
La ruta más corta se calcula como la ruta ponderada más corta (si el gráfico está ponderado) entre un par de nodos.

Esto se puede utilizar para determinar la dirección óptima de conducción o el grado de separación entre dos personas en una red social.

Hay muchas maneras de calcular la ruta más corta en el gráfico, incluido el algoritmo de Dijkstra, que es el algoritmo predeterminado en networkx. Para obtener más información sobre el problema de ruta más corto, consulte: https://en.wikipedia.org/wiki/Shortest_path_problem

Ejemplo con diagrama de karate club

nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

Esto devuelve una lista de las rutas más pequeñas entre cada nodo del gráfico:

all_shortest_path = nx.shortest_path(G_karate)

Aquí está la ruta más corta entre el nodo 0 y el resto de los nodos

print(all_shortest_path[0])

Por ejemplo, la ruta más corta entre el nodo 0 y el nodo 26 es [0, 8, 33, 26]

{0: [0], 1: [0, 1], 2: [0, 2], 3: [0, 3], 4: [0, 4], 5: [0, 5], 6: [0, 6], 7: [0, 7], 8: [0, 8], 10: [0, 10], 11: [0, 11], 12: [0, 12], 13: [0, 13], 17: [0, 17], 19: [0, 19], 21: [0, 21], 31: [0, 31], 30: [0, 1, 30], 9: [0, 2, 9], 27: [0, 2, 27], 28: [0, 2, 28], 32: [0, 2, 32], 16: [0, 5, 16], 33: [0, 8, 33], 24: [0, 31, 24], 25: [0, 31, 25], 23: [0, 2, 27, 23], 14: [0, 2, 32, 14], 15: [0, 2, 32, 15], 18: [0, 2, 32, 18], 20: [0, 2, 32, 20], 22: [0, 2, 32, 22], 29: [0, 2, 32, 29], 26: [0, 8, 33, 26]}

B. Camino más corto de una sola fuente
Ruta de acceso más corta de origen único (SSSP) es encontrar la ruta más corta entre un nodo determinado y todos los demás nodos del gráfico.

Esto se utiliza comúnmente en los Routing Protocol para las redes IP.

nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

Devolver la ruta más corta entre el nodo (origen) 0 dado y otros nodos en el gráfico

print(list(nx.single_source_shortest_path(G_karate, source=0)))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 17, 19, 21, 31, 30, 9, 27, 28, 32, 16, 33, 24, 25, 23, 14, 15, 18, 20, 22, 29, 26]

c. El camino más corto de todos los pares
El algoritmo all pairs shortest path (APSP) es encontrar la trayectoria más corta entre todos los pares de nodos.

Aunque puede proporcionar resultados similares, es más rápido que llamar al algoritmo de ruta de acceso más corta de origen único para cada par de nodos. Este algoritmo se puede utilizar normalmente para determinar la carga de tráfico de diferentes secciones de la cuadrícula de tráfico.

En [33]

nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

Devuelve el camino más corto de todos los pares

all_path_length = list(nx.all_pairs_shortest_path_length(G_karate))
print(all_path_length[0])
(0, {0: 0, 1: 1, 2: 1, 3: 1, 4: 1, 5: 1, 6: 1, 7: 1, 8: 1, 10: 1, 11: 1, 12: 1, 13: 1, 17: 1, 19: 1, 21: 1, 31: 1, 30: 2, 9: 2, 27: 2, 28: 2, 32: 2, 16: 2, 33: 2, 24: 2, 25: 2, 23: 3, 14: 3, 15: 3, 18: 3, 20: 3, 22: 3, 29: 3, 26: 3})

d. Árbol de expansión de peso mínimo (árbol de expansión mínimo) es un subgrafía de un gráfico (un árbol), que utiliza pesos y el borde más pequeño para conectar todos los nodos en el gráfico.

Tenga en cuenta que el árbol de expansión mínimo se debe utilizar para gráficos no dirigidos.

from networkx.algorithms import tree
mst = tree.minimum_spanning_edges(G_karate, algorithm='prim', data=False)
edgelist = list(mst)
edgelist = sorted(edgelist)
G = nx.Graph()#Create an empty network diagram
G.add_edges_from(edgelist)
plt.figure()
nx.draw(G,pos = pos, node_color = 'b',edge_color = 'r',with_labels = True,font_size =18, node_size =20)

2. Detección comunitaria La detección comunitaria es dividir los nodos en varios grupos según un índice de calidad determinado.

Esto a menudo se puede usar para identificar comunidades sociales, comportamiento de clientes o temas web. Una comunidad hace referencia a una colección de nodos conectados. Sin embargo, actualmente no hay una definición ampliamente aceptada de comunidad, pero los nodos dentro de la comunidad deben estar densamente conectados.

El algoritmo Girvan Newman es un algoritmo comúnmente utilizado para descubrir comunidades. Define la comunidad eliminando gradualmente los bordes dentro de la red. Llamamos intermediario «límite entre la unión (límite entre la unión)». Se trata de un valor proporcional al número de rutas más cortas entre pares de nodos que cruzan la arista.

Los pasos del algoritmo son los siguientes:

1. Calcule la intermediación de todas las aristas existentes en la red.
2. Retire el borde con el intermediario más alto.
3. Después de quitar la arista, vuelva a calcular las propiedades intermedias de todas las aristas.
4. Repita los pasos 2 y 3 hasta que no queden más bordes.

from networkx.algorithms import community
import itertools
k = 1
comp = community.girvan_newman(G_karate)
for communities in itertools.islice(comp, k):
    print(tuple(sorted(c) for c in communities))
([0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 16, 17, 19, 21], [2, 8, 9, 14, 15, 18, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33])

3. Agrupación jerárquica
   En la agrupación en clústeres jerárquicos, creamos una jerarquía de clústeres. Representamos clústeres en forma de dendrograma.
   

La idea es analizar la estructura de la comunidad en diferentes escalas. Normalmente construimos un diagrama de árbol de abajo hacia arriba. Comenzamos con un clúster por nodo y, a continuación, combinamos los dos nodos «más cercanos».

Pero, ¿cómo medimos si los clústeres son similares? Usamos la distancia de similitud. Deje que d(i,j) sea la longitud del camino más corto entre i y j.

Para obtener la conexión máxima, en cada paso, los dos clústeres separados por la distancia más corta se combinan entre sí. La distancia de similitud se puede ilustrar mediante el siguiente diagrama

Volvamos a nuestro ejemplo de karate. Antes de aplicar la agrupación en clústeres jerárquicos, necesitamos definir la matriz de distancia entre cada nodo.

pcc_longueurs=list(nx.all_pairs_shortest_path_length(G_karate))
distances=np.zeros((n,n))# distances[i, j] is the length of the shortest path between i and j
for i in range(n):
    for j in range(n):
        distances[i, j] = pcc_longueurs[i][1][j]

Ahora, usaremos la función AgglomerativeClustering de Sklearn para determinar la agrupación en clústeres jerárquicos.

from sklearn.cluster import AgglomerativeClustering
clustering = AgglomerativeClustering(n_clusters=2,linkage='average',affinity='precomputed').fit_predict(distances)
   Finally, according to the clustering results, draw the resulting map in different colors:
G.add_edges_from(edgelist)
plt.figure()
nx.draw(G_karate,  node_color = clustering, pos=pos)

Materiales de referencia y algoritmos más clásicos de la teoría de gráficos
Teoría gráfica y aprendizaje de gráficos (1): Conceptos básicos de gráficos

Teoría de gráficos y aprendizaje de gráficos (2): Algoritmo gráfico

github.com/maelfabien/Graph_Analysis.ipynb

versión aistudio Graph_Analysis

Más tutoriales de aprendizaje
github.com/maelfabien/Machine_Learning_Tutorials
Nota: El contenido proviene de Baidu Diagram Neural Network 7th Check-in Camp, bienvenido a reimprimir