Métricas de Centralidad para el Análisis de Influencia

Como se mencionó en el artículo ¨Análisis de Influencia en Redes Sociales. Introducción¨, la mayoría de las herramientas para el Análisis de Redes Sociales calculan la influencia combinando diversas métricas de centralidad presentes en las ciencias sociales y la teoría de grafos. Esto se debe a que una mayor centralidad en una red, supone una forma de ventaja estructural, rango, influencia o dominio (García et al., 2016). Las métricas de centralidad más utilizadas son el Grado, la Intermediación, la Cercanía, la Centralidad de Vector Propio, el PageRank y los valores del HITS. Estas determinan cuán relevante es un actor a partir de la estructura del grafo que representa red social a la que pertenece (Freeman, 1978; García et al., 2016; Riquelme et al., 2017). En este artículo explicaremos en que consiste cada una de ellas

Centralidad de grado (degree)

Coincide con el grado de un vértice del grafo. El grado de un vértice v es el número de líneas que tienen a v como nodo de uno de sus extremos. El grado de entrada, es el número de líneas que poseen v como nodo terminal y el grado de salida, el número de líneas que poseen a v como nodo inicial (Kuz et al., 2016).

En términos de grafos, la Centralidad de Grado de un actor se calcula como su número de vecinos (Monsalve, 2008), también llamados conexiones o aristas incidentes. La centralidad de grado con peso se define similarmente, pero sumando los pesos de las aristas incidentes (Beveridge & Shan, 2016). Si se está modelando una red social de amigos, la centralidad de cada actor consiste en su número de amigos (Monsalve, 2008). Las personas que tienen muchas conexiones con terceros pueden tener más influencia, más acceso a la información o más prestigio que los que tienen menos conexiones (García et al., 2016).

Centralidad de intermediación (betweenness)

Se define como el número de rutas mínimas en las que el actor participa (Monsalve, 2008). Se puede utilizar para identificar brókeres de información en la red o nodos que pueden conectar grupos separados (Lyon, 2016). Un nodo con alto betweenness tiene una gran influencia en la transferencia de información entre los nodos a través de la red, asumiendo que cada nodo transfiere siguiendo los caminos más cortos (Freeman, 1978; Kuz et al., 2016). Posee un potencial control sobre la información, ya que, si se opone a una idea, su difusión a otros segmentos del grupo puede ser bloqueada. Puede frenar los flujos, distorsionar lo que se transmite para servir a sus intereses. Su eliminación de la red provocaría una gran interrupción en la comunicación (García et al., 2016).

Centralidad de cercanía (closeness)

Se define como el promedio de las distancias de un vértice a todos los vértices, teniendo en cuenta que valores pequeños constituyen una mayor importancia (Beveridge & Shan, 2016). Representa los nodos que, a pesar de tener pocas conexiones, sus arcos permiten llegar a todos los puntos de la red más rápidamente que desde cualquier otro punto. Estos nodos poseen una excelente posición para monitorear el flujo de información de toda la red (Kuz et al., 2016).

En resumen, el valor de la cercanía entre dos nodos no es más que la longitud del camino mínimo que los une (cantidad de aristas que separan un nodo del otro). El valor bruto total de la cercanía de un nodo es igual al promedio de las cercanías para cada nodo. Es importante notar que el valor bruto total de la cercanía es una medida inversa de centralidad. Los nodos con menor valor son considerados los más centrales (Needham & Hodler, 2018). 

Existen algunas implementaciones de esta métrica de centralidad, como la desarrollada por la Comunidad de Neo4j (Needham & Hodler, 2018; Neo4j, 2018), donde se normaliza su valor teniendo en cuenta la cantidad de usuarios del grafo (ver Fórmula). En esta implementación, el valor de la Cercanía calculado no constituye una métrica inversa por lo que los nodos con mayores valores son los más centrales. 

$SN\; =\; (N\; –\; 1\; )/S$$$

