WebGraph
WebGraph is a framework for graph compression aimed at studying web graphs. It provides simple ways to manage very large graphs, exploiting modern compression techniques. More precisely, it is currently made of: A set of flat codes, called ζ codes, which are particularly suitable for storing web graphs (or, in general, integers with power-law distribution in a certain exponent range). The fact that these codes work well can be easily tested empirically, but we also try to provide a detailed mathematical analysis. Algorithms for compressing web graphs that exploit gap compression and referentiation (à la LINK), intervalisation and ζ codes to provide a high compression ratio (see our datasets). The algorithms are controlled by several parameters, which provide different tradeoffs between access speed and compression ratio. Algorithms for accessing a compressed graph without actually decompressing it, using lazy techniques that delay the decompression until it is actually necessary. Algorithms for analysing very large graphs, such as HyperBall, which has been used to show that Facebook has just four degrees of separation. A complete, documented implementation of the algorithms above in Java distributed under the GNU General Public License. Besides a clearly defined API, we also provide several classes tha modify (e.g., transpose) or recompress a graph, so to experiment with various settings. Datasets for very large graph (e.g., a billion of links). These are either gathered from public sources (such as WebBase), or produced by UbiCrawler and BUbiNG. In the end, with WebGraph you can access and analyse very large web graphs. Using WebGraph is as easy as installing a few jar files and downloading a dataset. This makes studying phenomena such as PageRank, distribution of graph properties of the web graph, etc. very easy.
Keywords for this software
References in zbMATH (referenced in 51 articles )
Showing results 1 to 20 of 51.
Sorted by year (- Davis, Timothy A.; Hager, William W.; Kolodziej, Scott P.; Yeralan, S. Nuri: Algorithm 1003: Mongoose, a graph coarsening and partitioning library (2020)
- Ferres, Leo; Fuentes-Sepúlveda, José; Gagie, Travis; He, Meng; Navarro, Gonzalo: Fast and compact planar embeddings (2020)
- Liang, Yuzhi; chen, Chen; Wang, Yukun; Lei, Kai; Yang, Min; Lyu, Ziyu: Reachability preserving compression for dynamic graph (2020)
- Bringmann, Karl; Keusch, Ralph; Lengler, Johannes: Geometric inhomogeneous random graphs (2019)
- Joana M. F. da Trindade, Konstantinos Karanasos, Carlo Curino, Samuel Madden, Julian Shun: Kaskade: Graph Views for Efficient Graph Analytics (2019) arXiv
- Pothen, Alex; Ferdous, S. M.; Manne, Fredrik: Approximation algorithms in combinatorial scientific computing (2019)
- Shen, Zhao-Li; Huang, Ting-Zhu; Carpentieri, Bruno; Wen, Chun; Gu, Xian-Ming; Tan, Xue-Yuan: Off-diagonal low-rank preconditioner for difficult PageRank problems (2019)
- van der Hoorn, Pim; Olvera-Cravioto, Mariana: Typical distances in the directed configuration model (2018)
- Bringmann, Karl; Keusch, Ralph; Lengler, Johannes: Sampling geometric inhomogeneous random graphs in linear time (2017)
- Broß, Jan; Gog, Simon; Hauck, Matthias; Paradies, Marcus: Fast construction of compressed web graphs (2017)
- Khan, Kifayat Ullah; Dolgorsuren, Batjargal; Anh, Tu Nguyen; Nawaz, Waqas; Lee, Young-Koo: Faster compression methods for a weighted graph using locality sensitive hashing (2017)
- Lamm, Sebastian; Sanders, Peter; Schulz, Christian; Strash, Darren; Werneck, Renato F.: Finding near-optimal independent sets at scale (2017)
- Mania, Horia; Pan, Xinghao; Papailiopoulos, Dimitris; Recht, Benjamin; Ramchandran, Kannan; Jordan, Michael I.: Perturbed iterate analysis for asynchronous stochastic optimization (2017)
- Navlakha, Saket: Learning the structural vocabulary of a network (2017)
- Riondato, Matteo; García-Soriano, David; Bonchi, Francesco: Graph summarization with quality guarantees (2017)
- Shen, Zhao-Li; Huang, Ting-Zhu; Carpentieri, Bruno; Gu, Xian-Ming; Wen, Chun: An efficient elimination strategy for solving PageRank problems (2017)
- Zhao, Junzhou; Wang, Pinghui; Lui, John C. S.; Towsley, Don; Guan, Xiaohong: I/O-efficient calculation of (H)-group closeness centrality over disk-resident graphs (2017)
- Akiba, Takuya; Iwata, Yoichi: Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover (2016)
- Crespelle, Christophe; Le, Tien-Nam; Perrot, Kevin; Phan, Thi Ha Duong: Linearity is strictly more powerful than contiguity for encoding graphs (2016)
- Firmani, Donatella; Georgiadis, Loukas; Italiano, Giuseppe F.; Laura, Luigi; Santaroni, Federico: Strong articulation points and strong bridges in large scale graphs (2016)