Analysis-of-Human-Mobility-Datasets.md

@@ -322,26 +322,26 @@ By including isolated nodes and small components in our analysis, rather than an
 
 ### Static Reachability
 
+One way to measure the connectivity of a dataset is to count how many devices in the dataset's static contact graph are reachable from a given source device by following the edges of the contact graph.
+Averaging over all possible source devices gives a metric that we call the *mean static reachability* of the dataset.
+This is the fraction of pairs of devices that belong to the same component as each other in the static contact graph.
+
 | Dataset | Mean static reachability |
 |---------|--------------------------|
 | Haggle  |                    92.7% |
 | Office  |                   100.0% |
 | Village |                    95.4% |
 
-We can measure *static reachability* by counting how many devices in the static contact graph are reachable from a given source device.
-Averaging over all possible source devices gives the *mean static reachability*.
-This is the fraction of pairs of devices that belong to the same component as each other in the static contact graph.
-
 The mean static reachability of the office dataset is 100% because all devices belong to the same component.
 
 The mean static reachability of the Haggle dataset is below 100% because the devices represented by the two isolated nodes in the static contact graph can't reach (or be reached by) any other devices.
 
 Similarly, the mean static reachability of the village dataset is below 100% because the two devices that belong to the small component of the static contact graph can only reach (and be reached by) each other.
 
-The mean static reachability of a dataset gives us an upper bound on the delivery performance that we can expect from any delay-tolerant network, given the mobility patterns recorded in the dataset.
-For example, no delay-tolerant network could deliver messages between more than 92.7% of sender-recipient pairs, given the mobility patterns recorded in the Haggle dataset, because two of the potential sender/recipient devices never made contact with other devices.
+The mean static reachability of a dataset gives us an upper bound on the delivery performance that we can expect any delay-tolerant network to achieve, given the mobility patterns recorded in the dataset.
+For example, given the mobility patterns recorded in the Haggle dataset, no delay-tolerant network could deliver messages between more than 92.7% of sender-recipient pairs.
 
-Next we'll see that we can tighten this upper bound by including information about the order in which contacts happened.
+Next we'll see how we can tighten this upper bound by including information about the order in which contacts happened.
 
 ## Dynamic Contact Graphs
 
@@ -349,19 +349,21 @@ The static contact graph captures information about which devices made contact w
 To capture this information as well, we can construct a *dynamic contact graph* for each dataset.
 
 To do this, we create a layered graph in which each layer represents the contacts between devices at a given instant.
+Every time there's a connectivity change (ie the start or end of a contact), we add a new layer to the graph representing the new state.
+
 We start by creating the bottom layer, which simply contains a node representing each device.
 Then we process the detection events in order of time.
 
 When a contact begins, we add a new layer to the graph that duplicates the nodes and edges of the layer below.
-We then an edge to the new layer that connects the two devices involved in the new contact.
+Then we add an edge to the new layer that connects the two devices involved in the new contact.
 
 When a contact ends, we likewise add a new layer that duplicates the nodes and edges of the layer below.
-We then remove from the new layer the edge representing the contact that has just ended.
+Then we remove from the new layer the edge representing the contact that has just ended.
 
 In both cases, we add a directed edge from each node in the layer below to the node representing the same device in the new layer.
 
-The result is a graph in which it is possible to follow edges horizontally within each layer, and vertically from each layer to the layer above (later in time), but *not* to the layer below (earlier in time).
-Horizontal edges represent contacts between devices at a given instant, while vertical edges connect nodes representing the same device at different instants.
+The result is a graph in which it is possible to follow edges horizontally within each layer, and vertically from each layer to the layer above (later in time), but *not* to the layer below (earlier in time), because the edges between layers are directed.
+Horizontal edges represent contacts between devices at a given instant, while vertical edges connect nodes that represent the same device at different instants.
 
 Thus, for example, if a contact occurs between devices `A` and `B`, and then after this contact has ended there is a second contact between devices `B` and `C`, the graph allows us to see that `C` is transitively reachable from `A`, but not vice versa.
 `A` could transfer a message to `B` during their contact, and `B` could then transfer this message to `C` during their later contact, but the reverse would not be possible, as the contact between `A` and `B` ends before the contact between `B` and `C` begins.
