Jak obliczyć miary centralności w 4 milionowej sieci brzegowej za pomocą R?

9

Mam plik CSV z 4 milionami krawędzi ukierunkowanej sieci reprezentującej osoby komunikujące się ze sobą (np. John wysyła wiadomość do Mary, Mary wysyła wiadomość do Ann, John wysyła inną wiadomość do Mary itp.). Chciałbym zrobić dwie rzeczy:

  1. Znajdź stopnie, miary między (a może) centralność wektora własnego dla każdej osoby.

  2. Uzyskaj wizualizację sieci.

Chciałbym to zrobić w wierszu polecenia na serwerze Linux, ponieważ mój laptop nie ma dużej mocy. Mam zainstalowany R na tym serwerze i bibliotece statnet. Znalazłem ten post w 2009 roku kogoś bardziej kompetentnego ode mnie, próbującego zrobić to samo i mającego z tym problemy. Zastanawiałem się więc, czy ktokolwiek ma jakieś wskazówki, jak to zrobić, najlepiej krok po kroku, ponieważ wiem tylko, jak załadować plik CSV i nic więcej.

Aby dać Ci wyobrażenie, tak wygląda mój plik CSV:

$ head comments.csv
    "src","dest"
    "6493","139"
    "406705","369798"
$ wc -l comments.csv 
4210369 comments.csv
amh
źródło
dla niektórych z tych miar to, czy R może to obsłużyć, czy notatkę, będzie zależeć od liczby osobnych osób (węzłów) w sieci. R niekoniecznie musi być najlepszym narzędziem do obliczeń. Jest facet o nazwisku Leskovec, który był w Carnegie Mellon --- myślę, że jako student --- zrobił wiele rzeczy z opisowymi statystykami na dużych wykresach. Istnieje wiele narzędzi do „wizualizacji” wykresów, ale przede wszystkim stwierdziłem, że są one dość trudne do interpretacji lub mają sens. Rysowanie tylko rozkładów stopni może być pierwszym początkiem.
kardynał
Nawet wykreślenie 4 milionów punktów może trochę potrwać ...
Wok
@wok, nah. Bułka z masłem na dzisiejszych komputerach. W każdym razie zawsze możesz najpierw zrzucić plik PNG, co prawdopodobnie wystarczy na rozkład stopni. Wykres OP nie jest wcale taki duży.
kardynał

Odpowiedzi:

7

To, co masz, to lista brzegowa, którą można przekształcić w obiekt sieciowy za pomocą biblioteki sieciowej. Oto przykład wykorzystujący fikcyjne dane.

library(network)

src <- c("A", "B", "C", "D", "E", "B", "A", "F")
dst <- c("B", "E", "A", "B", "B", "A", "F", "A")

edges <- cbind(src, dst)
Net <- as.network(edges, matrix.type = "edgelist")

summary(Net)
plot(Net)

Jednak ostrzeżenie jest w porządku: masz bardzo dużą sieć i nie jestem pewien, czy fabuła będzie tak pouczająca. Prawdopodobnie będzie to wyglądać jak duża kula przędzy. Nie jestem również pewien, jak dobrze te biblioteki radzą sobie z tak dużymi zestawami danych. Proponuję zapoznać się z dokumentacją bibliotek sieciowych, statnet i ergm. Journal of Statistical Software (V24 / 3) oferuje kilka artykułów dotyczących tych bibliotek. Problem można znaleźć tutaj:

http://www.jstatsoft.org/v24

Jason Morgan
źródło
1
Niejasno pamiętam mapę świata sieci Facebook, która została wykonana w R. Myślę, że autor opisał swój proces bardziej szczegółowo na swoim blogu. Przypuszczam, że zastosowanie tego podejścia wygenerowałoby mapę, która byłaby pouczająca nawet przy 4 milionach węzłów.
Owe Jessen
Przepraszamy za naiwne pytanie, ale jak przekonwertować tabelę na to, co masz jako srci dst. Tak zazwyczaj robię, aby załadować plik (teraz plik rozdzielany tabulatorami): el <- read.csv("comment-net/comments-ouids.tsv",header=T,sep="\t")
amh
Funkcja read.csv () powinna wygenerować ramkę danych. as.network () może przeczytać to bezpośrednio lub być może będziesz musiał zrobić as.matrix (el).
Jason Morgan
Jestem raczej sceptycznie nastawiony do tego, że te biblioteki mogą wiele zrobić z wykresem milionów węzłów. Czy rzeczywiście używałeś ich z porównywalnymi zestawami danych?
Szabolcs
Plakat dotyczył sieci o 4 milionach krawędzi , a nie węzłów. Korzystałem z statnetrodziny bibliotek w nieukierunkowanej sieci złożonej z ponad 3500 węzłów (~ 8 milionów możliwych krawędzi). Było to całkiem wykonalne, zwłaszcza gdy celem było po prostu obliczenie statystyk sieciowych. Oszacowałem nawet ERGM w sieciach tej wielkości. Ale twój punkt widzenia jest słuszny; Wątpię, czy sieci milionów węzłów można łatwo przeanalizować.
Jason Morgan
3

