The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
Time-varying graphs and dynamic networks
Abstract
The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems – delay-tolerant networks, opportunistic-mobility networks and social networks – obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe, and the formal models proposed so far to express some specific concepts are the components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms and results found in the literature into a unified framework, which we call time-varying graphs (TVGs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are atemporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Fast unfolding of communities in large networks
Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008) · Journal of Statistical Mechanics: Theory and Experiment · doi:10.1088/1742-5468/2008/10/p10008 · Cited by 21,424
Gephi: An Open Source Software for Exploring and Manipulating Networks
Bastian, M., Heymann, S., & Jacomy, M. (2009) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v3i1.13937 · Cited by 11,675
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326
A survey of mobility models for ad hoc network research
Camp, T., Boleng, J., & Davies, V. (2002) · Wireless Communications and Mobile Computing · doi:10.1002/wcm.72 · Cited by 4,621
Diameter of the World-Wide Web
Albert, R., Jeong, H., & Barabási, A.-L. (1999) · Nature · doi:10.1038/43601 · Cited by 4,260
Reality mining: sensing complex social systems
Eagle, N., & (Sandy) Pentland, A. (2006) · Personal and Ubiquitous Computing · doi:10.1007/s00779-005-0046-3 · Cited by 2,772
Spray and wait: an efficient routing scheme for intermittently connected mobile networks
Spyropoulos, T., Psounis, K., & Raghavendra, C. S. (2005) · doi:10.1145/1080139.1080143 · Cited by 2,649
Graph evolution: Densification and shrinking diameters
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,461
Probabilistic routing in intermittently connected networks
Lindgren, A., Doria, A., & Schelén, O. (2003) · ACM SIGMOBILE Mobile Computing and Communications Review · doi:10.1145/961268.961272 · Cited by 2,288
MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks
Burgess, J., Gallagher, B., Jensen, D., & Levine, B. N. (2006) · Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications · doi:10.1109/infocom.2006.228 · Cited by 2,042
Group formation in large social networks: membership, growth, and evolution
Backstrom, L., Huttenlocher, D., Kleinberg, J., & Lan, X. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150412 · Cited by 1,805
Routing in a delay tolerant network
Jain, S., Fall, K., & Patra, R. K. (2004) · ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM) · doi:10.1145/1015467.1015484 · Cited by 1,779
Handbook of Graph Grammars and Computing by Graph Transformation
(1997) · WORLD SCIENTIFIC eBooks · doi:10.1142/9789812384720 · Cited by 1,349
Impact of Human Mobility on Opportunistic Forwarding Algorithms
Chaintreau, A., Hui, P., Crowcroft, J., Diot, C., Gass, R., & Scott, J. (2007) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2007.1060 · Cited by 1,023
Zhang, Z. (2006) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2006.323440 · Cited by 813
Kronecker Graphs: An Approach to Modeling Networks
Leskovec, J., Chakrabarti, D., Kleinberg, J. M., Faloutsos, C., & Ghahramani, Z. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0812.4905 · Cited by 697
Vehicle Ad Hoc networks: applications and related technical issues
Toor, Y., Muhlethaler, P., Laouiti, A., & La Fortelle, A. (2008) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2008.4625806 · Cited by 661
Computation in networks of passively mobile finite-state sensors
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M. J., & Peralta, R. (2005) · Distributed Computing · doi:10.1007/s00446-005-0138-3 · Cited by 587
Cabernet: vehicular content delivery using WiFi
Eriksson, J., Balakrishnan, H., & Madden, S. (2008) · Proceedings of the 14th ACM international conference on Mobile computing and networking · doi:10.1145/1409944.1409968 · Cited by 427
Distributed computation in dynamic networks
Kuhn, F., Lynch, N., & Oshman, R. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806760 · Cited by 400
COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
Bui-Xuan, B.-M., Ferreira, A., & Jarry, A. (2003) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054103001728 · Cited by 376
The structure of information pathways in a social communication network
Kossinets, G., Kleinberg, J., & Watts, D. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401945 · Cited by 332
Practical Routing in Delay-Tolerant Networks
Jones, E. P. C., Li, L., Schmidtke, J. K., & Ward, P. A. S. (2007) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2007.1016 · Cited by 304
Small-world behavior in time-varying graphs
Tang, J., Scellato, S., Musolesi, M., Mascolo, C., & Latora, V. (2010) · Physical Review E · doi:10.1103/physreve.81.055101 · Cited by 301
Börner, K., Sanyal, S., & Vespignani, A. (2007) · Annual Review of Information Science and Technology · doi:10.1002/aris.2007.1440410119 · Cited by 279
Kostakos, V. (2009) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2008.11.021 · Cited by 254
Boldrini, C., & Passarella, A. (2010) · Computer Communications · doi:10.1016/j.comcom.2010.01.013 · Cited by 232
K-core decomposition of Internet graphs: hierarchies, self-similarity and measurement biases
Ignacio Alvarez-Hamelin, J., C. A. F. D. I., Dall'Asta, L., Barrat, A., Vespignani, A., A. S. I. C. F. T. P., L. (. D. C. 8., & S. O. I. (2008) · Networks & Heterogeneous Media · doi:10.3934/nhm.2008.3.371 · Cited by 224
Network reachability of real-world contact sequences
Holme, P. (2005) · Physical Review E · doi:10.1103/physreve.71.046119 · Cited by 213
Analysing information flows and key mediators through temporal centrality metrics
Tang, J., Musolesi, M., Mascolo, C., Latora, V., & Nicosia, V. (2010) · Proceedings of the 3rd Workshop on Social Network Systems · doi:10.1145/1852658.1852661 · Cited by 194
The diameter of opportunistic mobile networks
Chaintreau, A., Mtibaa, A., Massoulie, L., & Diot, C. (2007) · Proceedings of the 2007 ACM CoNEXT conference on - CoNEXT '07 · doi:10.1145/1364654.1364670 · Cited by 183
Harary, F., & Gupta, G. (1997) · Mathematical and Computer Modelling · doi:10.1016/s0895-7177(97)00050-2 · Cited by 181
Ros, F. J., Ruiz, P. M., & Stojmenovic, I. (2012) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2010.253 · Cited by 168
Characterising temporal distance and reachability in mobile and online social networks
Tang, J., Musolesi, M., Mascolo, C., & Latora, V. (2010) · ACM SIGCOMM Computer Communication Review · doi:10.1145/1672308.1672329 · Cited by 159
Protocols and impossibility results for gossip-based communication mechanisms
Kempe, D., & Kleinberg, J. M. (2003) · doi:10.1109/sfcs.2002.1181971 · Cited by 129
Flooding time in edge-Markovian dynamic graphs
Clementi, A. E. F., Macci, C., Monti, A., Pasquale, F., & Silvestri, R. (2008) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1400751.1400781 · Cited by 119
Balasubramanian, A., Zhou, Y., Croft, W. B., Levine, B. N., & Venkataramani, A. (2007) · ACM Workshop on Challenged Networks (CHANTS) · doi:10.1145/1287791.1287803 · Cited by 103
Vulnerability of scheduled networks and a generalization of Menger's Theorem
Berman, K. A. (1996) · Networks · doi:10.1002/(sici)1097-0037(199610)28:3<125::aid-net1>3.0.co;2-p · Cited by 89
Description and simulation of dynamic mobility networks
Scherrer, A., Borgnat, P., Eric Fleury, B., Guillaume, J., & Robardet, C. (2008) · Computer Networks · doi:10.1016/j.comnet.2008.06.007 · Cited by 86
Parsimonious flooding in dynamic graphs
Baumann, H., Crescenzi, P., & Fraigniaud, P. (2009) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/1582716.1582757 · Cited by 61
Social networks: Evolving graphs with memory dependent edges
Grindrod, P., & Parsons, M. C. (2011) · Physica A Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.06.015 · Cited by 19
Cited by
Community Discovery in Dynamic Networks: A Survey
Rossetti, G., & Cazabet, R. (2019) · ACM Computing Surveys · doi:10.1145/3172867 · Cited by 468
Distributed temporal graph analytics with GRADOOP
Rost, C., Gomez, K., Täschner, M., Fritzsche, P., Schons, L., Christ, L., Adameit, T., Junghanns, M., & Rahm, E. (2022) · The VLDB Journal · doi:10.1007/s00778-021-00667-4 · Cited by 39
Metadata
- Authors
- Casteigts, A., Flocchini, P., Quattrociocchi, W., & Santoro, N.
- Venue
- International Journal of Parallel, Emergent and Distributed Systems
- Publisher
- Informa UK Limited
- Published
- 2012-10
- Volume
- 27
- Issue
- 5
- Pages
- 387-408
- ISSN
- 1026-7689 (ISSN-L)
- 1744-5760
- 1744-5779
- OpenAlex
- W1746637951
- Cited by
- 592
- References
- 41
- FWCI
- 48.53
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.