Python | Clustering, Conectividad y otras propiedades de Graph usando Networkx

El cierre triádico de un gráfico es la tendencia de los Nodes que tienen un vecino común a tener un borde entre ellos. En caso de que se agreguen más bordes en el Gráfico, estos son los bordes que tienden a formarse. Por ejemplo en el siguiente gráfico: 

Los bordes que es más probable que se formen a continuación son (B, F), (C, D), (F, H) y (D, H) porque estos pares comparten un vecino común.

El coeficiente de agrupamiento local de un Node en un gráfico es la fracción de pares de vecinos del Node que son adyacentes entre sí. Por ejemplo, el Node C del gráfico anterior tiene cuatro Nodes adyacentes, A, B, E y F. 

El número de pares posibles que se pueden formar usando estos 4 Nodes es 4*(4-1)/2 = 6 . 
Número de pares reales que son adyacentes entre sí = 2 . Estos son (A, B) y (E, F). 
Por lo tanto, el coeficiente de agrupamiento local para el Node C en el gráfico dado = 2/6 = 0,667

Networkx nos ayuda a obtener los valores de agrupamiento fácilmente. 

import networkx as nx
 
G = nx.Graph()
 
G.add_edges_from([('A', 'B'), ('A', 'K'), ('B', 'K'), ('A', 'C'),
                  ('B', 'C'), ('C', 'F'), ('F', 'G'), ('C', 'E'),
                  ('E', 'F'), ('E', 'D'), ('E', 'H'), ('I', 'J')])
 
# returns a Dictionary with clustering value of each node
print(nx.clustering(G))
 
# This returns clustering value of specified node
print(nx.clustering(G, 'C'))

Output:
{'A': 0.6666666666666666,
 'B': 0.6666666666666666,
 'C': 0.3333333333333333,
 'D': 0,
 'E': 0.16666666666666666,
 'F': 0.3333333333333333,
 'G': 0,
 'H': 0,
 'I': 0,
 'J': 0,
 'K': 1.0}
0.3333333333333333

¿Cómo obtener el valor de agrupamiento para todo el gráfico?

Hay dos formas distintas de averiguarlo:

1. Podemos promediar el coeficiente de agrupamiento local de todos los Nodes individuales, que es la suma del coeficiente de agrupamiento local de todos los Nodes dividido por el número total de Nodes. 
nx.average_clustering(G) es el código para averiguarlo. En el gráfico anterior, esto devuelve un valor de 0,28787878787878785. 

2. Podemos medir la Transitividad del Gráfico. 

Transitividad de un Gráfico = 3 * Número de triángulos en un Gráfico / Número de tríadas conectadas en el Gráfico.

En otras palabras, es tres veces la relación entre el número de tríadas cerradas y el número de tríadas abiertas.

Esta es una tríada cerrada

Esta es una tríada abierta.
nx.transitivity(G) es el código para obtener la transitividad. En el gráfico anterior, devuelve un valor de 0,4090909090909091. 

Ahora, sabemos que la gráfica dada arriba no es conexa. Networkx proporciona una serie de funciones integradas para verificar las diversas funciones de conectividad de un gráfico. 
Se ilustran mejor en el siguiente código:  

import networkx as nx
 
G = nx.Graph()
 
G.add_edges_from([('A', 'B'), ('A', 'K'), ('B', 'K'), ('A', 'C'),
                  ('B', 'C'), ('C', 'F'), ('F', 'G'), ('C', 'E'),
                  ('E', 'F'), ('E', 'D'), ('E', 'H'), ('I', 'J')])
 
nx.draw_networkx(G, with_labels = True, node_color ='green')
 
# returns True or False whether Graph is connected
print(nx.is_connected(G))
 
# returns number of different connected components
print(nx.number_connected_components(G))
 
# returns list of nodes in different connected components
print(list(nx.connected_components(G)))
 
# returns list of nodes of component containing given node
print(nx.node_connected_component(G, 'I'))
 
# returns number of nodes to be removed
# so that Graph becomes disconnected
print(nx.node_connectivity(G))
 
# returns number of edges to be removed
# so that Graph becomes disconnected
print(nx.edge_connectivity(G))

Producción: 

False
2
[{'B', 'H', 'C', 'A', 'K', 'E', 'F', 'D', 'G'}, {'J', 'I'}]
{'J', 'I'}
0
0 

Conectividad para un gráfico dirigido –

Un grafo dirigido es fuertemente conexo si para cada par de Nodes u y v hay un camino dirigido de u a v y de v a u. 
Es débilmente conectado si reemplazar todos los bordes del gráfico dirigido con bordes no dirigidos producirá un gráfico conectado no dirigido. Se pueden comprobar con el siguiente código: 

nx.is_strongly_connected(G)
nx.is_weakly_connected(G)

El grafo dirigido dado es débilmente conexo, no fuertemente conexo.

Networkx nos permite encontrar caminos entre Nodes fácilmente en un gráfico. Examinemos de cerca el siguiente gráfico: 

