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. |
Year | Venue | Keywords |
---|---|---|
2016 | 2016 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA) | Graph Mining, Graph Summarization, Pseudo Boolean Constraints |
Field | DocType | Citations |
Data mining,Block graph,Comparability graph,Line graph,Forbidden graph characterization,Computer science,Cograph,Artificial intelligence,Pathwidth,Topological graph theory,Graph (abstract data type),Machine learning | Conference | 0 |
PageRank | References | Authors |
0.34 | 13 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Saïd Jabbour | 1 | 175 | 12.44 |
Nizar Mhadhbi | 2 | 0 | 2.70 |
Abdessattar Mhadhbi | 3 | 0 | 0.34 |
Badran Raddaoui | 4 | 93 | 15.31 |
Lakhdar Sais | 5 | 859 | 65.57 |