• SN es el valor normalizado de la cercanía,  la cantidad de nodos y   el valor bruto total de la cercanía.

Centralidad de vector propio (eigenvector)

Se define como una métrica de centralidad recursiva. Un actor central es aquel que tiene un vecindario con buena centralidad. Por ejemplo, un feriante puede conocer a mucha gente común mientras que un político puede conocer menos gente, pero que son personas influyentes. Al final, el político está mejor posicionado en influencia que el feriante, aunque conozca menos gente. Ahora, no todo el vecindario de un actor contará con la misma centralidad. Hay que considerar que los actores con mayor centralidad son más influyentes que el resto (Monsalve, 2008).

Siguiendo el concepto de centralidad recursiva, se dirá que la centralidad de un actor es proporcional a la suma de las centralidades de sus vecinos en el grafo. Matemáticamente, esto se expresa como c_i = ℷ∑_j a_ijc_j , donde ℷ es la constante de proporcionalidad y a_ij es el elemento de la fila i  y la columna j de la matriz de adyacencia A de la red social. En álgebra lineal c^→ = ℷAc^→, o sea, c^→ es un vector propio de A (y ℷ^-1  es su correspondiente valor propio) (Monsalve, 2008).

PageRank

PageRank es el popular algoritmo de búsqueda de Google. Fue inicialmente introducido para calcular el ranking de las páginas web en internet (Page, Brin, Motwani, & Winograd, 1999). Trabaja contando el número y calidad de links a una página para determinar cuán importante es. Constituye una variación de la Centralidad de vector propio (Needham & Hodler, 2018). En este algoritmo cada vértice del grafo adquiere un valor de importancia a partir de sus vecinos que, a diferencia de la Centralidad de vector propio, un vértice no adquiere el total de la importancia, en lugar de ello, esta importancia es dividida equitativamente entre sus conexiones directas. En otras palabras, un vértice con un alto grado de relevancia solo pasa una pequeña fracción de su importancia a cada vecino (Beveridge and Shan, 2016).

Otros usos de Page Rank

Este algoritmo permite tambièn isentificar nodos influyentes en las redes. Ha sido utilizado en diversos dominios como:

• análisis de redes de citas
• predicción de enlaces
• identificación de líderes de opinión
• modelos de influencia social que muestran que la autoridad es equivalente a la influencia (Zhao et al., 2018).

Se basa en el supuesto de que un hipervínculo desde una página que apunta a otra página, es un indicador implícito de la autoridad de la página de destino. Así, cuanto más enlace recibe una página i, más prestigio posee. Al mismo tiempo, una página se vuelve más importante si es apuntado por otras páginas importantes, generando una definición recursiva (Corbellini, 2015).

Para formular las ideas anteriores se tiene lo siguiente, dado el grafo dirigido G = (V, E) el valor de PageRank de la página , denotado como PR(i)  , se define como:

  PR(i) = (1 – ɑ) e + ɑ ∑_(j,i)∈E PR(i)/O_j

donde O_j es el número de links salientes del vértice j. El parámetro ɑ es llamado «factor de reducción«, y modela el hecho de que en cada paso el navegante puede saltar a una página Web al azar con probabilidad ɑ, o puede seguir alguno de los links en la página actual con probabilidad (1 – ɑ). En otras palabras, el algoritmo es una caminata aleatoria con reinicios al azar sobre G. Si e = 1, entonces existe igual chance de saltar a cualquier página o vértice en G . Personalizar e permite ajustar el comportamiento del caminante aleatorio (Corbellini, 2015).

HITS

Kleinberg (1999) presentó el algoritmo HITS para detectar concentradores (“hubs”) y autoridades (“authorities”) dentro de las redes de enlaces que se forman entre las diversas páginas webs de la World Wide Web (www).

