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ę.
r
clustering
data-visualization
numerics
EngrStudent
źródło
źródło
igraph
pakietu R.Odpowiedzi:
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
igraph
pakietu 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).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.
źródło
igraph
sieć.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.
źródło
Dla przyszłych czytelników
Oto zestaw funkcji z pakietów igraph, a ostatni z MCL:
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
źródło