Network Science - UDD

Centralidad y Mundo Pequeño

Cristian Candia-Castro Vallejos, Ph.D. $^{1, 2, 3, 4}$

[1] Data Science Institute (IDS), Universidad del Desarrollo, Chile
[2] Northwestern Institute on Complex Systems, Kellogg School of Management, Northwestern Unviersity, USA
[3] Centro de Investigación en Complejidad Social, Universidad del Desarrollo, Chile
[4] Computational Research in Social Science Laboratory, Facultad de Ingeniería y Facultad de Gobierno, Universidad del Desarrollo, Chile

Referencias: 1. https://publish.illinois.edu/pynetworkshop/ 2. https://github.com/MridulS/pydata-networkx

Redes? Grafos?

Una estructura matemática utilizada para modelar relaciones por pares entre objetos, donde los objetos generalmente se denominan nodos y la relación entre ellos enlaces.

$G = (V, E)$

$V$ = conjunto de nodos/vértices

$E$ = conjunto de $(x, y)$ enlaces

###Si `nx.erdos_renyi_graph` arroja el error random_state_index is incorrect, intentar:

# import decorator

# print(decorator.__version__)

# ! pip install decorator==5.0.9 #, 5.1.0

####Luego reiniciar Jupyter y correr:

# ! pip install networkx

# Module 1: Comenzando con NetworkX

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt 
import collections

import networkx as nx

%matplotlib inline

import urllib.request as urllib
import io

# path = 'https://saref.github.io/teaching/PyNetworkshop/'

G_rand=nx.erdos_renyi_graph(14, .01)

type(G_rand)

networkx.classes.graph.Graph

nx.draw_circular(nx.erdos_renyi_graph(14, 0.2), with_labels=True)

¿Ejemplos de redes?

¿Puedes pensar en algunas redes del mundo real?

Usando `NetworkX`

# Creating a graph/network object
G = nx.Graph()

# accessing nodes
G.nodes()

NodeView(())

# accessing edges
G.edges()

EdgeView([])

# Creemos una red de recetas

# G.add_node('Tomato')
# G.add_node('Eggs')
# G.add_node('Lamb')
# G.add_node('Chicken')
G.add_nodes_from(['Tomato', 'Eggs', 'Lamb', 'Chicken'])

# G.add_edge('Tomato', 'Eggs')
# G.add_edge('Lamb', 'Tomato')
# G.add_edge('Chicken', 'Tomato')
G.add_edges_from([('Tomato', 'Eggs'), ('Tomato', 'Lamb'), ('Tomato', 'Chicken')])

G.nodes()
#list(G.nodes())

NodeView(('Tomato', 'Eggs', 'Lamb', 'Chicken'))

G.edges()

EdgeView([('Tomato', 'Eggs'), ('Tomato', 'Lamb'), ('Tomato', 'Chicken')])

nx.draw(G, with_labels=True)

# cualquier objeto "hasheable" puede ser un nodo en la red
G.add_node([1, 2])

TypeError: unhashable type: 'list'

En Python, cualquier objeto inmutable (como un número entero, booleano, cadena, tupla) es hash, lo que significa que su valor no cambia durante su vida útil.

Creemos un grafo que se parezca al siguiente:

# Los datos de una red se pueden representar como un edgelist, una matriz o un grafo

G = nx.Graph()
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edges_from([(1, 2), (2,1), (2, 3), (1,3), (1,4), (1,5), (3,5)])# 7 tuplas

nx.draw(G, with_labels=True)

G.number_of_nodes()

G.number_of_edges() # observe que 1,2 y 2,1 cuentan como 1 enlace. Ya que este es un grafo no-dirigido

list(G.nodes)

[1, 2, 3, 4, 5]

list(G.edges)

[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (3, 5)]

#remueve nodos
G.remove_node(1) # take notice that once you remove node 1, all edges linked with 1 will be removed as well.

list(G.nodes)

[2, 3, 4, 5]

list(G.edges)

[(2, 3), (3, 5)]

nx.draw(G, with_labels=True)

#remueve enlaces
G.remove_edge(3,5) # remove edge from 3 to 5

list(G.edges)

[(2, 3)]

nx.draw(G, with_labels=True)

# agrega atributos a nodos y enlaces
G.add_node(1, occupation="Estudiante")
G.add_edge(1,2, weight="5") # creating a weighted network

#Atajo para crear enlaces con pesos
G.add_weighted_edges_from([(1, 2, 10), (1, 3, 1.30)])

nx.draw(G, with_labels=True)

# Estábamos trabajando con una red no dirigida. Intentemos crear una versión dirigida.
DiG= nx.DiGraph()#Base class for directed graphs.
DiG.add_nodes_from([1, 2, 3, 4, 5])

DiG.add_edges_from([(1, 2), (2, 1), (2, 3), (1,3), (1,4), (1,5), (3,5)])

nx.draw(DiG, with_labels=True)

DiG.number_of_nodes()

DiG.number_of_edges() # ahora observe que 1,2 y 2,1 se cuentan dos veces, ya que este es un grafo dirigido.

# otro atajo entre redes dirigidas y no-dirigidas
DirectedG = G.to_directed()
UndirectedG = DiG.to_undirected()

nx.draw(UndirectedG, with_labels=True)

nx.draw(DirectedG, with_labels=True)

Estadísticas descriptivas para una red en múltiples niveles (ego, díada, tríada, subgrupo, red)

# Let's load a well-known dataset, Krackkite graph (use nx. for existing datasets)
G = nx.krackhardt_kite_graph()

Nota: En teoría de grafos, el grafo de cometas de Krackhardt es un grafo simple con diez nodos. El grafo lleva el nombre de David Krackhardt, un investigador de la teoría de redes sociales.

Krackhardt introdujo el grafo en 1990 para distinguir diferentes conceptos de centralidad. Tiene la propiedad de que el vértice con grado máximo (etiquetado 3 en la figura, con grado 6), el vértice con centralidad máxima de intermediación (etiquetado 7) y los dos vértices con centralidad máxima de proximidad (etiquetado 5 y 6) son todos diferentes unos de otros.

plt.figure(figsize =(10, 10)) 
nx.draw_networkx(G)

Análisis a nivel de nodo

Centralidad

Los índices de centralidad son respuestas a la pregunta “¿Qué caracteriza a un nodo importante?” La palabra “importancia” tiene un gran número de significados, lo que lleva a muchas definiciones diferentes de centralidad.

Calcularemos (1) centralidad de grado, (2) centralidad de intermediación, (3) centralidad de proximidad, (4) centralidad de vector propio y las relaciones entre ellos.

# degree.items()

# list(reversed(sorted(degree.items(), key=lambda x: x[1])))

Centralidad de grado

Si importancia significa:

Que tan popular eres? Cuantas personas cononces?

también puede calcularse sin normalizar, dependiendo de la pregunta que se quiera responder.

Drawing

`nx.degree_centrality(G)`

#degree centrality (cuántas conocen / cuántas personas pueden conocer)
degree = nx.degree_centrality(G) 
print(degree)
[print('El nodo ',nodo," tiene centralidad: ",centralidad) for (nodo, centralidad) in reversed(sorted(degree.items(), key=lambda x: x[1]))]

{0: 0.4444444444444444, 1: 0.4444444444444444, 2: 0.3333333333333333, 3: 0.6666666666666666, 4: 0.3333333333333333, 5: 0.5555555555555556, 6: 0.5555555555555556, 7: 0.3333333333333333, 8: 0.2222222222222222, 9: 0.1111111111111111}
El nodo  3  tiene centralidad:  0.6666666666666666
El nodo  6  tiene centralidad:  0.5555555555555556
El nodo  5  tiene centralidad:  0.5555555555555556
El nodo  1  tiene centralidad:  0.4444444444444444
El nodo  0  tiene centralidad:  0.4444444444444444
El nodo  7  tiene centralidad:  0.3333333333333333
El nodo  4  tiene centralidad:  0.3333333333333333
El nodo  2  tiene centralidad:  0.3333333333333333
El nodo  8  tiene centralidad:  0.2222222222222222
El nodo  9  tiene centralidad:  0.1111111111111111

[None, None, None, None, None, None, None, None, None, None]

Nota: Una lambda es una función anónima a menudo se usa en funciones como sorted() que toman un invocable como parámetro (a menudo el parámetro de palabra clave key). También puede proporcionar una función existente en lugar de una lambda, siempre que sea un objeto invocable.

Nota: Un objeto invocable es un objeto que le permite usar paréntesis redondos () y eventualmente pasar algunos parámetros, al igual que las funciones.

Betweenness Centrality

Si importancia significa:
Capacidad de intermediación entre grupos.
Probabilidad de que la información que se origina en cualquier lugar de la red te alcance

Drawing

$d_{j k}$ el número de caminos mas cortos que pasan entre los nodos $j$ y $k$ .
$d_{j k} (i)$ número de caminos mas cortos entre j y k que pasan por el nodo $i$ . ###### nx.betweenness_centrality(G, k=None, normalized=True, weight=None, endpoints=False, seed=None)

## Betweenness centrality: ¿Con qué frecuencia un nodo está en el camino más corto entre otros 2 nodos?
# (con qué frecuencia nos encontramos con Alice en nuestro camino para llegar a otros)

between = nx.betweenness_centrality(G, normalized = True, endpoints = False) # normalize betweenness centrality when values get large 

[print(key,":",value) for (key, value) in reversed(sorted(between.items(), key=lambda x: x[1]))]

7 : 0.38888888888888884
6 : 0.23148148148148148
5 : 0.23148148148148148
8 : 0.2222222222222222
3 : 0.10185185185185183
1 : 0.023148148148148143
0 : 0.023148148148148143
9 : 0.0
4 : 0.0
2 : 0.0

[None, None, None, None, None, None, None, None, None, None]

Closeness centrality

Si importancia significa:
Estar cerca de todos los nodos

Drawing

$d_{i j}$ es la distancia entre los nodos $i$ y $j$ .

`nx.closeness_centrality(G, u=None, distance=None, normalized=True)`

## Closeness centrality: qué tan accesible es alguien para el resto de la red (networkx usa la distancia *inward* a un nodo, no hacia outward. Para usar la distancia outward, use `G.reverse())
closeness = nx.closeness_centrality(G)  
[print(key," : ",value) for (key, value) in reversed(sorted(closeness.items(), key=lambda x: x[1]))]#ordena en funcion del element en la segunda posicion (1)

6  :  0.6428571428571429
5  :  0.6428571428571429
7  :  0.6
3  :  0.6
1  :  0.5294117647058824
0  :  0.5294117647058824
4  :  0.5
2  :  0.5
8  :  0.42857142857142855
9  :  0.3103448275862069

[None, None, None, None, None, None, None, None, None, None]

Eigenvector centrality

Si importancia significa:
Estar conectado a nodos importantes

Drawing

$λ$ es el valor propio.
La solución (cuando existe) da la centralidad del nodo. Tomamos el mas alto $λ$ .
Este concepto es el núcleo del algoritmo de clasificación de Google.

`nx.eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight='weight')`

## Eigenvector centrality: alguien es tan importante en la medida en que el vecino de ese alguien es importante
eigenvector = nx.eigenvector_centrality(G) # eigenvector centrality
[print(key," : ",value) for (key, value) in reversed(sorted(eigenvector.items(), key=lambda x: x[1]))]

3  :  0.4810204881221006
6  :  0.3976910106255469
5  :  0.3976910106255469
1  :  0.35220898139203594
0  :  0.35220898139203594
4  :  0.2858347353163241
2  :  0.2858347353163241
7  :  0.19586185175360382
8  :  0.04807477501420294
9  :  0.011164058575824238

[None, None, None, None, None, None, None, None, None, None]

Resumen

Drawing

Ejemplo del mundo real: la red de familias de élite florentinas del siglo XIV

Ejemplo

Prestigio de las familias florentinas durante el Renacimiento.

Drawing

G2=nx.florentine_families_graph()

plt.figure(figsize =(8, 8)) 
nx.draw_networkx(G2)

TAREA 2.1

P: ¿Quiénes son las 3 familias principales en términos de: 1. ¿Centralidad de grado? 2. ¿Centralidad de intermediación? 3. ¿Centralidad de cercanía? 4. ¿Centralidad del vector propio?

Una matriz que muestra las relaciones entre las medidas de centralidad:

PageRank

Redes dirigidas.

El algoritmo del billón de dólares, PageRank, funciona contando el número y la importancia de los enlaces a una página para determinar una estimación aproximada de la importancia del sitio web. El algoritmo asigna un valor de importancia a cada página web en función del número y la calidad de los enlaces a la página. La suposición subyacente es que es probable que los sitios web más importantes reciban más enlaces de otros sitios web. Fue desarrollado por los fundadores de Google, Larry Page y Sergey Brin.

# Crear un grafo dirigido
G = nx.DiGraph()

# Añadir bordes (estos también añaden nodos)
G.add_edge('A', 'B')
G.add_edge('B', 'C')
G.add_edge('C', 'A')
G.add_edge('A', 'D')
G.add_edge('D', 'E')
G.add_edge('E', 'F')
G.add_edge('B', 'F')
G.add_edge('C', 'G')
G.add_edge('G', 'A')

# Aplicar el algoritmo PageRank
pagerank = nx.pagerank(G, alpha=0.85)

# Ordenar los valores de PageRank de mayor a menor
pagerank_sorted = sorted(pagerank.items(), key=lambda item: item[1], reverse=True)

# Imprimir los valores de PageRank ordenados
for node, pagerank_value in pagerank_sorted:
    print(f"Node: {node}, PageRank: {pagerank_value}")

# Crear una lista de tamaños para los nodos basada en los valores de PageRank
sizes = [pagerank[node] * 20000 for node in G.nodes]

# Dibujar la red
nx.draw(G, with_labels=True, node_size=sizes)

# Mostrar la red
plt.show()

Node: F, PageRank: 0.2329773721880849
Node: A, PageRank: 0.1721303892141963
Node: E, PageRank: 0.15416106912747013
Node: B, PageRank: 0.12287387024080189
Node: D, PageRank: 0.12287387024080189
Node: C, PageRank: 0.10193997532982814
Node: G, PageRank: 0.09304345365881689

Análisis a nivel de díadas: recuentos de díadas, caminos, geodésicas

## El número de diadas (same as calculating number of edges)
# For undirected networks: N(N-1)/2
# For directed networks: N(N-1)
G2.number_of_edges()

G2.nodes # lookup of the nodenames

NodeView(('Acciaiuoli', 'Medici', 'Castellani', 'Peruzzi', 'Strozzi', 'Barbadori', 'Ridolfi', 'Tornabuoni', 'Albizzi', 'Salviati', 'Pazzi', 'Bischeri', 'Guadagni', 'Ginori', 'Lamberteschi'))

G2.number_of_edges('Medici','Peruzzi') # comprueba si hay un enlace entre dos nodos

nx.has_path(G2,'Medici','Peruzzi') # comprobar si existe ruta entre los nodos Medici y Peruzzi

True

# Lista de todos los caminos posibles entre Medici y Peruzzi
paths = nx.all_simple_paths(G2, source='Medici', target='Peruzzi', cutoff=3) 
# cutoff fija el corte para la longitud de el manimo menor o igual que el valor dado (3)

print(list(paths))

[['Medici', 'Barbadori', 'Castellani', 'Peruzzi'], ['Medici', 'Ridolfi', 'Strozzi', 'Peruzzi']]

nx.shortest_path(G2,'Medici','Peruzzi') # encuentra una ruta geodésica

#Visualiza el camino mas corto
geodesic = nx.shortest_path(G2,'Medici','Peruzzi')
layout = nx.spring_layout(G2)

edges = [(geodesic[i], geodesic[i+1]) for i in range(len(geodesic) - 1)]
nx.draw_networkx_edges(G2, layout, edgelist = edges, edge_color="r", width=10)
nx.draw(G2, layout, with_labels=True)

# Que tan similares son los vecinos de los 2 nodos
list(nx.common_neighbors(G2,'Medici', 'Ginori'))

['Albizzi']

Trabajemos en una red real

La red de colaboración Arxiv GR-QC (Relatividad General y Cosmología Cuántica) es de e-print arXiv y cubre las colaboraciones científicas entre los artículos de los autores enviados a la categoría de Relatividad General y Cosmología Cuántica. Si un autor $i$ es coautor de un artículo con el autor $j$ , el grafo contiene un enlace no dirigido entre $i$ y $j$ . Si el artículo es co-autoreado por $k$ autores, esto genera un (sub) grafo completamente conectado con $k$ nodos.

fuente: http://snap.stanford.edu/data/index.html#canets

# Si seis autores escribieron un artículo juntos, tendrán un grafo completo
nx.draw(nx.complete_graph(5),with_labels=True)

# crear un grafo de autor a partir del conjunto de datos
import csv
authors_graph = nx.Graph()

with open('./Data/CA-GrQc.txt', 'r') as f:
    reader = csv.reader(f, delimiter='\t')
    for row in reader:
        authors_graph.add_edge(row[0], row[1])

type(authors_graph)

networkx.classes.graph.Graph

print(authors_graph.number_of_edges())
print(authors_graph.number_of_nodes())

14496
5242

authors_graph.nodes()

