nach oben

Erschienen in:

2022 | OriginalPaper | Buchkapitel

A Hybrid Adjacency and Time-Based Data Structure for Analysis of Temporal Networks

verfasst von : Tanner Hilsabeck, Makan Arastuie, Kevin S. Xu

Erschienen in: Complex Networks & Their Applications X

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Dynamic or temporal networks enable representation of time-varying edges between nodes. Conventional adjacency-based data structures used for storing networks such as adjacency lists were designed without incorporating time. When used to store temporal networks, such structures can be used to quickly retrieve all edges between two sets of nodes, which we call a node-based slice, but cannot quickly retrieve all edges that occur within a given time interval, which we call a time-based slice. We propose a hybrid data structure for storing temporal networks with timestamped edges, including instantaneous edges such as messages on social media and edges with duration such as phone calls. Our hybrid structure stores edges in both an adjacency dictionary, enabling rapid node-based slices, and an interval tree, enabling rapid time-based slices. We evaluate our hybrid data structure on many real temporal network data sets and find that they achieve much faster slice times than adjacency-based baseline structures with only a modest increase in creation time and memory usage.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Convergence Properties of Optimal Transport-Based Temporal Networks

Nächstes Kapitel Markov Modulated Process to Model Human Mobility

Not to be confused with the other use of interval graph as a graph constructed from overlapping intervals on \(\mathbb {R}\) [9].

All experiments were run on a workstation with 2 Intel Xeon 2.3 GHz CPUs, totaling 36 cores, and 384 GB of RAM on Python version 3.8.3. Code to reproduce experiments is available at https://github.com/hilsabeckt/hybridtempstruct.

Arastuie, M., Paul, S., Xu, K.S.: CHIP: a Hawkes process model for continuous-time networks with scalable and consistent estimation. In: Advances in Neural Information Processing Systems, vol. 33, pp. 16983–16996 (2020)

Casteigts, A., Flocchini, P., Santoro, N., Quattrociocchi, W.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387–408 (2012)CrossRef

Cazabet, R.: Data compression to choose a proper dynamic network representation. In: Benito, R.M., Cherifi, C., Cherifi, H., Moro, E., Rocha, L.M., Sales-Pardo, M. (eds.) COMPLEX NETWORKS 2020. SCI, vol. 943, pp. 522–532. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-65347-7_43CrossRef

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)MATH

Dietz, P.F.: Maintaining order in a linked list. In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 122–127 (1982)

Eagle, N., Pentland, A.S.: Reality mining: sensing complex social systems. Pers. Ubiquit. Comput. 10(4), 255–268 (2006)CrossRef

Eagle, N., Pentland, A.S., Lazer, D.: Inferring friendship network structure by using mobile phone data. Proc. Natl. Acad. Sci. 106(36), 15274–15278 (2009)CrossRef

Ediger, D., McColl, R., Riedy, J., Bader, D.A.: Stinger: high performance data structure for streaming graphs. In: Proceedings of the IEEE Conference on High Performance Extreme Computing, pp. 1–5. IEEE (2012)

Fulkerson, D., Gross, O.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835–855 (1965)MathSciNetCrossRefMATH

10.

Hagberg, A., et al.: NetworkX (2013). http://networkx.github.io

11.

Hagberg, A., Swart, P., Schult, D.: Exploring network structure, dynamics, and function using NetworkX. Technical report. LA-UR-08-5495, Los Alamos National Laboratory (2008)

12.

Hilsabeck, T., Arastuie, M., Do, H.N., Sloma, M., Xu, K.S.: IdeasLabUT/dynetworkx: Python package for importing and analyzing discrete- and continuous-time dynamic networks (2020). https://github.com/IdeasLabUT/dynetworkx

13.

Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012)CrossRef

14.

Holme, P., Saramäki, J.: Temporal Networks. Springer, Heidelberg (2013)CrossRef

15.

Holme, P., Saramäki, J.: Temporal Network Theory. Springer, Heidelberg (2019)CrossRefMATH

16.

Isella, L., Stehlé, J., Barrat, A., Cattuto, C., Pinton, J.F., Van den Broeck, W.: What’s in a crowd? Analysis of face-to-face behavioral networks. J. Theor. Biol. 271(1), 166–180 (2011)MathSciNetCrossRefMATH

