Online analysis of community evolution in data streams

Abstract

This paper discusses the problem of online change detection in a large set of interacting entities. Such trends include the gradual formation and dissolution of different communities of interaction. Our results are focussed on the case where the interacting entities are received in the form of a fast data stream of interactions. In such cases, a user may wish to perform repeated exploratory querying of the data for different kinds of user-defined parameters. This is difficult to perform in a fast data stream because of the one-pass constraints on the computations. We propose an online analytical processing framework which separates out online data summarization from offline exploratory querying. The result is a method which provides the ability to perform exploratory querying without compromising on the quality of the results. The algorithms are tested over large sets of graph data streams with varying levels of evolution. Copyright © by SIAM.