NodeView(('3466', '937', '5233', '8579', '10310', '15931', '17038', '18720', '19607', '1854', '4583', '9572', '10841', '13056', '14982', '16310', '19640', '23855', '24372', '24814', '5052', '899', '1796', '2287', '3096', '3386', '4472', '5346', '5740', '6094', '6376', '9124', '10235', '10427', '10597', '15159', '16148', '16741', '18235', '18549', '19297', '20511', '20595', '20613', '24371', '24559', '24731', '25102', '25271', '25396', '1658', '4822', '6864', '7689', '7926', '10268', '12971', '18600', '20421', '20886', '21048', '22393', '23186', '23214', '23298', '23945', '24939', '339', '624', '3731', '4743', '5407', '6610', '6700', '8045', '9099', '9639', '9785', '12141', '15184', '15784', '18719', '19870', '20532', '22527', '23576', '23577', '23649', '24199', '24293', '25201', '10243', '6774', '8049', '8053', '8517', '11964', '15538', '16694', '18648', '19423', '21012', '22457', '22691', '23452', '16174', '16470', '17822', '14265', '392', '2485', '2949', '3173', '3441', '3593', '3853', '3927', '3937', '3939', '5107', '5218', '5230', '6030', '7350', '7504', '7601', '8718', '9522', '11621', '12498', '12691', '15251', '16020', '16261', '17156', '17626', '18622', '19059', '19525', '19738', '20122', '20432', '21866', '22074', '23721', '8916', '13556', '14485', '8612', '615', '743', '2076', '4515', '5773', '9482', '10822', '11175', '11604', '14004', '15003', '15552', '15814', '16083', '17932', '20001', '20100', '23481', '16258', '1356', '1727', '2752', '4125', '6667', '6825', '10039', '10351', '11082', '14123', '16676', '21194', '10912', '14534', '17268', '19783', '21705', '22836', '2710', '62', '106', '260', '2959', '3677', '4708', '5172', '5541', '5794', '5807', '6575', '8458', '10601', '11401', '13026', '13205', '13659', '13989', '14007', '14009', '14599', '15301', '18757', '20934', '21543', '22184', '23647', '23708', '25916', '26023', '26051', '26100', '214', '5435', '6512', '10590', '23559', '1765', '3032', '5302', '7383', '7442', '7768', '13276', '17266', '22415', '10794', '7050', '25850', '10113', '10657', '12130', '17172', '4846', '676', '824', '2133', '2654', '4748', '5672', '10549', '12928', '13220', '14419', '17330', '17439', '18487', '20850', '22779', '23382', '24029', '11785', '45', '46', '570', '773', '1653', '2212', '2741', '2952', '3372', '4046', '4164', '4511', '4513', '5262', '6179', '6830', '7956', '8879', '11241', '11472', '12365', '12496', '12678', '12781', '12851', '14540', '14807', '15659', '16159', '17655', '17692', '18894', '19961', '20108', '20562', '20635', '21281', '21508', '21847', '22798', '22887', '23293', '24955', '25346', '25758', '934', '5579', '9755', '10550', '16032', '17331', '17603', '20644', '22497', '23387', '23907', '24924', '25080', '12422', '1339', '3164', '15580', '16393', '20478', '20956', '3890', '5621', '8824', '11613', '12306', '12860', '14547', '18182', '21707', '24696', '2661', '7899', '8067', '8208', '11132', '11402', '12980', '13364', '14969', '16389', '18109', '18365', '23038', '24845', '25379', '13740', '4550', '4702', '7264', '13096', '14128', '19489', '19527', '19784', '22476', '25006', '25486', '26', '1407', '1488', '8219', '10762', '11801', '12665', '12688', '13142', '15108', '15321', '20647', '20827', '20879', '23614', '3909', '17979', '3872', '5109', '7533', '12409', '20101', '23096', '8862', '78', '4877', '7459', '8254', '12155', '22598', '24932', '888', '1520', '6468', '6627', '7007', '7712', '10711', '13614', '14102', '18517', '18676', '23351', '23689', '24114', '2465', '2592', '3977', '5055', '5993', '9265', '12334', '19890', '20341', '21560', '17309', '24833', '543', '1958', '2193', '3917', '6858', '8148', '9092', '12478', '15366', '18125', '18398', '19675', '21806', '23693', '26196', '10115', '10134', '23916', '7893', '593', '5510', '9360', '12627', '16778', '18037', '18051', '13385', '19578', '12386', '13333', '23896', '8978', '9017', '15170', '15455', '16589', '2255', '3056', '6158', '7307', '7324', '8365', '9023', '11444', '12324', '12472', '13831', '14746', '16128', '17075', '18875', '19900', '20000', '20806', '21944', '21968', '23302', '23665', '23758', '24722', '12045', '12287', '14181', '20257', '21613', '7510', '197', '8851', '1343', '2991', '8299', '15416', '18088', '25286', '1254', '3420', '10130', '2250', '3243', '7717', '7985', '11015', '12085', '13714', '14767', '16056', '16994', '17414', '18971', '19216', '20534', '21776', '21860', '25205', '178', '1248', '1403', '2368', '2420', '16210', '18681', '20641', '24762', '2307', '6934', '22423', '231', '345', '1186', '1234', '1841', '1997', '2404', '2450', '2980', '3409', '5134', '5578', '8503', '9341', '9889', '12503', '13060', '13597', '16611', '18208', '18543', '18866', '22421', '22937', '23363', '23628', '25053', '25251', '2982', '4036', '4115', '12938', '13032', '19215', '21432', '22726', '22834', '22966', '23511', '25528', '25836', '14376', '8710', '22483', '1375', '2846', '5555', '5564', '5787', '9721', '10158', '10942', '13600', '13929', '21075', '21316', '22900', '23637', '23770', '25143', '25601', '25980', '17394', '18924', '3113', '8312', '10765', '17538', '25978', '1172', '5674', '26194', '375', '1838', '12733', '7188', '896', '921', '1508', '6815', '7209', '8279', '13008', '18605', '21158', '4632', '7844', '11053', '11148', '13411', '14512', '16594', '16722', '16726', '16876', '19954', '19992', '20391', '20774', '23403', '4870', '5175', '8282', '22046', '2449', '4766', '3561', '4868', '8352', '10456', '15365', '16931', '8157', '2120', '7713', '19052', '8302', '16484', '17778', '2556', '19159', '21699', '25382', '8701', '523', '5464', '7774', '17379', '18008', '23385', '25868', '26170', '1310', '2922', '3651', '6891', '10162', '10620', '11112', '13174', '14864', '17536', '23153', '24340', '11102', '18592', '22765', '1896', '6838', '25220', '4180', '10055', '12637', '1832', '4383', '7014', '9397', '14344', '14385', '21379', '24163', '4416', '9241', '2620', '3679', '4364', '5712', '13955', '14003', '15235', '18227', '19445', '19495', '20168', '23967', '1116', '15399', '18222', '21287', '23227', '4624', '5355', '6863', '12606', '12968', '15770', '21322', '22265', '22336', '23099', '23880', '25111', '4319', '12758', '22023', '14337', '5849', '10763', '11121', '11194', '15799', '16511', '16575', '16945', '21157', '2326', '10253', '13190', '14325', '19048', '20182', '3595', '18174', '17850', '20620', '12380', '3197', '6160', '8589', '9417', '9829', '14638', '14924', '15972', '17228', '18940', '19090', '19475', '20207', '22644', '22790', '24001', '25228', '9710', '3345', '3430', '5266', '5995', '7999', '8047', '8178', '8868', '10824', '15144', '19107', '19806', '22439', '23304', '24431', '11077', '10211', '14972', '15300', '17158', '17162', '17403', '20149', '20519', '21389', '22951', '23912', '23918', '25589', '6895', '3076', '7444', '8972', '17308', '20574', '21629', '245', '4983', '13480', '14562', '15912', '16976', '19974', '22245', '414', '8708', '23776', '1044', '4975', '5809', '12587', '16123', '20303', '4451', '9983', '15205', '15666', '15667', '19093', '21031', '24330', '5840', '6732', '8614', '13847', '15081', '22609', '3310', '5143', '9735', '17396', '26138', '4700', '5606', '1386', '1738', '2566', '2720', '5634', '9870', '16779', '24475', '25931', '1817', '3725', '5366', '15911', '9800', '26141', '18001', '22177', '25480', '1425', '2501', '2823', '5136', '7105', '7317', '9127', '14615', '17089', '19454', '22758', '23841', '3207', '7125', '20683', '25419', '2591', '8932', '9188', '9773', '13713', '19179', '14818', '26190', '3839', '13615', '16674', '7042', '9269', '11661', '21994', '9943', '10096', '15614', '16368', '17285', '21407', '8715', '21142', '21167', '13621', '25388', '284', '6427', '16835', '18677', '21696', '25854', '25940', '9485', '10435', '14698', '21823', '811', '9964', '11919', '15123', '17021', '19517', '22989', '23485', '8069', '2127', '11712', '10871', '15829', '16106', '17207', '17670', '18286', '18612', '19234', '19724', '22876', '3412', '894', '4814', '5441', '5717', '5934', '9075', '10623', '11223', '11491', '12659', '14351', '19807', '21324', '21665', '22734', '22778', '23246', '25698', '7615', '12806', '1620', '3922', '9133', '9895', '9907', '11791', '18457', '19131', '19997', '21491', '22426', '22791', '25158', '25316', '352', '3996', '10555', '15850', '19101', '20533', '21943', '22603', '23513', '25034', '1280', '5851', '11591', '13520', '16921', '21646', '17559', '1674', '3323', '8680', '9184', '13813', '19204', '19206', '19657', '20373', '23204', '409', '2474', '4241', '6746', '10476', '16568', '21771', '24620', '2081', '2664', '12212', '13528', '14628', '22574', '25872', '1545', '2202', '15206', '17233', '18158', '21317', '24271', '8547', '10791', '10919', '11275', '15600', '15608', '16644', '24568', '25996', '26098', '1059', '6154', '7725', '11125', '13705', '15435', '16039', '17821', '18540', '20536', '23529', '10588', '3916', '4525', '4952', '5352', '5729', '10490', '12101', '13801', '15311', '21754', '23134', '24614', '4493', '14627', '23720', '930', '3946', '4760', '17189', '10463', '10526', '11788', '17746', '18189', '21438', '22611', '26038', '4195', '7069', '9098', '17721', '21723', '24587', '7895', '11863', '12110', '1000', '1149', '1694', '2115', '4575', '5605', '6288', '12016', '12070', '13469', '16101', '18250', '20667', '20716', '23107', '23344', '23939', '25402', '25948', '6963', '8374', '17465', '19865', '3006', '3630', '5901', '5953', '7911', '8730', '10406', '12874', '13177', '16817', '19723', '24885', '13653', '22599', '3265', '3998', '8513', '10501', '13029', '13622', '13682', '16324', '16640', '16749', '26059', '26065', '580', '6431', '1877', '2042', '15880', '16967', '19710', '20014', '23163', '23225', '3683', '3845', '6748', '14664', '16065', '16963', '20650', '3804', '4032', '5194', '23137', '11495', '12842', '495', '2742', '3965', '5622', '7855', '8928', '8968', '9458', '17968', '18375', '8335', '1104', '5427', '13322', '13529', '18619', '18751', '6494', '2526', '6364', '6857', '7853', '14976', '24781', '321', '21853', '884', '5469', '5575', '10183', '10966', '16624', '24699', '14308', '5166', '5597', '9066', '20787', '23836', '25050', '5287', '17273', '9283', '953', '17794', '114', '2348', '6631', '8854', '4290', '8200', '11113', '12302', '21017', '23297', '6355', '7194', '20960', '7542', '15322', '18415', '23066', '3765', '14500', '17918', '3418', '4798', '12866', '20196', '2004', '21191', '21663', '14020', '22203', '1600', '15905', '21635', '16543', '238', '4793', '6218', '15516', '16553', '16563', '16565', '22964', '8442', '10412', '8887', '6072', '491', '1124', '1818', '4552', '5739', '6823', '7882', '13328', '17039', '17082', '22028', '23454', '3681', '7126', '3547', '449', '882', '1405', '1498', '3033', '3048', '3511', '7091', '14707', '17245', '18340', '6804', '12260', '19624', '22826', '25491', '25844', '6184', '19161', '21831', '88', '1995', '2338', '2530', '2535', '4355', '4755', '5210', '6340', '7197', '7635', '8727', '9313', '9656', '9869', '10350', '12507', '12710', '14648', '14766', '15010', '15244', '15245', '15457', '15933', '16654', '17807', '18225', '18453', '18778', '19114', '19446', '19645', '19939', '20346', '20576', '21178', '22504', '23712', '24453', '24718', '12308', '15935', '18276', '18904', '2190', '6172', '8592', '14933', '4249', '21718', '22290', '23441', '24113', '6421', '8224', '11182', '11696', '12286', '23423', '500', '2085', '2568', '3099', '4468', '4631', '9892', '10358', '10458', '10615', '11011', '12074', '13971', '14079', '16754', '18783', '19612', '20552', '20553', '21032', '23355', '24454', '25086', '25180', '25785', '10539', '4254', '9337', '1497', '6724', '16890', '2630', '7563', '14403', '17392', '23503', '2558', '21910', '18910', '2511', '10986', '13318', '14051', '14414', '22119', '1006', '4351', '11372', '16414', '639', '1941', '5227', '7015', '9647', '12852', '15846', '16333', '16347', '4576', '6941', '7206', '7485', '9389', '9426', '10246', '11026', '17953', '18946', '18983', '19013', '23458', '23986', '4697', '3007', '22082', '25537', '5695', '574', '6971', '13282', '15409', '18745', '18758', '21497', '22366', '23714', '1153', '17501', '4183', '6010', '9862', '12370', '16834', '16853', '16899', '21199', '22299', '22309', '22620', '20248', '12679', '573', '1430', '2072', '4966', '19493', '22278', '5769', '10896', '20915', '22848', '1347', '4782', '15582', '17472', '19707', '21930', '24835', '24959', '24009', '283', '1880', '5505', '15959', '15961', '24444', '14316', '14690', '22254', '749', '1373', '3607', '7245', '8031', '15907', '19164', '302', '2335', '6702', '11490', '16108', '17174', '17924', '3999', '8211', '12373', '20059', '2155', '4283', '6408', '7715', '8920', '23256', '2607', '3450', '4588', '5130', '5353', '5835', '9450', '12165', '12722', '20003', '20184', '24640', '4685', '15415', '24152', '8376', '8888', '13067', '4213', '7045', '11892', '20645', '23264', '10600', '13493', '13496', '18788', '18791', '23394', '140', '17304', '18587', '19404', '22462', '24122', '1078', '5164', '9387', '11640', '12545', '13371', '17116', '19741', '22149', '16331', '19184', '17843', '1685', '8134', '12687', '23409', '1321', '4433', '5125', '7625', '10895', '11899', '13711', '16162', '16475', '19167', '19387', '21089', '21727', '23863', '25565', '5060', '20660', '1608', '20030', '11447', '834', '2490', '5570', '15625', '15917', '18140', '18790', '24110', '4466', '8505', '16357', '20116', '20148', '22899', '25710', '4068', '9517', '11400', '11630', '11700', '11733', '11951', '12268', '14093', '15685', '16006', '16495', '17135', '20169', '22188', '22189', '22621', '22811', '22975', '23110', '23509', '23552', '23805', '23806', '25557', '25562', '7801', '14089', '14967', '25215', '11868', '24023', '2559', '5543', '5767', '10931', '24097', '14952', '16953', '20191', '25934', '10467', '13175', '20892', '21816', '25209', '14371', '17443', '141', '8408', '17286', '25827', '5246', '10524', '12337', '15419', '24', '3858', '15066', '23161', '25378', '205', '12389', '15718', '16506', '21650', '22502', '482', '3411', '4428', '5392', '6317', '7541', '15664', '16469', '17665', '20424', '24734', '8206', '12865', '13384', '17688', '3826', '12369', '13498', '19111', '22239', '19084', '23943', '75', '8807', '22530', '15353', '3449', '17950', '18522', '6709', '18003', '5545', '12135', '2475', '3209', '15973', '21928', '24765', '6219', '18160', '1833', '8177', '12107', '4819', '7863', '8596', '13635', '17848', '25152', '25408', '11891', '20243', '19233', '733', '20597', '3171', '19149', '19340', '7824', '8815', '12065', '14558', '15306', '15400', '22528', '22832', '10969', '13321', '16958', '19109', '23346', '2848', '4896', '8666', '10552', '12884', '18511', '25988', '22371', '11566', '11808', '18560', '15249', '15624', '1058', '2614', '3730', '7449', '10801', '14661', '21321', '22376', '24295', '5485', '23870', '6638', '17754', '25674', '9273', '9325', '2783', '9408', '12927', '13310', '6264', '7204', '12247', '19433', '18867', '24943', '731', '17359', '23558', '6828', '25319', '3953', '13196', '15568', '17163', '22954', '14606', '22144', '1840', '4713', '6824', '12492', '10478', '16675', '13859', '4141', '9267', '11052', '16091', '17755', '20053', '22395', '26168', '8378', '16607', '2054', '1552', '8719', '9760', '10355', '13741', '5116', '9629', '7087', '9984', '10153', '10543', '10967', '16336', '20435', '20479', '21433', '25569', '25783', '7039', '12166', '14970', '7277', '16766', '16770', '16858', '17113', '17389', '18408', '19089', '20033', '23429', '24578', '4724', '6904', '7452', '12491', '13369', '14346', '18065', '18271', '19244', '23989', '10983', '4642', '16708', '8231', '9616', '24149', '1519', '8768', '9937', '24270', '25435', '5181', '6316', '17235', '2870', '2536', '9207', '9732', '12654', '16041', '22555', '24753', '25870', '5830', '10991', '17306', '19924', '10923', '11821', '16013', '21469', '11944', '16429', '25784', '21608', '23092', '25571', '5444', '11734', '13931', '21549', '25615', '8476', '13388', '12739', '4847', '10842', '11293', '25125', '1672', '8079', '11461', '16755', '1711', '3174', '6726', '6813', '13703', '20046', '20854', '5411', '5503', '10390', '11186', '7522', '9944', '17086', '21341', '16010', '22696', '25585', '3526', '15786', '135', '1776', '4102', '12311', '12675', '15816', '19945', '26176', '1550', '20952', '24280', '365', '9511', '14552', '15585', '16906', '17187', '18579', '18736', '19791', '1229', '1862', '3194', '3532', '5400', '7154', '9946', '10381', '11107', '17934', '22721', '24129', '215', '185', '351', '1074', '1858', '4512', '6892', '8280', '14542', '17751', '18095', '18143', '18649', '18943', '19573', '22601', '22793', '3877', '4354', '5412', '6544', '7357', '7719', '10477', '11445', '12788', '18185', '19246', '19463', '20780', '21861', '22284', '22741', '23514', '18161', '11093', '165', '293', '3228', '6556', '17194', '6524', '22436', '9504', '5359', '2915', '10956', '20089', '25358', '2350', '2385', '20783', '25405', '15209', '15669', '10807', '21466', '6832', '19557', '1090', '3990', '4635', '4759', '15166', '24860', '6375', '10519', '20230', '4775', '7095', '9138', '9432', '20229', '2926', '22275', '6023', '13624', '19682', '17859', '6075', '13932', '14499', '20345', '4023', '11902', '13647', '19146', '22699', '23622', '25057', '11617', '21029', '12040', '1217', '269', '1150', '1611', '2165', '3944', '5488', '6033', '8128', '9974', '12735', '14430', '19877', '20495', '21638', '21708', '22242', '23233', '24126', '25648', '3501', '16278', '24705', '19355', '22018', '25660', '3312', '11493', '5059', '21530', '13485', '11032', '10719', '2200', '17729', '20052', '21830', '379', '6064', '9439', '10907', '4638', '23909', '18237', '19219', '18171', '85', '5413', '8630', '16521', '20517', '26005', '8774', '5209', '6943', '22748', '24057', '25902', '1014', '12112', '17440', '19150', '21027', '8087', '15523', '17339', '19711', '20307', '1194', '21858', '7829', '5360', '19544', '715', '16554', '4252', '24451', '23856', '6095', '7446', '25236', '2852', '12599', '25056', '25721', '11638', '7246', '17240', '25091', '13970', '80', '8742', '23063', '19903', '25469', '2851', '11416', '23751', '8552', '1595', '1910', '2293', '4135', '4554', '9316', '16498', '17939', '21587', '24160', '25354', '10676', '24961', '8305', '22771', '1736', '1914', '7586', '14424', '19462', '2569', '5546', '3654', '11557', '14154', '15477', '15882', '281', '5241', '9471', '20765', '3948', '4013', '25516', '25684', '546', '8641', '19922', '23175', '21206', '25662', '887', '3721', '9634', '14781', '18972', '25321', '8074', '13164', '14541', '15127', '18524', '16230', '20702', '25225', '70', '4727', '15559', '123', '23240', '3980', '16962', '3821', '17991', '3875', '9094', '19061', '2080', '4069', '5385', '1968', '9082', '9306', '15942', '1588', '2805', '8063', '9419', '5827', '6351', '6527', '10881', '5367', '14983', '19144', '24183', '2184', '3193', '4371', '15998', '23866', '26004', '11822', '21016', '21169', '2936', '10354', '18905', '21563', '15198', '18067', '18297', '19781', '10186', '1327', '6738', '10825', '25863', '4382', '2789', '6641', '15920', '18233', '24582', '24583', '6583', '15960', '15974', '17564', '18782', '23883', '14033', '25383', '22197', '9255', '20065', '22917', '23910', '25572', '25582', '193', '9993', '10819', '11231', '12149', '20129', '23114', '4878', '5184', '8643', '11967', '21779', '24503', '24942', '2119', '7637', '11442', '13651', '81', '1029', '3819', '869', '3618', '14709', '122', '6530', '6707', '6911', '15479', '3524', '19927', '19350', '25959', '7281', '25597', '727', '8471', '16649', '18331', '19469', '1105', '14985', '17911', '26127', '20215', '21333', '18625', '7584', '12049', '12763', '17382', '408', '13834', '17149', '23267', '5843', '11213', '25877', '5361', '18097', '272', '2912', '11811', '11840', '19012', '20305', '4483', '6175', '6266', '8215', '8310', '21401', '4673', '7475', '11426', '23673', '26088', '2797', '9314', '12291', '12639', '13292', '13320', '12664', '1109', '9126', '10655', '11610', '12742', '18445', '4052', '195', '17208', '19168', '20119', '21929', '17589', '6533', '8155', '14165', '24204', '25911', '24506', '24595', '9483', '25250', '1258', '12032', '12797', '21584', '6434', '21162', '10879', '11925', '15082', '18595', '8787', '11979', '16274', '22722', '183', '3982', '9090', '17543', '18723', '21090', '24589', '23145', '7573', '8193', '16576', '16889', '18521', '21391', '244', '1353', '3286', '4765', '16900', '18030', '22246', '3752', '4650', '15971', '24174', '16765', '17017', '17161', '8925', '16505', '20255', '21450', '3743', '839', '2394', '5848', '7098', '12642', '21184', '23149', '4442', '7935', '25896', '12406', '16485', '3034', '6156', '18381', '19686', '20335', '22523', '2451', '2341', '3508', '12641', '13068', '23723', '9713', '1963', '4302', '8475', '19022', '26181', '364', '396', '13616', '15214', '23266', '5425', '2784', '16109', '16224', '21808', '24161', '21927', '6626', '10805', '25069', '25628', '2239', '10652', '17984', '22147', '22979', '24592', '2877', '3876', '7481', '9338', '12611', '12861', '15175', '22493', '4301', '16265', '21614', '7578', '14834', '15821', '22100', '11607', '19351', '2563', '8437', '12071', '2770', '6806', '11806', '8678', '8301', '267', '24240', '6632', '8386', '12187', '13153', '14345', '10081', '3185', '13291', '20547', '20792', '7885', '19551', '22190', '9758', '17006', '1859', '4298', '15192', '17274', '18941', '20902', '21798', '3631', '23901', '13702', '14667', '17874', '18152', '19978', '199', '16935', '6482', '24148', '11629', '17099', '11325', '11318', '12720', '25729', '12743', '21712', '950', '1265', '1839', '3063', '3502', '4446', '5639', '6009', '6896', '9736', '9980', '13470', '15126', '16881', '17828', '17875', '18210', '19140', '19316', '23095', '23864', '25910', '25917', '14286', '17131', '20940', '6039', '6176', '6303', '15161', '20949', '22879', '18215', '19051', '21125', '2656', '14560', '24251', '1098', '16107', '26171', '8150', '16703', '13202', '22253', '4128', '5738', '5478', '6538', '8349', '12042', '17252', '18142', '13501', '16216', '1490', '20813', '4781', '6081', '6919', '19358', '23616', '4756', '5497', '8298', '12709', '18443', '18658', '18667', '26157', '450', '11284', '11910', '23477', '11923', '4293', '20616', '11602', '5636', '17988', '2883', '4015', '25189', '2055', '2560', '4146', '10926', '12553', '18668', '15495', '9264', '12614', '24970', '10640', '15247', '17426', '3037', '9712', '10726', '16482', '17990', '23151', '2339', '24594', '5477', '13497', '14496', '19457', '5529', '5655', '2771', '5417', '13352', '13619', '18585', '20513', '4117', '16471', '4199', '6443', '19932', '19936', '25864', '2118', '26132', '17944', '20884', '200', '492', '4422', '6708', '7013', '8151', '9020', '9021', '9208', '9722', '16719', '16882', '17016', '17022', '19586', '19678', '24861', '9994', '17276', '18383', '12701', '18879', '11841', '20550', '4211', '7104', '11670', '11876', '17808', '24121', '25962', '22283', '15824', '21195', '15171', '15305', '17864', '23417', '4139', '5698', '9659', '10496', '11713', '20002', '25598', '25607', '25661', '4138', '11328', '2455', '14353', '14886', '2043', '6315', '21131', '23859', '5156', '7483', '10904', '12707', '14282', '17933', '294', '8626', '21546', '11459', '6706', '8428', '10637', '18603', '21340', '12868', '17180', '17738', '18154', '16213', '20383', '24870', '6703', '12803', '13999', '15596', '17592', '18920', '15657', '10878', '26020', '11034', '18764', '22433', '9093', '13680', '13346', '6183', '369', '7727', '16433', '16570', '5601', '7645', '13675', '4186', '12616', '4485', '16266', '1822', '6503', '3773', '12887', '21695', '1594', '4774', '5673', '15382', '16717', '19603', '15172', '17076', '19018', '17595', '5078', '25172', '11035', '21864', '4284', '9643', '13837', '15194', '15623', '17250', '23470', '25094', '26067', '6056', '17289', '23051', '8823', '9194', '6635', '9216', '19019', '22507', '5519', '5730', '11047', '15252', '21289', '26167', '25112', '13389', '6185', '23224', '24412', '5363', '253', '4634', '17122', '21051', '2259', '10317', '11816', '6448', '1346', '2136', '9591', '17453', '309', '2186', '6012', '10677', '11030', '13704', '17015', '23946', '25611', '1050', '17120', '9595', '6744', '1125', '8055', '8526', '9486', '11537', '12453', '18880', '18909', '19962', '23476', '19078', '20427', '8520', '16177', '21100', '21156', '9125', '15943', '15626', '1154', '12017', '12930', '8704', '17591', '12161', '19162', '1093', '3059', '9649', '10251', '25903', '4143', '6808', '7802', '17127', '20554', '21777', '22108', '23555', '25718', '4247', '4250', '8726', '9491', '11379', '11405', '15196', '15938', '17126', '17764', '232', '1075', '8737', '13481', '13862', '16742', '24402', '128', '4353', '6558', '6920', '14865', '15941', '16877', '10000', '17337', '21634', '851', '2713', '13199', '16837', '18032', '19568', '20004', '1341', '1408', '4273', '5259', '7355', '9143', '14357', '16332', '19940', '853', '8441', '16070', '16087', '17231', '19434', '23944', '24499', '10062', '23681', '23727', '2169', '5938', '16084', '18724', '18739', '19581', '20954', '23991', '6629', '8786', '14078', '22088', '22224', '4641', '17937', '21660', '12056', '2761', '14647', '4269', '26159', '3066', '5434', '7991', '8116', '11609', '15384', '16946', '17612', '15528', '163', '3825', '20893', '10910', '25777', '14771', '24127', '2143', '12118', '15329', '25116', '12689', '17560', '21697', '17599', '19442', '12419', '3507', '11626', '19313', '21755', '19356', '23465', '598', '5255', '8864', '16131', '16235', '16280', '17137', '23810', '1728', '5656', '6082', '18488', '22610', '6390', '5731', '6280', '1499', '20261', '24002', '23653', '5225', '3849', '7010', '7506', '9312', '20781', '8728', '11227', '5862', '7959', '17569', '18973', '19207', '19580', '3988', '16348', '4017', '7888', '17291', '1008', '2185', '8369', '11824', '12066', '16888', '20808', '21815', '1985', '9763', '21657', '16225', '21404', '26058', '9893', '20526', '5202', '17800', '21995', '3188', '3136', '9248', '11108', '13966', '4189', '16234', '17251', '18373', '20557', '19871', '25526', '23786', '25534', '11631', '11861', '18580', '18623', '20217', '25436', '21588', '17797', '1667', '4258', '5608', '5771', '6675', '7386', '16264', '17401', '18741', '19895', '20315', '23741', '25107', '25439', '16281', '24728', '2762', '22378', '9986', '11719', '4467', '21658', '23490', '1669', '12703', '5260', '6810', '13636', '16696', '17739', '19605', '5838', '11572', '21630', '6073', '9391', '2059', '11746', '21800', '22372', '6465', '11563', '15891', '17385', '1599', '5812', '17248', '20618', '20853', '9392', '24252', '13422', '16349', '11939', '17191', '1350', '1023', '1675', '2512', '3058', '11815', '20924', '23420', '19464', '23968', '9597', '11820', '17019', '17121', '7811', '22269', '25272', '1787', '1279', '14550', '15258', '7071', '8195', '15951', '400', '4379', '6541', '6905', '8216', '14498', '17502', '17740', '5408', '19609', '11066', '2340', '2443', '6918', '7650', '8184', '8625', '14369', '15395', '17583', '25977', '18684', '19501', '20942', '17724', '25957', '25958', '8263', '12046', '19126', '2182', '3553', '15571', '10918', '20253', '15388', '15387', '3955', '10532', '7524', '8721', '15005', '15372', '16022', '18685', '22083', '22105', '11522', '8857', '12235', '22129', '25387', '2826', '23216', '8530', '10906', '21144', '1073', '18399', '14149', '3750', '8147', '11616', '14662', '16648', '19560', '22199', '23530', '4289', '9135', '12160', '19809', '4027', '7450', '836', '16747', '18193', '9095', '12043', '18742', '22890', '26044', '8876', '10990', '4255', '4771', '5251', '18256', '18337', '20236', '11279', '9832', '17750', '22976', '25609', '124', '14319', '15663', '16937', '18052', '20258', '9151', '25856', '2047', '3632', '15383', '24385', '3716', '8391', '14497', '24101', '2388', '16955', '12981', '19642', '7592', '8179', '7579', '21653', '5542', '4080', '14747', '17463', '19324', '20567', '21550', '24220', '25179', '25553', '25554', '11468', '11470', '17804', '17294', '2309', '6532', '8553', '4633', '11593', '16818', '23648', '939', '1834', '5056', '13664', '14037', '16940', '19613', '16335', '6913', '3594', '10024', '23713', '10376', '15325', '20344', '2001', '3633', '23064', '5083', '5084', '8711', '12712', '14324', '21409', '17124', '25719', '8261', '11464', '17997', '20662', '22837', '2316', '11929', '350', '951', '25676', '2532', '14067', '20086', '21772', '15715', '925', '8615', '6506', '9037', '13483', '14711', '23623', '23686', '864', '1311', '3983', '26013', '17882', '18379', '18217', '26173', '21297', '18447', '21165', '4988', '17125', '9913', '22382', '17884', '20538', '24032', '2009', '7309', '8156', '8403', '16011', '22929', '22993', '8732', '10022', '14932', '16659', '22377', '22806', '14809', '22953', '23950', '18489', '95', '15524', '3291', '12696', '14869', '6190', '10656', '11002', '11403', '20106', '24060', '25610', '22693', '23920', '4458', '5547', '5659', '7883', '8387', '12313', '15160', '19325', '21205', '22831', '1556', '11965', '14096', '23154', '15191', '5212', '6628', '19015', '19444', '25139', '9441', '10388', '8222', '21495', '6807', '2075', '3873', '4182', '10439', '14619', '2044', '4490', '17001', '18013', '9147', '24398', '5216', '17290', '20155', '1045', '6265', '5402', '15947', '2203', '7594', '21130', '21615', '2622', '4960', '16270', '16102', '17956', '20375', '22463', '3878', '16584', '2997', '6888', '11664', '4712', '11017', '7632', '14170', '20414', '11427', '5240', '9074', '12425', '18275', '20636', '4640', '19248', '11109', '21562', '21149', '312', '16545', '12786', '13673', '7958', '25130', '14543', '21221', '9266', '2750', '20668', '3068', '5631', '16067', '19569', '2917', '6031', '2010', '8064', '20599', '179', '547', '1829', '1982', '3178', '4989', '18870', '20062', '22464', '6878', '11528', '22244', '11812', '24248', '8122', '9769', '15253', '16647', '22489', '23412', '25443', '8511', '22503', '13604', '4704', '8801', '12695', '15125', '15420', '25204', '385', '1323', '1606', '7072', '9890', '12849', '14377', '17981', '18234', '21220', '22225', '23506', '23620', '24332', '376', '2611', '16620', '1908', '16621', '12106', '1267', '1511', '15793', '18102', '20772', '23248', '26193', '10872', '2666', '24250', '9630', '10252', '16820', '22830', '14159', '5144', '24852', '8869', '299', '14174', '18746', '22051', '22075', '24713', '14616', '17817', '2356', '6337', '17419', '18105', '2773', '5661', '6529', '6543', '16486', '8523', '19964', '2342', '2516', '21998', '941', '13712', '16727', '22321', '23383', '25442', '19980', '5957', '7716', '11233', '14090', '18397', '25541', '2249', '6077', '6611', '8672', '19955', '21832', '3316', '9759', '11865', '3199', '19507', '12798', '855', '4261', '7772', '23299', '8871', '17090', '3772', '4104', '4431', '4967', '11152', '15616', '16262', '18995', '19562', '22087', '22109', '22839', '23683', '24477', '25304', '14854', '24489', '6835', '24219', '3321', '1151', '2410', '3843', '6301', '10247', '15414', '18743', '22032', '22903', '23674', '24294', '24706', '25998', '2124', '3293', '5825', '628', '9413', '13641', '1962', '1613', '13992', '15217', '15665', '16154', '21159', '915', '10438', '18624', '20558', '10026', '15316', '17249', '18066', '12787', '21621', '24877', '93', '17343', '20328', '9103', '10684', '11878', '18557', '21101', '19909', '23474', '7093', '8000', '17395', '18582', '22375', '23419', '2593', '10433', '3231', '4705', '4773', '6411', '8549', '10500', '16352', '17546', '19808', '21931', '22369', '22466', '25159', '22815', '29', '16751', '750', '19641', '23480', '23652', '1278', '778', '1048', '16743', '22235', '4376', '18246', '3718', '7511', '6642', '17277', '18209', '7247', '9459', '11829', '10338', '7523', '12458', '12460', '14844', '16651', '19378', '161', '97', '3105', '11418', '19583', '21821', '22719', '21684', '22720', '24169', '16872', '24816', '9871', '17179', '19996', '380', '20078', '5061', '20317', '12411', '8922', '9488', '17182', '22894', '10041', '13995', '10383', '13319', '16115', '21583', '25229', '2074', '10996', '19080', '751', '2655', '20008', '25866', '2087', '2993', '4377', '6271', '7023', '13404', '1563', '2457', '3534', '4639', '5065', '6387', '14379', '15145', '15562', '15708', '15714', '15805', '17345', '17580', '17584', '18396', '18952', '19677', '20231', '23241', '24616', '24617', '24819', '1157', '16334', '9922', '2504', '19585', '9987', '21554', '19598', '11216', '13815', '7463', '12318', '15150', '19800', '7695', '3827', '8595', '14691', '7025', '25540', '3239', '11465', '11577', '6666', '17986', '21190', '9217', '2596', '23462', '23464', '25644', '3452', '6442', '9968', '14383', '14652', '17681', '20587', '21592', '2144', '2774', '3055', '3652', '3655', '3766', '3814', '6388', '7096', '9249', '12051', '12423', '12885', '14808', '15173', '15189', '15999', '18942', '19705', '20250', '21030', '21825', '25108', '13684', '18283', '19301', '21814', '1404', '2562', '11199', '18552', '17141', '11462', '11612', '24944', '5814', '17690', '1656', '4040', '5828', '11842', '21531', '1992', '3102', '12414', '18562', '24439', '14431', '20537', '20543', '21339', '1092', '3196', '23226', '4033', '20782', '23730', '4625', '12296', '20959', '3119', '19004', '7103', '2503', '5465', '18141', '20663', '7384', '6944', '12660', '14372', '26178', '7024', '17393', '17827', '24207', '1281', '3653', '10163', '12551', '17588', '18621', '25287', '9962', '2506', '10682', '22428', '6354', '15188', '19060', '10004', '25234', '18314', '3684', '5395', '5445', '11141', '18370', '19447', '20434', '4263', '6859', '17999', '18282', '9959', '6008', '20914', '5081', '12256', '17237', '8877', '3280', '13191', '13013', '18899', '21293', '1107', '6973', '2950', '9335', '25235', '25668', '6455', '19801', '65', '358', '8504', '21152', '19379', '19247', '18586', '27', '11114', '19081', '24726', '12320', '12321', '19222', '18344', '3292', '10391', '1857', '3967', '12053', '880', '252', '15418', '4019', '5626', '24957', '4148', '9863', '8457', '15478', '24203', '8557', '8308', '21288', '26191', '3516', '7053', '12618', '13144', '15413', '18634', '1378', '7877', '3852', '11622', '15422', '2984', '8731', '10564', '8970', '15187', '3850', '9128', '113', '4103', '12312', '17994', '20947', '26021', '3204', '25937', '2476', '18984', '187', '1821', '21386', '866', '17825', '20173', '6305', '7726', '14870', '14872', '20316', '1493', '2452', '3811', '9027', '14153', '1436', '20064', '20331', '13864', '21154', '10133', '18218', '3067', '18721', '1293', '2621', '2623', '3283', '3812', '3820', '3824', '4834', '5131', '6222', '6456', '6525', '6868', '7525', '8448', '9433', '12802', '13482', '13526', '14157', '14373', '15148', '17600', '17819', '17823', '17824', '18000', '18444', '22324', '22901', '24474', '24479', '24615', '26039', '844', '890', '11197', '13035', '16110', '26130', '1916', '20953', '24463', '15706', '374', '20776', '25449', '24341', '23135', '17818', '19697', '23219', '23809', '11583', '19252', '3195', '24597', '17280', '2785', '3682', '19956', '2879', '7861', '2355', '12704', '17297', '16227', '25219', '25089', '820', '2515', '194', '8628', '4425', '7278', '14559', '2459', '6380', '1025', '1026', '1696', '15197', '18195', '13832', '17114', '20489', '7088', '7546', '8146', '21028', '23418', '10897', '5548', '15898', '11924', '25437', '6159', '19554', '24878', '5577', '23881', '12387', '19520', '23084', '23554', '19931', '23553', '22888', '12547', '25181', '12617', '17388', '6037', '3431', '164', '2142', '13283', '23858', '24601', '800', '13167', '15485', '20260', '4275', '4081', '13625', '17878', '24471', '18122', '1699', '2303', '7878', '8541', '8593', '17575', '17683', '17923', '18771', '24593', '25875', '12645', '16803', '12749', '16819', '24034', '17861', '5415', '4380', '16756', '3100', '18098', '16729', '2049', '9915', '19380', '1695', '1825', '6226', '14317', '20775', '4469', '9618', '11285', '12193', '2306', '10514', '3964', '4018', '9414', '12640', '16608', '16800', '4051', '21187', '21313', '26092', '11879', '21310', '2803', '2295', '5826', '22', '11183', '19440', '22618', '25043', '3074', '23416', '1101', '9030', '17854', '22487', '25891', '1823', '2003', '22031', '885', '2505', '17192', '19911', '25487', '6229', '6423', '7647', '1966', '8048', '15717', '10847', '10148', '4875', '4488', '15913', '11009', '20157', '21344', '22990', '23471', '3206', '6535', '6579', '2386', '16941', '8446', '18597', '11502', '11903', '12157', '12158', '24210', '12290', '17307', '20031', '1860', '3073', '4000', '17173', '3685', '25853', '8404', '25', '22891', '28', '7916', '21515', '21523', '4656', '18196', '23303', '24841', '4265', '5267', '5271', '7597', '7638', '7648', '11844', '7854', '1668', '4835', '15007', '10559', '18245', '10445', '21594', '22738', '6389', '6914', '18279', '7468', '10002', '12041', '14384', '17341', '24470', '15186', '8443', '15248', '13683', '21203', '21778', '26042', '3451', '7038', '17951', '833', '2810', '18145', '21799', '192', '4826', '4021', '26022', '6161', '7055', '19712', '21024', '8071', '17178', '23215', '3062', '16892', '19572', '7857', '11968', '19810', '14841', '920', '25904', '25829', '25849', '13355', '13022', '8077', '6300', '2117', '5182', '13311', '1879', '21548', '21809', '15609', '21177', '1174', '2712', '14176', '21018', '5479', '16124', '20807', '24334', '16415', '7046', '14710', '15682', '17157', '23093', '21547', '15357', '6076', '7311', '8629', '12615', '15163', '16483', '17731', '18913', '13990', '4555', '7482', '15681', '20793', '10346', '15687', '19143', '19383', '6291', '19223', '19739', '20568', '8452', '22233', '12612', '14843', '19208', '20569', '17585', '15218', '19703', '7957', '18895', '4825', '8037', '9593', '14621', '19608', '15250', '15589', '4836', '11898', '1028', '9924', '12262', '15181', '2331', '17461', '188', '22920', '373', '21579', '23775', '11012', '8198', '13010', '320', '1897', '5602', '6024', '17464', '17590', '18042', '21315', '22770', '5483', '18884', '22727', '2487', '3052', '6711', '16232', '22725', '14991', '20560', '10356', '19062', '8973', '14600', '23138', '4372', '10880', '16598', '3851', '7011', '8702', '18159', '15200', '15617', '7807', '11828', '2352', '1855', '2527', '5057', '7094', '10432', '5774', '16891', '2624', '24202', '21314', '15572', '7356', '22556', '19102', '748', '8811', '22021', '2332', '18544', '21596', '16783', '15642', '17563', '12252', '22404', '9026', '18669', '19866', '25545', '8538', '19450', '7536', '7534', '3383', '1344', '18126', '1322', '10925', '15195', '16068', '17467', '11611', '20779', '24490', '4276', '24159', '717', '17865', '1376', '4267', '1289', '1560', '4365', '1915', '12263', '22000', '25136', '15259', '348', '5660', '15847', '16155', '315', '5629', '10499', '16718', '25599', '11969', '1967', '18996', '832', '3387', '4703', '7447', '9764', '10117', '14340', '14370', '15006', '16231', '16590', '16730', '19957', '21848', '22320', '15712', '19596', '5365', '7769', '15977', '17118', '1292', '6648', '10341', '14840', '16040', '10936', '19509', '19510', '23687', '17293', '15668', '25614', '26006', '22394', '10178', '3744', '24133', '19256', '3989', '17471', '510', '22285', '10679', '115', '5268', '8671', '23757', '830', '16802', '9053', '12504', '10850', '12644', '20528', '1589', '7603', '23759', '15208', '1561', '4484', '22379', '21558', '19683', '22744', '22746', '1981', '5468', '5668', '6908', '8187', '18034', '19879', '25444', '3818', '3388', '6735', '23167', '2806', '9209', '914', '2243', '3442', '5162', '18633', '5119', '10517', '13036', '6446', '8036', '25114', '21544', '13', '7596', '11196', '19170', '7090', '6350', '4495', '8372', '11823', '13628', '15246', '16014', '20332', '23710', '5137', '6884', '1013', '19011', '2123', '71', '20803', '6356', '25231', '1551', '8058', '2328', '8336', '24464', '12745', '19023', '10468', '8398', '9327', '8739', '13357', '25115', '25852', '403', '3200', '4264', '17468', '25510', '3279', '1782', '13521', '18784', '8976', '3910', '10513', '25059', '25595', '7477', '19257', '22961', '19906', '26102', '13749', '12121', '13034', '6079', '19941', '14135', '13325', '14502', '20926', '15899', '16338', '21390', '82', '3844', '7595', '8118', '15802', '15688', '22692', '4955', '4954', '5409', '8623', '11926', '8340', '5839', '7026', '12192', '3053', '20883', '787', '12940', '2222', '2215', '10792', '15695', '20422', '21309', '20379', '1549', '22766', '23168', '24732', '4272', '2557', '2247', '9606', '4958', '5973', '10884', '12122', '16353', '1427', '11037', '2981', '4427', '6669', '9865', '8449', '13490', '19528', '22577', '25440', '18366', '25217', '4750', '19147', '20174', '7588', '7590', '3599', '14130', '14302', '5432', '12676', '11721', '12151', '15221', '11792', '16831', '5667', '3297', '14770', '23461', '2329', '24846', '8367', '14894', '1670', '22927', '3362', '3347', '16957', '8969', '25649', '25839', '2938', '18581', '1024', '12552', '16513', '21593', '22325', '18970', '2409', '3522', '4286', '4288', '18278', '2201', '14868', '16226', '5211', '11028', '21171', '22730', '1187', '6290', '8161', '12054', '21468', '13677', '18288', '23206', '4110', '16523', '17696', '15641', '5466', '12801', '19548', '10352', '15423', '18144', '4959', '6867', '19110', '9149', '17346', '20319', '16042', '5533', '782', '11539', '15227', '16655', '18151', '21811', '254', '7572', '20150', '22312', '25226', '23621', '11623', '23306', '5960', '8705', '11662', '14094', '19014', '24575', '8255', '14842', '3719', '5067', '6907', '8072', '8375', '9025', '13649', '19545', '25060', '25289', '15683', '19923', '20664', '21824', '25359', '1989', '4106', '7515', '17782', '18231', '18628', '17785', '15583', '24272', '18091', '24456', '25211', '11971', '938', '5087', '17936', '7636', '12554', '4278', '18183', '10522', '10561', '25678', '1660', '3377', '23068', '25631', '1383', '6737', '9988', '14620', '822', '9518', '16358', '18238', '4777', '15396', '26180', '19064', '360', '2304', '7602', '8307', '9514', '1959', '9723', '21713', '25470', '5446', '5632', '20433', '18558', '10818', '11016', '25596', '6513', '25138', '17275', '16801', '19451', '9579', '16932', '6534', '11561', '22381', '12863', '18390', '1836', '8400', '13387', '22048', '23424', '8153', '15182', '16728', '22319', '8054', '24504', '22605', '21623', '7479', '2754', '5511', '7265', '10056', '13390', '25176', '10382', '25482', '2223', '4266', '20216', '16643', '20035', '6170', '8881', '16609', '372', '14131', '12113', '16886', '142', '18626', '8735', '25062', '1793', '5481', '3754', '8185', '16496', '9039', '11911', '18613', '10497', '357', '23300', '24960', '21303', '734', '19221', '17470', '18772', '21949', '18194', '5697', '14358', '8558', '13717', '8534', '8676', '14639', '2073', '1662', '2613', '9224', '10154', '11410', '16830', '4144', '18596', '23771', '16622', '18454', '13031', '8738', '13334', '13620', '16312', '16314', '20515', '23915', '12266', '15678', '17134', '21436', '23146', '23488', '25575', '11991', '3186', '14182', '17537', '15358', '18036', '18338', '9631', '10898', '14175', '12307', '22980', '5387', '18156', '19145', '23760', '1983', '13012', '20943', '22110', '5231', '22311', '20084', '6576', '1621', '7109', '9018', '14374', '18299', '19687', '12751', '6307', '13486', '4259', '18688', '4630', '9921', '10672', '12512', '831', '11280', '15154', '14132', '4034', '9715', '9717', '8512', '25492', '25511', '1798', '4828', '5404', '24462', '11641', '14338', '22729', '677', '4426', '4242', '19466', '7543', '24128', '17581', '10446', '11411', '24242', '5853', '5492', '9979', '18094', '8870', '9831', '12473', '18388', '20654', '9867', '4037', '25663', '4196', '15401', '1051', '4245', '25664', '24140', '16823', '5571', '13802', '19553', '25447', '15962', '19892', '18417', '4643', '20320', '14990', '25975', '24708', '19443', '23492', '8395', '8725', '11054', '14763', '4432', '5062', '19881', '20766', '11718', '15553', '15374', '5490', '8474', '1976', '23672', '12295', '9189', '2116', '9765', '9774', '12034', '17935', '12248', '98', '10116', '4181', '17992', '8409', '2248', '11579', '15073', '16922', '20925', '22645', '13415', '7585', '15386', '23772', '735', '6078', '74', '2298', '16129', '8717', '10638', '13558', '8669', '9038', '12213', '21710', '22318', '24888', '22728', '2561', '23094', '1969', '8472', '24141', '16971', '5228', '20170', '18608', '14339', '22816', '7280', '7267', '20309', '8891', '11893', '25667', '6776', '24733', '18455', '2334', '10180', '17587', '11215', '23156', '23970', '7718', '19502', '3748', '17503', '10602', '20805', '11467', '19575', '4038', '7058', '23811', '1878', '12338', '15800', '9130', '25095', '20066', '1010', '2749', '5829', '11642', '25230', '5256', '5257', '22827', '16015', '22938', '15774', '20333', '4262', '6701', '10407', '5406', '22435', '11120', '16340', '17851', '20233', '4366', '410', '9211', '13413', '19473', '23812', '24214', '4116', '25496', '19314', '19880', '25543', '26019', '26048', '24820', '20707', '5486', '8366', '5261', '6282', '18908', '25531', '12050', '5364', '14', '14171', '14845', '5232', '19521'))

