Temporal networks

• V. Batagelj: Temporal networks, 1220 Sredin seminar, 20. November 2013.

• Skye Bender-deMoll: Skyeome; papers
• Skye Bender-deMoll, Daniel A. McFarland: The Art and Science of Dynamic Network Visualization JOSS; PDF; data
• James Moody, Daniel McFarland, Skye Bender-deMoll: Dynamic Network Visualization paper
• Petter Holme, Jari Saramäki: Temporal Networks arXiv; slides; Petter Holme pubs
• Holme, Petter; Saramäki, Jari (Eds.): Temporal Networks book; example chapter
• STNA: Spatio-Temporal Network Analysis page
• Mrvar, Batagelj: Examples slides
• Ernesto Estrada: Communicability in temporal networks paper
• Edwin Grappin: Temporal network model – Barabási-Albert model with the library igraph blog
• Benjamin Blonder1, Tina W. Wey, Anna Dornhaus, Richard James, Andrew Sih: Temporal dynamics and network analysis abstract
• Janos Kertesz: Temporal networks slides
• David Kempe, Jon Kleinberg, Amit Kumar: Connectivity and Inference Problems for Temporal Networks paper
• Sungmin Lee, Luis E.C. Rocha, Fredrik Liljeros, Petter Holme: Exploiting Temporal Network Structures of Human Interaction to Effectively Immunize Populations paper
• slides
• Nilufer Onder: CS5811: Advanced Artificial Intelligencecourse; Temporal Constraint Networks slides
• Luke Hunsberger: pubs
• Roman Barták, Ondrej Cepek, Pavel Surynek: Modelling Alternatives in Temporal Networkspaper
• Peter A. Gloor, Rob Laubacher, Yan Zhao, Scott B.C. Dynes: Temporal Visualization and Analysis of Social Networks paper; pubs
• Rina Dechter: pubs; Constraint Processing (Morgan Kaufmann, 2003) book; Temporal Constraint Networks paper
• Cédric Pralet, Gérard Verfaillie: Time-dependent Simple Temporal Networksslides
• Nico Roos, Cees Witteveen: Diagnosis of Simple Temporal Networks paper
• Wikipedia: Dynamic network analysis
• Rajmohan Rajaraman: Introduction to Dynamic Networks; Models, Algorithms, and Analysis slides
• Cemal Cagatay Bilgin, Bulent Yener: Dynamic Network Evolution: Models, Clustering, Anomaly Detection paper
• Dynnetwork
• Commetrix
• Nadya Belov, Michael K. Martin, Jeff Patti, Jeff Reminga, Angela Pawlowski, Kathleen M. Carley: Dynamic Networks: Rapid Assessment of Changing Scenarios paper
• Ronald Breiger, Kathleen Carley, and Philippa Pattison (Eds): Dynamic Social Network Modeling and Analysis book
• Gonzalo Mateos and Ketan Rajawat: Dynamic Network Cartography paper
• Kristina Lerman, Rumi Ghosh, Jeon Hyung Kang: Centrality Metric for Dynamic Networks paper
• Dynamic Network Analysis Seminar Series page
• Algorithms on Complex Dynamic Networks page
• Clement Levallois: Gephi; A Tutorial – on dynamic networks slides
• Carter T. Butts: Package examples for networkDynamic: Dynamic Extensions for Network Objects paper
• Steffen Hadlak, Hans-Joerg Schulz, Heidrun Schumann: In Situ Exploration of Large Dynamic Networks paper
• Fabian Kuhn: Network Algorithms; Dynamic Networks course; chapter8
• Dynamic actor network analysis = DANA page
• Jérôme Kunegis, Damien Fay, Christian Bauckhage: Spectral evolution in dynamic networks paper
• Rossi F., van Beek P., Walsh T. (eds.) Handbook of constraint programming (Elsevier, 2006) book
• Lin Xu, Berthe Y. Choueiry: A New Efficient Algorithm for Solving the Simple Temporal Problem paper
• Leon Planken: Incrementally Solving the STP by Enforcing Partial Path Consistency paper
• Evangelos Kanoulas, Yang Du, Tian Xia, Donghui Zhang: Finding Fastest Paths on A Road Network with Speed Patterns paper
• D. Papadias, D. Zhang, and G. Kollios (Eds.): SSTD 2007, LNCS 4605: book
• Germán Creamer, Yong Ren, Jeffrey V. Nickerson: A Longitudinal Analysis of Asset Return, Volatility and Corporate News Network paper
• http://arxiv.org/abs/1012.0726
• Vassilis Kostakos: Temporal graphs paper
• Kenneth A. Berman: Vulnerability of scheduled networks and a generalization of Menger's Theorem. Networks, Volume 28, Issue 3, pages 125–134, October 1996 paper
• George B. Mertzios, Othon Michail, Ioannis Chatzigiannakis, Paul G. Spirakis: Temporal Network Optimization Subject to Connectivity Constraints paper
• John Tang, Mirco Musolesi, Cecilia Mascolo, Vito Latora: Temporal Distance Metrics for Social Network Analysis paper
• Mukesh Dalal, Yong Feng: Anytime temporal reasoning: Preliminary report paper
• Kathleen M. Carley: Dynamic Network Analysis paper
• B. Bui Xuan, A. Ferreira, A. Jarry: Computing shortest, fastest, and foremost journeys in dynamic networks. paper
• John Whitbeckyz, Marcelo Dias de Amorimy, Vania Conanz, Jean-Loup Guillaumey: Temporal Reachability Graphs paper
• Alex Hall, Steffen Hippler, Martin Skutella: Multicommodity flows over time: Efficient algorithms and complexity paper
• L. Fleischer, É. Tardos: Efficient continuous-time dynamic network flow algorithms paper
• Klaus Wehmuth, Eric Fleury, Artur Ziviani: A New Model for Time-Varying Graphs wanted
• Bolin Ding, Jeffrey Xu Yu, Lu Qin: Finding Time-Dependent Shortest Paths over Large Graphs paper
• L. da F. Costa, F. A. Rodrigues, G. Travieso & P. R. Villas Boas: Characterization of complex networks: A survey of measurements. Advances in Physics, Volume 56, Issue 1, 2007, pages 167-242. paper
• Kenneth L Cooke, Eric Halsey: The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, Volume 14, Issue 3, June 1966, Pages 493–498. paper
• Jean-Yves Le Boudec, Patrick Thiran: Network Calculus; A Theory of Deterministic Queuing Systems for the Internet. book
• Gergely Palla, Albert-László Barabási, Tamás Vicsek: Quantifying social group evolution. Nature 446, 664-667 (2007) paper

