Podejście i przykład grupowania wykresów w „R”

10

Szukam do grupowania / scalania węzłów na wykresie za pomocą klastrowania wykresów w 'r'.

Oto oszałamiająco zabawkowa odmiana mojego problemu.

  • Istnieją dwa „klastry”
  • Istnieje „most” łączący klastry

Oto sieć kandydacka:
wprowadź opis zdjęcia tutaj

Kiedy patrzę na odległość połączenia, „hopcount”, jeśli wolisz, mogę uzyskać następującą macierz:

 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))

Myśli tutaj:

  • Na szczęście lub ze względu na prostotę zabawki matryca ma oczywiste łaty, nie będzie tak w przypadku (bardzo dużej) matrycy. Gdybym losowo powiązał punkt z rzędem, nie byłoby to tak czyste.
  • Mogłem pomylić jeden błąd - więc jeśli mam literówkę, daj mi znać.
  • Liczba przeskoków jest tutaj najkrótszą liczbą przeskoków do połączenia punktu w rzędzie i z punktem w kolumnie j. Self-hop jest nadal hopem, więc przekątna to wszystko.

Zatem w tej macierzy większa odległość (chmiel) ma większą liczbę. Gdybym chciał macierzy pokazującej „łączność” zamiast odległości, mógłbym zrobić odwrotność kropki, w której każdą komórkę macierzy zastępuje się jej multiplikatywną odwrotnością.

Pytania:

Aby pomóc mi znaleźć własną drogę:

  • Jakie są warunki zmniejszenia liczby węzłów na wykresie poprzez ich połączenie? Czy to grupowanie, łączenie, mungowanie - jakich słów powinienem użyć?
  • Jakie są sprawdzone techniki? Czy istnieje podręcznik na ten temat? Czy możesz wskazać artykuły lub strony internetowe?
  • Teraz najpierw spróbowałem tu zajrzeć - to świetne miejsce do pierwszego sprawdzenia. Nie znalazłem tego, czego szukałem. Jeśli to przeoczyłem (co nie jest mało prawdopodobne), czy możesz wskazać mi pytanie lub dwa odpowiedzi na ten temat tutaj, w CV?

Aby zabrać mnie tam, dokąd zmierzam:

  • Czy istnieje pakiet „R”, który odpowiednio klastruje węzły w sieci?
  • Czy możesz mi wskazać przykładowy kod, aby to zrobić?
  • Czy istnieje pakiet „R”, który graficznie przedstawi wynikową zredukowaną sieć?
  • Czy możesz mi wskazać przykładowy kod, aby to zrobić?

Z góry dziękuję.

EngrStudent
źródło
2
Należy pamiętać, że proszenie o pakiety (R) lub kod są tutaj nie na temat. Możesz sprawić, by część „znajdź” była bardziej widoczna, a część „zdobądź” mniej.
Gung - Przywróć Monikę
3
Spróbuję udzielić pełnej odpowiedzi, kiedy będę miał szansę @gung. Jednak szybką odpowiedzią jest wykrywanie społeczności zastosowane do przykładowego wykresu EngrStudent przy użyciu igraphpakietu R.
Andy W
1
IMHO jest tylko jeden klaster na tym wykresie. Istnieją jednak trzy nakładające się kliki . Nie wiem, dlaczego masz zamiar zniszczyć środkową klikę - chyba że możesz to sformalizować, trudno ci będzie znaleźć algorytm.
Ma ZAKOŃCZENIE - Anony-Mousse
2
Jeśli chodzi o to, co jest warte, mcl ( micans.org/mcl ) uważa te dwa klastry (tak naprawdę nie zgadzam się z oceną Anony-Mousse i nie uważam, że podejście do klastrowania wykresów w klastrach graficznych jest szczególnie owocne). Jest tak, gdy jego pojedynczy parametr (kontrolowanie ziarnistości) jest ustawiony na wartość domyślną. Ten algorytm (mcl - opublikowałem go) jest dość szeroko stosowany w bioinformatyce i dostępny jest (wysoce skalowalny) kod źródłowy. Interfejs z R można łatwo wykonać za pomocą interfejsów tekstowych.
micans
2
Pytanie o kod i pakiety zawsze było tutaj nie na temat. Pytanie o pomoc w / istniejącym kodzie (tj. Masz powtarzalny przykład ) jest na temat przepełnienia stosu . Jeśli tego nie wiesz, czas się tego nauczyć. Pomysł, że użytkownicy odpowiadający na pytania kontrolne w sprawie SO nie mają specjalistycznej wiedzy statystycznej, jest dla mnie dziwny, ale wydaje się, że wiele osób to przypuszcza; w każdym razie to nieprawda. To, że na twoje Q odpowiedział post SO, powinno coś powiedzieć tutaj. OTOH, mówiąc: „co to za analiza, czy ktoś może wskazać mi zasoby” jest zdecydowanie na ten temat.
Gung - Przywróć Monikę