(authors_graph['3466'])

AtlasView({'937': {}, '5233': {}, '8579': {}, '10310': {}, '15931': {}, '17038': {}, '18720': {}, '19607': {}})

nx.draw(authors_graph,with_labels=True)

¿Podemos encontrar al investigador más influyente/importante en esta red?

¿Cómo evaluamos la importancia de algunas personas en una red?

Dentro de una red social, habrá determinadas personas que desempeñen determinadas funciones importantes. Por ejemplo, puede haber personas hiperconectadas que estén conectadas con muchas, muchas más personas. Ellas serán claves para la difusión de información. Alternativamente, si se tratara de una red de contactos de enfermedades, identificarlos sería útil para detener la propagación de enfermedades.

¿Cómo se identificaría a estas personas?

Tarea 2.2

Cree una lista de tuplas (nodo, grado de nodo) y busque el nodo con el grado máximo.

grado de nodo = número de vecinos

Repita el ejercicio para todas mas métricas de centralidad vistas en este notebook. Interprete sus resultados en función de la métrica.

El grado de un nodo se traduce en grado de centralidad (que es una versión normalizada de grado)

nx.degree_centrality(authors_graph)

{'3466': 0.0015264262545315779,
 '937': 0.0009540164090822362,
 '5233': 0.00038160656363289447,
 '8579': 0.0009540164090822362,
 '10310': 0.002480442663613814,
 '15931': 0.0019080328181644724,
 '17038': 0.003243655790879603,
 '18720': 0.0005724098454493417,
 '19607': 0.0007632131272657889,
 '1854': 0.0015264262545315779,
 '4583': 0.0005724098454493417,
 '9572': 0.006487311581759206,
 '10841': 0.0013356229727151307,
 '13056': 0.0019080328181644724,
 '14982': 0.00038160656363289447,
 '16310': 0.003243655790879603,
 '19640': 0.004770082045411181,
 '23855': 0.0015264262545315779,
 '24372': 0.00019080328181644724,
 '24814': 0.0040068689181453915,
 '5052': 0.00553329517267697,
 '899': 0.0005724098454493417,
 '1796': 0.00038160656363289447,
 '2287': 0.0026712459454302615,
 '3096': 0.0022896393817973667,
 '3386': 0.0020988360999809196,
 '4472': 0.0007632131272657889,
 '5346': 0.003816065636328945,
 '5740': 0.00019080328181644724,
 '6094': 0.0007632131272657889,
 '6376': 0.00038160656363289447,
 '9124': 0.0045792787635947334,
 '10235': 0.002480442663613814,
 '10427': 0.0015264262545315779,
 '10597': 0.0011448196908986834,
 '15159': 0.0007632131272657889,
 '16148': 0.00343445907269605,
 '16741': 0.0013356229727151307,
 '18235': 0.00019080328181644724,
 '18549': 0.00019080328181644724,
 '19297': 0.0030528525090631558,
 '20511': 0.0061057050181263115,
 '20595': 0.001717229536348025,
 '20613': 0.0019080328181644724,
 '24371': 0.004197672199961839,
 '24559': 0.004388475481778287,
 '24731': 0.00019080328181644724,
 '25102': 0.0013356229727151307,
 '25271': 0.0030528525090631558,
 '25396': 0.004388475481778287,
 '1658': 0.0011448196908986834,
 '4822': 0.00038160656363289447,
 '6864': 0.00038160656363289447,
 '7689': 0.0061057050181263115,
 '7926': 0.001717229536348025,
 '10268': 0.0013356229727151307,
 '12971': 0.00019080328181644724,
 '18600': 0.0007632131272657889,
 '20421': 0.0005724098454493417,
 '20886': 0.00038160656363289447,
 '21048': 0.0011448196908986834,
 '22393': 0.0009540164090822362,
 '23186': 0.0011448196908986834,
 '23214': 0.0007632131272657889,
 '23298': 0.00038160656363289447,
 '23945': 0.0005724098454493417,
 '24939': 0.0005724098454493417,
 '339': 0.005724098454493417,
 '624': 0.003243655790879603,
 '3731': 0.001717229536348025,
 '4743': 0.004770082045411181,
 '5407': 0.001717229536348025,
 '6610': 0.012974623163518412,
 '6700': 0.005914901736309864,
 '8045': 0.0028620492272467086,
 '9099': 0.001717229536348025,
 '9639': 0.005914901736309864,
 '9785': 0.012974623163518412,
 '12141': 0.0009540164090822362,
 '15184': 0.002480442663613814,
 '15784': 0.0020988360999809196,
 '18719': 0.004197672199961839,
 '19870': 0.0040068689181453915,
 '20532': 0.003816065636328945,
 '22527': 0.004770082045411181,
 '23576': 0.0007632131272657889,
 '23577': 0.001717229536348025,
 '23649': 0.001717229536348025,
 '24199': 0.0011448196908986834,
 '24293': 0.003816065636328945,
 '25201': 0.002480442663613814,
 '10243': 0.0026712459454302615,
 '6774': 0.005151688609044075,
 '8049': 0.0015264262545315779,
 '8053': 0.0005724098454493417,
 '8517': 0.0013356229727151307,
 '11964': 0.002480442663613814,
 '15538': 0.0026712459454302615,
 '16694': 0.001717229536348025,
 '18648': 0.0007632131272657889,
 '19423': 0.012020606754436176,
 '21012': 0.015455065827132226,
 '22457': 0.005724098454493417,
 '22691': 0.014691852699866437,
 '23452': 0.004197672199961839,
 '16174': 0.0007632131272657889,
 '16470': 0.00019080328181644724,
 '17822': 0.00019080328181644724,
 '14265': 0.007059721427208548,
 '392': 0.00019080328181644724,
 '2485': 0.00038160656363289447,
 '2949': 0.001717229536348025,
 '3173': 0.00019080328181644724,
 '3441': 0.0011448196908986834,
 '3593': 0.0011448196908986834,
 '3853': 0.00019080328181644724,
 '3927': 0.00038160656363289447,
 '3937': 0.0007632131272657889,
 '3939': 0.00343445907269605,
 '5107': 0.00343445907269605,
 '5218': 0.00038160656363289447,
 '5230': 0.00038160656363289447,
 '6030': 0.0007632131272657889,
 '7350': 0.0036252623545124977,
 '7504': 0.0020988360999809196,
 '7601': 0.00038160656363289447,
 '8718': 0.00038160656363289447,
 '9522': 0.0009540164090822362,
 '11621': 0.0013356229727151307,
 '12498': 0.00038160656363289447,
 '12691': 0.00038160656363289447,
 '15251': 0.00019080328181644724,
 '16020': 0.0013356229727151307,
 '16261': 0.00019080328181644724,
 '17156': 0.0005724098454493417,
 '17626': 0.0030528525090631558,
 '18622': 0.00038160656363289447,
 '19059': 0.0011448196908986834,
 '19525': 0.0005724098454493417,
 '19738': 0.0009540164090822362,
 '20122': 0.0007632131272657889,
 '20432': 0.0009540164090822362,
 '21866': 0.00019080328181644724,
 '22074': 0.0019080328181644724,
 '23721': 0.0005724098454493417,
 '8916': 0.0020988360999809196,
 '13556': 0.003816065636328945,
 '14485': 0.0040068689181453915,
 '8612': 0.00343445907269605,
 '615': 0.00343445907269605,
 '743': 0.001717229536348025,
 '2076': 0.00038160656363289447,
 '4515': 0.0015264262545315779,
 '5773': 0.0007632131272657889,
 '9482': 0.0040068689181453915,
 '10822': 0.00038160656363289447,
 '11175': 0.001717229536348025,
 '11604': 0.0009540164090822362,
 '14004': 0.00038160656363289447,
 '15003': 0.011829803472619728,
 '15552': 0.00343445907269605,
 '15814': 0.0022896393817973667,
 '16083': 0.0019080328181644724,
 '17932': 0.0020988360999809196,
 '20001': 0.00019080328181644724,
 '20100': 0.0022896393817973667,
 '23481': 0.0009540164090822362,
 '16258': 0.002480442663613814,
 '1356': 0.0007632131272657889,
 '1727': 0.0013356229727151307,
 '2752': 0.0007632131272657889,
 '4125': 0.0009540164090822362,
 '6667': 0.0005724098454493417,
 '6825': 0.00038160656363289447,
 '10039': 0.0020988360999809196,
 '10351': 0.0005724098454493417,
 '11082': 0.0022896393817973667,
 '14123': 0.002480442663613814,
 '16676': 0.00038160656363289447,
 '21194': 0.00019080328181644724,
 '10912': 0.0005724098454493417,
 '14534': 0.0022896393817973667,
 '17268': 0.0007632131272657889,
 '19783': 0.00019080328181644724,
 '21705': 0.0005724098454493417,
 '22836': 0.0005724098454493417,
 '2710': 0.006296508299942759,
 '62': 0.0013356229727151307,
 '106': 0.0007632131272657889,
 '260': 0.0009540164090822362,
 '2959': 0.0019080328181644724,
 '3677': 0.0022896393817973667,
 '4708': 0.0005724098454493417,
 '5172': 0.0019080328181644724,
 '5541': 0.0011448196908986834,
 '5794': 0.0005724098454493417,
 '5807': 0.001717229536348025,
 '6575': 0.0020988360999809196,
 '8458': 0.00038160656363289447,
 '10601': 0.00038160656363289447,
 '11401': 0.00038160656363289447,
 '13026': 0.0007632131272657889,
 '13205': 0.0009540164090822362,
 '13659': 0.0015264262545315779,
 '13989': 0.0019080328181644724,
 '14007': 0.0007632131272657889,
 '14009': 0.0005724098454493417,
 '14599': 0.005724098454493417,
 '15301': 0.00038160656363289447,
 '18757': 0.0015264262545315779,
 '20934': 0.0009540164090822362,
 '21543': 0.0013356229727151307,
 '22184': 0.0013356229727151307,
 '23647': 0.0022896393817973667,
 '23708': 0.0030528525090631558,
 '25916': 0.0019080328181644724,
 '26023': 0.0005724098454493417,
 '26051': 0.00038160656363289447,
 '26100': 0.00038160656363289447,
 '214': 0.0013356229727151307,
 '5435': 0.0005724098454493417,
 '6512': 0.009349360809005915,
 '10590': 0.0013356229727151307,
 '23559': 0.0005724098454493417,
 '1765': 0.0015264262545315779,
 '3032': 0.0022896393817973667,
 '5302': 0.0020988360999809196,
 '7383': 0.002480442663613814,
 '7442': 0.00343445907269605,
 '7768': 0.0019080328181644724,
 '13276': 0.004960885327227628,
 '17266': 0.001717229536348025,
 '22415': 0.0022896393817973667,
 '10794': 0.00038160656363289447,
 '7050': 0.0011448196908986834,
 '25850': 0.00038160656363289447,
 '10113': 0.0022896393817973667,
 '10657': 0.00038160656363289447,
 '12130': 0.0020988360999809196,
 '17172': 0.0015264262545315779,
 '4846': 0.004197672199961839,
 '676': 0.004960885327227628,
 '824': 0.002480442663613814,
 '2133': 0.0022896393817973667,
 '2654': 0.007250524709024995,
 '4748': 0.0036252623545124977,
 '5672': 0.00038160656363289447,
 '10549': 0.0007632131272657889,
 '12928': 0.0020988360999809196,
 '13220': 0.0020988360999809196,
 '14419': 0.0026712459454302615,
 '17330': 0.003243655790879603,
 '17439': 0.00553329517267697,
 '18487': 0.005151688609044075,
 '20850': 0.0028620492272467086,
 '22779': 0.0020988360999809196,
 '23382': 0.005724098454493417,
 '24029': 0.0009540164090822362,
 '11785': 0.0040068689181453915,
 '45': 0.009349360809005915,
 '46': 0.008013737836290783,
 '570': 0.009158557527189467,
 '773': 0.010494180499904597,
 '1653': 0.010684983781721046,
 '2212': 0.00896775424537302,
 '2741': 0.01240221331806907,
 '2952': 0.008586147681740125,
 '3372': 0.009349360809005915,
 '4046': 0.00019080328181644724,
 '4164': 0.01030337721808815,
 '4511': 0.008586147681740125,
 '4513': 0.008204541118107232,
 '5262': 0.00019080328181644724,
 '6179': 0.008776950963556573,
 '6830': 0.008586147681740125,
 '7956': 0.010684983781721046,
 '8879': 0.008586147681740125,
 '11241': 0.009349360809005915,
 '11472': 0.008586147681740125,
 '12365': 0.014691852699866437,
 '12496': 0.009158557527189467,
 '12678': 0.0007632131272657889,
 '12781': 0.010875787063537493,
 '12851': 0.008586147681740125,
 '14540': 0.008776950963556573,
 '14807': 0.011448196908986834,
 '15659': 0.008586147681740125,
 '16159': 0.0007632131272657889,
 '17655': 0.012593016599885518,
 '17692': 0.008586147681740125,
 '18894': 0.00896775424537302,
 '19961': 0.008586147681740125,
 '20108': 0.008586147681740125,
 '20562': 0.008586147681740125,
 '20635': 0.00896775424537302,
 '21281': 0.01507345926349933,
 '21508': 0.012783819881701965,
 '21847': 0.009158557527189467,
 '22798': 0.0011448196908986834,
 '22887': 0.00896775424537302,
 '23293': 0.010112573936271704,
 '24955': 0.009730967372638809,
 '25346': 0.010684983781721046,
 '25758': 0.009730967372638809,
 '934': 0.0013356229727151307,
 '5579': 0.00019080328181644724,
 '9755': 0.005914901736309864,
 '10550': 0.0007632131272657889,
 '16032': 0.0030528525090631558,
 '17331': 0.00019080328181644724,
 '17603': 0.0007632131272657889,
 '20644': 0.0011448196908986834,
 '22497': 0.0007632131272657889,
 '23387': 0.00038160656363289447,
 '23907': 0.0009540164090822362,
 '24924': 0.004197672199961839,
 '25080': 0.0026712459454302615,
 '12422': 0.0005724098454493417,
 '1339': 0.0009540164090822362,
 '3164': 0.0011448196908986834,
 '15580': 0.0013356229727151307,
 '16393': 0.0007632131272657889,
 '20478': 0.004960885327227628,
 '20956': 0.00019080328181644724,
 '3890': 0.001717229536348025,
 '5621': 0.004197672199961839,
 '8824': 0.00038160656363289447,
 '11613': 0.0005724098454493417,
 '12306': 0.0005724098454493417,
 '12860': 0.0005724098454493417,
 '14547': 0.00019080328181644724,
 '18182': 0.0005724098454493417,
 '21707': 0.0005724098454493417,
 '24696': 0.003816065636328945,
 '2661': 0.0013356229727151307,
 '7899': 0.0009540164090822362,
 '8067': 0.0009540164090822362,
 '8208': 0.0005724098454493417,
 '11132': 0.0013356229727151307,
 '11402': 0.0007632131272657889,
 '12980': 0.0015264262545315779,
 '13364': 0.0015264262545315779,
 '14969': 0.0013356229727151307,
 '16389': 0.004960885327227628,
 '18109': 0.0009540164090822362,
 '18365': 0.0026712459454302615,
 '23038': 0.006296508299942759,
 '24845': 0.0015264262545315779,
 '25379': 0.00038160656363289447,
 '13740': 0.0020988360999809196,
 '4550': 0.0040068689181453915,
 '4702': 0.00038160656363289447,
 '7264': 0.0028620492272467086,
 '13096': 0.004197672199961839,
 '14128': 0.0007632131272657889,
 '19489': 0.0030528525090631558,
 '19527': 0.0007632131272657889,
 '19784': 0.00038160656363289447,
 '22476': 0.0013356229727151307,
 '25006': 0.004197672199961839,
 '25486': 0.0005724098454493417,
 '26': 0.0009540164090822362,
 '1407': 0.0011448196908986834,
 '1488': 0.005914901736309864,
 '8219': 0.00038160656363289447,
 '10762': 0.005724098454493417,
 '11801': 0.0020988360999809196,
 '12665': 0.00019080328181644724,
 '12688': 0.0005724098454493417,
 '13142': 0.005342491890860523,
 '15108': 0.004197672199961839,
 '15321': 0.0009540164090822362,
 '20647': 0.0005724098454493417,
 '20827': 0.0015264262545315779,
 '20879': 0.0028620492272467086,
 '23614': 0.004960885327227628,
 '3909': 0.003243655790879603,
 '17979': 0.0009540164090822362,
 '3872': 0.0015264262545315779,
 '5109': 0.00038160656363289447,
 '7533': 0.0015264262545315779,
 '12409': 0.0005724098454493417,
 '20101': 0.00019080328181644724,
 '23096': 0.00019080328181644724,
 '8862': 0.0013356229727151307,
 '78': 0.0007632131272657889,
 '4877': 0.0005724098454493417,
 '7459': 0.0022896393817973667,
 '8254': 0.002480442663613814,
 '12155': 0.0005724098454493417,
 '22598': 0.00343445907269605,
 '24932': 0.0009540164090822362,
 '888': 0.0011448196908986834,
 '1520': 0.0011448196908986834,
 '6468': 0.0011448196908986834,
 '6627': 0.0005724098454493417,
 '7007': 0.004770082045411181,
 '7712': 0.00343445907269605,
 '10711': 0.004388475481778287,
 '13614': 0.0030528525090631558,
 '14102': 0.0013356229727151307,
 '18517': 0.001717229536348025,
 '18676': 0.001717229536348025,
 '23351': 0.001717229536348025,
 '23689': 0.0005724098454493417,
 '24114': 0.00019080328181644724,
 '2465': 0.0007632131272657889,
 '2592': 0.00038160656363289447,
 '3977': 0.0013356229727151307,
 '5055': 0.00019080328181644724,
 '5993': 0.002480442663613814,
 '9265': 0.00019080328181644724,
 '12334': 0.002480442663613814,
 '19890': 0.0011448196908986834,
 '20341': 0.00019080328181644724,
 '21560': 0.00038160656363289447,
 '17309': 0.00019080328181644724,
 '24833': 0.003243655790879603,
 '543': 0.0045792787635947334,
 '1958': 0.0036252623545124977,
 '2193': 0.0011448196908986834,
 '3917': 0.0005724098454493417,
 '6858': 0.0005724098454493417,
 '8148': 0.0005724098454493417,
 '9092': 0.0005724098454493417,
 '12478': 0.0019080328181644724,
 '15366': 0.0005724098454493417,
 '18125': 0.0005724098454493417,
 '18398': 0.0005724098454493417,
 '19675': 0.0030528525090631558,
 '21806': 0.0011448196908986834,
 '23693': 0.001717229536348025,
 '26196': 0.0013356229727151307,
 '10115': 0.00038160656363289447,
 '10134': 0.00019080328181644724,
 '23916': 0.00019080328181644724,
 '7893': 0.001717229536348025,
 '593': 0.0030528525090631558,
 '5510': 0.0013356229727151307,
 '9360': 0.0019080328181644724,
 '12627': 0.0028620492272467086,
 '16778': 0.0015264262545315779,
 '18037': 0.0005724098454493417,
 '18051': 0.0019080328181644724,
 '13385': 0.00019080328181644724,
 '19578': 0.00019080328181644724,
 '12386': 0.0009540164090822362,
 '13333': 0.0009540164090822362,
 '23896': 0.0028620492272467086,
 '8978': 0.0007632131272657889,
 '9017': 0.005342491890860523,
 '15170': 0.0007632131272657889,
 '15455': 0.003243655790879603,
 '16589': 0.0009540164090822362,
 '2255': 0.0009540164090822362,
 '3056': 0.0005724098454493417,
 '6158': 0.0007632131272657889,
 '7307': 0.004960885327227628,
 '7324': 0.0007632131272657889,
 '8365': 0.0022896393817973667,
 '9023': 0.00019080328181644724,
 '11444': 0.0005724098454493417,
 '12324': 0.0009540164090822362,
 '12472': 0.0020988360999809196,
 '13831': 0.0030528525090631558,
 '14746': 0.004770082045411181,
 '16128': 0.0007632131272657889,
 '17075': 0.0036252623545124977,
 '18875': 0.0015264262545315779,
 '19900': 0.0007632131272657889,
 '20000': 0.0009540164090822362,
 '20806': 0.00038160656363289447,
 '21944': 0.0007632131272657889,
 '21968': 0.002480442663613814,
 '23302': 0.0005724098454493417,
 '23665': 0.0022896393817973667,
 '23758': 0.00038160656363289447,
 '24722': 0.0007632131272657889,
 '12045': 0.00019080328181644724,
 '12287': 0.0005724098454493417,
 '14181': 0.0019080328181644724,
 '20257': 0.0005724098454493417,
 '21613': 0.0005724098454493417,
 '7510': 0.00038160656363289447,
 '197': 0.00038160656363289447,
 '8851': 0.0020988360999809196,
 '1343': 0.0007632131272657889,
 '2991': 0.00038160656363289447,
 '8299': 0.00019080328181644724,
 '15416': 0.00038160656363289447,
 '18088': 0.0015264262545315779,
 '25286': 0.002480442663613814,
 '1254': 0.0005724098454493417,
 '3420': 0.0005724098454493417,
 '10130': 0.0028620492272467086,
 '2250': 0.003243655790879603,
 '3243': 0.0005724098454493417,
 '7717': 0.003243655790879603,
 '7985': 0.0028620492272467086,
 '11015': 0.004197672199961839,
 '12085': 0.001717229536348025,
 '13714': 0.003243655790879603,
 '14767': 0.003243655790879603,
 '16056': 0.0022896393817973667,
 '16994': 0.003816065636328945,
 '17414': 0.001717229536348025,
 '18971': 0.003243655790879603,
 '19216': 0.003243655790879603,
 '20534': 0.003243655790879603,
 '21776': 0.0009540164090822362,
 '21860': 0.0015264262545315779,
 '25205': 0.003243655790879603,
 '178': 0.0015264262545315779,
 '1248': 0.0005724098454493417,
 '1403': 0.0013356229727151307,
 '2368': 0.001717229536348025,
 '2420': 0.0009540164090822362,
 '16210': 0.002480442663613814,
 '18681': 0.0005724098454493417,
 '20641': 0.00038160656363289447,
 '24762': 0.0007632131272657889,
 '2307': 0.00038160656363289447,
 '6934': 0.0026712459454302615,
 '22423': 0.0030528525090631558,
 '231': 0.005724098454493417,
 '345': 0.002480442663613814,
 '1186': 0.003243655790879603,
 '1234': 0.0013356229727151307,
 '1841': 0.0011448196908986834,
 '1997': 0.0015264262545315779,
 '2404': 0.0015264262545315779,
 '2450': 0.00038160656363289447,
 '2980': 0.0045792787635947334,
 '3409': 0.0030528525090631558,
 '5134': 0.0013356229727151307,
 '5578': 0.0013356229727151307,
 '8503': 0.0026712459454302615,
 '9341': 0.0007632131272657889,
 '9889': 0.003816065636328945,
 '12503': 0.001717229536348025,
 '13060': 0.001717229536348025,
 '13597': 0.003243655790879603,
 '16611': 0.0011448196908986834,
 '18208': 0.0045792787635947334,
 '18543': 0.0015264262545315779,
 '18866': 0.008395344399923678,
 '22421': 0.0011448196908986834,
 '22937': 0.00343445907269605,
 '23363': 0.0019080328181644724,
 '23628': 0.0011448196908986834,
 '25053': 0.001717229536348025,
 '25251': 0.00038160656363289447,
 '2982': 0.0005724098454493417,
 '4036': 0.0005724098454493417,
 '4115': 0.0009540164090822362,
 '12938': 0.0015264262545315779,
 '13032': 0.00038160656363289447,
 '19215': 0.00038160656363289447,
 '21432': 0.00343445907269605,
 '22726': 0.0005724098454493417,
 '22834': 0.0011448196908986834,
 '22966': 0.0007632131272657889,
 '23511': 0.0007632131272657889,
 '25528': 0.0005724098454493417,
 '25836': 0.0015264262545315779,
 '14376': 0.00019080328181644724,
 '8710': 0.00038160656363289447,
 '22483': 0.0015264262545315779,
 '1375': 0.00038160656363289447,
 '2846': 0.0030528525090631558,
 '5555': 0.0015264262545315779,
 '5564': 0.0019080328181644724,
 '5787': 0.0015264262545315779,
 '9721': 0.00038160656363289447,
 '10158': 0.00019080328181644724,
 '10942': 0.0020988360999809196,
 '13600': 0.00038160656363289447,
 '13929': 0.008586147681740125,
 '21075': 0.0030528525090631558,
 '21316': 0.00019080328181644724,
 '22900': 0.00019080328181644724,
 '23637': 0.0019080328181644724,
 '23770': 0.0019080328181644724,
 '25143': 0.00038160656363289447,
 '25601': 0.00019080328181644724,
 '25980': 0.00038160656363289447,
 '17394': 0.00019080328181644724,
 '18924': 0.0015264262545315779,
 '3113': 0.003243655790879603,
 '8312': 0.0013356229727151307,
 '10765': 0.0011448196908986834,
 '17538': 0.0011448196908986834,
 '25978': 0.0011448196908986834,
 '1172': 0.0015264262545315779,
 '5674': 0.00019080328181644724,
 '26194': 0.00038160656363289447,
 '375': 0.00019080328181644724,
 '1838': 0.00038160656363289447,
 '12733': 0.0019080328181644724,
 '7188': 0.0022896393817973667,
 '896': 0.0009540164090822362,
 '921': 0.00038160656363289447,
 '1508': 0.0005724098454493417,
 '6815': 0.0005724098454493417,
 '7209': 0.0005724098454493417,
 '8279': 0.0009540164090822362,
 '13008': 0.0036252623545124977,
 '18605': 0.00019080328181644724,
 '21158': 0.0005724098454493417,
 '4632': 0.0022896393817973667,
 '7844': 0.002480442663613814,
 '11053': 0.0011448196908986834,
 '11148': 0.0019080328181644724,
 '13411': 0.0015264262545315779,
 '14512': 0.0026712459454302615,
 '16594': 0.0036252623545124977,
 '16722': 0.0013356229727151307,
 '16726': 0.0005724098454493417,
 '16876': 0.0013356229727151307,
 '19954': 0.0011448196908986834,
 '19992': 0.0028620492272467086,
 '20391': 0.0013356229727151307,
 '20774': 0.0028620492272467086,
 '23403': 0.0020988360999809196,
 '4870': 0.0005724098454493417,
 '5175': 0.0011448196908986834,
 '8282': 0.0005724098454493417,
 '22046': 0.0020988360999809196,
 '2449': 0.006487311581759206,
 '4766': 0.00038160656363289447,
 '3561': 0.001717229536348025,
 '4868': 0.0011448196908986834,
 '8352': 0.00038160656363289447,
 '10456': 0.001717229536348025,
 '15365': 0.0009540164090822362,
 '16931': 0.0015264262545315779,
 '8157': 0.00019080328181644724,
 '2120': 0.00019080328181644724,
 '7713': 0.00019080328181644724,
 '19052': 0.00019080328181644724,
 '8302': 0.00019080328181644724,
 '16484': 0.00019080328181644724,
 '17778': 0.0009540164090822362,
 '2556': 0.0020988360999809196,
 '19159': 0.0011448196908986834,
 '21699': 0.0005724098454493417,
 '25382': 0.0005724098454493417,
 '8701': 0.0019080328181644724,
 '523': 0.00038160656363289447,
 '5464': 0.0011448196908986834,
 '7774': 0.0007632131272657889,
 '17379': 0.0026712459454302615,
 '18008': 0.0007632131272657889,
 '23385': 0.00019080328181644724,
 '25868': 0.00019080328181644724,
 '26170': 0.00038160656363289447,
 '1310': 0.0020988360999809196,
 '2922': 0.0005724098454493417,
 '3651': 0.0066781148635756534,
 '6891': 0.0013356229727151307,
 '10162': 0.00038160656363289447,
 '10620': 0.0005724098454493417,
 '11112': 0.0007632131272657889,
 '13174': 0.0007632131272657889,
 '14864': 0.0019080328181644724,
 '17536': 0.0019080328181644724,
 '23153': 0.00038160656363289447,
 '24340': 0.0005724098454493417,
 '11102': 0.0009540164090822362,
 '18592': 0.0009540164090822362,
 '22765': 0.00038160656363289447,
 '1896': 0.0015264262545315779,
 '6838': 0.0013356229727151307,
 '25220': 0.00038160656363289447,
 '4180': 0.0011448196908986834,
 '10055': 0.003243655790879603,
 '12637': 0.0005724098454493417,
 '1832': 0.0005724098454493417,
 '4383': 0.00019080328181644724,
 '7014': 0.00038160656363289447,
 '9397': 0.004388475481778287,
 '14344': 0.0005724098454493417,
 '14385': 0.0005724098454493417,
 '21379': 0.004197672199961839,
 '24163': 0.00038160656363289447,
 '4416': 0.0036252623545124977,
 '9241': 0.002480442663613814,
 '2620': 0.0015264262545315779,
 '3679': 0.0005724098454493417,
 '4364': 0.006296508299942759,
 '5712': 0.0026712459454302615,
 '13955': 0.0022896393817973667,
 '14003': 0.0011448196908986834,
 '15235': 0.0015264262545315779,
 '18227': 0.0007632131272657889,
 '19445': 0.00019080328181644724,
 '19495': 0.00019080328181644724,
 '20168': 0.0019080328181644724,
 '23967': 0.0028620492272467086,
 '1116': 0.001717229536348025,
 '15399': 0.0005724098454493417,
 '18222': 0.0007632131272657889,
 '21287': 0.0015264262545315779,
 '23227': 0.00019080328181644724,
 '4624': 0.0022896393817973667,
 '5355': 0.00038160656363289447,
 '6863': 0.00038160656363289447,
 '12606': 0.0013356229727151307,
 '12968': 0.0019080328181644724,
 '15770': 0.0009540164090822362,
 '21322': 0.00019080328181644724,
 '22265': 0.0020988360999809196,
 '22336': 0.0020988360999809196,
 '23099': 0.00038160656363289447,
 '23880': 0.0013356229727151307,
 '25111': 0.0009540164090822362,
 '4319': 0.0005724098454493417,
 '12758': 0.0005724098454493417,
 '22023': 0.00019080328181644724,
 '14337': 0.001717229536348025,
 '5849': 0.0005724098454493417,
 '10763': 0.00019080328181644724,
 '11121': 0.00019080328181644724,
 '11194': 0.0011448196908986834,
 '15799': 0.001717229536348025,
 '16511': 0.0007632131272657889,
 '16575': 0.0011448196908986834,
 '16945': 0.00019080328181644724,
 '21157': 0.00019080328181644724,
 '2326': 0.0013356229727151307,
 '10253': 0.00038160656363289447,
 '13190': 0.0020988360999809196,
 '14325': 0.00038160656363289447,
 '19048': 0.0022896393817973667,
 '20182': 0.0013356229727151307,
 '3595': 0.0007632131272657889,
 '18174': 0.0007632131272657889,
 '17850': 0.00019080328181644724,
 '20620': 0.00019080328181644724,
 '12380': 0.0005724098454493417,
 '3197': 0.0005724098454493417,
 '6160': 0.0005724098454493417,
 '8589': 0.0013356229727151307,
 '9417': 0.00038160656363289447,
 '9829': 0.0028620492272467086,
 '14638': 0.0009540164090822362,
 '14924': 0.004388475481778287,
 '15972': 0.00019080328181644724,
 '17228': 0.0022896393817973667,
 '18940': 0.0028620492272467086,
 '19090': 0.0005724098454493417,
 '19475': 0.0005724098454493417,
 '20207': 0.0019080328181644724,
 '22644': 0.0022896393817973667,
 '22790': 0.0015264262545315779,
 '24001': 0.0011448196908986834,
 '25228': 0.0009540164090822362,
 '9710': 0.003816065636328945,
 '3345': 0.0028620492272467086,
 '3430': 0.0009540164090822362,
 '5266': 0.0011448196908986834,
 '5995': 0.0005724098454493417,
 '7999': 0.00019080328181644724,
 '8047': 0.00038160656363289447,
 '8178': 0.00038160656363289447,
 '8868': 0.00019080328181644724,
 '10824': 0.00038160656363289447,
 '15144': 0.002480442663613814,
 '19107': 0.0011448196908986834,
 '19806': 0.00038160656363289447,
 '22439': 0.0005724098454493417,
 '23304': 0.00019080328181644724,
 '24431': 0.0015264262545315779,
 '11077': 0.0026712459454302615,
 '10211': 0.0019080328181644724,
 '14972': 0.0005724098454493417,
 '15300': 0.0036252623545124977,
 '17158': 0.0005724098454493417,
 '17162': 0.00038160656363289447,
 '17403': 0.0007632131272657889,
 '20149': 0.00038160656363289447,
 '20519': 0.0005724098454493417,
 '21389': 0.0009540164090822362,
 '22951': 0.0015264262545315779,
 '23912': 0.0005724098454493417,
 '23918': 0.0007632131272657889,
 '25589': 0.0005724098454493417,
 '6895': 0.00019080328181644724,
 '3076': 0.0007632131272657889,
 '7444': 0.005342491890860523,
 '8972': 0.0007632131272657889,
 '17308': 0.00038160656363289447,
 '20574': 0.007059721427208548,
 '21629': 0.0013356229727151307,
 '245': 0.00038160656363289447,
 '4983': 0.00038160656363289447,
 '13480': 0.0011448196908986834,
 '14562': 0.00019080328181644724,
 '15912': 0.00038160656363289447,
 '16976': 0.0020988360999809196,
 '19974': 0.0007632131272657889,
 '22245': 0.00019080328181644724,
 '414': 0.00019080328181644724,
 '8708': 0.00019080328181644724,
 '23776': 0.00019080328181644724,
 '1044': 0.0015264262545315779,
 '4975': 0.0009540164090822362,
 '5809': 0.00038160656363289447,
 '12587': 0.0028620492272467086,
 '16123': 0.0009540164090822362,
 '20303': 0.0019080328181644724,
 '4451': 0.00038160656363289447,
 '9983': 0.00019080328181644724,
 '15205': 0.0007632131272657889,
 '15666': 0.0005724098454493417,
 '15667': 0.0005724098454493417,
 '19093': 0.0009540164090822362,
 '21031': 0.00038160656363289447,
 '24330': 0.003816065636328945,
 '5840': 0.00038160656363289447,
 '6732': 0.0013356229727151307,
 '8614': 0.00019080328181644724,
 '13847': 0.0013356229727151307,
 '15081': 0.0007632131272657889,
 '22609': 0.0005724098454493417,
 '3310': 0.0030528525090631558,
 '5143': 0.00038160656363289447,
 '9735': 0.0007632131272657889,
 '17396': 0.00019080328181644724,
 '26138': 0.00038160656363289447,
 '4700': 0.00038160656363289447,
 '5606': 0.00038160656363289447,
 '1386': 0.0005724098454493417,
 '1738': 0.0005724098454493417,
 '2566': 0.0005724098454493417,
 '2720': 0.0005724098454493417,
 '5634': 0.00038160656363289447,
 '9870': 0.0005724098454493417,
 '16779': 0.00038160656363289447,
 '24475': 0.0005724098454493417,
 '25931': 0.0019080328181644724,
 '1817': 0.0009540164090822362,
 '3725': 0.0007632131272657889,
 '5366': 0.00038160656363289447,
 '15911': 0.0007632131272657889,
 '9800': 0.001717229536348025,
 '26141': 0.0007632131272657889,
 '18001': 0.00038160656363289447,
 '22177': 0.0040068689181453915,
 '25480': 0.0013356229727151307,
 '1425': 0.001717229536348025,
 '2501': 0.0019080328181644724,
 '2823': 0.0007632131272657889,
 '5136': 0.00038160656363289447,
 '7105': 0.0009540164090822362,
 '7317': 0.0013356229727151307,
 '9127': 0.0007632131272657889,
 '14615': 0.0019080328181644724,
 '17089': 0.0011448196908986834,
 '19454': 0.0005724098454493417,
 '22758': 0.0020988360999809196,
 '23841': 0.0019080328181644724,
 '3207': 0.00019080328181644724,
 '7125': 0.0019080328181644724,
 '20683': 0.0013356229727151307,
 '25419': 0.0009540164090822362,
 '2591': 0.0011448196908986834,
 '8932': 0.00019080328181644724,
 '9188': 0.0005724098454493417,
 '9773': 0.00038160656363289447,
 '13713': 0.00038160656363289447,
 '19179': 0.0013356229727151307,
 '14818': 0.0009540164090822362,
 '26190': 0.0009540164090822362,
 '3839': 0.0028620492272467086,
 '13615': 0.0005724098454493417,
 '16674': 0.002480442663613814,
 '7042': 0.0007632131272657889,
 '9269': 0.00038160656363289447,
 '11661': 0.0015264262545315779,
 '21994': 0.003243655790879603,
 '9943': 0.0020988360999809196,
 '10096': 0.00343445907269605,
 '15614': 0.0013356229727151307,
 '16368': 0.0020988360999809196,
 '17285': 0.0011448196908986834,
 '21407': 0.0011448196908986834,
 '8715': 0.0007632131272657889,
 '21142': 0.00038160656363289447,
 '21167': 0.00038160656363289447,
 '13621': 0.00019080328181644724,
 '25388': 0.00019080328181644724,
 '284': 0.00019080328181644724,
 '6427': 0.0011448196908986834,
 '16835': 0.00038160656363289447,
 '18677': 0.00038160656363289447,
 '21696': 0.00038160656363289447,
 '25854': 0.00038160656363289447,
 '25940': 0.00038160656363289447,
 '9485': 0.00038160656363289447,
 '10435': 0.0005724098454493417,
 '14698': 0.00019080328181644724,
 '21823': 0.0005724098454493417,
 '811': 0.001717229536348025,
 '9964': 0.0007632131272657889,
 '11919': 0.0007632131272657889,
 '15123': 0.0005724098454493417,
 '17021': 0.00038160656363289447,
 '19517': 0.0015264262545315779,
 '22989': 0.0009540164090822362,
 '23485': 0.0011448196908986834,
 '8069': 0.00038160656363289447,
 '2127': 0.00019080328181644724,
 '11712': 0.0022896393817973667,
 '10871': 0.0026712459454302615,
 '15829': 0.0007632131272657889,
 '16106': 0.0007632131272657889,
 '17207': 0.0019080328181644724,
 '17670': 0.0007632131272657889,
 '18286': 0.0013356229727151307,
 '18612': 0.0007632131272657889,
 '19234': 0.00019080328181644724,
 '19724': 0.0005724098454493417,
 '22876': 0.002480442663613814,
 '3412': 0.0005724098454493417,
 '894': 0.0009540164090822362,
 '4814': 0.0019080328181644724,
 '5441': 0.0015264262545315779,
 '5717': 0.001717229536348025,
 '5934': 0.003243655790879603,
 '9075': 0.00038160656363289447,
 '10623': 0.0011448196908986834,
 '11223': 0.0007632131272657889,
 '11491': 0.0005724098454493417,
 '12659': 0.001717229536348025,
 '14351': 0.001717229536348025,
 '19807': 0.00038160656363289447,
 '21324': 0.0009540164090822362,
 '21665': 0.0007632131272657889,
 '22734': 0.0005724098454493417,
 '22778': 0.0019080328181644724,
 '23246': 0.0011448196908986834,
 '25698': 0.002480442663613814,
 '7615': 0.0013356229727151307,
 '12806': 0.0011448196908986834,
 '1620': 0.0013356229727151307,
 '3922': 0.0019080328181644724,
 '9133': 0.00019080328181644724,
 '9895': 0.00019080328181644724,
 '9907': 0.0019080328181644724,
 '11791': 0.0005724098454493417,
 '18457': 0.00019080328181644724,
 '19131': 0.00019080328181644724,
 '19997': 0.00019080328181644724,
 '21491': 0.003816065636328945,
 '22426': 0.0011448196908986834,
 '22791': 0.00038160656363289447,
 '25158': 0.0005724098454493417,
 '25316': 0.0011448196908986834,
 '352': 0.0005724098454493417,
 '3996': 0.0009540164090822362,
 '10555': 0.0011448196908986834,
 '15850': 0.0009540164090822362,
 '19101': 0.0009540164090822362,
 '20533': 0.0005724098454493417,
 '21943': 0.002480442663613814,
 '22603': 0.00038160656363289447,
 '23513': 0.0007632131272657889,
 '25034': 0.0036252623545124977,
 '1280': 0.0005724098454493417,
 '5851': 0.0005724098454493417,
 '11591': 0.0015264262545315779,
 '13520': 0.0030528525090631558,
 '16921': 0.0022896393817973667,
 '21646': 0.001717229536348025,
 '17559': 0.002480442663613814,
 '1674': 0.0011448196908986834,
 '3323': 0.0009540164090822362,
 '8680': 0.0009540164090822362,
 '9184': 0.0040068689181453915,
 '13813': 0.002480442663613814,
 '19204': 0.0020988360999809196,
 '19206': 0.0005724098454493417,
 '19657': 0.0019080328181644724,
 '20373': 0.004770082045411181,
 '23204': 0.0022896393817973667,
 '409': 0.0005724098454493417,
 '2474': 0.0005724098454493417,
 '4241': 0.00343445907269605,
 '6746': 0.0005724098454493417,
 '10476': 0.0007632131272657889,
 '16568': 0.0007632131272657889,
 '21771': 0.0013356229727151307,
 '24620': 0.0005724098454493417,
 '2081': 0.00019080328181644724,
 '2664': 0.00019080328181644724,
 '12212': 0.0028620492272467086,
 '13528': 0.00038160656363289447,
 '14628': 0.00038160656363289447,
 '22574': 0.001717229536348025,
 ...}

