Finding informative cuboids in graphs with numerical attributes

Details

Supervisors

Nijssen, Siegfried

Faculty

Ecole polytechnique de Louvain

Degree label

Master [120] : ingénieur civil en informatique

Abstract

Graphs are an indispensable model to represent networked data. As our world becomes more interconnected, it is increasingly important to have the tools to analyse and understand large, complicated graphs. This is why the topic of graph mining is seeing rising interest. Moreover, the availability of richer graph dataset — containing not only the network structure but also attributes on the edges and vertices — have created the need for new graph mining frameworks. One such framework is an adaptation of OLAP (On Line Analytical Processing) for networked data, called Graph Cube. In the graph cube, the network is aggregated into a smaller graph which summarizes the connections between nodes sharing some properties. For example in a social network, instead of edges between persons, the summarized graph will show groups of people with a shared property, such as nationality or common interest. In this thesis, I explore one of the open questions in the Graph Cube Mining framework. Namely, how to generate informative cuboids, when some of the attributes are numerical. I present a new measure of informativeness for cuboids, based on a yet unexplored connection between Graph Cubes and Stochastic Blockmodels. Then, I explore three different approaches to build informative cuboids with numerical attribute: A binning approach, an approach based on Expectation Maximization, and an approach based on clustering.