期刊
KNOWLEDGE AND INFORMATION SYSTEMS
卷 24, 期 3, 页码 467-497出版社
SPRINGER LONDON LTD
DOI: 10.1007/s10115-009-0253-8
关键词
Graph mining; Dynamic social networks; Periodic patterns; Frequent closed subgraphs; Parsimony
资金
- NSF [IIS-0705822, IIS-0747369, CNS-025214, IOB-9874523]
In systems of interacting entities such as social networks, interactions that occur regularly typically correspond to significant, yet often infrequent and hard to detect, interaction patterns. To identify such regular behavior in streams of dynamic interaction data, we propose a new mining problem of finding a minimal set of periodically recurring subgraphs to capture all periodic behavior in a dynamic network. We analyze the computational complexity of the problem and show that it is polynomial, unlike many related subgraph or itemset mining problems. We propose an efficient and scalable algorithm to mine all periodic subgraphs in a dynamic network. The algorithm makes a single pass over the data and is also capable of accommodating imperfect periodicity. We demonstrate the applicability of our approach on several real-world networks and extract interesting and insightful periodic interaction patterns. We also show that periodic subgraphs can be an effective way to uncover and characterize the natural periodicities in a system.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据