WebGraph

WebGraph est un cadre pour étudier le graphe du web. WebGraph fournit des moyens simples pour gérer de très grands graphes, en exploitant des techniques de compression modernes. Plus précisément, il est constitué de:
1. Un ensemble de codes plates, appelées codes, qui sont particulièrement appropriés pour stocker graphiques Web (ou, en général, des entiers avec une distribution en loi de puissance dans une certaine gamme d'exposant). Le fait que ces codes fonctionnent bien peut être facilement testée empiriquement, mais nous essayons aussi de fournir une analyse mathématique détaillée.
2. algorithmes de compression de graphiques web qui exploitent la compression des écarts et référenciation (la LINK), intervalisation et les codes pour fournir un taux de compression élevé: par exemple, le graphique WebBase (2001 crawl) est comprimée à 3,08 bits par lien, et un instantané d'environ 18.500.000 pages du domaine .uk recueillies par UbiCrawler est comprimée à 2,22 bits par lien (les chiffres correspondants pour les graphiques sont transposées 2,89 bits par lien et 1,98 bits par lien). Les algorithmes sont commandés par plusieurs paramètres, qui fournissent différents compromis entre la vitesse d'accès et le taux de compression.
3. Algorithmes pour accéder à un graphique comprimé sans vraiment décompresser, en utilisant des techniques paresseux qui retardent la décompression jusqu'à ce qu'il est réellement nécessaire.
4. Une complet, documenté mise en œuvre des algorithmes ci-dessus en Java, contenue dans l'emballage it.unimi.dsi.webgraph. Outre une API bien définie, le package contient plusieurs classes qui permettent de modifier (par exemple, la transposition) ou recompresser un graphique, afin d'expérimenter avec différents réglages. Le paquet repose sur fastutil d'un cadre de collections spécifique de type, haute performance, sur MG4J pour le niveau bits d'E / S, sur la distribution de COLT pour des algorithmes efficaces prêts à l'emploi et sur GNU getopt pour la ligne-commande analyse.
5. Les ensembles de données à très grande graphique (par exemple, d'un milliard de liens). Ceux-ci sont soit recueillies auprès de sources publiques (comme WebBase), ou produits par UbiCrawler.
En fin de compte, avec WebGraph vous pouvez accéder et d'analyser un très grand graphe du web, même sur un PC avec aussi peu que 256 Mo de RAM. Utilisation WebGraph est aussi facile à installer quelques fichiers jar et le téléchargement d'un ensemble de données. Cela rend l'étude des phénomènes tels que PageRank, la distribution des propriétés des graphes du graphe du web, etc. très facile

Ce qui est nouveau dans cette version:.

• Cette version ajoute plusieurs améliorations à HyperANF, et corrige quelques bogues.
• WebGraph peut maintenant être trouvé sur Maven Central.

Quoi de neuf dans la version 2.4.5:

• Cette version contient une mise en œuvre de HyperANF, une nouvelle algorithme hautement évolutive pour calculer la fonction de voisinage d'un graphe, et les méthodes qui calculent le plus court chemin moyenne et d'autres données provenant de la fonction de voisinage.
• De plus, une multitude de données statistiques est désormais calculée lors de la compression.

Quoi de neuf dans la version 2.4.4:.

• Certaines anciennes options ont été supprimées
• Les fichiers de propriétés contiennent maintenant une mine de statistiques utiles.
• la vitesse d'accès aléatoire a été amélioré.

Ce qui est nouveau dans la version 2.4.3:

• ArrayListMutableGraph.addNodes fixes () (merci à Erik Lumer pour trouver et corriger ce bug).
• Nouvelles options pour décaler la sortie de graphiques ASCII.
• RemappedImmutableGraph.successorArray (x) fournissait le même tableau à chaque appel, rendant ainsi les successeurs héréditaires (x) de la méthode inutilisable à analyser dans différentes listes parallèles. Fixe (maintenant il renvoie une copie du tableau, à la place).
• New transformation aléatoire qui permute au hasard un graphique.

Quoi de neuf dans la version 2.4.2:

• Un nouveau & quot; composer & quot; construire permet de composer (arc-étiqueté) graphiques.