An Empirical Study of Compression-friendly Community Detection Methods

Real-world graphs are massive in size and we need a huge amount of space to store them. Graph compression allows us to compress a graph so that we need a lesser number of bits per link to store it. Of many techniques to compress a graph, a typical approach is to find clique-like caveman or tradition...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2021-05
Main Authors: Muhammad Irfan Yousuf, Izza Anwer, Abid, Muhammad
Format: Article
Language:English
Subjects:
Cost function
Graphs
Spokes
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Real-world graphs are massive in size and we need a huge amount of space to store them. Graph compression allows us to compress a graph so that we need a lesser number of bits per link to store it. Of many techniques to compress a graph, a typical approach is to find clique-like caveman or traditional communities in a graph and encode those cliques to compress the graph. On the other side, an alternative approach is to consider graphs as a collection of hubs connecting spokes and exploit it to arrange the nodes such that the resulting adjacency matrix of the graph can be compressed more efficiently. We perform an empirical comparison of these two approaches and show that both methods can yield good results under favorable conditions. We perform our experiments on ten real-world graphs and define two cost functions to present our findings.
ISSN:2331-8422