17.

Jenks, G.: Python sorted containers. J. Open Source Softw. 4(38), 1330 (2019)CrossRef

18.

Junuthula, R., Haghdan, M., Xu, K.S., Devabhaktuni, V.: The block point process model for continuous-time event-based dynamic networks. In: The World Wide Web Conference, pp. 829–839 (2019)

19.

Korda, M., Raman, R.: An experimental evaluation of hybrid data structures for searching. In: Vitter, J.S., Zaroliagis, C.D. (eds.) WAE 1999. LNCS, vol. 1668, pp. 213–227. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48318-7_18CrossRef

20.

Kostakos, V.: Temporal graphs. Physica A 388(6), 1007–1023 (2009)MathSciNetCrossRef

21.

Lambiotte, R., Masuda, N.: A Guide to Temporal Networks, vol. 4. World Scientific (2016)

22.

Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min. 8(1), 1–29 (2018)CrossRefMATH

23.

Lee, D.: Interval, segment, range, and priority search trees. In: Multidimensional and Spatial Structures, p. 1 (2005)

24.

Leskovec, J., Krevl, A.: SNAP datasets: stanford large network dataset collection (2014)

25.

Leskovec, J., Sosič, R.: SNAP: a general-purpose network analysis and graph-mining library. ACM Trans. Intell. Syst. Technol. (TIST) 8(1), 1 (2016)

26.

Ligtenberg, W., Pei, Y.: Introduction to a temporal graph benchmark. arXiv preprint arXiv:1703.02852 (2017)

27.

Nicosia, V., Tang, J., Mascolo, C., Musolesi, M., Russo, G., Latora, V.: Graph metrics for temporal networks. In: Holme, P., Saramäki, J. (eds.) Temporal Networks, pp. 15–40. Springer, Heidleberg (2013). https://doi.org/10.1007/978-3-642-36461-7_2CrossRef

28.

Overmars, M.H.: The Design of Dynamic Data Structures, vol. 156. Springer, Heidelberg (1987)

29.

Paranjape, A., Benson, A.R., Leskovec, J.: Motifs in temporal networks. In: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, pp. 601–610 (2017)

30.

Priebe, C.E., Conroy, J.M., Marchette, D.J., Park, Y.: Scan statistics on Enron graphs. Comput. Math. Organ. Theory 11, 229–247 (2005)CrossRefMATH

31.

Priebe, C.E., Conroy, J.M., Marchette, D.J., Park, Y.: Scan statistics on Enron graphs (2009). http://cis.jhu.edu/~parky/Enron/enron.html

32.

Schiller, B., Castrillon, J., Strufe, T.: Efficient data structures for dynamic graph analysis. In: Proceedings of the 11th International Conference on Signal-Image Technology & Internet-Based Systems, pp. 497–504. IEEE (2015)

33.

Thankachan, R.V., Swenson, B.P., Fairbanks, J.P.: Performance effects of dynamic graph data structures in community detection algorithms. In: Proceedings of the IEEE High Performance extreme Computing Conference, pp. 1–7. IEEE (2018)

34.

Transport for London: cycling.data.tfl.gov.uk (2021). https://cycling.data.tfl.gov.uk/

35.

Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P.: On the evolution of user interaction in Facebook. In: Proceedings of the 2nd ACM Workshop on Online Social Networks, pp. 37–42 (2009)

36.

Wehmuth, K., Ziviani, A., Fleury, E.: A unifying model for representing time-varying graphs. In: Proceedings of the IEEE International Conference on Data Science and Advanced Analytics, pp. 1–10. IEEE (2015)

Titel: A Hybrid Adjacency and Time-Based Data Structure for Analysis of Temporal Networks
verfasst von: Tanner Hilsabeck
Makan Arastuie
Kevin S. Xu
Verlag: Springer International Publishing
Buch: Complex Networks & Their Applications X
Print ISBN: 978-3-030-93408-8

Electronic ISBN: 978-3-030-93409-5

Copyright-Jahr: 2022
DOI: https://doi.org/10.1007/978-3-030-93409-5_49

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner