A novel user-centric method for graph summarization considering syntactical and semantical attributes

In this paper, we proposed a user-interactive and knowledge-based method for summarizing graphs based on both structure and vertex attributes. Because of being interactive method, a user can decide to stop or continue summarization process at any step based on the resulted summary. The proposed method is a general method that covers three kinds of graph summarization named structural, attribute-based and structural/attribute-based summarization. In summarization based on both the structure and attributes, the contributions of syntactical and semantical attributes and also the importance degrees of attributes are variable and can be specified by the user. We also proposed a new criterion based on density and entropy to evaluate the quality of a hybrid summary. In the aims of evaluation, we generated a synthetic graph with 1000 nodes and 2500 edges and extracted the overall features of the graph using the Gephi tool and a new developed application in Java. Finally, we generated summaries with different sizes and different values for the structure contribution (α parameter). We calculated the values of density and entropy for each summary in order to measure their qualities based on the proposed criterion. The experimental results show that the proposed criterion causes to generate a summary with a better quality.