Tarea 2.3

Trace un histograma de centralidad de grado y grado de author_graph.

Sugerencia: plt.hist(list_of_values) trazará un histograma

(count vs centralidad grado)

Repita el ejercicio para todas las métricas de centralidad vistas en este notebook.

Interprte sus resultados.

Echemos un vistazo a los componentes conectados de un grafo.

En la teoría de grafos, un componente conectado (o simplemente un componente) de un grafo no dirigido es un subgrafo en el que dos vértices cualesquiera están conectados entre sí por caminos, y que no está conectado a ningún vértice adicional en el supergrafo.

G = nx.erdos_renyi_graph(n=10, p=0.15, seed=1)
nx.draw(G, with_labels=True)

print([len(c) for c in sorted(nx.connected_components(authors_graph),
                              key=len, reverse=True)])

[4158, 14, 12, 10, 9, 9, 8, 8, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1]

Nota: la función sorted () tiene un parámetro opcional llamado key que toma una función como su valor. Esta función key transforma cada elemento antes de ordenar, toma el valor y se usa dentro de sorted en lugar del valor original.

# Guardamos subgrafos en una lista
graphs = [authors_graph.subgraph(c).copy() for c in sorted(nx.connected_components(authors_graph), key=len, reverse=True)]

len(graphs[0])