Nie sądzę, że R jest tutaj pierwszym wyborem (może się mylę). Będziesz potrzebował tutaj ogromnych tablic, aby zindeksować i przygotować pliki sieciowe w odpowiednim formacie danych. Przede wszystkim spróbuję użyć biblioteki SNAP Jure'a (Rob wspomniał o nim w powyższym poście) ; jest napisany w C ++ i działa bardzo dobrze w dużych sieciach.

Andrej
źródło
Dzięki za wzmiankę o SNAP. Patrzę na to. Użyłeś tego? Dołączona do niej próbka centralności wydaje się bliska temu, czego chcę. Próbowałem go zmodyfikować, aby działał z moimi wielokierunkowymi danymi grafowymi, ale nie udało się go skompilować. Nie jestem pewien, czy należy zadać pytanie na ten temat tutaj, więc mogę utworzyć nowe pytanie.
amh
1
@ andresmh, możesz najpierw spróbować zmniejszyć wykres, aby mieć pojedynczą obserwację na parę kierowaną. W przypadku wartości własnych dane są prawdopodobnie podobne lub równoważne losowemu spacerowi na wykresie. Nie jestem pewien, czy SNAP to obsługuje, ale prawdopodobnie tak jest. Jeśli wszystko inne zawiedzie, możesz wysłać bardzo konkretny e-mail do Jure. Jest bardzo miłym facetem, więc nie zdziwiłbym się, gdyby udzielił szybkich wskazówek.
kardynał
@cardinal: Znalazłem przykładowy kod w SNAP, który robi dokładnie to, co chcę, ale dla niekierowanego wykresu. Myślę, że mój wykres jest tym, co dokumenty SNAP nazywają „ukierunkowanym multi-wykresem”. Więc zmieniłem tylko jedną linię centrality.cppz TUNGraphna TNEGraph(patrz pastebin.com/GHUquJvT linia 24). To się już nie kompiluje. Podejrzewam, że wymaga innego typu węzła? Występuje błąd: centrality.cpp:24: error: conversion from ‘TUNGraph::TNodeI’ to non-scalar type ‘TNEGraph::TNodeI’ requested(zobacz pełny błąd na pastebin.com/86mCbByG )
amh
3

Gephi ( http://gephi.org/ ) może być łatwym sposobem na eksplorację danych. Prawie na pewno możesz to zwizualizować i wykonać pewne obliczenia (chociaż nie używałem go od jakiegoś czasu, więc nie pamiętam wszystkich funkcji).

celenius
źródło
3

Na podstawie dotychczasowych doświadczeń z siecią 7 milionów węzłów, myślę, że wizualizacja całej sieci da niezrozumiały obraz. Mogę zasugerować różne wizualizacje przy użyciu podzbiorów danych, takich jak użycie 10 najlepszych węzłów z największą liczbą linków przychodzących lub wychodzących. Drugą sugestię celeniusa dotyczącą używania gephi.

Zubin
źródło
@andresmh, Maslov i Sneppen ( Science , 2002) mają wizualizację, która może być przydatna w tym kontekście. Przeszukując ostatnich statystykach / comp-sci - Powiązane cytowań tej pracy, znalazłem to jak dobrze. Oto kolejna powiązana praca.
kardynał
1

Jeśli martwisz się rozmiarem sieci, możesz wypróbować igraphpakiet w R. A jeśli działa on słabo w R, może działać lepiej jako moduł Pythona. Lub nawet networkxpakiet dla Pythona

fioghual
źródło
1

Czy podejrzewasz, że sieć ma niewielką liczbę bardzo dużych podłączonych komponentów? Jeśli nie, możesz go rozłożyć na odrębne komponenty, co znacznie ułatwi obliczenie miar centralności.

Michael Bishop
źródło
+1 do tego - jeśli jest to całkowicie podłączony komponent, to jedno, ale jeśli możesz zdekomponować sieć, masz zarówno mniejsze dane, jak i kilka niezależnych sieci, które można analizować równolegle.
Fomite
1

Można użyć kilku pakietów oprogramowania R, w tym „sna” i „sieć”. Jedną z rzeczy, nie koniecznie polegać na, jeśli masz problemy z wydajnością z SNA jest NetworkX. Uwielbiam NetworkX na śmierć i używam go do większości moich analiz, ale NetworkX jest dumny z tego, że jest implementacją czysto pytonową. Nie wykorzystuje szczególnie dobrze szybkiego, wstępnie skompilowanego kodu, a sna często znacznie wyprzedza NetworkX.

Fomite
źródło