Access the full text.
Sign up today, get DeepDyve free for 14 days.
Loading next page...
/lp/springer-journals/a-study-of-connectivity-on-dynamic-graphs-computing-persistent-mxCwhs5v70
References (32)
-
A. Koster, X. Muñoz (2009)
Graphs and Algorithms in Communication Networks: Studies in Broadband, Optical, Wireless and Ad Hoc Networks -
D. Watts, S. Strogatz (1998)
Collective dynamics of ‘small-world’ networksNature, 393
-
Thibaut Démare, C. Bertelle, Antoine Dutot, L. Lévêque (2017)
Modeling logistic systems with an agent-based model and dynamic graphsJournal of Transport Geography, 62
-
Binh-Minh Bui-Xuan, Afonso Ferreira, Aubin Jarry (2003)
Computing Shortest, Fastest, and Foremost Journeys in Dynamic NetworksInt. J. Found. Comput. Sci., 14
-
A. Casteigts, R. Klasing, Yessin Neggaz, J. Peters (2015)
Efficiently Testing T -Interval Connectivity in Dynamic GraphsArXiv, abs/1502.00089
-
Eleni Akrida, P. Spirakis (2015)
On Verifying and Maintaining Connectivity of Interval Temporal Networks -
Regular graphs, which are generated using GraphStream Grid generator -
Random geometric graphs, which are particularly well suited for applications with explicit space dimension, such as communication networks or logistic networks -
Scale-free graphs, which are used to model many social networks or web networks. Graphstream Barabasi-Albert generator is used -
M. Karsai, N. Perra, Alessandro Vespignani (2013)
Time varying networks and the weakness of strong tiesScientific Reports, 4
-
O. Michail (2015)
An Introduction to Temporal Graphs: An Algorithmic Perspective*Internet Mathematics, 12
-
Christian Vestergaard, Mathieu Génois, A. Barrat (2014)
How memory generates heterogeneous dynamics in temporal networksPhysical review. E, Statistical, nonlinear, and soft matter physics, 90 4
-
P. Erdos, A. Rényi (1984)
On the evolution of random graphsTransactions of the American Mathematical Society, 286
-
Petter Holme (2015)
Modern temporal network theory: a colloquiumThe European Physical Journal B, 88
-
This generator adds a vertex to the graph and connects it to one or several vertices randomly chosen using Barabasi-Albert's (Albert and Barabási 2002) preferential attachment rule -
R Albert, AL Barabási (2002)
Statistical mechanics of complex networksRev Mod Phys, 74
-
A. Casteigts, P. Flocchini, Walter Quattrociocchi, N. Santoro (2010)
Time-varying graphs and dynamic networksInternational Journal of Parallel, Emergent and Distributed Systems, 27
-
Charles Huyghues-Despointes, B. Bui-Xuan, Clémence Magnien (2016)
Forte ∆-connexité dans les flots de liens -
D. Kempe, J. Kleinberg, Amit Kumar (2000)
Connectivity and inference problems for temporal networksJ. Comput. Syst. Sci., 64
-
V. Nicosia, J. Tang, Mirco Musolesi, G. Russo, C. Mascolo, V. Latora (2011)
Components in time-varying graphsChaos, 22 2
-
Aubin Jarry, Zvi Lotker (2004)
Connectivity in evolving graph with geometric properties -
L. Gauvin, Mathieu Génois, M. Karsai, Mikko Kivelä, T. Takaguchi, E. Valdano, Christian Vestergaard (2018)
Randomized reference models for temporal networksArXiv, abs/1806.04032
-
Carlos Gómez-Calzado, A. Casteigts, A. Lafuente, M. Larrea (2015)
A Connectivity Model for Agreement in Dynamic Systems -
Yoann Pigné, Antoine Dutot, F. Guinand, D. Olivier (2008)
GraphStream: A Tool for bridging the gap between Complex Systems and Dynamic GraphsArXiv, abs/0803.2093
-
S. Bhadra, Afonso Ferreira (2003)
Complexity of Connected Components in Evolving Graphs and the Computation of Multicast Trees in Dynamic Networks -
M. Newman (2003)
The Structure and Function of Complex NetworksSIAM Rev., 45
-
R. Albert, A. Barabási (2001)
Statistical mechanics of complex networksArXiv, cond-mat/0106096
-
J. Leskovec, A. Krevl (2014)
{SNAP Datasets}: {Stanford} Large Network Dataset Collection -
Nam Nguyen, Thang Dinh, Ying Xuan, M. Thai (2011)
Adaptive algorithms for detecting community structure in dynamic social networks2011 Proceedings IEEE INFOCOM
-
P. Erd6s, A. R~nyi
On the Evolution of Random Graphs -
Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations -
GraphStream's Random Euclidean graph generator randomly places vertices on a
- Publisher
- Springer Journals
- Copyright
- Copyright © The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2022
- ISSN
- 1619-4500
- eISSN
- 1614-2411
- DOI
- 10.1007/s10288-022-00507-3
- Publisher site
- See Article on Publisher Site
Abstract
This work focuses on connectivity in a dynamic graph. An undirected graph is defined on a finite and discrete time interval. Edges can appear and disappear over time. The first objective of this work is to extend the notion of connected component to dynamic graphs in a new way. Persistent connected components are defined by their size, corresponding to the number of vertices, and their length, corresponding to the number of consecutive time steps they are present on. The second objective of this work is to develop an algorithm computing the largest, in terms of size and length, persistent connected components in a dynamic graph. PICCNIC algorithm (PersIstent Connected CompoNent InCremental Algorithm) is a polynomial time algorithm of minimal complexity. Another advantage of this algorithm is that it works online: knowing the evolution of the dynamic graph is not necessary to execute it. PICCNIC algorithm is implemented using the GraphStream library and experimented in order to carefully study the outcome of the algorithm according to different input graph types, as well as real data networks, to verify the theoretical complexity, and to confirm its feasibility for graphs of large size.
Journal
4OR – Springer Journals
Published: Jun 1, 2023
Keywords: Dynamic graphs; Connectivity; Online algorithm; Persistent connected component; 05C85; 68R10; 90B10; 90C27