Camino más corto de la red

print(nx.shortest_path(graphs[0], '22504', '23991'))#camino entre a y b.

print(len(nx.shortest_path(graphs[0], '22504', '23991')))#distancia en nodos (incluye ppio y fin)
print(nx.shortest_path_length(graphs[0], '22504', '23991'))#distancia en enlaces (#nodos-1)

['22504', '6512', '18757', '2710', '3677', '23991']
6
5

# help(nx.shortest_path)

Plot redes con nodos de distinto tamaño

g = graphs[1]# ejemplo
pos=pos = nx.spring_layout(g) # Layout para la red (coordenadas de los nodos y enlaces)

nx.draw(g,pos)

#Codigo para el tamaño del nodo
# g = graphs[0]# ejemplo
# pos=pos = nx.spring_layout(g) # Layout para la red (coordenadas de los nodos y enlaces)


degree_g = dict(nx.degree(g))
clustering_g=dict(nx.clustering(g))

nx.draw(g,pos, nodelist=degree_g.keys(), node_size=[v*100 for v in degree_g.values()])
plt.show()


nx.draw(g, pos,nodelist=clustering_g.keys(), node_size=[v *1000 for v in clustering_g.values()])
plt.show()

# nx.draw(g,pos, nodelist=list(degree_g.keys()), node_size=[v**(1/2) for v in degree_g.values()])
# plt.show()