• Michael G. H. Bell, Yasunori Iida: Transportation network analysis. google
• L. R. Ford, Jr. & D. R. Fulkerson: Flows in Networks.page
• Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin: Network Flows: Theory, Algorithms, and Applications. Amazon
• Kerner, Boris S.: Introduction to Modern Traffic Flow Theory and Control.Springer
• Feng Xie, David M. Levinson: Evolving Transportation Networks.google

• Frederic Amblard, Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: On the Temporal Analysis of Scientific Network Evolutionpaper, paper
• Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: Time-varying graphs and dynamic networks. paper
• Nicola Santoro, Walter Quattrociocchi, Paola Flocchini, Arnaud Casteigts, Frederic Amblard: Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics paper
• Walter Quattrociocchi, Frederic Amblard, Eugenia Galeota: Selection in scientific networks paper
• A. Casteigts, P. Flocchini, E. Godard, N. Santoro, M. Yamashita: Expressivity of Time-Varying Graphs and the Power of Waiting in Dynamic Networks paper
• Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro: Shortest, Fastest, and Foremost Broadcast in Dynamic Networks paper
• Arnaud Casteigts and Paola Flocchini: Deterministic algorithms in dynamic networks / Formal models and metrics report; search

• Mehryar Mohri: Semiring frameworks and algorithms for shortest-distance problems paper
• A Very General Method of Computing Shortest Paths page
• Stephen Dolan: Fun with Semirings paper
• Jason Eisner: Expectation Semirings paper
• Liang Huang: Advanced Dynamic Programming in Semiring and Hypergraph Frameworks paper
• Bistarelli: Semirings for Soft Constraint Solving and Programming book
• Joao Luís Sobrinho: An Algebraic Theory of Dynamic Network Routing paper

• Extending ORA for Spatial and Temporal Data poster
• Skye Bender-deMol, Martina Morris, James Moody: Prototype Packages for Managing and Animating Longitudinal Network Data: dynamic network and rSoNIA jStatSoft; paper
• Representing time dependent graphs in Neo4j page

• Derek Greene, Donal Doyle, Padraig Cunningham: Tracking the Evolution of Communities in Dynamic Social Networks report
• Frederic Gilbert, Paolo Simonetto, Faraz Zaidi, Fabien Jourdan, Romain Bourqui: Communities and hierarchical structures in dynamic social networks: analysis and visualization paper
• Shalizi's notebooks: network data analysis; bootstrap; homophily-influence;

• Other references

October 28-30, 2013

Overview of the definitions/approaches from literature:

• Pajek's approach (intervals and events) - discrete time
• Sonia's approach - continuos time
• Holme's approach

Types of temporal networks: Can be important in solving the problems.

• Sonia
• Pajek
• Holme
• single intervals with the same terminal time - publications, citations

Which of the “standard” problems (reachability/connectivity, strong components, fastest/shortest paths, …) can be extended to temporal networks and how?

It seems that some of these problems were already (at least partially) studied.

Questions:

• How is the movement realized? Instantaneously? The weight of a link equals to the transition time?
• Can a vertex in which is the traveler be inactive between its arrival and its departure?
• Can we construct semirings for the selected problems?