Recurrent Events in Dynamic Networks
Dynamic networks are becoming a central and intense subject of study due to their
ubiquitous incarnation in fields ranging from social networks to ethology, protein
interaction, web analysis, population dynamics, and more.
One feature common to most of these instances is in that the nodes of the network
have a unique identifier, which overcomes the classical computational barriers induced by
graph isomorphism and makes many interesting questions tractable.
This tutorial concentrates on the problem of extracting recurrent events such
as periodically repeating, over-represented or otherwise interesting
patterns that might be present in a long series of observations of a dynamic
network.
Reading list: (provided as links to the papers)
A. Apostolico et al., Efficient algorithms for the periodic
subgraphs mining problem, Journal of Discrete Algorithms (2012)
M. Lahiri, T. Berger-Wolf, Periodic subgraph mining in dynamic
networks, Knowledge and Information Systems 24 (2010) 467\u2013497.
J. Han, H. Cheng, D. Xin, X. Yan, Frequent Pattern Mining: Current
Status and Future Directions, Data Mining and Knowledge Discovery 14
(2007).
P. Juang, H. Oki, Y. Wang, M. Martonosi, L.S. Peh, D. Rubenstein,
Energy-efficient computing for wildlife tracking: Design tradeoffs and
early experiences with zebranet, in: ASPLOS-X: Proceedings of the 10th
International Conference on Architectural Support for Programming Languages
and Operating Systems, ACM Press, New York, NY, USA, 2002,
pp. 96\u2013107.
N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Efficient mining of association
rules using closed itemset lattices, Inf. Syst. 24 (1999) 25\u201346.
Clauset A, Eagle N (2007) Persistence and periodicity in a dynamic proximity network. In: DIMACS/Dy-
DAn 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\u2013437