ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

An efficient weighted graph aggregation algorithm

  • Kunming University of Science and Technology Faculty of Information Engineering and Automatic 650500

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2016.03.002
  • Received Date: 27 August 2015
  • Accepted Date: 29 September 2015
  • Rev Recd Date: 29 September 2015
  • Publish Date: 30 March 2016
    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.

    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.
    • FullText(HTML)
  • loading
    • References(14)
  • [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.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.)
    Recommended articles
    TrendMD
    Volume 46 Issue 3 page: 180-187
    Cover

    Article Metrics

    Article views (42) PDF downloads(86)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return