Approche et exemple de regroupement de graphes en «R»

10

Je cherche à regrouper / fusionner des nœuds dans un graphique en utilisant le regroupement de graphiques dans «r».

Voici une variation étonnamment jouet de mon problème.

  • Il existe deux "clusters"
  • Il existe un "pont" reliant les clusters

Voici un réseau de candidats:
entrez la description de l'image ici

Quand je regarde la distance de connexion, le "hopcount", si vous voulez, je peux obtenir la matrice suivante:

 mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

Réflexions ici:

  • Par chance ou en raison de la simplicité du jouet, la matrice a des patchs évidents, ce ne sera pas le cas dans la matrice (très grande). Si je randomisais la relation entre le point et la ligne, ce ne serait pas si propre.
  • Je me suis peut-être trompé - donc si j'ai une faute de frappe, faites le moi savoir.
  • Le nombre de sauts ici est le nombre de sauts le plus court pour connecter le point de la ligne i au point de la colonne j. Un self-hop est toujours un hop, donc la diagonale est tout entière.

Donc, dans cette matrice, une plus grande distance (sauts) a un nombre plus élevé. Si je voulais une matrice montrant la "connectivité" au lieu de la distance, alors je pourrais faire un point-inverse, où chaque cellule de la matrice est remplacée par son inverse multiplicatif.

Des questions:

Pour m'aider à trouver ma propre voie:

  • Quels sont les termes pour réduire le nombre de nœuds sur un graphe en les combinant? Est-ce un regroupement, une fusion, une fusion - quels sont les mots que je devrais utiliser?
  • Quelles sont les techniques éprouvées? Existe-t-il un manuel sur le sujet? Pouvez-vous indiquer des articles ou des sites Web?
  • Maintenant, j'ai essayé de regarder ici en premier - c'est un excellent point de "premier contrôle". Je n'ai pas trouvé ce que je cherchais. Si je l'ai raté (ce qui n'est pas improbable), pouvez-vous m'indiquer une ou deux réponses à une question sur le sujet ici, sur CV?

Pour m'amener où je vais:

  • Existe-t-il un package «R» qui regroupera correctement les nœuds sur le réseau?
  • Pourriez-vous m'indiquer un exemple de code pour ce faire?
  • Existe-t-il un package «R» qui présentera graphiquement le réseau réduit résultant?
  • Pourriez-vous m'indiquer un exemple de code pour ce faire?

Merci d'avance.

EngrStudent
la source
2
Veuillez noter que demander des packages (R) ou du code est hors sujet ici. Vous voudrez peut-être rendre la partie "trouver" plus visible et la partie "obtenir" moins.
gung - Reinstate Monica
3
J'essaierai de faire une réponse complète un jour quand j'aurai une chance @gung. Mais pour une réponse rapide, voici la détection de communauté appliquée à l'exemple de graphique d'EngrStudent utilisant le igraphpackage R.
Andy W
1
À mon humble avis, il n'y a qu'un seul cluster dans ce graphique. Il existe cependant trois cliques qui se chevauchent . Je ne sais pas pourquoi votre plan est de détruire la clique du milieu - à moins que vous ne puissiez formaliser cela, vous aurez du mal à trouver un algorithme.
A QUIT - Anony-Mousse
2
Pour ce que ça vaut, mcl ( micans.org/mcl ) trouve les deux clusters (je ne suis pas vraiment d'accord avec l'évaluation d'Anony-Mousse, et je ne trouve pas l'approche de modélisation de clique pour le clustering de graphiques particulièrement fructueuse). Il s'agit de son paramètre unique (contrôle de la granularité) défini par défaut. Cet algorithme (mcl - je l'ai publié) est utilisé assez largement en bioinformatique, et un code source (hautement évolutif) est disponible. L'interfaçage avec R se fait facilement à l'aide d'interfaces de texte.
micans
2
Demander du code et des packages a toujours été hors sujet ici. Demander de l'aide avec le code existant (c'est-à-dire que vous avez un exemple reproductible ) est sur le sujet de Stack Overflow . Si vous ne le saviez pas, il est temps de l'apprendre. L'idée que les utilisateurs qui répondent aux R Q sur SO n'ont pas d'expertise statistique me semble bizarre, mais beaucoup de gens semblent le supposer; en tout cas ce n'est pas vrai. Que votre Q ait été répondu par un message SO devrait dire quelque chose ici. OTOH, en disant «quel genre d'analyse est-ce, quelqu'un peut-il m'indiquer des ressources» est définitivement sur le sujet ici.
gung - Rétablir Monica

Réponses:

9