Grado de nodo vs coeficiente de clustering

degree_g = dict(nx.degree(graphs[0]))
clustering_g=dict(nx.clustering(graphs[0]))

x = degree_g.values()
y = clustering_g.values()


# colors = np.random.rand(N)
# area = (30 * np.random.rand(N))**2  # 0 to 15 point radii

plt.scatter(x, y, alpha=0.5)
plt.show()

MUNDO PEQUEÑO

Seis grados de separación, número de Erdos, número de Bacon !!

https://oracleofbacon.org

https://www.csauthors.net/

Tarea 2.4

Encuentre el “número” del autor ‘22504’ del grafo author_graph, si no hay conexión entre los nodos, asignele el número ‘-1’. También trace un histograma del “número” autor ‘22504’.

Encuentre la longitud de ruta más corta promedio en el primer componente, es decir, graphs[0]

SUGERENCIA: nx.shortest_path_length

Interprete sus resultados

d = {}
for node in authors_graph.nodes():#para cada nodo
    try:
        #calcula la longitud del camino mas corto entre node y `22504`
        d[node] = nx.shortest_path_length(graphs[0], '22504', node) #21012;22504
    except:
        #si arroja error (no hay camino) asinga un -1.
        next

# d

plt.hist(list(d.values()))
plt.show()