Odpowiedzi:

9

Twój konkretny przykład sugeruje znalezienie społeczności w sieci, które mają więcej połączeń między węzłami w społeczności i stosunkowo niewiele krawędzi między węzłami w różnych społecznościach. Różni się to od znajdowania izolowanych społeczności , w których istnieją podgrupy całkowicie odłączone.

Oto przykład wykrywania wspólnoty w R przy użyciu igraphpakietu i algorytmu opisanego w Clauset i in. (2004) . Aby użyć tego algorytmu, zmieniam „liczbę przeskoków” w binarną macierz przylegania bez własnych pętli. Algorytm wymaga niekierowanej macierzy, która jest spójna z odręcznie napisanym diagramem i dostarczonymi danymi (krawędzie są symetryczne).

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)

wprowadź opis zdjęcia tutaj

Nie mogę komentować zasadności zwijania takich węzłów do dalszej analizy, ale takie wykrywanie społeczności jest zdecydowanie przydatne do eksploracji sieci. Istnieje również wiele innych algorytmów wykrywania społeczności (a także inne biblioteki do analizy sieci w języku R). To tylko jeden przykład, który pozwala uzyskać pożądaną wydajność dla tego problemu z zabawkami.

Andy W.
źródło
1
Biorąc również pod uwagę poprzednie komentarze na temat korzystania z bazy danych grafów, nie trzeba przedstawiać wykresu jako macierzy przylegania. Tabela dla węzłów i wiersz dla każdej krawędzi jest bardziej typowym / wydajnym formatem i można go przekształcić w igraphsieć.
Andy W
1

Jeśli nie jesteś jeszcze przywiązany do repozytorium dla twojego węzła i danych połączenia, możesz spojrzeć na pakiet Rneo4j. Ale to oznacza użycie neo4j (bazy danych grafów, a nie RDBMS) do przechowywania danych. Nie jestem tutaj ekspertem, ale myślę, że to podejście może być szczególnie skuteczne, jeśli a) jak sugeruje Anony-Mousse, nie możesz sformalizować tego, lub b) liczba węzłów i połączeń jest szczególnie duża, lub c) zwijasz masz dodatkowe pytania dotyczące Twojej sieci.

użytkownik3123116
źródło
Nie wiedziałem, że coś takiego istnieje. Schludny! Czy to przyzwoity przykład materiału? nicolewhite.github.io/RNeo4j/examples
EngrStudent
Jak przejść od danych w neo4j do grupowania grafów? Czy mcl lub igraph będą z nim współpracować?
EngrStudent
2
Po przeniesieniu danych z neo4j do R możesz użyć dowolnego innego pakietu R (np. AndyW sugeruje igraph) w stosunku do danych. Alternatywnie - pakiet Rneo4j zawiera polecenia do pobierania danych, a także pozwala na uruchomienie języka zapytań Cypher (analogicznie do SQL, ale zbudowany na zamówienie dla db db neo4j). W Cypher możesz wykonywać skomplikowane zapytania i uruchamiać niektóre predefiniowane algorytmy (najkrótsze ścieżki, wszystkie ścieżki, wszystkie proste ścieżki, Dijkstra itp.). Mam tutaj swoje ograniczenia zarówno pod względem postaci, jak i treści - jeśli chcesz pójść tą ścieżką (przepraszam!), Witryna neo4j może być Twoim następnym przystankiem.
user3123116
1

Dla przyszłych czytelników

Oto zestaw funkcji z pakietów igraph, a ostatni z 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)

Dokumentację można znaleźć tutaj http://igraph.org/r/doc/ i tutaj https://cran.r-project.org/web/packages/MCL/MCL.pdf

Uważam, że walktrap jest szczególnie przydatny

Omar Jaafor
źródło
Chociaż może to być związane z pytaniem, nie wydaje się, że jest to odpowiedź.
Michael R. Chernick
2
odpowiedziałem na dwa pytania: Czy istnieje pakiet „R”, który odpowiednio klastruje węzły w sieci? Czy możesz mi wskazać przykładowy kod, aby to zrobić? Ale tak, to nie odpowiada na cały zestaw pytań.
Omar Jaafor