Comment conserver les informations de la communauté dans un graphique

Question

J'ai des bases de données graphiques (réseaux d'amis, historique des achats, etc.) que je persiste avec Neo4j.Je prévois de les analyser avec des algorithmes de détection de communauté tels que Girvan Newman .Ces algorithmes renvoient généralement un dendrogramme , représentant la division du graphique du réseau entier aux nœuds individuels.Je me demande comment je pourrais persister ces résultats.Je suppose qu'il pourrait être stocké sous forme de graphique séparé, mais existe-t-il un moyen de le stocker dans le graphique lui-même?Ce qui me préoccupe, c'est la nécessité de créer des nœuds pour représenter les groupes, ce que je voudrais éviter.

Answer 1

Une façon de représenter un dendrogramme est sous la forme d'une liste de paires, contenant (n-1) paires pour n éléments.En supposant que l'élément de gauche de la paire est celui dont l'ID est conservé pour faire référence à tous les éléments d'une communauté, un exemple de dendrogramme pourrait ressembler à

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

Donc, une autre façon de persister qui pourrait être de stocker à chaque nœud à quel moment il est fusionné dans un autre nœud (avec tous les nœuds qui y ont été précédemment fusionnés).

Vous attacheriez donc (0: 0) à 1, (1: 2) à 3 et (2: 0) à 2 (pas de temps: nouveau 'nom' du nœud).

edit: Concrètement, cela pourrait signifier attacher deux attributs à valeur entière, par exemple'merge_timestep' et 'merge_into' à chaque objet nœud Neo4J.

Answer 2

La plupart des algorithmes de détection de communauté fonctionnent en agglomérant les communautés le long des arêtes existantes dans le graphique;Girvan-Newman est un peu inhabituel en ce qu'il fonctionne par tranchants.Dans tous les cas, le dendrogramme peut être considéré comme montrant un ordre des opérations sur les bords du graphique.Ainsi, au lieu de stocker le dendrogramme en tant qu'objet séparé, vous pouvez attacher des propriétés aux arêtes (relations) indiquant dans quel ordre elles doivent être fusionnées / coupées.Ma connaissance de Neo4j est extrêmement limitée, je vous laisse donc les détails.

Il y a quelques complications avec la fusion, car il y aura généralement plusieurs arêtes équivalentes, chacune reliant différents sommets au sein des communautés à fusionner.En gros, choisissez simplement une stratégie qui vous permet de comprendre les communautés liées depuis les bords.