# Calcule el promedio de la longitud de los caminos más cortos de todo el grafo aca:

np.mean(list(d.values()))

5.61014911014911

Cambiemos de tema y hablemos de Juego de tronos (Network of Thrones)

¿Es sorprendente verdad? ¿Cuál es la relación entre un programa de televisión / novela de fatansia y la ciencia de redes o Python?

Si no has oído hablar de Game of Thrones, entonces debes ser muy bueno para aislarte. Game of Thrones es la popular serie de televisión de HBO basada en la (también) popular serie de libros “A Song of Ice and Fire” de George R.R. Martin.

Ahora, analizaremos la red de co-ocurrencia de los personajes en los libros de Juego de Tronos. Aquí, se considera que dos personajes coexisten si sus nombres aparecen en hasta a 15 palabras de distancia entre sí en los libros.

# !conda install --yes --prefix {sys.prefix} community # 

# # !conda install --yes --prefix {sys.prefix} python-louvain # 

# !pip install python-louvain

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
from matplotlib import cm
# import community
from community import community_louvain
import numpy as np


%matplotlib inline

Cargamos los datasets

book1 = pd.read_csv('data/asoiaf-book1-edges.csv')
book2 = pd.read_csv('data/asoiaf-book2-edges.csv')
book3 = pd.read_csv('data/asoiaf-book3-edges.csv')
book4 = pd.read_csv('data/asoiaf-book4-edges.csv')
book5 = pd.read_csv('data/asoiaf-book5-edges.csv')

El DataFrame resultante book1 tiene 5 columnas: origen, destino, tipo, peso y libro. El origen y el destino son los dos nodos que están vinculados por un enlace. Una red puede tener enlaces dirigidos o no dirigidos y en esta red todos los enlaces no están dirigidos. El atributo de peso de cada enlace nos dice el número de interacciones que los personajes han tenido sobre el libro, y la columna del libro nos dice el número del libro.

# book1.head()
book1.sort_values('weight',ascending=False).head()

	Source	Target	Type	weight	book
329	Eddard-Stark	Robert-Baratheon	Undirected	291	1
134	Bran-Stark	Robb-Stark	Undirected	112	1
62	Arya-Stark	Sansa-Stark	Undirected	104	1
249	Daenerys-Targaryen	Drogo	Undirected	101	1
479	Joffrey-Baratheon	Sansa-Stark	Undirected	87	1

Una vez que tenemos los datos cargados como un DataFrame de pandas, es hora de crear una red. Creamos un grafo para cada libro. Es posible crear un MultiGraph en lugar de 5 grafos, pero es más fácil jugar con diferentes gráficos.

G_book1 = nx.Graph()
G_book2 = nx.Graph()
G_book3 = nx.Graph()
G_book4 = nx.Graph()
G_book5 = nx.Graph()

Completemos el grafo con los enlaces del DataFrame de pandas.

for row in book1.iterrows(): #Itera las filas de DataFrame como pares (index, series).
    G_book1.add_edge(row[1]['Source'], row[1]['Target'],weight=row[1]['weight'], book=row[1]['book'])

for row in book2.iterrows():
    G_book2.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
for row in book3.iterrows():
    G_book3.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
for row in book4.iterrows():
    G_book4.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])
for row in book5.iterrows():
    G_book5.add_edge(row[1]['Source'], row[1]['Target'], weight=row[1]['weight'], book=row[1]['book'])

books = [G_book1, G_book2, G_book3, G_book4, G_book5]

Echemos un vistazo a estos enlaces

list(G_book1.edges(data=True))[16]#data=True muestra los atributos del enlace: peso y libro en este caso

('Jaime-Lannister', 'Loras-Tyrell', {'weight': 3, 'book': 1})

list(G_book1.edges(data=True))[400]

('Benjen-Stark', 'Theon-Greyjoy', {'weight': 4, 'book': 1})

len(list(G_book1.edges()))

print(G_book1.number_of_edges())
print(G_book1.number_of_nodes())

684
187

Encontrar el nodo/personaje más importante en estas redes.

¿Es Jon Snow, Tyrion, Daenerys o alguien más? ¡Vamos a ver! Network Science nos ofrece muchas métricas diferentes para medir la importancia de un nodo en una red como vimos en la primera parte del taller.

Tenga en cuenta que no existe una forma “correcta” de calcular el nodo más importante de una red, cada métrica tiene un significado diferente.

Primero, midamos la importancia de un nodo en una red observando la cantidad de vecinos que tiene, es decir, la cantidad de nodos a los que está conectado. Por ejemplo, una cuenta influyente en Twitter, donde la relación seguidor-seguidor forma la red, es una cuenta que tiene un alto número de seguidores. Esta medida de importancia se llama centralidad de grado.

Usando esta medida, extraigamos los diez personajes más importantes del primer libro (libro [0]) y el quinto libro (libro [4]).

deg_cen_book1 = nx.degree_centrality(books[0])

deg_cen_book5 = nx.degree_centrality(books[4])

sorted(deg_cen_book1.items(), key=lambda x:x[1], reverse=True)[0:10]

[('Eddard-Stark', 0.3548387096774194),
 ('Robert-Baratheon', 0.2688172043010753),
 ('Tyrion-Lannister', 0.24731182795698928),
 ('Catelyn-Stark', 0.23118279569892475),
 ('Jon-Snow', 0.19892473118279572),
 ('Robb-Stark', 0.18817204301075272),
 ('Sansa-Stark', 0.18817204301075272),
 ('Bran-Stark', 0.17204301075268819),
 ('Cersei-Lannister', 0.16129032258064518),
 ('Joffrey-Baratheon', 0.16129032258064518)]

sorted(deg_cen_book5.items(), key=lambda x:x[1], reverse=True)[0:10]
#key recive la funcion para ordenar, lambda es la funcion "al vuelo" para ordenar

[('Jon-Snow', 0.1962025316455696),
 ('Daenerys-Targaryen', 0.18354430379746836),
 ('Stannis-Baratheon', 0.14873417721518986),
 ('Tyrion-Lannister', 0.10443037974683544),
 ('Theon-Greyjoy', 0.10443037974683544),
 ('Cersei-Lannister', 0.08860759493670886),
 ('Barristan-Selmy', 0.07911392405063292),
 ('Hizdahr-zo-Loraq', 0.06962025316455696),
 ('Asha-Greyjoy', 0.056962025316455694),
 ('Melisandre', 0.05379746835443038)]

# Plot a histogram of degree centrality
plt.hist(list(dict(nx.degree(G_book1)).values()))

plt.show()

d= {}
for i, j in dict(nx.degree(G_book1)).items():
    if j in d:
        d[j] += 1
    else:
        d[j] = 1
x = list((d.keys()))
y = list(d.values())
plt.scatter(x, y, alpha=0.9)
plt.show()

d = {}
for i, j in dict(nx.degree(G_book1)).items():
    if j in d:
        d[j] += 1
    else:
        d[j] = 1
x = np.log10(list((d.keys())))
y = np.log10(list(d.values()))
plt.scatter(x, y, alpha=0.9)
plt.show()

Tarea 2.5

Cree una nueva medida de centralidad, weighted_degree(Graph, weight) que toma Graph y el atributo de peso y devuelve un diccionario de grados ponderados. El grado ponderado se calcula sumando el peso de todos los enlaces de un nodo. Luego, encuentre los cinco personajes más importantes de acuerdo con esta medida.

Interprete sus resultados con respecto a lo obtenido usando degree (sin peso)

#Escriba su código acá (siempre pueden agregar más líneas de ser necesario):

weighted_degree= lindo código!
# print(list(nx.neighbors(G_book1,'Eddard-Stark')))

# plt.hist(list(weighted_degree(G_book1, 'weight').values()))
# plt.show()

d = {}
for i, j in dict(nx.degree(G_book1)).items():
#     print(i,j)
    if j in d:
        d[j] += 1 #cuenta la cantidad de veces que el mismo grado "ocurre"
    else:
        d[j] = 1
x = np.log2(list((d.keys())))
y = np.log2(list(d.values()))
plt.scatter(x, y, alpha=0.9)
plt.show()

# sorted(weighted_degree(G_book1, 'weight').items(), key=lambda x:x[1], reverse=True)[0:5]

Hagamos esto para la centralidad de Betweenness y verifiquemos si esto hace alguna diferencia

G = nx.barbell_graph(5, 1) #Recordemos: El nodo del centro es el de mayor betweennes
nx.draw(G)

# Primero verifique el grafo no ponderado, solo la estructura

sorted(nx.betweenness_centrality(G_book1).items(), key=lambda x:x[1], reverse=True)[0:10]

[('Eddard-Stark', 0.2696038913836117),
 ('Robert-Baratheon', 0.21403028397371796),
 ('Tyrion-Lannister', 0.1902124972697492),
 ('Jon-Snow', 0.17158135899829566),
 ('Catelyn-Stark', 0.1513952715347627),
 ('Daenerys-Targaryen', 0.08627015537511595),
 ('Robb-Stark', 0.07298399629664767),
 ('Drogo', 0.06481224290874964),
 ('Bran-Stark', 0.05579958811784442),
 ('Sansa-Stark', 0.03714483664326785)]

# Consideremos el peso ahora

sorted(nx.betweenness_centrality(G_book1, weight='weight').items(), key=lambda x:x[1], reverse=True)[0:10]

[('Robert-Baratheon', 0.23341885664466297),
 ('Eddard-Stark', 0.18703429235687297),
 ('Tyrion-Lannister', 0.15311225972516293),
 ('Robb-Stark', 0.1024018949825402),
 ('Catelyn-Stark', 0.10169012330302643),
 ('Jon-Snow', 0.09027684366394043),
 ('Jaime-Lannister', 0.07745109164464009),
 ('Rodrik-Cassel', 0.07667992877670296),
 ('Drogo', 0.06894355184677767),
 ('Jorah-Mormont', 0.0627085149665795)]

# por defecto, el atributo de peso en el pagerank es `weight`,
# por lo que usamos `peso = None` para encontrar los resultados no ponderados
sorted(nx.pagerank(G_book1, weight=None).items(), key=lambda x:x[1], reverse=True)[0:10]

[('Eddard-Stark', 0.04550213151218522),
 ('Tyrion-Lannister', 0.03301449867019286),
 ('Catelyn-Stark', 0.030189729639356143),
 ('Robert-Baratheon', 0.02982527420823678),
 ('Jon-Snow', 0.026840579868198603),
 ('Robb-Stark', 0.02155918676623074),
 ('Sansa-Stark', 0.019998050283349653),
 ('Bran-Stark', 0.019940543257472354),
 ('Jaime-Lannister', 0.017500555351025744),
 ('Cersei-Lannister', 0.017074603349338583)]

sorted(nx.pagerank(G_book1, weight='weight').items(), key=lambda x:x[1], reverse=True)[0:10]

[('Eddard-Stark', 0.07236162026570049),
 ('Robert-Baratheon', 0.04849367196106829),
 ('Jon-Snow', 0.04770801150205558),
 ('Tyrion-Lannister', 0.04367631315626212),
 ('Catelyn-Stark', 0.034666613211363564),
 ('Bran-Stark', 0.02977004993932226),
 ('Robb-Stark', 0.029214217154195955),
 ('Daenerys-Targaryen', 0.027098612952214246),
 ('Sansa-Stark', 0.02694466267974004),
 ('Cersei-Lannister', 0.02162037092438613)]

Tarea 2.6

¿Existe una correlación entre estas métricas para todos los libros?

Encuentre la correlación entre estas cuatro métricas de centralidad.

Eigenvector Centrality (PageRank, no apto para redes no-dirigidas).
betweenness_centrality
weighted_degree
centralidad de grado

Inteprete sus resultados en función de como se relacionan las métricas, ej. Alto Eigenvector y bajo Betweenness Centrality, etc.

cor = pd.DataFrame.from_records(
    [nx.pagerank_numpy(G_book1, weight='weight'),
     nx.betweenness_centrality(G_book1, weight='weight'),
#      weighted_degree(G_book1, 'weight'),
     nx.degree_centrality(G_book1)])

