View article

Computer-implemented techniques for lossless and lossy summarization of large-scale graphs. Beneficially, the loss less summarization process is designed such that it can be performed in a parallel processing manner. In addition, the lossless summarization process is designed such that it can be performed with having to store only a certain small number of adjacency list node objects in-memory at once and without having to store an adjacency list representation of the entire input graph in-memory at once. In some embodiments, the techniques involve further summarizing the reduced graph output from the lossless summarization process in a lossy manner. Beneficially, the lossy summari zation process uses a condition that is computationally efficient to evaluate when determining whether to drop edges of the reduced graph while at the same time ensuring the accuracy of a graph restored from the lossy …