@@ -371,8 +373,10 @@ We can use the dynamic contact graph to study the emergent properties of the mob
 For example, if we start from a given device at a given time, which devices are transitively reachable, and how long does it take to reach them?
 How do these properties vary with the choice of starting device or starting time?
 
-A dynamic contact graph can be built from directed or undirected contacts.
-As discussed above, we're mainly interested in undirected contacts because the delay-tolerant networks we're interested in building will use two-way communication to exchange messages.
+A dynamic contact graph can be built from directed or undirected contacts, resulting in a graph that has directed or undirected edges within each layer.
+(The edges between layers are always directed.)
+
+As discussed above, for the purposes of this research we're mainly interested in undirected contacts, because the delay-tolerant networks we're interested in building will use two-way communication to exchange messages.
 But it's possible to imagine delay-tolerant networks that use one-way broadcasts to propagate messages, and such networks can be modeled using dynamic contact graphs with directed contacts - that is, with directed edges within each layer.
 
 ### Events With the Same Timestamp
@@ -382,6 +386,41 @@ When building a dynamic contact graph, if two or more events have the same times
 In particular, an event indicating the end of a contact is always processed after the event indicating the beginning of the same contact, even if they have the same timestamp.
 (This is common, because as discussed above, many contacts have recorded durations of zero, and so the events indicating the beginning and end of such a contact have the same timestamp.)
 
+### Example
+
+The following figures show how to construct a dynamic contact graph for a simple dataset with three devices: `A`, `B` and `C`.
+The dataset starts at time `t<sub>1</sub>`.
+There's a contact between `A` and `B` beginning at `t<sub>2</sub>` and ending at `t<sub>3</sub>`, and there's a contact between `B` and `C` beginning at `t<sub>4</sub>` and ending at `t<sub>5</sub>`.
+
+---
+
+![dynamic-contact-graph-1.png](uploads/img/dynamic-contact-graph-1.png)
+
+**The bottom layer of the contact graph has a node for each device.**
+
+---
+
+![dynamic-contact-graph-2.png](uploads/img/dynamic-contact-graph-2.png)
+
+**Each time an event occurs, we add a new layer to the graph, duplicating the nodes and edges from the layer below.**
+
+---
+
+![dynamic-contact-graph-3.png](uploads/img/dynamic-contact-graph-3.png)
+
+**In this case the event is the start of a contact, so we add an edge to the new layer representing the new contact. We also add directed edges from each node in the layer below to the node representing the same device in the new layer.**
+
+---
+
+![dynamic-contact-graph-full.png](uploads/img/dynamic-contact-graph-full.png)
+
+**The finished graph shows the full sequence of events.**
+
+---
+
+In the finished graph, we can see that if we start from device `A` at time `t<sub>1</sub>` it's possible to reach `B` at `t<sub>2</sub>` and `C` at `t<sub>4</sub>`.
+On the other hand, if we start from `C` at `t<sub>1</sub>`, we reach `B` at `t<sub>4</sub>` and we can't reach `A` at all.
+
 ## Dynamic Reachability Analysis
 
 By building a dynamic contact graph for each dataset we can begin to study which devices are reachable from which others at which times, which tells us which devices would potentially be able to send messages to each other in a delay-tolerant network.
@@ -402,14 +441,16 @@ A negative result at this stage could save us a lot of effort designing and depl
 ### Dynamic Reachability
 
 Just as we measured static reachability in a static contact graph by counting how many devices are reachable from a given source device, in a dynamic contact graph we can measure *dynamic reachability* by counting how many devices are reachable from a given source device, *starting at a given time*.
-Averaging over all possible source devices gives the *mean dynamic reachability* at the given time.
+Averaging over all possible source devices gives a metric that we call the *mean dynamic reachability* at the given time.
 
 This is the fraction of source-destination pairs such that a delay-tolerant path exists from the source to the destination starting at the given time, and thus a message sent by the source at the given time could, in principle, eventually reach the destination.
 
 The figures below show the mean dynamic reachability for each dataset, as a function of the start time.
 
 The dashed line in each figure shows the mean static reachability, for comparison.
-Static reachability is always at least as high as dynamic reachability, as it ignores the order in which contacts occur.
+Static reachability is always at least as high as dynamic reachability, as static reachability ignores the order in which contacts occur.
+
+One way to think of it is that static reachability is what we get if we flatten all the layers of the dynamic contact graph into a single layer.
 
 ---