On Dense Pattern Mining in Graph Streams
On Dense Pattern Mining in Graph Streams
复制标题
DOI：
10.14778/1920841.1920964
复制
发表时间：
2010-09-01
影响因子：
2.5
通讯作者：
Jin, Ruoming
中科院分区：
文献类型：
--
作者：
Aggarwal, Charu C.;Li, Yao;Jin, Ruoming
许多大规模的Web和通信网络应用程序创建的数据可以表示为一个大规模的连续流的边缘。例如，电信网络中的对话或社交网络中的消息可以被表示为大量边流。这种流通常非常大，因为在这种网络中有大量的底层活动。在这些领域中的一个重要应用是确定底层图形流中频繁出现的密集结构。一般来说，我们希望确定潜在相互作用中频繁和密集的模式。我们引入了一个模型，密集模式挖掘，并提出概率算法，有效地确定这种结构模式。概率方法的目的是创建图流的摘要，其可用于进一步的模式挖掘。我们表明，这种总结方法导致有效和高效的结果流模式挖掘了一些真实的和合成数据集。
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 telecommunication 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 underlying activity in such networks. An important application in these domains is to determine frequently occurring dense structures in the underlying graph stream. In general, 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 efficiently. 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 summarization approach leads to effective and efficient results for stream pattern mining over a number of real and synthetic data sets.