• Concentradores: aquellas páginas que tienen enlaces salientes hacia un gran número de páginas.
• Autoridades: aquellas que son ampliamente referenciadas (enlaces entrantes) por otras páginas.

La noción de concentrador expresa la calidad de una página Web como un acceso a recursos útiles (por ejemplo, los directorios Web actúan como buenos “hubs”), y la noción de autoridad establece la calidad de la página como un recurso en sí. De esta manera, a cada página de la Web se le asignan puntajes de concentrador y de autoridad (Corbellini, 2015).

HITS tiene sus raíces en la noción de relación de refuerzo mutuo entre concentradores y autoridades. Un buen concentrador es una página que apunta a buenas autoridades, mientras que una buena autoridad es una página apuntada por buenos concentradores. A la luz de esto, el algoritmo tiene como objetivo la búsqueda de sitios web de autoridad. Ambos resultados, concentradores y autoridades, se calculan mediante un algoritmo iterativo que actualiza los resultados de una página basada en las puntuaciones de las páginas de su vecindad inmediata (Corbellini, 2015).

En un grafo representativo de una red social un nodo con alto puntaje de autoridad se puede considerar como un usuario influyente

Conclusión

Como se ha podido apreciar, representar una red social como un grafo es muy útil, pues al analizar su estructura, utilizando las Métricas de Centralidad, se pueden identificar posibles usuarios influyentes teniendo en cuenta su gerarquía en la red, pero no siempre es suficiente conocer esto para medir la influencia. En ocasiones es necesario identificar también que reacciones provocan las acciones de un usuario sobre otro. De este tema hablaremos en el próximo artículo.

Bibliografía

• García, M. del F., Daly, A. J., & Sánchez-Cabezudo, S. S. (2016). Identifying the new Infl uencers in the Internet Era : Social Media and Social Network Analysis. Revista Española de Investigaciones Sociológicas, 153, 23–42. https://doi.org/10.5477/cis/reis.153.23
• Freeman, L. C. (1978). Centrality in Social Networks Conceptual Clarification. Social Networks, 1(1968), 215–239. https://doi.org/10.1016/0378-8733(78)90021-7
• Riquelme, F., Gonzalez-Cantergiani, P., Molinero, X., & Serna, M. (2017). Centrality measure in social networks based on linear threshold model. Knowledge-Based Systems, 140, 92–102. https://doi.org/10.1016/j.knosys.2017.10.029
• Kuz, A., Falco, M., & Giandini, R. (2016). Análisis de redes sociales : un caso práctico. Computación y Sistemas, 20(1), 89–106. https://doi.org/10.13053/CyS-20-1-2321
• Beveridge, A., & Shan, J. (2016). Network of Thrones. Math Horizons, 23(4), 18–22. https://doi.org/http://dx.doi.org/10.4169/mathhorizons.23.4.18
• Needham, M., & Hodler, A. E. (2018). A Comprehensive Guide to Graph Algorithms in Neo4j. Neo4j.
• Monsalve, M. (2008). Análisis de redes sociales : un tutorial. Bits de Ciencia, 2, 1–6.
• Lyon, W. (2016). Analyzing the Graph of Thrones Import initial data into Neo4j. Retrieved March 25, 2018, from http://www.lyonwj.com/2016/06/26/graph-of-thrones-neo4j-social-network-analysis/
• Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank Citation Ranking: Bringing Order to the Web. Retrieved from http://ilpubs.stanford.edu:8090/422/
• Zhao, H., Lee, D. L., & Chen, Z. (2018). Ranking Users in Social Networks with Higher-Order Structures Motif-based PageRank. Association for the Advancement of Artificial Intelligence (Www.Aaai.Org).
• Corbellini, I. A. (2015). Mecanismos de soporte para procesamiento distribuido de algoritmos de recomendación en redes sociales. Universidad Nacional del Centro de la Provincia de Buenos Aires. Retrieved from http://ridaa.unicen.edu.ar/xmlui/handle/123456789/583