Relational Change Pattern Mining Based on Modularity Difference

This paper is concerned with a problem of detecting relational changes. Many kinds of graph data including social networks are increasing nowadays. In such a graph, the relationships among vertices are changing day by day. Therefore, it would be worth investigating a data mining method for detecting significant patterns informing us about what changes. We present in this paper a general framework for detecting relational changes over two graphs to be contrasted. Our target pattern with relational change is defined as a set of vertices common in both graphs in which the vertices are almost disconnected in one graph, while densely connected in the other. We formalize such a target pattern based on the notions of modularity and k-plex. A depth-first algorithm for the mining task is designed as an extension of k-plex enumerators with some pruning mechanisms. Our experimental results show usefulness of the proposed method for two pairs of graphs representing actual reply-communications among Twitter users and word co-occurrence relations in Japanese news articles.