WebGraph

WebGraph är ett ramverk för att studera webb grafen. WebGraph ger enkla sätt att hantera mycket stora grafer, utnyttjar modern komprimeringstekniker. Närmare bestämt är det för närvarande görs av:
1. En uppsättning platta koder, så kallade koder, som är särskilt lämpliga för att lagra webb grafer (eller, i allmänhet, heltal med power-lag distribution i ett visst exponent intervall). Det faktum att dessa koder fungerar bra kan lätt testas empiriskt, men vi försöker också ge en detaljerad matematisk analys.
2. Algoritmer för att komprimera webb grafer som utnyttjar gap komprimering och referentiation (la LÄNK), intervalisation och koder för att ge ett högt kompressionsförhållande: till exempel, är det WebBase grafen (2001 crawl) komprimeras vid 3,08 bitar per länk, och en ögonblicksbild cirka 18.500.000 sidor i .uk domän som samlats in av UbiCrawler komprimeras vid 2.22 bitar per länk (motsvarande siffror för de införlivade grafer är 2.89 bitar per länk och 1,98 bitar per länk). Algoritmerna styrs av flera parametrar, som ger olika avvägningar mellan åtkomsthastighet och kompressionsförhållande.
3. Algoritmer för att komma åt en komprimerad graf utan att faktiskt dekomprimering det, med hjälp av lata tekniker som försenar dekompression tills det är faktiskt nödvändigt.
4. En komplett, dokumenterat genomförande av algoritmerna ovan i Java, som ingår i paketet it.unimi.dsi.webgraph. Förutom en tydligt definierad API, innehåller paketet flera klasser som gör att ändra (t.ex. transponera) eller komprimera en graf, så att experimentera med olika inställningar. Paketet bygger på fastutil en ram typ specifikt, högpresterande samlingar, på MG4J för bit-nivå I / O, om COLT fördelningen för färdiga att använda, effektiva algoritmer och på GNU getopt för linjekommandot pars.
5. Datauppsättningar för mycket stora graf (t.ex. en miljard av länkar). Dessa är antingen hämtas från offentliga källor (t.ex. WebBase), eller produceras av UbiCrawler.
I slutändan, med WebGraph kan du komma åt och analysera en mycket stor webbsida graf, även på en dator med så lite som 256 MB RAM-minne. Att använda WebGraph är lika enkelt som att installera några jar-filer och ladda ner en datamängd. Detta gör studerar fenomen som Pagerank, distribution av graf egenskaper hos webb grafen, etc. mycket lätt

Vad är nytt i den här versionen:.

• Denna version lägger till flera förbättringar HyperANF och några buggfixar.
• WebGraph kan nu hittas på Maven Central.

Vad är nytt i version 2.4.5:

• Denna version innehåller en implementering av HyperANF, ett nytt mycket skalbar algoritm för beräkning trakten funktionen av en kurva, och metoder som beräknar den genomsnittliga kortaste vägen och andra härledda data från trakten funktionen.
• Dessutom en mängd statistiska uppgifter är nu beräknad under kompression.

Vad är nytt i version 2.4.4:.

• Några gamla alternativ har tagits bort
• Fastighets filer innehåller numera en uppsjö av användbar statistik.
• Random tillgång hastighet har förbättrats.

Vad är nytt i version 2.4.3:

• Fasta ArrayListMutableGraph.addNodes () (tack till Erik Lumer för att hitta och rätta felet).
• Nya alternativ för att flytta produktionen av ASCII grafer.
• RemappedImmutableGraph.successorArray (x) var att ge samma array på varje samtal, vilket gör de ärvda efterträdare (x) metoden oanvändbar för att skanna i parallella olika listor. Fast (nu den returnerar en kopia av arrayen, i stället).
• Ny slumpmässig omvandling som permutes slumpmässigt en graf.

Vad är nytt i version 2.4.2:

• En ny & quot; komponera & quot; konstruera gör det möjligt att komponera (arc-märkta) grafer.