@inproceedings{467df6ea9a354de5b51c3963306304b7,
title = "Summarizing big graphs by means of pseudo-boolean constraints",
abstract = "How to succinctly represent the truly relevant information in big data graphs? The approach presented in this paper aims to discover hidden graph structures and exploit them to compactly summarize large graphs. First, we show that some special graph classes such as cliques and bicliques can be represented efficiently as Pseudo-Boolean (PB) constraints. Then, we propose three new graph classes representable as PB constraints, called nested, sequence and clique-nested bi-partite graphs. Finally, we derive a general approach for partial or complete summarization of an arbitrary graph as a disjunction of PB constraints. Our representation can be seen as an original way to represent the edges of the graph, as they correspond to particular solutions of the PB constraints. An extensive experimental evaluation on several real-world networks shows that our framework is competitive with the state-of-the-art compression technique.",
keywords = "Graph Mining, Graph Summarization, Pseudo Boolean Constraints",
author = "Said Jabbour and Nizar Mhadhbi and Abdesattar Mhadhbi and Badran Radaoui and Lakhdar Sais",
note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 4th IEEE International Conference on Big Data, Big Data 2016 ; Conference date: 05-12-2016 Through 08-12-2016",
year = "2016",
month = jan,
day = "1",
doi = "10.1109/BigData.2016.7840683",
language = "English",
series = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "889--894",
editor = "James Joshi and George Karypis and Ling Liu and Hu, \{Xiaohua Tony\} and Ronay Ak and Yinglong Xia and Weijia Xu and Aki-Hiro Sato and Sudarsan Rachuri and Lyle Ungar and Yu, \{Philip S.\} and Rama Govindaraju and Toyotaro Suzumura",
booktitle = "Proceedings - 2016 IEEE International Conference on Big Data, Big Data 2016",
}