Skip to main content
SpringerLink
Log in

Temporal Scale of Dynamic Networks

  • Chapter
  • First Online:
Temporal Networks

Part of the book series: Understanding Complex Systems ((UCS))

Abstract

Interactions, either of molecules or people, are inherently dynamic, changing with time and context. Interactions have an inherent rhythm, often happening over a range of time scales. Temporal streams of interactions are commonly aggregated into dynamic networks for temporal analysis. Results of this analysis are greatly affected by the resolution at which the original data are aggregated. The mismatch between the inherent temporal scale of the underlying process and that at which the analysis is performed can obscure important insights and lead to wrong conclusions. In this chapter we describe the challenge of identifying the range of inherent temporal scales of a stream of interactions and of finding the dynamic network representation that matches those scales. We describe possible formalizations of the problem of identifying the inherent time scales of interactions and present some initial approaches at solving it, noting the advantages and limitations of these approaches. This is a nascent area of research and our goal is to highlight its importance and to establish a computational foundation for further investigations.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 79.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 99.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 129.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Ackerman, M., Ben-David, S., Loker, D.: Towards property-based classification of clustering paradigms. In: Lafferty, J., Williams, C.K.I., Shawe-Taylor, J., Zemel, R.S., Culotta, A. (eds.) Neural Information Processing Systems, pp. 10–18 (2010). http://nips.cc/

  2. Baldock, K., Memmott, J., Ruiz-Guajardo, J., Roze, D., Stone, G.S.: Daily temporal structure in african savanna flower visitation networks and consequences for network sampling. Ecology 92, 687–698 (2011)

    Article  Google Scholar 

  3. Barabasi, A.L.: Bursts: The Hidden Pattern Behind Everything We Do. Dutton, New York (2010)

    Google Scholar 

  4. Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)

    Article  MathSciNet  ADS  Google Scholar 

  5. Barron, A.R., Rissanen, J., Yu, B.: The minimum description length principle in coding and modeling. IEEE Trans. Inf. Theor. 44(6), 2743–2760 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  6. Ben-David, S., Ackerman, M.: Measures of clustering quality: a working set of axioms for clustering. Neural Information Processing Systems, pp. 121–128 (2008)

    Google Scholar 

  7. Bender-deMoll, S., McFarland, D.A.: The art and science of dynamic network visualization. J. Soc. Struct. 7(2), 1206–1241 (2006)

    Google Scholar 

  8. Blonder, B., Wey, T.W., Dornhaus, A., James, R., Sih, A.: Temporal dynamics and network analysis. In: Methods in Ecology and Evolution, pp. 958–972. Blackwell Publishing Ltd., Oxford (2012)

    Google Scholar 

  9. Butts, C.T.: An axiomatic approach to network complexity. J. Math. Sociol. 24, 273–301 (2000)

    Article  MATH  Google Scholar 

  10. Caceres, R.S., Berger-Wolf, T., Grossman, R.: Temporal scale of processes in dynamic networks. In: IEEE 11th ICDM Workshops, pp. 925–932 (2011)

    Google Scholar 

  11. Chapanond, A., Krishnamoorthy, M., Yener, B.: Graph theoretic and spectral analysis of enron email data. Comput. Math. Organ. Theor. 11, 265–281 (2005)

    Article  MATH  Google Scholar 

  12. Chung, F., Lu, L., Vu, V.: Spectra of random graphs with given expected degrees. Proc. Natl. Acad. Sci. 100(11), 6313–6318 (2003)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  13. Clauset, A., Eagle, N.: Persistence and periodicity in a dynamic proximity network. In: DIMACS Workshop on Computational Methods for Dynamic Interaction Networks. DIMACS, Piscataway (2007)

    Google Scholar 

  14. Clauset, A., Shalizi, C.R., Newman, M.E.J.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661–703 (2009)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  15. Cross, P.C., Lloyd-Smith, J.O., Getz, W.M.: Disentangling association patterns in fission-fusion societies using african buffalo as an example. Anim. Behav. 69, 499–506 (2005)

    Article  Google Scholar 

  16. Eagle, N., Pentland, A.: Reality mining: sensing complex social systems. Pers. Ubiquitous Comput. V10(4), 255–268 (2006)

    Article  Google Scholar 

  17. Erdos, P., Renyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5, 17–61 (1960)

    MathSciNet  Google Scholar 

  18. Feldmann, A., Gilbert, A.C., Willinger, W., Kurtz, T.: The changing nature of network traffic: scaling phenomena. Comput. Comm. Rev. 28, 5–29 (1998)

    Article  Google Scholar 

  19. Fischhoff, I.R., Sundaresan, S.R., Cordingley, J., Larkin, H.M., Sellier, M.J., Rubenstein, D.I.: Social relationships and reproductive state influence leadership roles in movements of plains zebra, equus burchellii. Anim. Behav. 73(5), 825–831 (2007). doi:10.1016/j.anbehav.2006.10.012

    Article  Google Scholar 

  20. Gao, Q., Li, M., Vitányi, P.M.B.: Applying MDL to learn best model granularity. Artif. Intell. 121(1–2), 1–29 (2000)

    Article  MATH  Google Scholar 

  21. Hinde, R.A.: Interactions, relationships, and social structure. Man 11, 1–17 (1976)

    Article  Google Scholar 

  22. Holme, P.: Network reachability of real-world contact sequences. Phys. Rev. E 71, 046119 (2004)

    Article  ADS  Google Scholar 

  23. Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012) ArXiv e-prints (2011)

    Google Scholar 

  24. Hu, B., Rakthanmanon, T., Hao, Y., Evans, S., Lonardi, S., Keogh, E.J.: Discovering the intrinsic cardinality and dimensionality of time series using mdl. In: ICDM, pp. 1086–1091. IEEE Computer Society, Washington (2011)

    Google Scholar 

  25. Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., Barabasi, A.L.: The large-scale organization of metabolic networks. Nature 407(6804), 651–654 (2000)

    Article  ADS  Google Scholar 

  26. Karsai, M., Kivelä, M., Pan, R.K., Kaski, K., Kertész, J., Barabási, A.L., Saramäki, J.: Small but slow world: how network topology and burstiness slow down spreading. Phys. Rev. E 83, 025102 (2011)

    Article  ADS  Google Scholar 

  27. Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820–842 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  28. Keogh, E.J., Chu, S., Hart, D., Pazzani, M.J.: An online algorithm for segmenting time series. In: ICDM, pp. 289–296. IEEE Computer Society, Washington (2001)

    Google Scholar 

  29. Kivelä, M., Pan, R.K., Kaski, K., Kertész, J., Saramäki, J., Karsai, M.: Multiscale analysis of spreading in a large communication network. J. Stat. Mech. Theor. Exp. 3, 5 (2012)

    Google Scholar 

  30. Kleinberg, J.: An impossibility theorem for clustering. In: Advances in Neural Information Processing Systems, pp. 446–453 (2002)

    Google Scholar 

  31. Kleinberg, J.: Bursty and hierarchical structure in streams. Data Min. Knowl. Discov. 7(4), 373–397 (2003)

    Article  MathSciNet  Google Scholar 

  32. Krings, G., Karsai, M., Bernharsson, S., Blondel, V.D., Saramäki, J.: Effects of time window size and placement on the structure of aggregated networks. CoRR abs/1202.1145 (2012). http://arxiv.org/abs/1202.1145 ArXiv e-prints (2012)

  33. Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Trawling the web for emerging cyber-communities. Comput. Netw. 31(11–16), 1481–1493 (1999)

    Article  Google Scholar 

  34. Kumar, R., Novak, J., Tomkins, A.: Structure and evolution of online social networks. In: Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 611–617. ACM, New York (2006)

    Google Scholar 

  35. Lahiri, M., Berger-Wolf, T.Y.: Structure prediction in temporal networks using frequent subgraphs. In: Proceedings of the IEEE Symposium on Computational Intelligence and Data Mining, pp. 35–42. IEEE, New York (2007)

    Google Scholar 

  36. Lahiri, M., Maiya, A.S., Caceres, R.S., Habiba, Berger-Wolf, T.Y.: The impact of structural changes on predictions of diffusion in networks. In: Workshops Proceedings of the 8th IEEE International Conference on Data Mining, pp. 939–948. IEEE, New York (2008)

    Google Scholar 

  37. Meila, M.: Comparing clusterings: an axiomatic view. In: In ICML ’05: Proceedings of the 22nd international conference on Machine learning, pp. 577–584. ACM, New York (2005)

    Google Scholar 

  38. Miller, B.A., Bliss, N.T., Wolfe, P.J.: Toward signal processing theory for graphs and non-euclidean data. In: ICASSP, pp. 5414–5417. IEEE, New York (2010)

    Google Scholar 

  39. Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2–3), 161–180 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  40. Molloy, M., Reed, B.: The size of the giant component of a random graph with a given degree sequence. Comb. Probab. Comput. 7(3), 295–305 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  41. Moody, J., McFarland, D., Bender-deMoll, S.: Dynamic network visualization. Am. J. Sociol. 110(4), 1206–1241 (2005)

    Article  Google Scholar 

  42. Morris, M., Kretzschmar, M.: Concurrent partnerships and transmission dynamics in networks. Soc. Netw. 17, 299–318 (1995)

    Article  Google Scholar 

  43. Papadimitriou, S., Li, F., Kollios, G., Yu, P.S.: Time series compressibility and privacy. In: VLDB, pp. 459–470. VLDB Endowment, Vienna (2007)

    Google Scholar 

  44. Partridge, C., Cousins, D., Jackson, A.W., Krishnan, R., Saxena, T., Strayer, W.T.: Using signal processing to analyze wireless data traffic. In: Proceedings of the ACM Workshop on Wireless Security, pp. 67–76. ACM, New York (2002)

    Google Scholar 

  45. Pesaran, M.H., Timmermann, A.: Model instability and choice of observation window. Economics Working Paper Series 99–19, Department of Economics, UC San Diego, 1999

    Google Scholar 

  46. Riolo, C., Koopman, J., Chick, S.: Methods and measures for the description of epidemiologic contact networks. J. Urban Health 78, 446–457 (2001)

    Article  Google Scholar 

  47. Rissanen, J.: Modeling by shortest data description. Automatica 14, 465–471 (1978)

    Article  MATH  Google Scholar 

  48. Rubenstein, D., Sundaresan, S., Fischhoff, I., Saltz, D.: Social networks in wild asses: comparing patterns and processes among populations, pp. 159–176. Martin-Luther-University Halle-Wittenberg, Halle (2007)

    Google Scholar 

  49. Sedley, D.: The stoic criterion of identity. Phronesis 27, 255–75 (1982)

    Article  Google Scholar 

  50. Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423, 623–656 (1948)

    MathSciNet  Google Scholar 

  51. Shetty, J., Adibi, J.: Enron email dataset. Institute, USC Information Sciences (2004). http://www.isi.edu/adibi/Enron/Enron.htm

  52. Silk, J., Alberts, S., Altmann, J.: Social relationships among adult female baboons ( < i > papio cynocephalus < /i > ) ii. variation in the quality and stability of social bonds. Behav. Ecol. Sociobiol. 61(2), 197–204 (2006)

    Google Scholar 

  53. Sulo, R., Berger-Wolf, T., Grossman, R.: Meaningful selection of temporal resolution for dynamic networks. In: Proceedings of the 8th Workshop on Mining and Learning with Graphs, MLG ’10, pp. 127–136. ACM, New York (2010)

    Google Scholar 

  54. Sun, J., Faloutsos, C., Papadimitriou, S., Yu, P.S.: Graphscope: parameter-free mining of large time-evolving graphs. In: KDD ’07: Proceedings of the 13th ACM SIGKDD on Knowledge Discovery and Data Mining, pp. 687–696. ACM, New York (2007)

    Google Scholar 

  55. Sundaresan, S.R., Fischhoff, I.R., Dushoff, J., Rubenstein, D.I.: Network metrics reveal differences in social organization between two fission-fusion species, grevy’s zebra and onager. Oecologia, 140–149 (2006)

    Google Scholar 

  56. Tanaka, Y., Iwamoto, K., Uehara, K.: Discovery of time-series motif from multi-dimensional data based on mdl principle. Mach. Learn. 58(2–3), 269–300 (2005)

    Article  MATH  Google Scholar 

  57. Tantipathananandh, C., Berger-Wolf, T., Kempe, D.: A framework for community identification in dynamic social networks. In: KDD ’07: Proceedings of the 13th ACM SIGKDD on Knowledge Discovery and Data Mining, pp. 717–726. ACM, New York (2007)

    Google Scholar 

  58. Yosef, N., Regev, A.: Impulse control: temporal dynamics in gene transcription. Cell 144, 886–896 (2011)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Illinois at Chicago, Chicago, IL, 60607, USA

    Rajmonda Sulo Caceres & Tanya Berger-Wolf

Authors
  1. Rajmonda Sulo Caceres
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tanya Berger-Wolf
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rajmonda Sulo Caceres .

Editor information

Editors and Affiliations

  1. Ice Lab, Department of Physics, Umeå University, Ice Lab, 3rd floor, NA wing, Naturvetarhuset, Umeå, 901 87, Sweden

    Petter Holme

  2. and Computational Sciences (BECS), Department of Biomedical Engineering, Aalto University, Rakentajanaukio, Otaniemi campus 2, Aalto, 00076, Finland

    Jari Saramäki

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Caceres, R.S., Berger-Wolf, T. (2013). Temporal Scale of Dynamic Networks. In: Holme, P., Saramäki, J. (eds) Temporal Networks. Understanding Complex Systems. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36461-7_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-36461-7_4

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-36460-0

  • Online ISBN: 978-3-642-36461-7

  • eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)

Publish with us

Policies and ethics

Search

Navigation