Votre exemple particulier suggère de trouver des communautés au sein du réseau qui ont plus de connexions entre les nœuds de la communauté et relativement peu de bords entre les nœuds de différentes communautés. C'est différent de trouver des communautés isolées , dans lesquelles il y a des sous-graphiques qui sont complètement déconnectés.

Voici un exemple de détection de communauté dans R à l'aide du igraphpackage et d'un algorithme décrit dans Clauset et al. (2004) . Pour utiliser cet algorithme, je transforme votre "nombre de sauts" en une matrice d'adjacence binaire sans boucles auto. L'algorithme a besoin d'une matrice non dirigée, qui est cohérente avec votre diagramme manuscrit et les données que vous avez fournies (les bords sont symétriques).

library(igraph)
mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

#turn this into an adjacency matrix
adjMat <- mymatrix == 1
diag(adjMat) <- 0 #no self loops

g  <- graph.adjacency(adjMat)
plot(g)

#only works for undirected graphs, which this example is fine since symetric
fc <- fastgreedy.community(as.undirected(g))

#make colors for different communities
V(g)$color <- ifelse(membership(fc)==1,"red","blue")
plot(g)

entrez la description de l'image ici

Je ne peux pas commenter la pertinence de réduire ces nœuds pour une analyse plus approfondie, mais une telle détection de communauté est certainement utile pour explorer le réseau. Il existe également de nombreux autres algorithmes de détection de communauté (ainsi que d'autres bibliothèques pour l'analyse de réseau dans R). Ce n'est qu'un exemple qui se produit pour produire la sortie souhaitée pour ce problème de jouet.

Andy W
la source
1
Compte tenu également des commentaires précédents sur l'utilisation d'une base de données de graphiques, vous n'avez pas besoin que le graphique soit représenté comme une matrice d'adjacence. Un tableau pour les nœuds et une ligne pour chaque bord est un format plus typique / efficace, et vous pouvez le transformer en igraphréseau.
Andy W
1

Si vous n'êtes pas déjà connecté à un référentiel pour vos données de nœud et de connexion, vous pouvez consulter le package Rneo4j. Mais cela implique l'utilisation du neo4j (une base de données graphique, pas un SGBDR) pour stocker vos données. Je ne suis pas un expert ici, mais je pense que cette approche pourrait être particulièrement efficace si a) comme suggéré par Anony-Mousse, vous ne pouvez pas formaliser cela, ou b) le nombre de nœuds et de connexions est particulièrement important, ou c) vous enroulez jusqu'à avoir des questions supplémentaires concernant votre réseau.

user3123116
la source
Je ne savais pas qu'une telle chose existait. Soigné! Est-ce un bon exemple du matériau? nicolewhite.github.io/RNeo4j/examples
EngrStudent
Comment passer des données de neo4j au clustering de graphes? Est-ce que mcl ou igraph fonctionnerait avec cela?
EngrStudent
2
Une fois que vous avez extrait vos données de neo4j dans R, vous pouvez utiliser n'importe quel autre package R (par exemple, AndyW suggère igraph) contre les données. Alternativement - le package Rneo4j comprend des commandes pour récupérer des données et vous permet également d'exécuter le langage de requête Cypher (analogue à SQL, mais personnalisé pour le graphe neo4j db). Dans Cypher, vous pouvez effectuer des requêtes sophistiquées et exécuter des algorithmes prédéfinis (chemins les plus courts, tous les chemins, tous les chemins simples, Dijkstra, etc.). Je suis à ma limite ici en termes de personnages et de contenu - Si vous voulez suivre ce chemin (désolé!), Le site neo4j pourrait être votre prochain arrêt.
user3123116
1

Pour les futurs lecteurs,

Voici un ensemble de fonctions des packages igraph et la dernière vient de MCL:

print("LABEL PROPAGATION")
w<-cluster_label_prop(g)

print("Leading Eigen")
w<-cluster_leading_eigen(g)

print("SpinGlass")
w<-cluster_spinglass(g, stop.temp = 0.05)

print("walktrap")
w<-cluster_walktrap(g, steps=4)

print("MCL")
adj<-get.adjacency(g)
w<-mcl(adj,addLoops=TRUE)

Vous pouvez trouver la documentation ici http://igraph.org/r/doc/ et ici https://cran.r-project.org/web/packages/MCL/MCL.pdf

Je trouve le walktrap particulièrement utile

Omar Jaafor
la source
Bien que cela puisse être lié à la question, cela ne semble pas être une réponse.
Michael R. Chernick
2
j'ai répondu aux deux questions: Existe-t-il un package «R» qui regroupera correctement les nœuds sur le réseau? Pourriez-vous m'indiquer un exemple de code pour ce faire? Mais oui, il ne répond pas à l'ensemble des questions.
Omar Jaafor