Skip to main content
Springer Nature Link
Log in

Dense Subgraphs Summarization: An Efficient Way to Summarize Large Scale Graphs by Super Nodes

  • Conference paper
  • First Online:
Intelligent Computing Methodologies (ICIC 2020)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 12465))

Included in the following conference series:

  • 1349 Accesses

Abstract

For large scale graphs, the graph summarization technique is essential, which can reduce the complexity for large-scale graphs analysis. The traditional graph summarization methods focus on reducing the complexity of original graph, and ignore the graph restoration after summarization. So, in this paper, we proposed a graph Summarization method based on Dense Subgraphs (DSS) and attribute graphs (dense subgraph contains cliques and quasi cliques), which recognizes the dense components in the complex large-scale graph and converts the dense components into super nodes after deep sub-graph mining process. Due to the nodes in the dense component are closely connected, our method can easily achieve the lossless reduction of the summarized graph. Experimental results show that our method performs well in execution time and information retention, and with the increase of data, DSS algorithm shows good scalability.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (France)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 85.59
Price includes VAT (France)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 105.49
Price includes VAT (France)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. LeFevre, K., Terzi, E.: GraSS: graph structure summarization. In: Proceedings of the SIAM International Conference on Data Mining, pp. 454–465 (2010)

    Google Scholar 

  2. Purohit, M., Prakash, B.A., Kang, C., Zhang, Y., Subrahmanian, V.S.: Fast influence-based coarsening for large networks. In: Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD’2014), pp. 1296–1305 (2014)

    Google Scholar 

  3. Kumar, K.A., Efstathopoulos, P.: Utility-driven graph summarization. Proc. VLDB Endowment 12(4), 335–347 (2018)

    Article  Google Scholar 

  4. Navlakha, S., Rastogi, R., Shrivastava, N.: Graph summarization with bounded error. In: International Conference on Management of Data, SIGMOD, pp. 419–432 (2008)

    Google Scholar 

  5. Riondato, M., García-Soriano, D., Bonchi, F.: Graph summarization with quality guarantees. In: Proceedings of the 2016 IEEE 16th International Conference on Data Mining (ICDM’2014), pp. 947–952 (2016)

    Google Scholar 

  6. Dunne, C., Shneiderman, B.: Motif simplification: improving network visualization readability with fan, connector, and clique glyphs. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI’2013), pp. 3247–3256 (2013)

    Google Scholar 

  7. Zhu, L., Ghasemi-Gol, M., Szekely, P., Galstyan, A., Knoblock, Craig A.: Unsupervised entity resolution on multi-type graphs. In: Groth, P., Simperl, E., Gray, A., Sabou, M., Krötzsch, M., Lecue, F., Flöck, F., Gil, Y. (eds.) ISWC 2016. LNCS, vol. 9981, pp. 649–667. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46523-4_39

    Chapter  Google Scholar 

  8. Dunne, C., Shneiderman, B.: Motif simplification: improving network visualization readability with fan, connector, and clique glyphs. In: Conference on Human Factors in Computing Systems, CHI, pp. 3247–3256 (2013)

    Google Scholar 

  9. Koutra, D., Kang, U., Vreeken, J., Faloutsos, C.: Summarizing and understanding large graphs. Stat. Anal. Data Min. 8(3), 183–202 (2015)

    Article  MathSciNet  Google Scholar 

  10. Li, C., Baciu, G., Wang, Y.: Modulgraph: modularity-based visualization of massive graphs. SIGGRAPH Asia 2015 Visualization in High Performance Computing, pp. 1–4. (2015)

    Google Scholar 

  11. Meng, J., Tu, Y.-C.: Flexible and feasible support measures for mining frequent patterns in large labeled graphs. In: SIGMOD’17: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 391–402 (2017)

    Google Scholar 

  12. Verma, A., Butenko, S.: Network clustering via clique relaxations: a community based. Graph Partitioning Graph Clustering 588, 129 (2013)

    Article  MathSciNet  Google Scholar 

  13. Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)

    Article  Google Scholar 

  14. Liu, G., Wong, L.: Effective pruning techniques for mining quasi-cliques. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008. LNCS (LNAI), vol. 5212, pp. 33–49. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-87481-2_3

    Chapter  Google Scholar 

  15. Sanei-Mehri, S.-V., Das, A., Tirthapura, S.: Enumerating top-k quasi-cliques. In: IEEE International Conference on Big Data (Big Data) (2018)

    Google Scholar 

  16. http://snap.stanford.edu/data/

  17. Koutra, D., Kang, U., Vreeken, J., Faloutsos, C.: VOG: summarizing and understanding large graphs. Stat. Anal. Data Min. 8(3) (2014)

    Google Scholar 

Download references

Acknowledgement

This work was supported by the National Natural Science Foundation of China (No. 61701104), and by the Science and Technology Development Plan of Jilin Province, China (No.20190201194JC, and No.20200403039SF).

Author information

Authors and Affiliations

  1. Department of Computer Science and Technology, School of Computer Science, Northeast Electric Power University, Jilin, China

    Ling Wang, Yu Lu, Bo Jiang, Kai Tai Gao & Tie Hua Zhou

Authors
  1. Ling Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yu Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bo Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Kai Tai Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Tie Hua Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tie Hua Zhou .

Editor information

Editors and Affiliations

  1. Machine Learning and Systems Biology, Tongji University, Shanghai, China

    De-Shuang Huang

  2. School of Electrical, Computer and Telecommunications Engineering, University of Wollongong, North Wollongong, NSW, Australia

    Prashan Premaratne

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Wang, L., Lu, Y., Jiang, B., Gao, K.T., Zhou, T.H. (2020). Dense Subgraphs Summarization: An Efficient Way to Summarize Large Scale Graphs by Super Nodes. In: Huang, DS., Premaratne, P. (eds) Intelligent Computing Methodologies. ICIC 2020. Lecture Notes in Computer Science(), vol 12465. Springer, Cham. https://doi.org/10.1007/978-3-030-60796-8_45

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-60796-8_45

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-60795-1

  • Online ISBN: 978-3-030-60796-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation