Graph Partitioning Change Detection Using Tree-Based Clustering

We are concerned with the issue of detecting changes of graph partitioning structures from a graph sequence. We call this issue GPCD(graph partitioning change detection). The graph partitioning structures may represent network communities. Hence GPCD is important in that it leads to discovery of important events which cause changes of network communities. We introduce a new algorithm for GPCD, denoted as TREE. The key ideas are: 1) we employ probabilistic trees to represent probabilistic models of graph partitioning structures. 2) We then reduce GPCD into the issue of detecting changes of trees on the basis of the minimum description length (MDL) principle. 3) By taking the cost of changes into consideration, we realize significantly less false alarm rates for change detection than the baseline method called Graph Scope. We empirically demonstrate that TREE is able to detect changes more accurately than Graph Scope.