NDLI: Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments

Content Provider	IEEE Xplore Digital Library
Author	Yongwook Choi Szpankowski, W.
Copyright Year	1963
Abstract	Information theory traditionally deals with “conventional data,” be it textual data, image, or video data. However, databases of various sorts have come into existence in recent years for storing “unconventional data” including biological data, social data, web data, topographical maps, and medical data. In compressing such data, one must consider two types of information: the information conveyed by the structure itself, and the information conveyed by the data labels implanted in the structure. In this paper, we attempt to address the former problem by studying information of graphical structures (i.e., unlabeled graphs). As the first step, we consider the Erdös-Rényi graphs G(n,p) over n vertices in which edges are added independently and randomly with probability p. We prove that the structural entropy of G(n,p) is (n;2)h(p)-logn!+o(1)=(n;2)h(p)-nlog+O(n), where h(p)=-plogp-(1-p)log(1-p) is the entropy rate of a conventional memoryless binary source. Then, we propose a two-stage compression algorithm that asymptotically achieves the structural entropy up to the nlog term (i.e., the first two leading terms) of the structural entropy. Our algorithm runs either in time O(n²) in the worst case for any graph or in time O(n+e) on average for graphs generated by G(n,p), where e is the average number of edges. To the best of our knowledge, this is the first provable (asymptotically) optimal graph compressor for Erdös-Rényi graph models. We use combinatorial and analytic techniques such as generating functions, Mellin transform, and poissonization to establish these findings. Our experiments confirm the theoretical results and also show the usefulness of our algorithm for some real-world graphs such as the Internet, biological networks, and social networks.
Sponsorship	IEEE Information Theory Society
Starting Page	620
Ending Page	638
Page Count	19
File Size	800916
File Format	PDF
ISSN	00189448
Volume Number	58
Issue Number	2
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-02-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Entropy Partitioning algorithms Encoding Orbits Compression algorithms Data structures Biological information theory unlabeled graphs Analytic information theory arithmetic encoder digital trees Erdös–Rényi graphs graph automorphism Mellin transform poissonization structural entropy
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

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

A New Binomial Recurrence Arising in a Graphical Compression Algorithm

A New Binomial Recurrence Arising in a Graphical Compression Algorithm

On Tries, Contention Trees and Their Analysis

Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression

On Optimally Partitioning a Text to Improve Its Compression

Algorithms and Fundamental Limits for Unlabeled Detection using Types

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models

Distribution of inter-node distances in digital trees

One-sided Variations on Tries: Path Imbalance, Climbing, and Key Sampling

Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments

Similar Documents

A New Binomial Recurrence Arising in a Graphical Compression Algorithm

A New Binomial Recurrence Arising in a Graphical Compression Algorithm

On Tries, Contention Trees and Their Analysis

Rényi Information Dimension: Fundamental Limits of Almost Lossless Analog Compression

On Optimally Partitioning a Text to Improve Its Compression

Algorithms and Fundamental Limits for Unlabeled Detection using Types

Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models

Distribution of inter-node distances in digital trees

One-sided Variations on Tries: Path Imbalance, Climbing, and Key Sampling

Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments