INDIGO Home University of Illinois at Urbana-Champaign logo uic building uic pavilion uic student center

Periodic Subgraph Mining in Dynamic Networks

Show full item record

Bookmark or cite this item:

Files in this item

File Description Format
PDF PeriodicSubgraphMining (1).pdf (509KB) (no description provided) PDF
Title: Periodic Subgraph Mining in Dynamic Networks
Author(s): Lahiri, Mayank; Berger-Wolf, Tanya Y.
Subject(s): Graph mining dynamic social networks periodic patterns frequent closed subgraphs parsimony
Abstract: In systems of interacting entities like 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.
Issue Date: 2011-02
Publisher: Springer Verlag
Citation Info: Lahiri, M. & Berger-Wolf, T. Y. 2011. Periodic subgraph mining in dynamic networks. Knowledge and Information Systems, 24(3): 467-497. DOI: 10.1007/s10115-009-0253-8
Type: Article
Description: The original version is available through Springer Verlag at DOI: 10.1007/s10115-009-0253-8
ISSN: 0219-1377
Sponsor: Our work is supported by NSF grants IIS-0705822 and CAREER IIS-0747369. We are grateful to Dan Rubenstein, Ilya Fischhoff, and Siva Sundaresan of the Department of Ecology and Evolutionary Biology at Princeton University for sharing the Plains Zebra data. Their work was supported by the NSF grants CNS-025214 and IOB-9874523.
Date Available in INDIGO: 2012-05-26

This item appears in the following Collection(s)

Show full item record


Country Code Views
United States of America 85
China 18
United Kingdom 10
India 2
Netherlands 2


My Account


Access Key