Cómo persistir la información de la comunidad en un gráfico

Question

Tengo algunas bases de datos de gráficos (redes de amigos, historial de compras, etc.) que persiste con Neo4J. Planeo analizarlos con Algoritmos de detección de la comunidad como Girvan Newman. Estos algoritmos generalmente devuelven un dendrograma, que representa la división del gráfico de toda la red a nodos individuales. Me pregunto cómo podría persistir estos resultados. Supongo que podría almacenarse como un gráfico separado, pero ¿hay alguna manera de almacenarlo dentro del gráfico en sí? Mi preocupación al hacerlo es la necesidad de crear nodos para representar a los grupos, que es algo que me gustaría evitar.

Answer 1

Una forma de representar un dendrograma es una lista de pares, que contienen (N-1) pares para elementos N. Suponiendo que el elemento izquierdo del par es aquel cuya identificación se consulte para referirse a todos los elementos en una comunidad, un dendrograma de muestra podría parecer

[[0,1],[2,3],[0,2]]

Entonces, una forma alternativa de persistir que podría ser almacenar en cada nodo en el que el paso se fusiona en otro nodo (junto con todos los nodos que se han fusionado previamente en él).

Entonces se adjuntará (0: 0) a 1, (1: 2) a 3 y (2: 0) a 2 (tiempo de tiempo: nuevo 'nombre' del nodo).

Editar: concretamente, esto podría significar adjuntar dos atributos con valor entero, por ejemplo, 'merge_timestep' y 'merge_into' a cada objeto NEO4J del nodo.

Answer 2

La mayoría de los algoritmos de detección comunitaria funcionan aglomerando a las comunidades a lo largo de los bordes existentes en el gráfico; Girvan-Newman es un poco inusual, ya que funciona cortando bordes. De cualquier manera, el dendrograma puede verse como un orden de operaciones en los bordes del gráfico. Por lo tanto, en lugar de almacenar el dendrograma como un objeto separado, puede conectar propiedades a los bordes (relaciones) que muestran en qué orden deben fusionarse/cortar. Mi conocimiento de Neo4J es extremadamente limitado, así que te dejaré los detalles.

Hay algunas complicaciones con la fusión, ya que generalmente habrá múltiples bordes equivalentes, cada uno que vincula diferentes vértices dentro de las comunidades para fusionarse. Básicamente, solo elija una estrategia que le permita descubrir las comunidades vinculadas desde los bordes.