Dynamic graph summarization is the task of obtaining and updating a summary of the current snapshot of a dynamic graph when changes (edge insertions/deletions) occur in the graph. As real graphs are massive and undergoing lots of changes, we need dynamic summarization algorithms that scale and are able to respond rapidly to changes in the graph. In this paper, we present two algorithms for lossless summarization of dynamic graphs. We first give an algorithm (Optimal) that is able to obtain and dynamically update the smallest-possible-anytime lossless summary in terms of node reduction. We achieve up to 8 orders of magnitude running time improvement over batch counterparts, and up to 12x improvement over the state-of-art in dynamic graph summarization, while at the same time offering up to 6x improvement in node reduction. We then present an even faster lossless summarization algorithm (Scalable), which goes further into speeding up dynamic updates by offering an additional order of magnitude improvement over Optimal at the cost of having lesser node reduction. Extensive experiments show that Scalable offers node reduction rates that are close to those of Optimal for many datasets. As such, Scalable is a preferred choice when speed of change is very high.

We present new algorithms for graph summarization where the loss in utility is fully controllable by the user. Specifically, we make three key contributions. First, we present a utility-driven graph summarization method G-SCIS, based on a clique and independent set decomposition, that produces optimal compression with zero loss of utility. The compression provided is significantly better than state-of-the-art in lossless graph summarization, while the runtime is two orders of magnitude lower. Second, we propose a highly scalable, utility-driven algorithm, T-BUDS, for fully controlled lossy summarization. It achieves high scalability by combining memory reduction using Maximum Spanning Tree with a novel binary search procedure. T-BUDS outperforms state-of-the-art drastically in terms of the quality of summarization and is about two orders of magnitude better in terms of speed. In contrast to the competition, we are able to handle web-scale graphs in a single machine without performance impediment as the utility threshold (and size of summary) decreases. Third, we show that our graph summaries can be used as-is to answer several important classes of queries, such as triangle enumeration, Pagerank and shortest paths.

Summarizing graphs is of paramount importance due to diverse applications of large-scale graph analysis. A popular family of summarization methods is the group-based approach. The general idea consists of merging nodes of the original graph into supernodes of the summary graph, encoding original edges into superedges/correction set edges, and dropping certain superedges or correction set edges (for lossy summarization). The current state of the art has several steps in its computation that are serious bottlenecks in terms of running time and scalability. In this work, we propose algorithm LDME, a correction set based graph summarization algorithm that produces compact output representations in a fast and scalable manner. To achieve this, we introduce (1) weighted locality sensitive hashing to drastically reduce the number comparisons required to find good node merges, (2) an efficient way to compute the best quality merges that produces more compact outputs, and (3) a new sort-based encoding algorithm that is faster and more robust. More interestingly, our algorithm provides performance tuning settings to allow the option of trading compression for running time. On high compression settings, LDME achieves compression equal to or better than the state of the art with up to 53x speedup in running time. On high speed settings, LDME achieves up to two orders of magnitude speedup with only slightly lower compression.

Community detection is considered as a fundamental task in analyzing social networks. Even though many techniques have been proposed for community detection, most of them are based exclusively on the connectivity structures. However, there are node features in real networks, such as gender types in social networks, feeding behavior in ecological networks, and location on e-trading networks, that can be further leveraged with the network structure to attain more accurate community detection methods. We propose a novel probabilistic graphical model to detect communities by taking into account both network structure and nodes' features. The proposed approach learns the relevant features of communities through a generative probabilistic model without any prior assumption on the communities. Furthermore, the model is capable of determining the strength of node features and structural elements of the networks on shaping the communities. The effectiveness of the proposed approach over the state-of-the-art algorithms is revealed on synthetic and benchmark networks.