CoChat
Sign Up
Cited by 45Graph Theory and AlgorithmsComplex Network Analysis TechniquesAdvanced Database Systems and Queries

The DOI matches its Crossref record; the references it cites are not checked yet.

Summarizing static and dynamic big graphs

Open access
Khan, Arijit, Bhowmick, Sourav S., Bonchi, Francesco·2017·Proceedings of the VLDB Endowment
DOI 10.14778/3137765.3137825
Open this paper in CoChat — free account

Abstract

Large-scale, highly-interconnected networks pervade our society and the natural world around us, including the World Wide Web, social networks, knowledge graphs, genome and scientific databases, medical and government records. The massive scale of graph data often surpasses the available computation and storage resources. Besides, users get overwhelmed by the daunting task of understanding and using such graphs due to their sheer volume and complexity. Hence, there is a critical need to summarize large graphs into concise forms that can be more easily visualized, processed, and managed. Graph summarization has indeed attracted a lot of interests from various research communities, such as sociology, physics, chemistry, bioinformatics, and computer science. Different ways of summarizing graphs have been invented that are often complementary to each other. In this tutorial, we discuss algorithmic advances on graph summarization in the context of both classical (e.g., static graphs) and emerging (e.g., dynamic and stream graphs) applications. We emphasize the current challenges and highlight some future research directions.

Overview

Integrity signals

Registry

Crossref · 10.14778/3137765.3137825

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Citations

The citation lists haven’t been fetched yet

References 55 · Cited by 45

