WebGraph

WebGraph jest ramy studiować wykres internetowej. WebGraph zapewnia proste sposoby zarządzania bardzo duże wykresy, wykorzystując nowoczesne techniki kompresji. Dokładniej, jest on obecnie z:
1. zestaw kodów płaskich, zwane kody, które są szczególnie odpowiednie do przechowywania wykresy internetowych (lub w ogóle, liczby całkowite z dystrybucji mocy prawa w pewnym zakresie wykładnik). Fakt, że te kody działają dobrze można łatwo sprawdzić empirycznie, ale również staramy się przedstawić szczegółową analizę matematyczną.
2. Algorytmy kompresji wykresy internetowych, które wykorzystują luki i referentiation kompresji (la LINK), intervalisation i kodów, aby zapewnić wysoki współczynnik kompresji: na przykład, wykres WebBase (2001 indeksowania) jest skompresowany w 3,08 bitów na łączu, a migawka z około 18,5 milionów stron w domenie .pl zebranych przez UbiCrawler jest skompresowany w 2,22 bitów na łączu (odpowiednie wskaźniki dla transpozycji wykresy są 2,89 bitów na linku i 1,98 bitów na link). Algorytmy są kontrolowane przez kilka parametrów, które zapewniają różne kompromisy między szybkość dostępu i stopniu sprężania.
3. Algorytmy dostępu do skompresowanego wykresu bez konieczności dekompresji, przy użyciu technik, które opóźniają leniwymi w dekompresji, dopóki nie jest rzeczywiście konieczne.
4. kompletna, udokumentowana wdrożenie algorytmów powyżej w Javie, zawarte w it.unimi.dsi.webgraph pakietu. Poza tym wyraźnie określonym API, pakiet zawiera kilka klas, które pozwalają modyfikować (np transpozycji) lub rekompresji wykres, więc eksperymentować z różnymi ustawieniami. Pakiet opiera się na fastutil w ramach kolekcji specyficznego typu, o wysokiej wydajności, na MG4J na poziomie bitów I / O, na dystrybucji COLT dla gotowych do użycia, wydajnych algorytmów i na GNU getopt dla linii poleceń parsowania.
5. Zestawy danych dla bardzo dużych wykresu (np mld linków). Są one albo zebrane ze źródeł publicznych (takich jak WebBase), lub wyprodukowane przez UbiCrawler.
W końcu, z WebGraph można uzyskać dostęp i analizować bardzo duży wykres internetowej, nawet na komputerze z zaledwie 256 MB pamięci RAM. Korzystanie WebGraph jest równie łatwe jak instalacja kilku pliki jar i pobieranie zestawu danych. To sprawia, że ​​badanie zjawisk, takich jak PageRank, dystrybucji właściwości wykresu wykres internetowej itp bardzo łatwe

Co nowego w tym wydaniu:.

• W tej wersji dodano kilka usprawnień HyperANF oraz kilka poprawek błędów.
• WebGraph można teraz znaleźć na Maven Central.

Co nowego w wersji 2.4.5:

• Ta wersja zawiera implementację HyperANF, nowa wysoce skalowalne algorytm do obliczania funkcji sąsiedztwa grafu i metody, które obliczają średnią najkrótszą drogę i innych danych pochodzących z funkcji sąsiedztwa.
• Ponadto, wiele danych statystycznych jest teraz obliczana podczas kompresji.

Co nowego w wersji 2.4.4:.

• Niektóre stare opcje zostały usunięte
• Pliki własności teraz zawierają mnóstwo przydatnych statystyk.
• Losowe łącze została poprawiona.

Co nowego w wersji 2.4.3:

• Poprawiono ArrayListMutableGraph.addNodes () (dzięki Erik Lumer na znalezienie i naprawienie tego błędu).
• Nowe opcje do zmiany wyjście wykresów ASCII.
• RemappedImmutableGraph.successorArray (x) został zapewniając taką samą tablicę na każde wezwanie, dzięki czemu odziedziczone następców (x) Metoda nadaje się do użytku do skanowania w równoległych różnych list. Stała (obecnie zwraca kopię tablicy, zamiast).
• Nowa transformacja losowa permutuje losowo wykres.

Co nowego w wersji 2.4.2:

• nowej & quot; komponowania & quot; konstrukt pozwala komponować (ARC znakowanej) wykresów.