Dynamic graphs

Dynamic graphs are graphs that change over time.

Almost all networks observed in the real world expose a temporal behaviour [1]. There are different types of dynamic graphs depending on what elements change:

  • Intermittent edges — various social networks that present interaction between nodes over time (e.g. phone calls, e-mails, chatting groups, collaboration networks, etc.)
  • Intermittent nodes and edges — nodes in graph can appear and disappear (e.g. citation networks, wireless sensor networks)
  • Mobile nodes and intermittent edges — various mobile ad hoc network, where nodes can move and edges exist based on the position of nodes (e.g. vehicular ad hoc networks).
  • Mobile and intermittent nodes — nodes not only move but also can be switched of (e.g. pocket switched networks (PSNs))

Analysis of dynamic graphs is challenging as a dynamic graph evolves over time. Traditional approaches used for static social networks usually base on centralised metrics, what makes them inefficient for computing at every change in a graph. Therefore, decentralised graph algorithms are being used in order to analyse the characteristics of the network [2].

Besides standard graph analysis metrics, dynamic graphs can be measured additional dynamic graph metrics [3].
Graph metrics:

  • Degree — number of neighbors of a node, e.g. the average degree, the distributions of degree and the joint degree distributions.
  • Clustering Coefficient — how close the graph from being a clique and whether a node’s neighbors are also neighbors of each other are defined.
  • Shortest Path — the shortest path between two nodes. Given the shortest path lengths between a node and all the reachable nodes from the node other metrics are defined eccentricity and closeness (the maximum and the average of these shortest path lengths, respectively). The maximum eccentricity is referred as
    the diameter of the graph.

Dynamic graph metrics:

  • Graph Similarity — feature-based or structure-based
  • Community detection — assigning nodes to a group based on a similarity metric.
  • Anomaly Detection – done by time-series analysis of graph data, minimum description length method from graph-theory, or statistical window based approaches.

Read more:

  1. Holme, Petter, and Jari Saramäki. “Temporal networks.” Physics reports 519.3 (2012): 97-125.[doi]
  2. Sun, Jie, et al. “Dynamic computation of network statistics via updating schema.” Physical Review E 79.3 (2009): 036116., [doi]
  3. Bilgin, Cemal Cagatay, and Bülent Yener. “Dynamic network evolution: Models, clustering, anomaly detection.” IEEE Networks (2006).[pdf]