On dense pattern mining in graph streams

Many massive web and communication network applications create data which can be represented as a massive sequential stream of edges. For example, conversations in a telecom- munication network or messages in a social network can be represented as a massive stream of edges. Such streams are typically very large, because of the large amount of un- derlying activity in such networks. An important applica- tion in these domains is to determine frequently occurring dense structures in the underlying graph stream. In gen- eral, we would like to determine frequent and dense patterns in the underlying interactions. We introduce a model for dense pattern mining and propose probabilistic algorithms for determining such structural patterns effectively and ef- ficiently. The purpose of the probabilistic approach is to create a summarization of the graph stream, which can be used for further pattern mining. We show that this summa- rization approach leads to effective and efficient results for stream pattern mining over a number of real and synthetic data sets. © 2010 VLDB Endowment.