Mining Periodic Behavior in Dynamic Social Networks
Authors:
- Mayank LahiriMLMayank Lahiri
- Tanya Y. Berger-WolfTBTanya Y. Berger-Wolf
- 1 December 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 373-382
Abstract
Social interactions that occur regularly typically correspond to significant yet often infrequent and hard to detect interaction patterns. To identify such regular behavior, we propose a new mining problem of finding periodic or near periodic subgraphs in dynamic social networks. We analyze the computational complexity of the problem, showing that, unlike any of the related subgraph mining problems, it is polynomial. We propose a practical, efficient and scalable algorithm to find such subgraphs that takes imperfect periodicity into account. We demonstrate the applicability of our approach on several real-world networks and extract meaningful and interesting periodic interaction patterns.Keywords
This publication has 24 references indexed in Scilit:
- Social relationships and reproductive state influence leadership roles in movements of plains zebra, Equus burchelliiAnimal Behaviour, 2007
- Frequent pattern mining: current status and future directionsData Mining and Knowledge Discovery, 2007
- Reality mining: sensing complex social systemsPersonal and Ubiquitous Computing, 2005
- Graphs over time2005
- Mining asynchronous periodic patterns in time series dataIEEE Transactions on Knowledge and Data Engineering, 2003
- Energy-efficient computing for wildlife trackingACM SIGOPS Operating Systems Review, 2002
- Evolution of the social network of scientific collaborationsPhysica A: Statistical Mechanics and its Applications, 2002
- Clustering and preferential attachment in growing networksPhysical Review E, 2001
- An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data2000
- Efficient mining of association rules using closed itemset latticesInformation Systems, 1999