import networkx as nx
import matplotlib.pyplot as plt
 
G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'K'), ('B', 'K'), ('A', 'C'),
                  ('B', 'C'), ('C', 'F'), ('F', 'G'), ('C', 'E'),
                  ('E', 'F'), ('E', 'D'), ('E', 'H'), ('H', 'I'), ('I', 'J')])
 
plt.figure(figsize =(9, 9))
nx.draw_networkx(G, with_labels = True, node_color ='green')
 
print(nx.shortest_path(G, 'A'))
# returns dictionary of shortest paths from A to all other nodes
 
print(int(nx.shortest_path_length(G, 'A')))
# returns dictionary of shortest path length from A to all other nodes
 
print(nx.shortest_path(G, 'A', 'G'))
# returns a shortest path from node A to G
 
print(nx.shortest_path_length(G, 'A', 'G'))
# returns length of shortest path from node A to G
 
print(list(nx.all_simple_paths(G, 'A', 'J')))
# returns list of all paths from node A to J
 
print(nx.average_shortest_path_length(G))
# returns average of shortest paths between all possible pairs of nodes

Producción: 

{‘A’: [‘A’], 
‘B’: [‘A’, ‘B’], 
‘C’: [‘A’, ‘C’], 
‘D’: [‘A’, ‘C ‘, ‘E’, ‘D’], 
‘E’: [‘A’, ‘C’, ‘E’], 
‘F’: [‘A’, ‘C’, ‘F’], 
‘G’ : [‘A’, ‘C’, ‘F’, ‘G’], 
‘H’: [‘A’, ‘C’, ‘E’, ‘H’], 
‘I’: [‘A’, ‘C’, ‘E’, ‘H’, ‘I’], 
‘J’: [‘A’, ‘C’, ‘E’, ‘H’, ‘I’, ‘J’], 
‘K’ : [‘A’, ‘K’]} 
{‘A’: 0, 
‘B’: 1, 
‘C’: 1, 
‘D’: 3, 
‘E’: 2, 
‘F’: 2, 
‘G ‘: 3, 
‘H’: 3, 
‘I’: 4, 
‘J’: 5, 
‘K’: 1} 
[‘A’, ‘C’, ‘F’, ‘G’] 
3 
[[‘A’, ‘C’, ‘F’, ‘E’, ‘H’, ‘I’, ‘J’], [‘A’, ‘C’, ‘E’, ‘H’, ‘I ‘, ‘J’], [‘A’, ‘K’, ‘B’, ‘C’, ‘F’, ‘E’, ‘H’, ‘I’, ‘J’], [‘A’, ‘K’, ‘B’, ‘C’, ‘E’, ‘H’, ‘I’, ‘J’], [‘A’, ‘B’, ‘C’, ‘F’, ‘E’, ‘H’, ‘I’, ‘J’], [‘A’, ‘B’, ‘C’, ‘E’, ‘H’, ‘I’, ‘J’]] 
2.6363636363636362 
  

Algunas características importantes de un gráfico:

• Excentricidad: para un Node n en el gráfico G, la excentricidad de n es la distancia de ruta más corta posible entre n y todos los demás Nodes.
• Diámetro: La distancia máxima más corta entre un par de Nodes en un gráfico G es su Diámetro. Es el mayor valor de excentricidad posible de un Node.
• Radio: Es el valor mínimo de excentricidad de un Node.
• Periferia: Es el conjunto de Nodes que tienen su excentricidad igual a su Diámetro.
• Centro: Centro de un Gráfico es el conjunto de Nodes cuya excentricidad es igual al radio del Gráfico.

Networkx ofrece una función integrada para calcular todas estas propiedades.  

import networkx as nx
import matplotlib.pyplot as plt
 
G = nx.Graph()
G.add_edges_from([('A', 'B'), ('A', 'K'), ('B', 'K'), ('A', 'C'),
                  ('B', 'C'), ('C', 'F'), ('F', 'G'), ('C', 'E'),
                  ('E', 'F'), ('E', 'D'), ('E', 'H'), ('H', 'I'), ('I', 'J')])
 
plt.figure(figsize =(9, 9))
nx.draw_networkx(G, with_labels = True, node_color ='green')
 
print("Eccentricity: ", nx.eccentricity(G))
print("Diameter: ", nx.diameter(G))
print("Radius: ", nx.radius(G))
print("Preiphery: ", list(nx.periphery(G)))
print("Center: ", list(nx.center(G)))

Producción: 
 

Excentricidad: {‘A’: 5, ‘K’: 6, ‘B’: 5, ‘H’: 4, ‘J’: 6, ‘E’: 3, ‘C’: 4, ‘I’: 5 , ‘F’: 4, ‘D’: 4, ‘G’: 5} 
Diámetro: 6 
Radio: 3 
Periferia: [‘K’, ‘J’] 
Centro: [‘E’] 
 

Referencia: https://networkx.github.io/documentation .