CoreCube: Core Decomposition in Multilayer Graphs

摘要

Many real-life complex networks are modelled as multilayer graphs where each layer records a certain kind of interaction among entities. Despite the powerful modelling functionality, the decomposition on multilayer graphs remains unclear and inefficient. As a well-studied graph decomposition, core decomposition is efficient on a single layer graph with a variety of applications on social networks, biology, finance and so on. Nevertheless, core decomposition on multilayer graphs is much more challenging due to the various combinations of layers. In this paper, we propose efficient algorithms to compute the CoreCube which records the core decomposition on every combination of layers. We also devise a hybrid storage method that achieves a superior trade-off between the size of CoreCube and the query time. Extensive experiments on 8 real-life datasets demonstrate our algorithms are effective and efficient.