El grado de centralidad es la medida más simple y directa de las medidas de centralidad Esta corresponde en términos simples al número de enlaces o conexiones que posee un vértice con el resto de los nodos pertenecientes a un grafo. Descubre a continuación cómo funciona el algoritmo que realiza este importante calculo.
¿Qué es el algoritmo de grado de centralidad?
La medida del grado de centralidad es una medida propuesta por Linton C. Freeman en un documento académico que se remonta a 1979 titulado «Centralidad en Redes Sociales. Aclaración Conceptual». El algoritmo dedicado a realizar la estimación del grado de centralidad es normalmente utilizado para detectar la popularidad o el grado de influencia individual que posee un vértice dentro de un grafo.
También es utilizado para realizar un análisis total para detectar el grado mínimo, medio, máximo y la desviación estándar que existe dentro de un grafo.
Casos de uso de un algoritmo de grado de centralidad
Los algorimos de grado de centralidad son componentes muy interesantes para conocer el grado de influencia que puede tenerse dentro de un entorno determinado. Esto es de gran utilidad en la actualidad para realizar análisis en redes de interconexión como las redes sociales. Este algoritmo evalúa los nodos pertenecientes a un grafo y determina cual tiene mayor nivel de conexiones, otorgandole una puntuación determinada. Mientras mayor sea la puntuación, mayor será el grado de influencia.
Cuando se pondera el valor que devuelve el algoritmo al analizar un grafo, este número puede ser utilizado para distinguir a usuarios que pretenden distorsionar datos en entornos controlados como sitios de subasta en linea.
Ejemplo del algoritmo desarrollado en Neo4j
A continuación desarrollaremos un análisis de un grafo que toma sus datos en una red social parecida a Twitter, en la que algunos miembros de la comunidad de usuarios se sigue entre si. Con este ejemplo intentaremos determinar cual de los usuarios de la red social posee mayor grado de influencia en base a sus conexiones.
En primer lugar construimos un grafo con la información de la siguiente manera
MERGE (nAlice:User {id:'Alice'})
MERGE (nBridget:User {id:'Bridget'})
MERGE (nCharles:User {id:'Charles'})
MERGE (nDoug:User {id:'Doug'})
MERGE (nMark:User {id:'Mark'})
MERGE (nMichael:User {id:'Michael'})
MERGE (nAlice)-[:FOLLOWS]->(nDoug)
MERGE (nAlice)-[:FOLLOWS]->(nBridget)
MERGE (nAlice)-[:FOLLOWS]->(nCharles)
MERGE (nMark)-[:FOLLOWS]->(nDoug)
MERGE (nMark)-[:FOLLOWS]->(nMichael)
MERGE (nBridget)-[:FOLLOWS]->(nDoug)
MERGE (nCharles)-[:FOLLOWS]->(nDoug)
MERGE (nMichael)-[:FOLLOWS]->(nDoug)Iniciamos la ejecución del análisis por parte del algoritmo obteniendo entonces la siguiente información
CALL algo.degree.stream("User", "FOLLOWS", {direction: "incoming"})
YIELD nodeId, score
RETURN algo.asNode(nodeId).id AS name, score AS followers
ORDER BY followers DESCCulminamos el análisis por parte del algoritmo y nos devuelve lo siguiente
CALL algo.degree("User", "FOLLOWS", {direction: "incoming", writeProperty: "followers"})Adicionalmente para conocer los resultados obtenemos la siguiente tabla
| Name | Followers |
|---|---|
| Doug | 5.0 |
| Bridget | 1.0 |
| Charles | 1.0 |
| Michael | 1.0 |
| Mark | 0.0 |
| Alice | 0.0 |
En el resultado de la tabla que devuelve la ejecución del algoritmo, podemos observar que el vértice con mayor nivel de conectividad dentro del grafo es el que identifica a Doug. Este ejemplo podría ser gran utilidad para entender la influencia o la potencialidad de usuarios en redes sociales como Instagram o Twitter.
Esperamos que esta información sea de utilidad para entender el funcionamiento de este importante algoritmo.
Visita más de Grapheverywhere para descubrir toda la información que necesitas sobre algoritmos de grafos.
