WebGraph

WebGraph er en ramme for at studere på nettet grafen. WebGraph indeholder enkle måder at håndtere meget store grafer, der udnytter moderne komprimeringsteknikker. Mere præcist er det i øjeblikket består af:
1. Et sæt af flade koder, kaldet koder, som er særligt egnet til opbevaring web grafer (eller generelt, heltal med power-lov distribution i et bestemt eksponent interval). Det forhold, at disse koder fungerer godt let kan testes empirisk, men vi forsøger også at give en detaljeret matematisk analyse.
2. Algoritmer til komprimering web grafer, der udnytter hul kompression og referentiation (la LINK), intervalisation og koder til at give en høj kompressionsforhold: for eksempel, er det WebBase grafen (2001 crawl) komprimeret ved 3.08 bit pr link, og et snapshot af omkring 18.500.000 sider af .uk domænet indsamlet af UbiCrawler komprimeres ved 2.22 bits per link (de tilsvarende tal for de gennemførte grafer er 2,89 bits per link og 1,98 bit pr link). De algoritmer styres af flere parametre, som giver forskellige kompromiser mellem adgang hastighed og kompressionsforhold.
3. Algoritmer for adgang til en komprimeret graf uden egentlig dekomprimere det, ved hjælp dovne teknikker, som forsinker dekompression, indtil det er faktisk nødvendigt.
4. En komplet, dokumenteret gennemførelse af algoritmer ovenfor i Java, der er indeholdt i pakken it.unimi.dsi.webgraph. Udover en klart defineret API, pakken indeholder flere klasser, der tillader at ændre (f.eks gennemførelse) eller komprimere en graf, så at eksperimentere med forskellige indstillinger. Pakken afhængig fastutil for en ramme typespecifikke, højtydende samlinger, om MG4J for bit-niveau I / O, om COLT fordeling for klar-til-brug, effektive algoritmer og GNU getopt til line-kommando parsing.
5. datasæt for meget stor graf (fx en milliard af links). Disse er enten indsamlet fra offentlige kilder (såsom WebBase) eller er fremstillet af UbiCrawler.
I sidste ende, med WebGraph kan du få adgang til og analysere et meget stort web graf, selv på en pc med så lidt som 256 MB RAM. Brug WebGraph er så let som at installere et par jar filer og downloade et datasæt. Dette gør at studere fænomener som PageRank, distribution af graf egenskaber af web graf osv meget let

Hvad er nyt i denne udgivelse:.

• Denne version tilføjer flere forbedringer HyperANF og et par fejlrettelser.
• WebGraph kan nu findes på Maven Central.

Hvad er nyt i version 2.4.5:

• Denne version indeholder en implementering af HyperANF, en ny meget skalerbar algoritme til beregning nabolaget funktion af en graf, og metoder, der beregner gennemsnittet korteste vej og andre afledte data fra kvarteret funktionen.
• Desuden et væld af statistiske oplysninger er nu beregnet under kompression.

Hvad er nyt i version 2.4.4:.

• Nogle gamle muligheder er blevet fjernet
• Ejendommen filer indeholder nu et væld af nyttige statistikker.
• Random adgang hastighed er blevet forbedret.

Hvad er nyt i version 2.4.3:

• Faste ArrayListMutableGraph.addNodes () (tak til Erik Lumer til at finde og fastsættelse af denne fejl).
• Nye muligheder for at flytte produktionen af ​​ASCII grafer.
• RemappedImmutableGraph.successorArray (x) blev levere den samme array på alle opkald, og dermed gøre de nedarvede efterfølgere (x) Metode ubrugelig til at scanne i parallelle forskellige lister. Fast (nu den returnerer en kopi af array i stedet).
• Ny tilfældig transformation, permuterer tilfældigt en graf.

Hvad er nyt i version 2.4.2:

• En ny & quot; komponere & quot; konstruere gør det muligt at sammensætte (bue-mærket) grafer.