El algoritmo de propagación de etiquetas es un algoritmo de gran utilidad que permite encontrar comunidades dentro de un grafo de forma muy veloz. Este detecta las comunidades utilizando la red estructural del grafo como una guía sin necesidad de determinar de forma la información que contienen los miembros de la comunidad a detectar.

Una de las características más interesantes del algoritmo de propagación de etiquetas es que pueden asignarse de forma preliminar algunas etiquetas que nos pueden indicar el rango de soluciones que posee el nodo. Esto significa que pueden utilizarse como un método semi-estructurado para conseguir comunidades especificas y seleccionables para su estudio.

Características del algoritmo de propagación de etiquetas

El algoritmo de propagación de etiquetas es de muy reciente data. Este funciona propagando etiquetas asignadas a nodos o vértices dentro de un grafo y conformando comunidades basándose en el proceso de propagación de etiquetas. El algoritmo al funcionar de esta manera permite que una sola etiqueta pueda convertirse rápidamente en un factor dominante dentro de los nodos que están densamente conectados.

Las etiquetas al hacer el recorrido por la estructura del grafo quedarán atrapadas dentro de un grupo denso de nodos y aquellos que posean la misma etiqueta al finalizar el análisis del algoritmo pueden ser denominados miembros de la misma comunidad.

El proceso mediante el cual funciona el algoritmo inicia con una etiqueta de una comunidad única que cumple la función de indicador. Estas etiquetas se propagan a través de la red. En cada iteración de propagación cada uno de los nodos del grafo actualiza su etiqueta a la que pertenece el número máximo de vecinos en la estructura. Las conexiones se establecen y cesan de forma uniforme y aleatoria. Este algoritmo alcanza totalmente la convergencia cuando cada nodo posee una etiqueta correspondiente al vértice más cercano o «vecino».

Casos de uso

Uno de los usos más importantes que puede otorgarse al  algoritmo de propagación de etiquetas se puede encontrar en la red social de microbloggin Twitter. La propagación de etiquetas puede asignarse al estudio de la polaridad de los tweets determinando gustos y preferencias de forma eficiente en base a las reacciones del usuario.

Adicionalmente la propagación de etiquetas se utiliza para estimar combinaciones de elementos que pueden representar contradicciones de asignaciones de información, por ejemplo, puede estudiarse la asignación de tratamiento de fármacos que  con combinaciones potencialmente peligrosas para el paciente basándose en algunos criterios especiales.

Ejemplo de aplicación

Tomando como base un grafo que representa una red social donde convergen un número finito de personas, se construye el grafo de la siguiente forma:

MERGE (nAlice:User {id:'Alice'}) SET nAlice.seed_label=52
MERGE (nBridget:User {id:'Bridget'}) SET nBridget.seed_label=21
MERGE (nCharles:User {id:'Charles'}) SET nCharles.seed_label=43
MERGE (nDoug:User {id:'Doug'}) SET nDoug.seed_label=21
MERGE (nMark:User {id:'Mark'}) SET nMark.seed_label=19
MERGE (nMichael:User {id:'Michael'}) SET nMichael.seed_label=52

MERGE (nAlice)-[:FOLLOW]->(nBridget)
MERGE (nAlice)-[:FOLLOW]->(nCharles)
MERGE (nMark)-[:FOLLOW]->(nDoug)
MERGE (nBridget)-[:FOLLOW]->(nMichael)
MERGE (nDoug)-[:FOLLOW]->(nMark)
MERGE (nMichael)-[:FOLLOW]->(nAlice)
MERGE (nAlice)-[:FOLLOW]->(nMichael)
MERGE (nBridget)-[:FOLLOW]->(nAlice)
MERGE (nMichael)-[:FOLLOW]->(nBridget)
MERGE (nCharles)-[:FOLLOW]->(nDoug);

Se ejecuta el algoritmo de la siguiente manera

CALL algo.labelPropagation.stream("User", "FOLLOW",
  {direction: "OUTGOING", iterations: 10})

Al culminar la aplicación del algoritmo nos devuelve los siguientes resultados:

CALL algo.labelPropagation('User', 'FOLLOW',
  {iterations: 10, writeProperty: 'community', write: true, direction: 'OUTGOING'})
YIELD nodes, iterations, loadMillis, computeMillis, writeMillis, write, writeProperty;

Adicionalmente obtenemos una tabla en la que podemos detallar de forma directa el grado de propagación que posee cada uno de los nodos pertenecientes al grafo.

Name	Community
Alice	5
Charles	4
Bridget	5
Michael	5
Doug	4
Mark	4

El resultado del análisis nos indica que existe dentro del grafo analizado dos estructuras de comunidades de datos conectados.

Esperamos que esta información sea de utilidad para descubrir el funcionamiento y la importancia de este tipo de algoritmo.

Visita más de Grapheverywhere y descubre todo lo que necesitas sobre los algoritmos de detección de comunidades.