NDLI: Set-based approximate approach for lossless graph summarization

Content Provider	Springer Nature Link
Author	Lee, Young Koo Khan, Kifayat Ullah Nawaz, Waqas
Copyright Year	2015
Abstract	Graph summarization is valuable approach to analyze various real life phenomenon, like communities, influential nodes, and information flow in a big graph. To summarize a graph, nodes having similar neighbors are merged into super nodes and their corresponding edges are compressed into super edges. Existing methods find similar nodes either by nodes ordering or perform pairwise similarity computations. Compression-by-node ordering approaches are scalable but provide lesser compression due to exhaustive similarity computations of their counterparts. In this paper, we propose a novel set-based summarization approach that directly summarizes naturally occurring sets of similar nodes in a graph. Our approach is scalable since we avoid explicit similarity computations with non-similar nodes and merge sets of nodes in each iteration. Similarly, we provide good compression ratio as each set consists of highly similar nodes. To locate sets of similar nodes, we find candidate sets of similar nodes by using locality sensitive hashing. However, member nodes of every candidate set have varying similarities with each other. Therefore, we propose a heuristic based on similarity among degrees of candidate nodes, and a parameter-free pruning technique to effectively identify subset of highly similar nodes from candidate nodes. Through experiments on real world graphs, our approach requires lesser execution time than pairwise graph summarization, with margin of an order of magnitude in graphs containing nodes with highly diverse neighborhood, and produces summary at similar accuracy. Similarly, we observe comparable scalability against the compression-by-node ordering method, while providing better compression ratio.
Ending Page	1207
Page Count	23
Starting Page	1185
File Format	PDF
ISSN	0010485X
e-ISSN	14365057
Journal	Computing
Issue Number	12
Volume Number	97
Language	English
Publisher	Springer Vienna
Publisher Date	2015-04-28
Publisher Place	Vienna
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	LSH Vertex degrees Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) Graph summarization MDL Software Engineering Auto pruning Computer Application in Administrative Data Processing Computer Science Artificial Intelligence (incl. Robotics) Approximation algorithms Information Systems Applications (incl. Internet) Graph algorithms Degree similarity Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics Numerical Analysis Computer Science Applications Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

RDF approximate queries based on semantic similarity

Adaptive Predictor for Lossless Image Compression

Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction

Semidefinite Programs and Association Schemes

Finding large $$k$$ -clubs in undirected graphs

Personalised code generation from large schema sets for geospatial mobile applications

Distributed discovery of frequent subgraphs of a network using MapReduce

Approximate algorithms for static and continuous range queries in mobile navigation

Dynamic Programming Revisited: Improving Knapsack Algorithms

Set-based approximate approach for lossless graph summarization

Similar Documents

RDF approximate queries based on semantic similarity

Adaptive Predictor for Lossless Image Compression

Algorithms for Partition of Some Class of Graphs under Compaction and Vertex-Compaction

Semidefinite Programs and Association Schemes

Finding large $$k$$ -clubs in undirected graphs

Personalised code generation from large schema sets for geospatial mobile applications

Distributed discovery of frequent subgraphs of a network using MapReduce

Approximate algorithms for static and continuous range queries in mobile navigation

Dynamic Programming Revisited: Improving Knapsack Algorithms

Set-based approximate approach for lossless graph summarization