Los algoritmos de componentes débilmente conectados son una especie diferente de algoritmos de comunidades que están diseñados para determinar la conectividad de nodos de un mismo conjunto que se encuentran dentro de un grafo no dirigido conforman una estructura de componente conectado.
A continuación descubriremos información importante sobre estos algoritmos, sus usos y un ejemplo para comprender su aplicabilidad.
¿Qué es un algoritmo de componentes débilmente conectados?
Los algoritmos de grafos proporcionan los medios necesarios para comprender, modelar y establecer los parámetros de predicción de dinámicas que suceden a niveles de alta complejidad. Un ejemplo de esto pueden ser los flujos de recursos o información a través de una red en la que se pueden propagar fallas o datos inválidos, la influencia o la resistencia de los grupos a captar la información.
Dentro de estos importantes algoritmos se encuentran los algoritmos de componentes débilmente conectados que ayudan a detectar conjuntos o grupos de nodos donde cada uno de los nodos es accesible desde cualquier otro nodo en el mismo grupo sin que la dirección de las relaciones tenga algún nivel de influencia.
Es posible detectar estas comunidades o conexiones múltiples entre vértices con el algoritmo nombrado en las librerías de Neo4j como “Union Find”. Este detecta los nodos vinculados dentro del grafo no dirigido, entendiendo que puede accederse a él desde cualquier otro vértice.
Presenta una importante diferencia con otro algoritmo de conectividad nombrado “SCC” o “Algoritmo de componentes fuertemente conectados”. En este caso se necesita solamente una ruta, en una sola dirección para que la conexión sea válida, mientras que en el algoritmo de componentes fuertemente conectados la unión entre los vértices debe existir en ambas direcciones
El algoritmo Unión Find suele ser utilizado para comprender inicialmente la estructura de un grafo.
Casos de uso del algoritmo
Los algoritmos de componentes débilmente conectados tienden a tener un rango de aplicabilidad para casos especiales o específicos que detallaremos a continuación. Este tipo de algoritmo permite realizar pruebas internas a los componentes de un grafo y determinar la conectividad entre ellos. Gracias a esto podemos entender a profundidad la estructura y el comportamiento de un grafo. En ocasiones es difícil conseguir en un recorrido simple todas las conexiones existentes.
Con este tipo especial de algoritmo podemos realizar seguimientos exhaustivos a los grupos de registros que conforman una base de datos para realizar una des-duplicación, que es un proceso vital que garantiza la calidad de una gestión de datos de alta complejidad.
Los componentes débilmente conectados pueden también utilizarse para analizar las redes de citas en trabajos académicos o inclusive para determinar el nivel de estabilidad de la conectividad de una red y observar si existen modificaciones en los nodos del grafo.
Es de especial importancia destacar que el algoritmo de componentes débilmente conectados es utilizado con mucha frecuencia para ejecutar otros algoritmos de forma independiente dentro de un conjunto específico e identificado de datos, siendo una especie de paso previo al procesamiento de grafos dirigidos ya que podemos ubicar de forma rápida y sencilla los nodos que no se encuentran conectados.
Ejemplo de uso del algoritmo de componentes débilmente conectados
A continuación construiremos un ejemplo simple de ejecución del Union Find o algorimto de componentes débilmente conectados para entender su funcionalidad. En primer lugar construiremos un grafo en Cypher en el entorno de Neo4j como el siguiente:
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)-[:FRIEND]->(nBridget) MERGE (nAlice)-[:FRIEND]->(nCharles) MERGE (nMark)-[:FRIEND]->(nDoug) MERGE (nMark)-[:FRIEND]->(nMichael);
Posteriormente se ejecuta el algoritmo de la siguiente manera
CALL algo.unionFind.stream("User", "FRIEND", {}) YIELD nodeId,setId< MATCH (u:User) WHERE id(u) = nodeId RETURN u.id AS user, setId y obtenemos como resultado lo siguiente:
| Nombre | Centrality Weight |
| C | 0.6666666666666666 |
| B | 0.5714285714285714 |
| D | 0.5714285714285714 |
| A | 0.4 |
| E | 0.4 |
Permitiéndonos entender que existe una conexión entre algunos de los conjuntos de datos.
Esperamos que esta información sea de utilidad para aprender sobre el funcionamiento de estos importantes algoritmos.
Visita más de Grapheverywhere para conocer todo lo que necesitas sobre algoritmos de grafos.
