Come persistere alle informazioni sulla comunità in un grafico

Question

Ho alcuni database di grafici (reti di amici, cronologia degli acquisti, ecc.) Che persisto con Neo4j. Ho intenzione di analizzarli con Algoritmi di rilevamento della comunità come Girvan Newman. Questi algoritmi di solito restituiscono a dendrogramma, rappresentando la divisione del grafico dall'intera rete ai singoli nodi. Mi chiedo come potrei persistere a questi risultati. Suppongo che possa essere archiviato come un grafico separato, ma c'è un modo per archiviarlo all'interno del grafico stesso? La mia preoccupazione nel farlo è la necessità di creare nodi per rappresentare i gruppi, cosa che vorrei evitare.

Answer 1

Un modo per rappresentare un dendrogramma è come un elenco di coppie, contenenti coppie (N-1) per N elementi. Supponendo che l'elemento sinistro della coppia sia quello il cui ID è tenuto a riferirsi a tutti gli elementi di una comunità, potrebbe apparire un dendrogramma campione

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

Quindi un modo alternativo per persistere che potrebbe essere quello di archiviare in ciascun nodo in quale fase del tempo viene unita in un altro nodo (insieme a tutti i nodi che sono stati precedentemente uniti in esso).

Quindi allegheresti (0: 0) a 1, (1: 2) a 3 e (2: 0) a 2 (timestep: nuovo "nome" del nodo).

EDIT: concretamente, ciò potrebbe significare allegare due attributi con valori interi, ad esempio "Merge_Timestep" e "Merge_into" a ciascun oggetto nodo NEO4J.

Answer 2

La maggior parte degli algoritmi di rilevamento della comunità funzionano dalle comunità agglomerate lungo i bordi esistenti nel grafico; Girvan-Newman è un po 'insolito in quanto funziona tagliando i bordi. In entrambi i casi, il dendrogramma può essere visto come mostrare un ordinamento delle operazioni sui bordi del grafico. Pertanto, invece di conservare il dendrogramma come oggetto separato, è possibile allegare proprietà ai bordi (relazioni) che mostrano quale ordine dovrebbero essere uniti/tagliati. La mia conoscenza di Neo4j è estremamente limitata, quindi ti lascerò i dettagli.

Ci sono alcune complicazioni con la fusione, in quanto generalmente ci saranno più bordi equivalenti, ognuno che collega diversi vertici all'interno delle comunità da unire. Fondamentalmente, scegli una strategia che ti consente di capire le comunità collegate dai bordi.