/var/folders/q8/5g879lls62l1z8smyjkh4h700000gn/T/ipykernel_50635/2590846740.py:2: DeprecationWarning: networkx.pagerank_numpy is deprecated and will be removed in NetworkX 3.0, use networkx.pagerank instead.
  [nx.pagerank_numpy(G_book1, weight='weight'),

cor.T.corr()

	0	1	2
0	1.000000	0.870214	0.949307
1	0.870214	1.000000	0.871385
2	0.949307	0.871385	1.000000

Evolución de la importancia de los personajes sobre los libros

Según la centralidad de grado, el personaje más importante del primer libro es Eddard Stark, pero ni siquiera está en el top 10 del quinto libro. La importancia cambia en el transcurso de cinco libros (hay muchas muertes :B)

Veamos la evolución de la centralidad de grado de un par de personajes como Eddard Stark, Jon Snow, Tyrion, que aparecieron en el top 10 de centralidad de grado en el primer libro.

Creamos un DataFrame con columnas de personajes y los libros como índices donde cada entrada es la centralidad de grado del personaje en ese libro en particular y trazamos la evolución de la centralidad de grado para Eddard Stark, Jon Snow y Tyrion.

Podemos ver que la importancia de Eddard Stark en la red diminuye y con Jon Snow hay una caída en el cuarto libro pero un aumento repentino en el quinto libro.

evol = [nx.degree_centrality(book) for book in books]#para cada red calcula el grado de nodo

evol_df = pd.DataFrame.from_records(evol).fillna(0)#Crea un objeto DataFrame a partir de un ndarray estructurado, una secuencia de tuplas o diccionarios, o un DataFrame.
evol_df

	Addam-Marbrand	Jaime-Lannister	Tywin-Lannister	Aegon-I-Targaryen	Daenerys-Targaryen	Eddard-Stark	Aemon-Targaryen-(Maester-Aemon)	Alliser-Thorne	Bowen-Marsh	Chett	...	Yellow-Dick	Walda-Frey-(daughter-of-Merrett)	Roose-Ryswell	Scar	Shrouded-Lord	Theomore	William-Foxglove	Willow-Witch-eye	Thistle	Wulfe
0	0.010753	0.155914	0.118280	0.010753	0.112903	0.354839	0.037634	0.053763	0.026882	0.016129	...	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
1	0.000000	0.081395	0.065891	0.019380	0.069767	0.085271	0.023256	0.015504	0.000000	0.003876	...	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
2	0.026490	0.149007	0.096026	0.009934	0.079470	0.052980	0.059603	0.023179	0.033113	0.016556	...	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
3	0.014652	0.234432	0.058608	0.000000	0.000000	0.029304	0.025641	0.000000	0.000000	0.000000	...	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000	0.000000
4	0.000000	0.031646	0.028481	0.003165	0.183544	0.044304	0.015823	0.003165	0.028481	0.000000	...	0.009494	0.006329	0.003165	0.006329	0.003165	0.006329	0.003165	0.003165	0.003165	0.003165

5 rows × 796 columns

evol_df[['Eddard-Stark', 'Tyrion-Lannister', 'Jon-Snow','Daenerys-Targaryen']].plot()



#Nota: Los corchetes interiores son para la lista y los corchetes externos son operadores de indexación, es decir, 
#debe usar corchetes dobles si seleccionas dos o más columnas. Con un nombre de columna, un solo par de corchetes 
#devuelve una Series, mientras que los corchetes dobles devuelven un dataframe.

<AxesSubplot:>

evol_df['Eddard-Stark']#, 'Tyrion-Lannister', 'Jon-Snow']

0    0.354839
1    0.085271
2    0.052980
3    0.029304
4    0.044304
Name: Eddard-Stark, dtype: float64

# Buscamos a los 3 personajes mas importantes de cada libro y creamos un arreglo con sus nombres.
set_of_char = set()
for i in range(5):
    set_of_char |= set(list(evol_df.T[i].sort_values(ascending=False)[0:3].index))# `|=` hace una unión de conjuntos y reasigna (junta los 5 libros)
#     print(set_of_char)
set_of_char

# VER: https://stackoverflow.com/questions/3929278/what-does-ior-do-in-python

{'Brienne-of-Tarth',
 'Cersei-Lannister',
 'Daenerys-Targaryen',
 'Eddard-Stark',
 'Jaime-Lannister',
 'Joffrey-Baratheon',
 'Jon-Snow',
 'Robert-Baratheon',
 'Stannis-Baratheon',
 'Tyrion-Lannister'}

Ejercicio resuelto

Trace la evolución de la centralidad de grado ponderado de los personajes antes mencionados sobre los 5 libros y repita el mismo ejercicio para la centralidad de intermediación.

evol_df[list(set_of_char)].plot(figsize=(19,10))
plt.xlabel('Capitulo de libro')
plt.ylabel('Centralidad de grado')

Text(0, 0.5, 'Centralidad de grado')

evol = [nx.betweenness_centrality(graph, weight='weight') for graph in [G_book1, G_book2, G_book3, G_book4, G_book5]]
evol_df = pd.DataFrame.from_records(evol).fillna(0)



set_of_char = set()
for i in range(5):
    set_of_char |= set(list(evol_df.T[i].sort_values(ascending=False)[0:3].index))


evol_df[list(set_of_char)].plot(figsize=(19,10))

plt.ylabel('Betweenness Centrality')
plt.xlabel('Capitulo de libro')

Text(0.5, 0, 'Capitulo de libro')

Entonces, ¿qué pasa con Stannis Baratheon?

nx.draw(nx.barbell_graph(5, 1), with_labels=True)

sorted(nx.degree_centrality(G_book5).items(), key=lambda x:x[1], reverse=True)[:5]#ordena por centralidad (con 0 ordena por el nombre)

[('Jon-Snow', 0.1962025316455696),
 ('Daenerys-Targaryen', 0.18354430379746836),
 ('Stannis-Baratheon', 0.14873417721518986),
 ('Tyrion-Lannister', 0.10443037974683544),
 ('Theon-Greyjoy', 0.10443037974683544)]

sorted(nx.betweenness_centrality(G_book5).items(), key=lambda x:x[1], reverse=True)[:5]

[('Stannis-Baratheon', 0.45283060689247934),
 ('Daenerys-Targaryen', 0.2959459062106149),
 ('Jon-Snow', 0.24484873673158666),
 ('Tyrion-Lannister', 0.20961613179551256),
 ('Robert-Baratheon', 0.17716906651536968)]

Detección de comunidad en redes (Spoiler)

Se dice que una red tiene una estructura de comunidades si los nodos de la red se pueden agrupar “fácilmente” en conjuntos de nodos (potencialmente superpuestos) de modo que cada conjunto de nodos esté densamente conectado internamente (dentro de cada comunidad).

Usaremos el algoritmo de detección de la comunidad de Louvain para encontrar los módulos en nuestro grafo.

def draw_communities(G, partition, pos, n_labels=10):
    """Dibuja el grafo G con una coloración de los nodos de acuerdo a la partición de la comunidad proporcionada.
    
    Parámetros:
    - G: un objeto networkx.Graph
    - partition: un diccionario mapeando nombres de nodos a etiquetas de comunidad
    - pos: un diccionario mapeando nombres de nodos a posiciones en el espacio 2D
    - n_labels: la cantidad de nodos con el grado más alto para los que se mostrarán las etiquetas
    """

    # Creamos un mapa de colores
    cmap = cm.get_cmap('viridis', max(partition.values()) + 1)

    # Dibujamos los nodos, coloreándolos por su comunidad y ajustando su tamaño por su grado
    nx.draw_networkx_nodes(G, pos, node_color=[cmap(partition[n]) for n in G.nodes()], 
                           node_size=[G.degree(n) * 100 for n in G.nodes()])

    # Dibujamos las aristas
    nx.draw_networkx_edges(G, pos, alpha=0.2)

    # Seleccionamos los n_labels nodos de mayor grado para etiquetar
    degree_dict = dict(G.degree(G.nodes()))
    highest_degree_nodes = sorted(degree_dict.items(), key=lambda item: item[1], reverse=True)[:n_labels]
    labels = {node[0]:node[0] for node in highest_degree_nodes}

    # Ajustamos las posiciones de las etiquetas
    label_pos = {node: (pos[node][0], pos[node][1] + 0.04) for node in labels}  # Movemos las etiquetas un poco hacia arriba
    nx.draw_networkx_labels(G, label_pos, labels=labels)


    # nx.draw_networkx_labels(G, pos, labels=labels)

    plt.show()

def community_layout(g, partition):
    """
    Calcule el diseño para una red modular. Esto mejora la separación de las comunidades.
    """

    # Crear un nuevo gráfico que esté ponderado en función de la comunidad (partición)
    inter_community_edges = [(u, v) for u, v in g.edges() if partition[u] != partition[v]]
    
    # Ponderamos las aristas inter-comunidad a 0.01 y las intra-comunidad a 1
    weights = {edge: 0.01 if edge in inter_community_edges else 1 for edge in g.edges()}
    nx.set_edge_attributes(g, weights, "weight")
    
    # Recalculamos el diseño con los pesos ajustados
    pos_communities = nx.spring_layout(g, k=0.2, weight='weight', iterations=50)

    return pos_communities



plt.figure(figsize=(15, 10))
# Uso de la función:
partition = community_louvain.best_partition(G_book1)
pos = community_layout(G_book1, partition)
draw_communities(G_book1, partition, pos, n_labels=15)  # Se etiquetan los 15 nodos de mayor grado

# Creamos un diccionario de personajes y sus respectivas comunidades
d = {}
for character, par in partition.items():
    if par in d:
        d[par].append(character)
    else:
        d[par] = [character]
d

{0: ['Addam-Marbrand',
  'Jaime-Lannister',
  'Tywin-Lannister',
  'Tyrion-Lannister',
  'Catelyn-Stark',
  'Bronn',
  'Chiggen',
  'Marillion',
  'Shae',
  'Shagga',
  'Vardis-Egen',
  'Willis-Wode',
  'Brynden-Tully',
  'Edmure-Tully',
  'Hoster-Tully',
  'Lysa-Arryn',
  'Nestor-Royce',
  'Walder-Frey',
  'Colemon',
  'Donnel-Waynwood',
  'Eon-Hunter',
  'Masha-Heddle',
  'Moreo-Tumitis',
  'Mya-Stone',
  'Mychel-Redfort',
  'Robert-Arryn',
  'Stevron-Frey',
  'Tytos-Blackwood',
  'Wendel-Manderly',
  'Chella',
  'Clement-Piper',
  'Karyl-Vance',
  'Conn',
  'Coratt',
  'Danwell-Frey',
  'Hosteen-Frey',
  'Jared-Frey',
  'Dolf',
  'Gunthor-son-of-Gurn',
  'Harys-Swyft',
  'Kevan-Lannister',
  'Jonos-Bracken',
  'Jyck',
  'Morrec',
  'Kurleket',
  'Leo-Lefford',
  'Lyn-Corbray',
  'Mord',
  'Timett',
  'Ulf-son-of-Umar'],
 1: ['Aegon-I-Targaryen',
  'Daenerys-Targaryen',
  'Aggo',
  'Drogo',
  'Jhogo',
  'Jorah-Mormont',
  'Quaro',
  'Rakharo',
  'Cohollo',
  'Haggo',
  'Qotho',
  'Doreah',
  'Eroeh',
  'Illyrio-Mopatis',
  'Irri',
  'Jhiqui',
  'Mirri-Maz-Duur',
  'Viserys-Targaryen',
  'Jommo',
  'Ogo',
  'Rhaego',
  'Fogo'],
 2: ['Eddard-Stark',
  'Aerys-II-Targaryen',
  'Brandon-Stark',
  'Gerold-Hightower',
  'Jon-Arryn',
  'Robert-Baratheon',
  'Alyn',
  'Harwin',
  'Jory-Cassel',
  'Tomard',
  'Arthur-Dayne',
  'Cersei-Lannister',
  'Petyr-Baelish',
  'Vayon-Poole',
  'Arys-Oakheart',
  'Balon-Greyjoy',
  'Renly-Baratheon',
  'Barristan-Selmy',
  'Pycelle',
  'Varys',
  'Lyanna-Stark',
  'Cayn',
  'Janos-Slynt',
  'Stannis-Baratheon',
  'Rhaegar-Targaryen',
  'Daryn-Hornwood',
  'Torrhen-Karstark',
  'Gendry',
  'Howland-Reed',
  'Jacks',
  'Joss',
  'Porther',
  'Raymun-Darry',
  'Tobho-Mott',
  'Tregar',
  'Varly',
  'Wyl-(guard)',
  'Wylla',
  'Oswell-Whent',
  'Heward',
  'Hugh',
  'Lancel-Lannister'],
 3: ['Aemon-Targaryen-(Maester-Aemon)',
  'Alliser-Thorne',
  'Bowen-Marsh',
  'Chett',
  'Clydas',
  'Jeor-Mormont',
  'Jon-Snow',
  'Samwell-Tarly',
  'Albett',
  'Halder',
  'Rast',
  'Grenn',
  'Pypar',
  'Benjen-Stark',
  'Yoren',
  'Jaremy-Rykker',
  'Mance-Rayder',
  'Dareon',
  'Donal-Noye',
  'Dywen',
  'Todder',
  'Hobb',
  'Jafer-Flowers',
  'Matthar',
  'Othor',
  'Randyll-Tarly'],
 4: ['Arya-Stark',
  'Desmond',
  'Ilyn-Payne',
  'Jeyne-Poole',
  'Joffrey-Baratheon',
  'Meryn-Trant',
  'Mordane',
  'Mycah',
  'Myrcella-Baratheon',
  'Sandor-Clegane',
  'Sansa-Stark',
  'Syrio-Forel',
  'Tommen-Baratheon',
  'Balon-Swann',
  'Boros-Blount',
  'Beric-Dondarrion',
  'Gregor-Clegane',
  'Loras-Tyrell',
  'Thoros-of-Myr',
  'High-Septon-(fat_one)',
  'Marq-Piper',
  'Mace-Tyrell',
  'Paxter-Redwyne',
  'Maegor-I-Targaryen'],
 6: ['Bran-Stark',
  'Rickon-Stark',
  'Robb-Stark',
  'Rodrik-Cassel',
  'Luwin',
  'Theon-Greyjoy',
  'Hali',
  'Hallis-Mollen',
  'Hodor',
  'Hullen',
  'Joseth',
  'Nan',
  'Osha',
  'Rickard-Karstark',
  'Rickard-Stark',
  'Stiv',
  'Jon-Umber-(Greatjon)',
  'Galbart-Glover',
  'Roose-Bolton',
  'Maege-Mormont'],
 5: ['Waymar-Royce', 'Gared', 'Will-(prologue)']}

# la densidad de un grafo es una propiedad que determina la proporción de aristas que posee. 

nx.density(G_book1)

0.03933068828704502

nx.density(nx.subgraph(G_book1, d[4]))

0.12659698025551683

nx.density(nx.subgraph(G_book1, d[7]))

1.0

nx.density(nx.subgraph(G_book1, d[1]))#/nx.density(G_book1)

0.2813852813852814

Tarea 2.7

Encuentre el nodo más importante en cada partición/comunidad según su centralidad de grado (HINT: use la centralidad normalizada, por qué?).

from sinfo import sinfo
sinfo()

-----
community   0.15
matplotlib  3.5.0
networkx    2.6.3
numpy       1.22.4
pandas      1.3.4
sinfo       0.3.1
-----
IPython             7.29.0
jupyter_client      7.1.0
jupyter_core        4.9.1
jupyterlab          3.2.4
notebook            6.4.6
-----
Python 3.10.0 | packaged by conda-forge | (default, Nov 20 2021, 02:25:38) [Clang 11.1.0 ]
macOS-10.15.7-x86_64-i386-64bit
16 logical CPU cores, i386
-----
Session information updated at 2023-06-16 01:06

Centralidad y Mundo Pequeño

Cristian Candia-Castro Vallejos, Ph.D.1,2,3,4

Redes? Grafos?

¿Ejemplos de redes?

Usando NetworkX

Estadísticas descriptivas para una red en múltiples niveles (ego, díada, tríada, subgrupo, red)

Análisis a nivel de nodo

Centralidad

Centralidad de grado

nx.degree_centrality(G)

Betweenness Centrality

Closeness centrality

nx.closeness_centrality(G, u=None, distance=None, normalized=True)

Eigenvector centrality

nx.eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight='weight')

Resumen

Ejemplo del mundo real: la red de familias de élite florentinas del siglo XIV

Ejemplo

TAREA 2.1

PageRank

Análisis a nivel de díadas: recuentos de díadas, caminos, geodésicas

Trabajemos en una red real

¿Podemos encontrar al investigador más influyente/importante en esta red?

¿Cómo evaluamos la importancia de algunas personas en una red?

¿Cómo se identificaría a estas personas?

Tarea 2.2

Tarea 2.3

Echemos un vistazo a los componentes conectados de un grafo.

Camino más corto de la red

Plot redes con nodos de distinto tamaño

Grado de nodo vs coeficiente de clustering

MUNDO PEQUEÑO

Seis grados de separación, número de Erdos, número de Bacon !!

Tarea 2.4

Cambiemos de tema y hablemos de Juego de tronos (Network of Thrones)

Cargamos los datasets

Encontrar el nodo/personaje más importante en estas redes.

Tarea 2.5

Hagamos esto para la centralidad de Betweenness y verifiquemos si esto hace alguna diferencia

Tarea 2.6

¿Existe una correlación entre estas métricas para todos los libros?

Evolución de la importancia de los personajes sobre los libros

Ejercicio resuelto

Entonces, ¿qué pasa con Stannis Baratheon?

Detección de comunidad en redes (Spoiler)

Tarea 2.7

Cristian Candia-Castro Vallejos, Ph.D. $^{1, 2, 3, 4}$

Usando `NetworkX`

`nx.degree_centrality(G)`

`nx.closeness_centrality(G, u=None, distance=None, normalized=True)`

`nx.eigenvector_centrality(G, max_iter=100, tol=1e-06, nstart=None, weight='weight')`