Abstract
A temporal graph \({\mathcal {G}}\) is a sequence of static graphs indexed by a set of integers representing time instants. Given \(\varDelta\) an integer, a \(\varDelta\)-module is a set of vertices A having the same neighbourhood outside of A for \(\varDelta\) consecutive instants. We address specific cases of \(\varDelta\)-module enumeration, when \(|A| = 2\) or when \(\varDelta = \infty\). Our main parameter for time complexity analysis is the history length \(\tau = \max \{t:G_t\in {\mathcal {G}}\text { not empty }\}-\min \{t:G_t\in {\mathcal {G}}\text { not empty }\}\). Using red-black tree data structure, we give solutions to above enumeration problems in time logarithmic in \(\tau\). For the general \(\varDelta\)-module enumeration problem, we give a preprocessing using overlapping properties of minimal \(\varDelta\)-modules. Numerical analysis of our implementation on graphs collected from real-world data scales up to a history length of \(10^8\) time instants.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
This paper encompasses the results on temporal twins presented in Bui-Xuan et al. (2020), and extends them to temporal modules, by a careful analysis of overlapping minimal temporal modules. Our source code is open at https://github.com/DaemonFire/deltaModules.
In our implementation, the inner search consists in determining whether an edge does not exist between some u and some w in graph \(G_t\), given a time instant t. It is implemented in a hash map called mapEdgeByInstant in function computeEternalTwinsByEdgesIterationWithoutMatrices defined in src/TwinsAlgorithms.java, cf. https://github.com/DaemonFire/deltatwinsMEI/. The lookup time is then practically constant instead of O(m). Our full numerical analysis is available at https://github.com/DaemonFire/deltatwinsMEI/blob/master/results.csv and plotted in Bui-Xuan et al. (2020) along with an extensive discussion.
Source code at https://github.com/DaemonFire/deltaModules.
References
Bui-Xuan BM, Ferreira A, Jarry A (2003) Computing shortest, fastest, and foremost journeys in dynamic networks. Int J Found Comput Sci 14(2):267–285
Bui-Xuan B, Hourcade H, Miachon C (2020) Computing temporal twins in time logarithmic in history length. In: 9th International conference on complex networks and their applications, SCI, vol 944. pp 651–663
Casteigts A, Flocchini P, Godard E, Santoro N, Yamashita M (2013) Expressivity of time-varying graphs. In: 19th International symposium on fundamentals of computation theory. pp 95–106 (2013)
Dibbelt J, Pajor T, Strasser B, Wagner D (2018) Connection scan algorithm. ACM J Exp Algorithmics 23:1–56
Ehrenfeucht A, Harju T, Rozenberg G (1999) The theory of 2-structures: a framework for decomposition and transformation of graphs. World Scientific, Singapore
Erlebach T, Hoffmann M, Kammer F (2015) On temporal graph exploration. In: 42nd international colloquium on automata, languages, and programming, LNCS, vol 9134. pp 444–455
Foschini L, Hershberger J, Suri S (2014) On the complexity of time-dependent shortest paths. Algorithmica 68(4):1075–1097
Habib M, Paul C (2010) A survey of the algorithmic aspects of modular decomposition. Comput Sci Rev 4(1):41–59
Habib M, Paul C, Viennot L (1999) Partition refinement techniques: an interesting algorithmic tool kit. Int J Found Comput Sci 10(2):147–170
Heber S, Mayr R, Stoye J (2011) Common intervals of multiple permutations. Algorithmica 60:175–206
Kempe D, Kleinberg J, Kumar A (2002) Connectivity and inference problems for temporal networks. J Comput Syst Sci 64(4):820–842
Klimt B, Yang Y (2004) Introducing the Enron Corpus. In: CEAS
Latapy M, Viard T, Magnien C (2018) Stream graphs and link streams for the modeling of interactions over time. Soc Netw Anal Min 8(61):1–29
Ros F, Ruiz P, Stojmenovic I (2012) Acknowledgment-based broadcast protocol for reliable and efficient data dissemination in vehicular ad-hoc networks. IEEE Trans Mob Comput 11(1):33–46
Spinrad J (2003) Efficient graph representations. Field institute monographs, vol 19. American Mathematical Society, Providence
Tournoux PU, Leguay J, Benbadis F, Conan V, De Amorim MD, Whitbeck J (2009) The accordion phenomenon: analysis, characterization, and impact on DTN routing. In: 28th IEEE conference on computer communications
Tsalouchidou I, Baeza-Yates R, Bonchi F, Liao K, Sellis T (2019) Temporal betweenness centrality in dynamic graphs. Int J Data Sci Anal 9:1–16
Acknowledgements
We are grateful to Emmanuel Chailloux for helpful discussion and pointers. We are grateful to the anonymous reviewers of the conference version of this paper for their helpful comments which greatly improved the paper and to the reviewers of the present version who guided us in polishing structure and sense.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supported by Courtanet – Sorbonne Université convention C19.0665 and ANRT Grant 2019.0485.
Rights and permissions
About this article
Cite this article
Bui-Xuan, BM., Hourcade, H. & Miachon, C. Computing small temporal modules in time logarithmic in history length. Soc. Netw. Anal. Min. 12, 19 (2022). https://doi.org/10.1007/s13278-021-00820-5
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s13278-021-00820-5