An efficient weighted graph aggregation algorithm

doi:10.3969/j.issn.0253-2778.2016.03.002

Abstract

Abstract: Graph aggregation (graph summarization) technique is one of the effective ways to mine and analyze huge graphs. However, in reality, these graphs are not only huge but also carry weighted edges. The current algorithms do not or seldom take the weight into consideration, leading to a great difference between the aggregation graph and the original one. In order to solve this problem and improve the quality and efficiency of graph aggregation, The weighted graph aggregation algorithm was studied, the consistency of grouping area values of the adjacent matrix of the aggregation graphs was introduced to measure the consistency of weights of edges, compression ratio was defined to measure the spatial efficiency of the graph aggregation algorithm, and error rate was used to evaluate the difference between the aggregation graph and the original graph. The compression quality is ensured by controlling error rates and a comparison is made between the proposed algorithm and the existing graph aggregation algorithms. The experiment results show the effectiveness of the graph aggregation algorithm.

Key words: graph data, weighted graph, graph aggregation, graph summarization, compression ratio

CLC Number:

TP311

HU Baoli, YOU Jinguo, ZHOU Cuilian, WANG Yang, CUI Hongbo. An efficient weighted graph aggregation algorithm[J]. Journal of University of Science and Technology of China, 2016, 46(3): 180-187.

References

［1］
LOUATI A, Aufaure M A, Lechevallier Y. Graph Aggregation: Application to Social Networks[A]. Advances in Theory and Applications of High Dimensional and Symbolic Data Analysis. 2013: 157-177.
[2] 冯国栋，肖仰华. 大图的分布式存储[J].中国计算机学会通讯，2012，8 (11): 12-15.
[3] 尹丹, 高宏, 邹兆年. 一种新的高效图聚集算法[J]. 计算机研究与发展, 2011, 48(10): 1831-1841.
YIN Dan, GAO Hong, ZOU Zhaonian. A novel efficient graph aggregation algorithm[J]. Journal of Computer Research and Development, 2011, 48(10): 1831-1841.
[4] 潘秋萍,游进国,张志朋,等. 图聚集技术的现状与挑战[J].软件学报,2015, 26(1):167-177.
PAN Qiuping, YOU Jinguo, ZHANG Zhipeng, et al. Progress and challenges of graph aggregation and summarization techniques[J]. Journal of Software, 2015, 26(1):167-177.
[5] CHEN C, YAN X F, ZHU F D, et al. Graph OLAP: Towards online analytical processing on graphs[C]// Proceedings of the 8th International Conference on Data Mining. Pisa, Italy: IEEE Press, 2008: 103-112.
[6] LEFEVRE K, TERZI E. GraSS: Graph structure summarization[C]// SIDM International Conference on Data Mining. Columbus, USA: IEEE Press, 2010: 454-465.
[7] NAVLAKHA S, RASTOGI R, SHRIVASTAVA N. Graph summarization with bounded error[C]// Proceedings of the ACM-SIGMOD International Conference on Management of Data. Vancouver, Canada: IEEE Press, 2008: 419-432.
[8] ZHOU Y, CHENG H, YU J X. Graph clustering based on structural/attribute similarities [J]. Proceedings of the VLDB Endowment, 2009, 2(1): 718-729.
[9] LIU Z, YU J X. On summarizing graph homogeneously[C]// Proceedings of the 16th International Conference on Database Systems for Advanced Applications. Hong Kong, China: IEEE Press, 2011: 299-310.
[10] LIU Z, YU J X, CHENG H. Approximate homogeneous graph summarization [J]. Journal of Information Processing, 2011, 20(1): 77-88.
[11] ZHANG N, TIAN Y, PATEL J M. Discovery-driven graph summarization[C]// Proceedings of the 26th International Conference on Data Engineering. Long Beach, USA: IEEE Press, 2010: 41(3): 880-891.
[12] FAN T F, LIAU C J. Logical characterizations of regular equivalence in weighted social networks[J]. Artificial Intelligence, 2014, 214: 66-88.
[13] TOIVONEN H, ZHOU F, HARTIKAINEN A, et al. Compression of weighted graphs[C]// Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Diego, USA: ACM Press, 2011: 965-973.
[14] 潘秋萍. 基于条件熵的图聚集算法研究[D]. 硕士学位论文，昆明理工大学，2014.

()
()

[1]	WU Jiayu, LI Yongkun, XU Yinlong. A read/write balanced high-performance key-value store [J]. Journal of University of Science and Technology of China, 2020, 50(6): 825-831.
[2]	CAI Yong, CHEN Hongmei,. A parallel algorithm for constructing concept lattice based on hierarchical concept under MapReduce [J]. Journal of University of Science and Technology of China, 2018, 48(4): 275-283.
[3]	WANG Yong, HUANG Zhiqiu, WEI Liangfen, LU Guifu. Locating failure-inducing combinations based on fault forest [J]. Journal of University of Science and Technology of China, 2018, 48(1): 28-34.
[4]	XU Wanru, YANG Panlong. Mobile user propagation capability evaluation and coverage optimization algorithm [J]. Journal of University of Science and Technology of China, 2017, 47(7): 569-574.
[5]	HUANG Dongmei, SUN Le, ZHAO Danfeng. A composite index strategy for big marine data based on adaptive method of data merging strategy [J]. Journal of University of Science and Technology of China, 2015, 45(10): 813-821.
[6]	ZHU Meiling, WANG Xiongbin, ZHANG Shouli,LIU Chen, HAN Yanbo. Instant traveling companion discovery based on large scale streaming ANPR data [J]. Journal of University of Science and Technology of China, 2016, 46(1): 47-55.
[7]	HUANG Dongmei, SUN Le, SHI Shaohua, SU Cheng, ZHAO Danfeng. Tabular-oriented data model and its query issues [J]. Journal of University of Science and Technology of China, 2016, 46(1): 56-65.
[8]	CHANG Li, MA Chengxue, GAO Lifu. Corn-counting method based on photoelectric signal [J]. Journal of University of Science and Technology of China, 2015, 45(4): 275-279.
[9]	JI Duo, BI Chen, CAI Dongfeng. A latent semantic analysis classification technique based on optimized categorization information [J]. Journal of University of Science and Technology of China, 2015, 45(4): 314-320.