El algoritmo de coeficiente de agrupación  es un método de detección de comunidades que se utiliza para determinar el número de triángulos que pasan entre cada uno de los nodos de un grafo. Este algoritmo es de gran utilidad para diversos casos de análisis de datos y es desarrollado dentro del entorno de trabajo de Neo4j. 

A continuación conoceremos algunos conceptos importantes sobre este algoritmo en específico, sus principales casos de uso y un ejemplo práctico desarrollado en Cypher para comprender su funcionamiento. 

¿Qué es el algoritmo de coeficientes de agrupación? 

Basado en el recuento de triángulos es un análisis que tiene cierta relevancia en redes sociales ya que es util para detectar comunidades y medir la cohesión que poseen entre ellas. Dependiendo del tipo de aplicación este algoritmo puede también ser utilizado para determinar la estabilidad de un grafo o como parte del cálculo de índices de red a raíz de su coeficiente de agrupación. 

Tipos de de coeficiente de agrupación 

El coeficiente de agrupación se presenta en dos tipos principales: 

Coeficiente de agrupación local:

Este coeficiente de agrupación local calcula la probabilidad de que sus vecinos estén conectados también al grafo en estudio. Para detectar esto se realiza una puntuación que implica el conteo de los triángulos que conforman el cluster. 

Coeficiente de agrupamiento global

Este coeficiente se calcula tomando la suma normalizada de todos los coeficientes que conforman el cluster de forma local. 

Casos de uso  

La experiencia ha demostrado que el recuento de triángulos y el  calculo de este tipo de coeficiente es de gran utilidad para elaborar la clasificación de las características de un sitio web. Esto nos permite elaborar listas de contenido deseado o no deseado. 

También el coeficiente de agrupación se ha utilizado para investigar y descifrar la estructura de comunidades en entornos de redes sociales como Facebook. En  estos casos se pueden construir vecindarios de alta densidad de usuarios y reflejarlas en un grafo de alto nivel. 

Además puede utilizarse para calcular el coeficiente y explorar la estructura temática de una web y detectar comunidades que se crean en base a un  conjunto páginas que poseen un tema o características comunes y los enlaces de direccionamiento existentes entre ellas le dan forma a la estructura. 

Ejemplo de aplicación del algoritmo de coeficiente de agrupación

En primer lugar para analizar con este algoritmo un conjunto de datos es crear en Neo4j un grafo similar al que presentamos a continuación: 

MERGE (alice:Person{id:"Alice"})

MERGE (michael:Person{id:"Michael"})

MERGE (karin:Person{id:"Karin"})

MERGE (chris:Person{id:"Chris"})

MERGE (will:Person{id:"Will"})

MERGE (mark:Person{id:"Mark"})

MERGE (michael)-[:KNOWS]->(karin)

MERGE (michael)-[:KNOWS]->(chris)

MERGE (will)-[:KNOWS]->(michael)

MERGE (mark)-[:KNOWS]->(michael)

MERGE (mark)-[:KNOWS]->(will)

MERGE (alice)-[:KNOWS]->(michael)

MERGE (will)-[:KNOWS]->(chris)

MERGE (chris)-[:KNOWS]->(karin);

Adicionalmente se identifica cada triangulo de datos

CALL algo.triangle.stream('Person','KNOWS')

YIELD nodeA,nodeB,nodeC

RETURN algo.asNode(nodeA).id AS nodeA, algo.asNode(nodeB).id AS nodeB, algo.asNode(nodeC).id AS nodeC

Al ejecutar el algoritmo este nos devuelve una tabla con los resultados que conforman los triangulos o el cluster de datos: 

Podemos observar claramente cómo se agrupa en tríos, por el número de datos, todo el grafo. Gracias a esto podemos comprender que cada uno de los integrantes del triángulo o cluster tiene conocimiento de un miembro de otro triángulo. 

Ahora bien para contar el número de triángulos a los que pertenece un vértice debemos introducir lo siguiente para conocer el coeficiente de agrupación del grafo: 

CALL algo.triangleCount('Person', 'KNOWS',

concurrency:4, write:true, writeProperty:'triangles',clusteringCoefficientProperty:'coefficient'})

YIELD loadMillis, computeMillis, writeMillis, nodeCount, triangleCount, averageClusteringCoefficient;

Si deseamos contar el número de triángulos a los que conforma un nodo, debemos introducir lo siguiente para obtener el cálculo exacto del coeficiente:

CALL algo.triangleCount.stream('Person', 'KNOWS', {concurrency:4})

YIELD nodeId, triangles, coefficient

RETURN algo.asNode(nodeId).id AS name, triangles, coefficient

ORDER BY coefficient DESC

Obteniéndose los siguientes resultados: 

Name

Triangles

Coefficient

Karin

1

1

Mark

1

1

Chris

2

0.6666666666666666

Will

2

0.6666666666666666

Michael

3

0.3

Alice

0

0

Mientras más elevado sea el número del coeficiente se entenderá que el nodo pertenece a mayor numero de triángulos. 

Esperamos que esta información sea de utilidad para comprender las bondades de este importante algoritmo de Neo4j. 

Visita más de Grapheverywhere para conocer todo lo que necesitas sobre algoritmos de componentes conectados.