A Novel User-Centric Method for Graph Summarization Based on Syntactical and Semantical Attributes
Subject Areas : Pervasive computingNosratali Ashrafi Payaman 1 , Mohammadreza Kangavari 2 *
1 - Iran University of Science and Technology
2 - Iran University of Science and Technology
Keywords: Graph summarization, , summary graph, , super-node, , semantical summarization,
Abstract :
In this paper, we proposed an interactive knowledge-based method for graph summarization. Due to the interactive nature of this method, the user can decide to stop or continue summarization process at any step based on the summary graph. The proposed method is a general one that covers three kinds of graph summarization called structural, attribute-based, and structural/attribute-based summarization. In summarization based on both structure and vertex attributes, the contributions of syntactical and semantical attributes, as well as the importance degrees of attributes are variable and could be specified by the user. We also proposed a new criterion based on density and entropy to assess the quality of a hybrid summary. For the purpose 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 developed application in Java. Finally, we generated summaries of different sizes and values for the structure contribution (α parameter). We calculated the values of density and entropy for each summary to assess their qualities based on the proposed criterion. The experimental results show that the proposed criterion causes to generate a summary with better quality.
[1] U. Kang, “Mining Tera-Scale Graphs: Theory, Engineering and Discoveries,” 2012.
[2] “Facebook active users.” [Online]. Available: https://www.yahoo.com/news/number-active-users-facebook-over-230449748.html.
[3] S. Navlakha, R. Rastogi, and N. Shrivastava, “Graph summarization with bounded error,” Proc. 2008 ACM SIGMOD Int. Conf. Manag. data - SIGMOD ’08, p. 419, 2008.
[4] K. LeFevre and E. Terzi, “GraSS: Graph Structure Summarization,” Proc. 2010 SIAM Int. Conf. Data Min., pp. 454–465, 2010.
[5] N. Zhang, Y. Tian, and J. M. Patel, “Discovery-driven graph summarization,” 2010 IEEE 26th Int. Conf. Data Eng. (ICDE 2010), pp.
880–891, 2010.
[6] M. A. Beg, M. Ahmad, A. Zaman, and I. Khan, “Scalable approximation algorithm for graph summarization,” Lect. Notes Comput. Sci.
(including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 10939 LNAI, pp. 502–514, 2018.
[7] Y. Liu, T. Safavi, N. Shah, and D. Koutra, “Reducing large graphs to small supergraphs: a unified approach,” Soc. Netw. Anal. Min., vol. 8, no. 1, 2018.
[8] Y. Tian, R. A. Hankins, and J. M. Patel, “Efficient Aggregation for Graph Summarization,” pp. 567–579.
[9] Y. Bei, Z. Lin, and D. Chen, “Summarizing scale-free networks based on virtual and real links,” Phys. A Stat. Mech. its Appl., vol. 444, no. 2, pp. 360–372, 2016.
[10] H. Cheng, Y. Zhou, and J. X. Yu, “Clustering Large Attributed Graphs: A Balance between Structural and Attribute Similarities,” ACM Trans. Knowl. Discov. Data, vol. 5, no. 2, pp. 1–33, 2011.
[11] M. Riondato, D. García-Soriano, and F. Bonchi, “Graph summarization with quality guarantees,” Data Min. Knowl. Discov., vol. 31, no. 2, pp. 314–349, 2017. [12] X. Liu, Y. Tian, Q. He, W.-C. Lee, and J. McPherson, “Distributed Graph Summarization,” Proc. 23rd ACM Int. Conf. Conf. Inf. Knowl. Manag. - CIKM ’14, pp. 799–808, 2014. [13] C. Chen, C. X. Lin, M. Fredrikson, M. Christodorescu, X. Yan, and J. Han, “Mining graph patterns efficiently via randomized summaries,” Proc. VLDB Endow., vol. 2, no. 1, pp. 742–753, 2009.
[14] S. Hosseini, H. Yin, M. Zhang, Y. Elovici, and X. Zhou, “Mining Subgraphs From Propagation Networks Through Temporal Dynamic Analysis,” in 2018 19th IEEE International Conference on Mobile Data Management (MDM). IEEE, 2018.
[15] P. Pourashraf, N. Tomuro, S. B. Shouraki, “From Windows to Logos: Analyzing Outdoor Images to Aid Flyer Classification”, International Conference Image Analysis and Recognition, Springer, Cham, pp. 175-184, 2018.
[16] U. Von Luxburg, “A Tutorial on Spectral Clustering,” Stat. Comput., vol. 17, no. March, pp. 395–416, 2007.
[17] I. Dhillon, Y. Guan, and B. Kulis, “A unified view of kernel k-means, spectral clustering and graph cuts”, Technical Report, Computer Science Department, University of Texas at Austin, pp. 1–20, 2004.
[18] B. Auffarth, “Spectral Graph Clustering,” Univ. Barcelona course Rep. Tech. Av. Aprendizaj Univ. Politec. Catalunya, pp. 1–12, 2007.
[19] S. Uw, A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” Adv. Neural Inf. Process. Syst. 14, pp. 849–856, 2002.
[20] D. Zhou and C. J. C. Burges, “Spectral clustering and transductive learning with multiple views,” Proc. 24th Int. Conf. Mach. Learn. - ICML ’07, pp. 1159–1166, 2007.
[21] S. Smyth and S. White, “A spectral clustering approach to finding communities in graphs,” Proc. 5th SIAM Int. Conf. Data Min., pp. 76–84, 2005.
[22] J. Liu, C. Wang, M. Danilevsky, and J. Han, “Large-scale spectral clustering on graphs,” IJCAI Int. Jt. Conf. Artif. Intell., pp. 1486–1492, 2013.
[23] C.-D. Wang, J.-H. Lai, and P. S. Yu, “Dynamic Community Detection in Weighted Graph Streams,” Proc. 2013 SIAM Int. Conf. Data Min., pp. 151–161, 2013.
[24] G. T. Prabavathi and V. Thiagarasu, “Overlapping Community Detection Algorithms in Dynamic Networks: An Overview,” Int. J. Emerg. Technol. Comput. Appl. Sci., pp. 299–303, 2013.
[25] P. Ben Sheldon, “Community Detection Algorithms: a comparative evaluation on artificial and real-world networks D . Phil student report,” Other, pp. 1–27, 2010.
[26] W. Wang and W. N. Street, “A novel algorithm for community detection and influence ranking in social networks,” ASONAM 2014 - Proc. 2014 IEEE/ACM Int. Conf. Adv. Soc. Networks Anal. Min., no. Asonam, pp. 555–560, 2014.
[27] O. Benyahia et al., “Community detection in dynamic graphs with missing edges To cite this version: HAL Id: hal-01590597 Community Detection in Dynamic Graphs with Missing Edges,” 2017.
[28] C. Chen, X. Yan, F. Zhu, J. Han, and P. S. Yu, “Graph OLAP - Towards Online Analytical Processing on Graphs,” Data Mining, 2008. ICDM’08. Eighth IEEE Int. Conf., pp. 103–112, 2008.
[29] Y. Wu, Z. Zhong, W. Xiong, and N. Jing, “Graph summarization for attributed graphs,” Proc. - 2014 Int. Conf. Inf. Sci. Electron. Electr. Eng. ISEEE 2014, vol. 1, pp. 503–507, 2014.
[30] S. Grimm, P. Hitzler, and A. Abecker, “Knowledge Representation and Ontologies Logic, Ontologies and Semantic Web Languages,” Semant. Web Serv., pp. 51–105, 2007.
[31] N. Ashrafi Payaman, M. R. Kangavari, “GSSC: Graph Summarization based on both Structure and Concepts”, International Journal of Information & Communication Technology Research, vol. 9, no. 1, pp. 33-44, 2017.
[32] N. Ashrafi Payaman, M. R. Kangavari. “Graph Hybrid Summarization”, Journal of AI and Data Mining, vol. 6, no. 2 pp. 335-340, 2018.