Algoritmos de componentes fuertemente conectados

Los algoritmos de componentes fuertemente conectados funcionan bajo los postulados del algoritmo de tiempo lineal de Tarjan. En este se estudia la descomposición de un grafo dirigido, analizando la conexión que existe entre todos sus componentes, partiendo de la aplicación clásica del algoritmo de búsqueda de profundidad. 

A continuación descubriremos más información respecto a estos importantes algoritmos, sus casos de uso y un ejemplo para comprender de mejor manera su utilización. 

¿Qué son los algoritmos de componentes fuertemente conectados? 

Como ya habéis podido detallar en la introducción de esta entrada, los algoritmos de componentes fuertemente conectados  permiten entender el comportamiento de los nodos que conforman un grafo dirigido y poseen un tipo específico de conectividad. Para que se considere un componente fuertemente conectado o conexo este grafo debe poseer nodos que estén totalmente conectados entre sí. 

Dentro de un grafo dirigido es posible que no exista una conexión fuerte, aunque es posible que exista una o varias vinculaciones. Se busca con estos algoritmos determinar los componentes fuertemente conectados de mayor tamaño. 

Casos de uso del algoritmo de componentes fuertemente conectados

Existen diversas oportunidades en las que debemos ejecutar estos algoritmos para entender a el comportamiento de los vértices que componen un grafo. Uno de los casos más importantes que podemos utilizar para ejemplificar esto puede ser dentro de las transacciones enmarcadas dentro de una corporación transnacional. Este tipo de algoritmo permite conocer las acciones directas o indirectas que se realizan entre los miembros que la conforman. 

Ayuda a analizar los flujos de procesos de líneas operativas que pueden servir para incrementar beneficios o disminuir los costos de transacción en estructuras grandes. 

También puede utilizarse este tipo de algoritmo para calcular la conectividad entre diferentes componentes de una red. Podemos medir el rendimiento del enrutamiento en redes inalámbricas de múltiples sitios. En redes sociales podemos analizar grupos de personas que pueden conformar componentes fuertemente conectados debido a las múltiples relaciones, gustos e inclusive lugares comunes, sirviendo como un sistema que puede gestionar recomendaciones para quienes conforman estos componentes. 

conectado

Ejemplo de uso del algoritmo

A continuación te presentaremos un ejemplo de ejecución de este algoritmo desarrollado en Neo4j.  Construiremos un grafo con la información de 6 personas en una red social, para comprender su nivel de conexión. Ellos deben estar todos conectados entre sí. Así que para poder ejecutar esta proyección en Neo4j debemos construir un grafo como el que presentamos a continuación:

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)-[:FOLLOW]->(nBridget)

MERGE (nAlice)-[:FOLLOW]->(nCharles)

MERGE (nMark)-[:FOLLOW]->(nDoug)

MERGE (nMark)-[:FOLLOW]->(nMichael)

MERGE (nBridget)-[:FOLLOW]->(nMichael)

MERGE (nDoug)-[:FOLLOW]->(nMark)

MERGE (nMichael)-[:FOLLOW]->(nAlice)

MERGE (nAlice)-[:FOLLOW]->(nMichael)

MERGE (nBridget)-[:FOLLOW]->(nAlice)

MERGE (nMichael)-[:FOLLOW]->(nBridget);

Se ejecuta el algoritmo y Neo4j nos devuelve: 

CALL algo.scc('User','FOLLOW', {write:true,partitionProperty:'partition'})

YIELD loadMillis, computeMillis, writeMillis, setCount, maxSetSize, minSetSize;
Name
Partition
1 Alice
1
2 Bridget
1
2 Michael
1
4 Charles
0
5 Doug
2
6 Mark
2

Este resultado que nos devuelve la aplicación del algoritmo al conjunto de datos nos demuestra que existen 3 componentes fuertemente conectados. Existe un componente principal que contiene tres miembros y están plenamente identificados con el número uno. Posteriormente existe un componente conformado por 2 usuarios y por último se destaca un componente conformado por un solo usuario que no está conectado a ninguno de los nodos pertenecientes al grafo. 

Esperamos que esta información sea útil para comprender la utilidad de estos importantes algoritmos. 

Descubre más sobre algoritmos de componentes conectados visitando el contenido de GraphEverywhere.

Share This