Research works printed but not linked: 55

  1. 10.5555/2095116.2095156 · DOI
  2. 10.1145/2213556.2213560 · DOI
  3. 10.1145/1963405.1963488 · DOI
  4. 10.1145/988672.988752 · DOI
  5. 10.1007/978-3-642-03784-9_3 · DOI
  6. 10.1145/1341531.1341547 · DOI
  7. 10.14778/1687627.1687711 · DOI
  8. C. Chen , C. X. Lin , M. Fredrikson , M. Christodorescu , X. Yan , and J. Han , Mining Large Information Networks by Graph Summarization. Link Mining: Models, Algorithms, and Applications. (pp. 475--501) , Springer New York , 2010 . C. Chen, C. X. Lin, M. Fredrikson, M. Christodorescu, X. Yan, and J. Han, Mining Large Information Networks by Graph Summarization. Link Mining: Models, Algorithms, and Applications. (pp. 475--501), Springer New York, 2010.
  9. 10.1109/ICDM.2008.30 · DOI
  10. C. Chen , F. Zhu , X. Yan , J. Han , P. S. Yu , and R. Ramakrishnan , InfoNetOLAP: OLAP and Mining of Information Networks. Link Mining: Models, Algorithms, and Applications. (pp. 411--438) , Springer New York , 2010 . C. Chen, F. Zhu, X. Yan, J. Han, P. S. Yu, and R. Ramakrishnan, InfoNetOLAP: OLAP and Mining of Information Networks. Link Mining: Models, Algorithms, and Applications. (pp. 411--438), Springer New York, 2010.
  11. 10.1145/1557019.1557049 · DOI
  12. 10.1109/TIT.2011.2173710 · DOI
  13. 10.5555/1618595.1618605 · DOI
  14. 10.1145/1065167.1065201 · DOI
  15. 10.1145/2213836.2213855 · DOI
  16. 10.1137/070683155 · DOI
  17. 10.1145/2592798.2592799 · DOI
  18. 10.1109/ICDM.2011.26 · DOI
  19. 10.1145/2020408.2020580 · DOI
  20. 10.1109/ASONAM.2016.7752224 · DOI
  21. 10.1007/s13278-017-0443-4 · DOI
  22. 10.1007/s11280-016-0388-y · DOI
  23. D. Koutra , Summarizing Large-Scale Graph Data , SDM , 2017 . D. Koutra, Summarizing Large-Scale Graph Data, SDM, 2017.
  24. 10.1002/sam.11267 · DOI
  25. Y. Liu , A. Dighe , T. Safavi , and D. Koutra , A Graph Summarization: A Survey , CoRR, abs/1612.04883 , 2016 . Y. Liu, A. Dighe, T. Safavi, and D. Koutra, A Graph Summarization: A Survey, CoRR, abs/1612.04883, 2016. · arXiv
  26. 10.1137/1.9781611972801.40 · DOI
  27. 10.1109/ASONAM.2009.38 · DOI
  28. S.-D. Lin , M.-Y. Yeh , and C.-T. Li , Sampling and Summarization for Social Networks , SDM , 2013 . S.-D. Lin, M.-Y. Yeh, and C.-T. Li, Sampling and Summarization for Social Networks, SDM, 2013.
  29. 10.1145/2661829.2661862 · DOI
  30. 10.1145/2627692.2627694 · DOI
  31. 10.1145/1835804.1835873 · DOI
  32. 10.1109/ICDM.2012.14 · DOI
  33. 10.1145/1376616.1376661 · DOI
  34. 10.1145/2623330.2623701 · DOI
  35. 10.1007/978-3-662-44851-9_38 · DOI
  36. S. Raghavan and H. Garcia-Molina , Representing Web Graphs , ICDE , 2003 . S. Raghavan and H. Garcia-Molina, Representing Web Graphs, ICDE, 2003.
  37. 10.1007/s10618-016-0468-8 · DOI
  38. 10.1109/TNET.2013.2272604 · DOI
  39. B.-S. Seah , S. S. Bhowmick , C. F. Dewey Jr , and H. Yu , FUSE: A Profit Maximization Approach for Functional Summarization of Biological Networks, BMC Bioinformatics , 13(Suppl 3 ): S10 , 2012 . B.-S. Seah, S. S. Bhowmick, C. F. Dewey Jr, and H. Yu, FUSE: A Profit Maximization Approach for Functional Summarization of Biological Networks, BMC Bioinformatics, 13(Suppl 3):S10, 2012.
  40. B.-S. Seah , S. S. Bhowmick , and C. F. Dewey Jr , DiffNet: Automatic Differential Functional Summarization of dE-MAP Networks ., Methods, 69(3) , 2014 . B.-S. Seah, S. S. Bhowmick, and C. F. Dewey Jr, DiffNet: Automatic Differential Functional Summarization of dE-MAP Networks., Methods, 69(3), 2014.
  41. 10.1145/2783258.2783321 · DOI
  42. 10.1109/TVCG.2006.107 · DOI
  43. 10.1109/ICDE.2016.7498314 · DOI
  44. 10.1145/2882903.2915223 · DOI
  45. 10.1109/BigData.2016.7840704 · DOI
  46. 10.1145/1376616.1376675 · DOI
  47. Y. Tian and J. M. Patel , Interactive Graph Summarization. Link Mining: Models, Algorithms, and Applications. (pp. 389--410) , Springer New York , 2010 . Y. Tian and J. M. Patel, Interactive Graph Summarization. Link Mining: Models, Algorithms, and Applications. (pp. 389--410), Springer New York, 2010.
  48. 10.1145/2020408.2020566 · DOI
  49. 10.1145/2939672.2939753 · DOI · Paper page
  50. 10.14778/2556549.2556561 · DOI
  51. 10.1109/ICDE.2010.5447830 · DOI
  52. 10.1109/ICDE.2015.7113411 · DOI
  53. 10.14778/2078331.2078335 · DOI
  54. 10.1145/1989323.1989413 · DOI
  55. 10.1109/ICDM.2010.133 · DOI

Metadata

Authors
Khan, A., Bhowmick, S. S., & Bonchi, F.
Affiliations
  • Nanyang Technological University (SG)
  • Institute for Scientific Interchange (IT)
ORCID
Venue
Proceedings of the VLDB Endowment
Publisher
Association for Computing Machinery (ACM)
Published
2017-08
Volume
10
Issue
12
Pages
1981-1984
ISSN
2150-8097 (ISSN-L)
DOI
10.14778/3137765.3137825
OpenAlex
W2752632498
Cited by
45
References
55
Citations by year
2026: 2 · 2025: 7 · 2024: 1 · 2023: 3 · 2022: 11 · 2021: 3 · 2020: 3 · 2019: 6 · 2018: 9
FWCI
2.16
Type
journal article
Language
en
Open access
Licence
cc-by-nc-nd
Locations
  • Proceedings of the VLDB Endowment (publishedVersion)
  • DR-NTU (Nanyang Technological University) (submittedVersion, cc-by-nc-nd)
Funders
Ministry of Education, India
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
  • Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
  • Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
Keywords
graph summarization, large-scale graphs, dynamic graphs, network visualization, graph algorithms, static graphs, graph data management

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review