Correlation and Contrast Link Formation Patterns in a Time Evolving Graph

A time evolving graph is becoming increasingly abundant in a wide variety of application domains. While several classes of advanced frequent patterns in time evolving graphs are proposed, in this paper, correlation and contrast patterns on link formations are developed, which can be regarded as nontrivial upgrades of corresponding patterns in item set mining into the graph domain. More concretely, hyper clique patterns and conditional contrast patterns are adopted to develop new correlation and contrast link formation patterns, respectively. In addition, another novel correlation pattern is derived by the analogy of conditional contrast patterns. Discovery of sets of link formation patterns having opposite characteristics, i.e. correlation and contrast, can expect to obtain deep understanding of target dataset which in turn brings new findings. To discover correlation and contrast patterns efficiently, a series of algorithms is developed by using conventional methods in closed sub graph discovery, item set mining and pseudo clique enumeration. Experiments using real world datasets confirm the effectiveness of the proposed framework.