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

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:

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ę.

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)

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.

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.

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