Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agrawal R, Srikant R (1994) Fast algorithms for mining association rules in large databases. In: Proceedings of the 20th international conference on very large data bases (San Francisco, CA, 1994). Morgan Kaufmann Publishers Inc., pp 487–499
Agrawal R, Srikant R (1995) Mining sequential patterns. In: Proceedings of the eleventh international conference on data engineering (Washington, DC, USA, 1995). IEEE Computer Society, pp 3–14
Barabási AL, Jeong H, Neda Z, Ravasz E, Schubert A, Vicsek T (2002) Evolution of the social network of scientific collaborations. Physica A: Stat Mech Appl 311(3–4): 590–614
Boros E, Gurvich V, Khachiyan L, Makino K (2002) On the complexity of generating maximal frequent and minimal infrequent sets. In: Proceedings of the 19th annual symposium on theoretical aspects of Computer Science (London, UK, 2002). Springer-Verlag, pp 133–141
Bringmann B, Zimmermann A (2009) One in a million: picking the right patterns. Knowl Inf Syst 18(1): 61–81
Carpineto C, Romano G (2004) Concept data analysis: theory and applications. Wiley, New York
Chapanond A, Krishnamoorthy MS, Yener B (2005) Graph theoretic and spectral analysis of Enron email data. Comput Math Organ Theory 11(3): 265–281
Cheng J, Ke Y, Ng W (2008) A survey on algorithms for mining frequent itemsets over data streams. Knowl Inf Syst 16(1): 1–27
Clauset A, Eagle N (2007) Persistence and periodicity in a dynamic proximity network. In: DIMACS/DyDAn workshop on computational methods for dynamic interaction networks
Dickinson PJ, Bunke H, Dadej A, Kraetzl M (2003) On graphs with unique node labels, vol 2726 of Lecture Notes in Computer Science. Springer, Berlin, pp 409–437
Diesner J, Carley KM (2005) Exploration of communication networks from the Enron Email corpus. In: Proceedings of the 2005 SIAM workshop on link analysis, counterterrorism and security, pp 3–14
Eagle N, Pentland A (2006) Reality mining: sensing complex social systems. Pers Ubiquitous Comput 10(4): 255–268
Elfeky MG, Aref WG, Elmagarmid AK (2005) Periodicity detection in time series databases. IEEE Trans Knowl Data Eng 17(7): 875–887
Elfeky MG, Aref WG, Elmagarmid AK (2005) WARP: time warping for periodicity detection. In: Proceedings of the fifth IEEE international conference on data mining (Washington, DC, USA, 2005). IEEE Computer Society, pp 138–145
Faloutsos M, Faloutsos P, Faloutsos C (1999) On power-law relationships of the internet topology. In: Proceedings of the conference on applications, technologies, architectures, and protocols for computer communication (New York, NY, 1999). ACM, pp 251–262
Fischhoff IR, Sundaresan SR, Cordingley J, Larkin HM, Sellier M-J, Rubenstein DI (2007) Social relationships and reproductive state influence leadership roles in movements of Plains zebra, Equus burchellii. Anim Behav 73(5): 825–831
Garofalakis M, Rastogi R, Shim K (1999) SPIRIT: sequential pattern mining with regular expression constraints. In: Proceedings of the international conference on very large data bases, pp 223–234
Han J, Cheng H, Xin D, Yan X (2007) Frequent pattern mining: current status and future directions. Data Min Knowl Discov 15(1): 55–86
Han J, Yin Y, Dong G (1999) Efficient mining of partial periodic patterns in time series database. In: Proceedings of the 15th international conference on data engineering (Los Alamitos, CA, 1999). IEEE Computer Society, pp 106–115
Huang K-Y, Chang C-H (2005) SMCA: a general model for mining asynchronous periodic patterns in temporal databases. IEEE Trans Knowl Data Eng 17(6): 774–785
Inokuchi A, Washio T, Motoda H (2000) An apriori-based algorithm for mining frequent substructures from graph data. In: Proceedings of the 4th European conference on principles of data mining and knowledge discovery, pp 13–23
Juang P, Oki H, Wang Y, Martonosi M, Peh LS, Rubenstein DI (2002) Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet. ACM SIGPLAN Notices 37(10): 96–107
Kuramochi M, Karypis G (2001) Frequent subgraph discovery. In: Proceedings of the 2001 IEEE international conference on data mining, pp 313–320
Lahiri M, Berger-Wolf TY (2007) Structure prediction in temporal networks using frequent subgraphs. In: Proceedings of IEEE symposium on computational intelligence and data mining, pp 35–42
Lahiri M, Berger-Wolf TY (2008) Mining periodic behavior in dynamic social networks. In: Proceedings of the IEEE international conference on data mining (ICDM), pp 373–382
Ma S, Hellerstein JL (2001) Mining partially periodic event patterns with unknown periods. In: Proceedings of the 17th international conference on data engineering (Washington, DC, USA, 2001). IEEE Computer Society, pp 205–214
Nanavati AA, Gurumurthy S, Das G, Chakraborty D, Dasgupta K, Mukherjea S, Joshi A (2006) On the structural properties of massive telecom call graphs: findings and implications. In: Proceedings of the 15th ACM international conference on Information and knowledge management (New York, NY, USA, 2006). ACM, pp 435–444
Newman MEJ (2001) From the cover: the structure of scientific collaboration networks. Proc Natl Acad Sci 98: 404–409
Özden B, Ramaswamy S, Silberschatz A (1998) Cyclic association rules. In: Proceedings of the fourteenth international conference on data engineering (Washington, DC, USA, 1998). IEEE Computer Society, pp 412–421
Pasquier N, Bastide Y, Taouil R, Lakhal L (1999) Efficient mining of association rules using closed itemset lattices. Inf Syst 24(1): 25–46
Pei J, Han J (2000) Can we push more constraints into frequent pattern mining? In: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, New York, pp 350–354
Pei J, Han J, Wang W (2002) Mining sequential patterns with constraints in large databases. In: Proceedings of the eleventh international conference on information and knowledge management. ACM, New York, pp 18–25
Sundaresan SR, Fischhoff IR, Dushoff J, Rubenstein DI (2007) Network metrics reveal differences in social organization between two fission–fusion species, Grevys zebra and onager. Oecologia 151(1): 140–149
Tatti N (2008) Maximum entropy based significance of itemsets. Knowl Inf Syst 17(1): 57–77
Wasserman S, Faust K (1994) Social network analysis: methods and applications. Cambridge UniversityPress, Cambridge
Yan X, Cheng H, Han J, Yu PS (2008) Mining significant graph patterns by leap search. In: SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD international conference on management of data (New York, NY, USA, 2008). ACM, pp 433–444
Yang G (2004) The complexity of mining maximal frequent itemsets and maximal frequent patterns. In: Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining (New York, NY, 2004). ACM, pp 344–353
Yang J, Wang W, Yu PS (2001) InfoMiner: mining surprising periodic patterns. In: Proceedings of the 7th ACM SIGKDD international conference on Knowledge discovery and data mining (New York, NY, 2001). ACM, pp 395–400
Yang J, Wang W, Yu PS (2002) InfoMiner+: mining partial periodic patterns with gap penalties. In: Proceedings of the 2002 IEEE international conference on data mining (Washington, DC, 2002). IEEE Computer Society, p 725
Yang J, Wang W, Yu PS (2003) Mining asynchronous periodic patterns in time series data. IEEE Trans Knowl Data Eng 15(3): 613–628
Zhu F, Yan X, Han J, Yu PS (2007) gPrune: a constraint pushing framework for graph pattern mining. Lect Notes Comput Sci 4426: 388
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lahiri, M., Berger-Wolf, T.Y. Periodic subgraph mining in dynamic networks. Knowl Inf Syst 24, 467–497 (2010). https://doi.org/10.1007/s10115-009-0253-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10115-009-0253-8