4 Temporal Network Analysis and Visualisation in pathpy

Ingo Scholtes
Data Analytics Group
Department of Informatics (IfI)
University of Zurich

September 4 2018

Introduction to the TemporalNetwork class

We have considered the Paths class, which is useful if you have direct access to path statistics in your time series data. This includes clickstreams of users in information networks, origin-destination statistics in transportation networks, flight ticket sequences, or other collections of short, ordered sequences.

In this unit, we expand this view towards temporal networks, i.e. high-resolution time series network data, where edges carry fine-grained time stamps. Considering technical, social, and biological systems that can be modelled as dynamic networks, such data cover a broad class of complex systems that can be studied with higher-order network models.

pathpy provides special support for the analysis of temporal networks data via its TemporalNetwork class. It is suitable for data that captures time-stamped edges $(v, w, t)$ instantaneously occurring at discrete time stamps $t$. Let us start by creating an empty instance of this class.

**TODO:** Import the package `pathpy` and rename it to `pp`. Create a new instance `t` of the class `TemporalNetwork` and print a summary of the instance.

In [1]:
import pathpy as pp

t = pp.TemporalNetwork()
print(t)
Nodes:			0
Time-stamped links:	0
Links/Nodes:		N/A

The TemporalNetwork instance t stores two key information: a list of nodes t.nodes and a collection t.tedges of time-stamped edges $(v, w, t)$. Let us add some time-stamped edges to this instance.

**TODO:** Use the `add_edge` function to add six (directed) time-stamped edges $(a,b, 1), (b, a, 3), (b, c, 3), (d, c, 4), (c, d, 5), (c, b, 6)$ and print the result.

In [2]:
t.add_edge('a', 'b', 1)
t.add_edge('b', 'a', 3)
t.add_edge('b', 'c', 3)
t.add_edge('d', 'c', 4)
t.add_edge('c', 'd', 5)
t.add_edge('c', 'b', 6)
print(t)
Nodes:			4
Time-stamped links:	6
Links/Nodes:		1.5
Observation period:	[1, 6]
Observation length:	 5 
Time stamps:		 5 
Avg. inter-event dt:	 1.25
Min/Max inter-event dt:	 1/2

We get basic summary statistics, such as the number of time-stamped interactions, the minimum and maximum timestamp, the duration of the observation, the number of different timestamps, as well as the average, minimum, and maximum time difference between consecutive time-stamped edges.

Above we used integer timestamps, which represent discrete time units. But we often have data where time is given in terms of a date and/or time of day. Luckily, pathpy supports arbitrary timestamp formats. Let us try this in an example.

**TODO:** Create a new `TemporalNetwork` instance `t_realtime` and add three time-stamped edges with string timestamps in the format "YYYY-MM-DD HH:mm:SS". Print the resulting instance and print all time-stamped edges.

In [3]:
t_realtime = pp.TemporalNetwork()
t_realtime.add_edge('a', 'b', '2018-08-22 09:30:22')
t_realtime.add_edge('b', 'c', '2018-08-22 09:30:25')
t_realtime.add_edge('c', 'a', '2018-08-22 10:30:25')
print(t_realtime)

for e in t_realtime.tedges:
    print(e)
Nodes:			3
Time-stamped links:	3
Links/Nodes:		1.0
Observation period:	[1534923022, 1534926625]
Observation length:	 3603 
Time stamps:		 3 
Avg. inter-event dt:	 1801.5
Min/Max inter-event dt:	 3/3600
('a', 'b', 1534923022)
('b', 'c', 1534923025)
('c', 'a', 1534926625)

We observe that pathpy internally converts such timestamps into UNIX timestamps. For custom formats, we can set a custom timestamp_format parameter that will be used for this conversion. After the conversion, all time units will be in seconds (see e.g. the min/max inter-event time).

Just like other pathpy objects, we can directly embed interactive visualisations of a TemporalNetwork in-line in jupyter. Let us try this with our first example instance t.

**TODO:** Visualise the `TemporalNetwork` instance `t` by writing the instance variable in an empty `jupyter` cell.

In [4]:
t
Out[4]:
t stop restart

Using the default parameters, this visualisation is too fast. Luckily, we can use the generic pp.visualisation.plot function to pass a style for the visualisation. We can use all parameters that we used for static networks, plus additional parameters that influence temporal aspects of the visualisation.

Of particular importance are the parameters ms_per_frame and ts_per_frame: The first specifies how many time units will be shown in one frame of the visualisation, allowing us to compress the visualisation by showing multiple timestamps in a single frame. This is helpful when you want to coarse-grain visualisations of high-resolution temporal network data. The parameter ms_per_frame defines the target frame rate of the visualisation by adjusting how many milliseconds each frame is displayed.

Two more parameters will influence the force-directed layout algorithm, that is used to position nodes in the network. In a temporal network, the question is which time-stamped edges should be taken into account for the force-calculation at any given time stamp. If we only consider currently active edges, the layout will change too fast to recognize interesting patterns. If we consider all edges at every time step, node positions will be static despite the dynamics of edges. In real settings we want a compromise between those extremes, i.e. we specify a time window around the current time stamp within which edges are taken into account in the force-directed layout calculation. We can achieve this by setting the number of timestamps to consider before and after the currently shown frame via the look_ahead and look_behind parameters.

Finally, we can style active and inactive nodes and edges individually via the parameters active_edge_width, inactive_edge_width, active_node_color, and inactive_node_color. This allows us to change the color and/or size of nodes/edges whenever they are involved in an interaction.

**TODO:** Create a visualisation where a single timestamp is shown per frame, and each frame is shown for 2 seconds. For the force-directed layout, consider edges active up to two time units before and after the current timestamp. Increase the thickness of currently active egdes.

In [6]:
style = {    
    'ts_per_frame': 1, 
    'ms_per_frame': 2000,
    'look_ahead': 2, 
    'look_behind': 2, 
    'node_size': 15, 
    'inactive_edge_width': 2,
    'active_edge_width': 4, 
    'label_color' : '#ffffff',
    'label_size' : '24px',
    'label_offset': [0,5]
    }
pp.visualisation.plot(t, **style)
t stop restart

Again, this generates an embedded interactive visualisation, i.e. you can pan and zoom, or drag nodes. The controls in the top part of the visualisation allow you to stop, start or restart the simulation.

We can easily save such interactive visualisations as stand-alone HTML5 files, which can be distributed via the Web.

**TODO:** Save the visualisation from above to a file and open it in a Browser.

In [7]:
pp.visualisation.export_html(t, '../visualisations/4_temporal_network.html', **style)

Calculating path statistics in temporal networks

In the previous session, we modelled, analysed and visualised path statistics using higher-order network models. But how can we apply this higher-order analytics framework to time-stamped network data?

The key idea is that the ordering and timing in which time-stamped edges occur in a TemporalNetwork gives rise to so-called causal or time-respecting paths. In a nutshell, for two time-stamped edges $(a, b, t)$ and $(b, c, t')$ to contribute to a causal path $a \rightarrow b \rightarrow c$ it must hold that $t < t'$. If we swap timestamps such that the edge $(b, c)$ occurs before (a,b), no causal path $a \rightarrow b \rightarrow c$ exists.

So we observe that the chronological order of time-stamped edges crucially influences causal paths, i.e. which nodes can possibly influence each other in time-stamped edge sequences. Moreover, we often want to limit the maximum time difference between consecutive edges that contribute to a causal path. For data on dynamic social interactions that spans several years, it does not make sense to consider all chronologically ordered edges as possible causal paths for the propagation of information. After all, humans have limited memory and we should thus consider interactions that occur far apart in time as independent.

We can formally add this condition by setting a maximum time difference $\delta$ for the path calculation. That is, we only consider two edges $(a, b, t)$ and $(b, c, t')$ to contribute to a causal path $a \rightarrow b \rightarrow c$ if $ 0 < t' - t \leq \delta$.

With this definition at hand, and by setting our maximum time difference $\delta$, we can now calculate causal path statistics in time-stamped network data. pathpy provides powerful algorithms to calculate (or estimate) causal path statistics based on a TemporalNetwork instance. Let us try this in our toy example.

**TODO:** Use the method `pp.path_extraction.paths_from_temporal_network_dag` to calculate causal path statistics for the example temporal network `t` and a maximum time difference $\delta=1$. Print the resulting `Paths` object. as well as all causal paths.

In [8]:
causal_paths = pp.path_extraction.temporal_paths.paths_from_temporal_network_dag(t, delta=1)
print(causal_paths)

for l in causal_paths.paths:
    for p in causal_paths.paths[l]:
        if causal_paths.paths[l][p][1]>0:
            print('{0} -> {1}'.format(p, causal_paths.paths[l][p][1]))
2018-09-04 22:19:21 [Severity.INFO]	Constructing time-unfolded DAG ...
2018-09-04 22:19:21 [Severity.INFO]	finished.
Directed Acyclic Graph
Nodes:		10
Roots:		4
Leaves:		5
Links:		6
Acyclic:	None

2018-09-04 22:19:21 [Severity.INFO]	Generating causal trees for 4 root nodes ...
2018-09-04 22:19:21 [Severity.INFO]	finished.
Total path count: 		5.0 
[Unique / Sub paths / Total]: 	[5.0 / 13.0 / 18.0]
Nodes:				4 
Edges:				6
Max. path length:		2
Avg path length:		1.2 
Paths of length k = 0		0.0 [ 0.0 / 11.0 / 11.0 ]
Paths of length k = 1		4.0 [ 4.0 / 2.0 / 6.0 ]
Paths of length k = 2		1.0 [ 1.0 / 0.0 / 1.0 ]

('b', 'c') -> 1.0
('b', 'a') -> 1.0
('c', 'b') -> 1.0
('a', 'b') -> 1.0
('d', 'c', 'd') -> 1.0

For $\delta=1$, it is easy to verify that this output is correct. After all, there is only one pair of (directed) edges $(d, c, 4), (c, d, 5)$ that contributes to a causal path of length two. In addition, we have four time-stamped edges, each of which is a trivial causal path of length one.

This brings us to an important observation: In line with what we have discussed in the previous session, time-aggregated models of temporal networks discard the ordering and timing of links. They are thus maximum entropy, first-order network models for causal paths in temporal networks.

While it is easy to understand the path statistics for a maximum time difference of $\delta=1$, already for $\delta=2$ the situation gets more complicated.

**TODO:** Generate and print all causal paths emerging for a maximum time difference $\delta=2$.

In [9]:
causal_paths = pp.path_extraction.paths_from_temporal_network_dag(t, delta=2)
print(causal_paths)

for l in causal_paths.paths:
    for p in causal_paths.paths[l]:
        if causal_paths.paths[l][p][1]>0:
            print('{0} -> {1}'.format(p, causal_paths.paths[l][p][1]))
2018-09-04 22:19:37 [Severity.INFO]	Constructing time-unfolded DAG ...
2018-09-04 22:19:37 [Severity.INFO]	finished.
Directed Acyclic Graph
Nodes:		13
Roots:		2
Leaves:		8
Links:		12
Acyclic:	None

2018-09-04 22:19:37 [Severity.INFO]	Generating causal trees for 2 root nodes ...
2018-09-04 22:19:37 [Severity.INFO]	finished.
Total path count: 		4.0 
[Unique / Sub paths / Total]: 	[4.0 / 24.0 / 28.0]
Nodes:				4 
Edges:				6
Max. path length:		3
Avg path length:		2.25 
Paths of length k = 0		0.0 [ 0.0 / 13.0 / 13.0 ]
Paths of length k = 1		0.0 [ 0.0 / 9.0 / 9.0 ]
Paths of length k = 2		3.0 [ 3.0 / 2.0 / 5.0 ]
Paths of length k = 3		1.0 [ 1.0 / 0.0 / 1.0 ]

('d', 'c', 'b') -> 1.0
('a', 'b', 'a') -> 1.0
('d', 'c', 'd') -> 1.0
('a', 'b', 'c', 'd') -> 1.0

We now observe one causal path $a \rightarrow b \rightarrow c \rightarrow d$ of length three, and three additional causal paths of length two. All shorter causal paths are contained in those longer causal paths, as shown by the path statistics shown above.

While I will not go into the full details of pathpy's path calculation algorithm, we can at least peek into how it is done. Internally, pathpy generates a so-called time-unfolded directed and acyclic graph (see definition and illustration in this work). This graph is then the basis to calculate causal path statistics. We can get an idea how this works by manually generating a time-unfolded graph from a temporal network.

**TODO:** Use the `pp.DAG.from_temporal_network` method to create a time-unfolded graph from the `TemporalNetwork` `t` for $\delta=2$. Generate a visualisation where you color all time-unfolded nodes according to the "real" node to which they belong and increase the size of root nodes so you can easily tell them apart.

In [10]:
dag, node_map = pp.DAG.from_temporal_network(t, delta=2)

color_map = {'a': 'red',
             'b': 'green',
             'c': 'blue',
             'd': 'red'}

style = { 
    'width': 400, 
    'height': 300, 
    'node_color': { v: color_map[node_map[v]] for v in dag.nodes }, 
    'node_size': { v: 8 if v in dag.roots else 5 for v in dag.nodes }
}

pp.visualisation.plot(dag, **style)
[save svg]

We obtain a time-unfolded graph, where each node is a temporal copy of an actual node, and where colors indicate to which node each temporal copy belongs. Importantly, the resulting directed acyclic graph has two root nodes (shown as larger nodes) with degree zero. Each of these root nodes shows where a causal path can possibly start. These roots are the basis for pathpy's path calculation algorithm, i.e. in the simplest case pathpy will simply process all of these results to generate the path statistics.

Higher-order analysis of real dynamic social networks

To simplify the analysis of large collections of time-stamped network data, pathpy natively supports SQLite databases. For this, let us import python's sqlite3 module and use the connect function to connect to a SQLite database file. In order to access columns by name rather than index, we also need to set the default row_factory on the Connection object that is returned by the connect function to sqlite3.Row.

**TODO:** Import the module `sqlite3` and connect to the `SQLite` database file `temporal_networks.db`, which we provide for you in the `/data` directory. Set the `row_factory` of the resulting connection to `row_factory`.

In [11]:
import sqlite3
con = sqlite3.connect('../data/temporal_networks.db')
con.row_factory = sqlite3.Row

We can now generate temporal networks from an SQLite database. For this, we must pass a so-called SQLite cursor to the constructor of TemporalNetwork. This cursor essentially tells which rows and columns of the database should be used for the temporal network creation. We can create it by passing an SQL query to the execute function of the connection object.

The TemporalNetwork class assumes that the source, target, and timestamp of time-stamped edges are stored in columns called source, target and time. If your database has a different format, you can use the SQL as keyword to rename the columns in the query. Note that you can use the extension SQLite to browse the SQLite database file within Visual Studio Code. Once you have installed it, hit CTRL + Shift + P and enter the command SQLite: Open Database in Explorer. This will bring up a new database panel in the explorer section on the left, which you can use to show the structure and contents of the database.

Let us now try this with a data set on (undirected) time-stamped proximity contacts between patients and workers in a hospital, collected via the Sociopatterns project.

**TODO:** Create an undirected `TemporalNetwork` instance `t_ho` from an `SQL` query of the database `sociopatterns_hospital` and print the resulting object.

In [12]:
t_ho = pp.TemporalNetwork.from_sqlite(con.execute('SELECT source, target, time FROM sociopatterns_hospital'),
                                      directed=False)
print(t_ho)
2018-09-04 22:20:07 [Severity.INFO]	Retrieving undirected time-stamped links ...
2018-09-04 22:20:08 [Severity.INFO]	Building index data structures ...
2018-09-04 22:20:08 [Severity.INFO]	Sorting time stamps ...
2018-09-04 22:20:08 [Severity.INFO]	finished.
Nodes:			75
Time-stamped links:	64848
Links/Nodes:		864.64
Observation period:	[140, 347640]
Observation length:	 347500 
Time stamps:		 9453 
Avg. inter-event dt:	 36.76470588235294
Min/Max inter-event dt:	 20/26980

We see that this temporal network has more than 64,000 time-stamped contacts between 75 individuals. On average, each individual engages in more than 860 contacts and the average time difference between contacts is approx. 36 seconds. More interestingly, the minimum inter-event time is 20 seconds, which is due to the fact that the sensor equipment used registered contacts every 20 seconds.

Blindly calculating causal paths for large values of $\delta$ (say $\delta=300$ for a maximum time difference between contacts of five minutes) would lead to the generation of a huge time-unfolded graph. However, since the sampling interval in this data set is larger than the time unit of 1 second, we can use pathpy's time rescaling feature. It helps us to more efficiently calculate causal paths by rescaling internal time units to match a data set's sampling frequency. In the Sociopatterns data, we can rescale time by a factor of 20 without any loss of information. This means that timestamps 20, 40, 80 will be mapped to integer time units 1, 2, 4. Let us try this:

**TODO:** Repeat the previous step, but rescale internal time units by a factor of 20. Print the resulting instance `t_ho`

In [13]:
t_ho = pp.TemporalNetwork.from_sqlite(con.execute('SELECT source, target, time FROM sociopatterns_hospital'),
                                      directed=False, time_rescale=20)
print(t_ho)
2018-09-04 22:20:15 [Severity.INFO]	Retrieving undirected time-stamped links ...
2018-09-04 22:20:15 [Severity.INFO]	Building index data structures ...
2018-09-04 22:20:16 [Severity.INFO]	Sorting time stamps ...
2018-09-04 22:20:16 [Severity.INFO]	finished.
Nodes:			75
Time-stamped links:	64848
Links/Nodes:		864.64
Observation period:	[7, 17382]
Observation length:	 17375 
Time stamps:		 9453 
Avg. inter-event dt:	 1.838235294117647
Min/Max inter-event dt:	 1/1349

The fact that the minimum inter-event time is now 1 shows that the internal time units have been scaled accordingly. Note that as long as we match the time rescaling to the ssampling frequency, this does not change path structure of the resulting temporal network. We must, however, account for the time unit when we specifiy the $\delta for the causal path calculation.

**TODO:** Calculate causal paths in the temporal network `t_ho` and set the maximum time difference to one minute.

In [14]:
causal_paths = pp.path_extraction.paths_from_temporal_network_dag(t_ho, delta=3)
print(causal_paths)
2018-09-04 22:20:24 [Severity.INFO]	Constructing time-unfolded DAG ...
2018-09-04 22:20:26 [Severity.INFO]	finished.
Directed Acyclic Graph
Nodes:		85215
Roots:		8276
Leaves:		34570
Links:		194544
Acyclic:	None

2018-09-04 22:20:26 [Severity.INFO]	Generating causal trees for 8276 root nodes ...
---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-14-e246a94e630c> in <module>()
----> 1 causal_paths = pp.path_extraction.paths_from_temporal_network_dag(t_ho, delta=3)
      2 print(causal_paths)

~\Anaconda3\lib\site-packages\pathpy\path_extraction\temporal_paths.py in paths_from_temporal_network_dag(tempnet, delta, max_subpath_length)
    356 
    357         # calculate all unique longest path in causal tree
--> 358         causal_paths += paths_from_dag(causal_tree, causal_mapping, repetitions=False, max_subpath_length=max_subpath_length)
    359         current_root += 1
    360 

~\Anaconda3\lib\site-packages\pathpy\path_extraction\dag_paths.py in paths_from_dag(dag, node_mapping, max_subpath_length, separator, repetitions, unique)
    143 
    144         Log.add('Expanding Subpaths', Severity.INFO)
--> 145         p.expand_subpaths()
    146         Log.add('finished.', Severity.INFO)
    147         return p

~\Anaconda3\lib\site-packages\pathpy\classes\paths.py in expand_subpaths(self)
    574                         # Add frequency as a subpath to *first* entry of array
    575                         path_slice = path[s:s + k + 1]
--> 576                         self.paths[k][path_slice][0] += frequency
    577 
    578 

KeyboardInterrupt: 

For this calculation, pathpy needs to analyse a time-unfolded graph with more than 85,000 nodes and more than 8276 root nodes, which are processed in the path calculation. This takes a moment, so let us skip it here by interrupting the kernel. In fact, depending on the size and temporal characteristics of your data set, exhaustively calculating all causal paths for large values of $\delta$ can quickly become prohibitive.

Instead of exhaustively calculating all causal paths we actually want an efficient method to get a quick estimate of causal path statistics, which we can then use to infer a higher-order models for causal paths. pathpy provides a smart way to do this by randomly sampling roots in the time-unfolded acyclic graph. Let us try this for 50 root nodes.

**TODO:** Use the method `sample_paths_from_temporal_network_dag` to estimate causal path statistics in the temporal network `t_ho` for a maximum time difference of one minute, randomly sampling 50 roots in the time-unfolded graph.

In [15]:
causal_paths = pp.path_extraction.sample_paths_from_temporal_network_dag(t_ho, delta=3, num_roots=50)
print(causal_paths)
Directed Acyclic Graph
Nodes:		85215
Roots:		8276
Leaves:		34570
Links:		194544
Acyclic:	None

Total path count: 		6492.0 
[Unique / Sub paths / Total]: 	[6491.0 / 32222737.0 / 32229229.0]
Nodes:				66 
Edges:				575
Max. path length:		339
Avg path length:		71.96996303142329 
Paths of length k = 0		0.0 [ 0.0 / 473721.0 / 473721.0 ]
Paths of length k = 1		13.0 [ 12.0 / 467216.0 / 467229.0 ]
Paths of length k = 2		26.0 [ 26.0 / 460711.0 / 460737.0 ]
Paths of length k = 3		40.0 [ 40.0 / 454218.0 / 454258.0 ]
Paths of length k = 4		57.0 [ 57.0 / 447748.0 / 447805.0 ]
Paths of length k = 5		53.0 [ 53.0 / 441339.0 / 441392.0 ]
Paths of length k = 6		69.0 [ 69.0 / 434967.0 / 435036.0 ]
Paths of length k = 7		71.0 [ 71.0 / 428662.0 / 428733.0 ]
Paths of length k = 8		72.0 [ 72.0 / 422427.0 / 422499.0 ]
Paths of length k = 9		77.0 [ 77.0 / 416259.0 / 416336.0 ]
Paths of length k = 10		78.0 [ 78.0 / 410167.0 / 410245.0 ]
Paths of length k = 11		67.0 [ 67.0 / 404164.0 / 404231.0 ]
Paths of length k = 12		81.0 [ 81.0 / 398214.0 / 398295.0 ]
Paths of length k = 13		84.0 [ 84.0 / 392342.0 / 392426.0 ]
Paths of length k = 14		86.0 [ 86.0 / 386552.0 / 386638.0 ]
Paths of length k = 15		77.0 [ 77.0 / 380857.0 / 380934.0 ]
Paths of length k = 16		83.0 [ 83.0 / 375233.0 / 375316.0 ]
Paths of length k = 17		78.0 [ 78.0 / 369697.0 / 369775.0 ]
Paths of length k = 18		79.0 [ 79.0 / 364238.0 / 364317.0 ]
Paths of length k = 19		71.0 [ 71.0 / 358866.0 / 358937.0 ]
Paths of length k = 20		70.0 [ 70.0 / 353566.0 / 353636.0 ]
Paths of length k = 21		71.0 [ 71.0 / 348335.0 / 348406.0 ]
Paths of length k = 22		81.0 [ 81.0 / 343165.0 / 343246.0 ]
Paths of length k = 23		71.0 [ 71.0 / 338086.0 / 338157.0 ]
Paths of length k = 24		76.0 [ 76.0 / 333073.0 / 333149.0 ]
Paths of length k = 25		70.0 [ 70.0 / 328142.0 / 328212.0 ]
Paths of length k = 26		74.0 [ 74.0 / 323277.0 / 323351.0 ]
Paths of length k = 27		67.0 [ 67.0 / 318493.0 / 318560.0 ]
Paths of length k = 28		69.0 [ 69.0 / 313774.0 / 313843.0 ]
Paths of length k = 29		60.0 [ 60.0 / 309133.0 / 309193.0 ]
Paths of length k = 30		66.0 [ 66.0 / 304546.0 / 304612.0 ]
Paths of length k = 31		58.0 [ 58.0 / 300033.0 / 300091.0 ]
Paths of length k = 32		59.0 [ 59.0 / 295577.0 / 295636.0 ]
Paths of length k = 33		65.0 [ 65.0 / 291174.0 / 291239.0 ]
Paths of length k = 34		59.0 [ 59.0 / 286842.0 / 286901.0 ]
Paths of length k = 35		59.0 [ 59.0 / 282569.0 / 282628.0 ]
Paths of length k = 36		63.0 [ 63.0 / 278351.0 / 278414.0 ]
Paths of length k = 37		62.0 [ 62.0 / 274197.0 / 274259.0 ]
Paths of length k = 38		59.0 [ 59.0 / 270108.0 / 270167.0 ]
Paths of length k = 39		59.0 [ 59.0 / 266078.0 / 266137.0 ]
Paths of length k = 40		61.0 [ 61.0 / 262105.0 / 262166.0 ]
Paths of length k = 41		64.0 [ 64.0 / 258190.0 / 258254.0 ]
Paths of length k = 42		61.0 [ 61.0 / 254342.0 / 254403.0 ]
Paths of length k = 43		56.0 [ 56.0 / 250560.0 / 250616.0 ]
Paths of length k = 44		57.0 [ 57.0 / 246833.0 / 246890.0 ]
Paths of length k = 45		58.0 [ 58.0 / 243162.0 / 243220.0 ]
Paths of length k = 46		56.0 [ 56.0 / 239551.0 / 239607.0 ]
Paths of length k = 47		56.0 [ 56.0 / 235996.0 / 236052.0 ]
Paths of length k = 48		56.0 [ 56.0 / 232497.0 / 232553.0 ]
Paths of length k = 49		55.0 [ 55.0 / 229055.0 / 229110.0 ]
Paths of length k = 50		56.0 [ 56.0 / 225667.0 / 225723.0 ]
Paths of length k = 51		54.0 [ 54.0 / 222337.0 / 222391.0 ]
Paths of length k = 52		54.0 [ 54.0 / 219061.0 / 219115.0 ]
Paths of length k = 53		50.0 [ 50.0 / 215843.0 / 215893.0 ]
Paths of length k = 54		45.0 [ 45.0 / 212680.0 / 212725.0 ]
Paths of length k = 55		45.0 [ 45.0 / 209562.0 / 209607.0 ]
Paths of length k = 56		45.0 [ 45.0 / 206489.0 / 206534.0 ]
Paths of length k = 57		43.0 [ 43.0 / 203463.0 / 203506.0 ]
Paths of length k = 58		46.0 [ 46.0 / 200477.0 / 200523.0 ]
Paths of length k = 59		49.0 [ 49.0 / 197534.0 / 197583.0 ]
Paths of length k = 60		49.0 [ 49.0 / 194640.0 / 194689.0 ]
Paths of length k = 61		48.0 [ 48.0 / 191796.0 / 191844.0 ]
Paths of length k = 62		45.0 [ 45.0 / 189003.0 / 189048.0 ]
Paths of length k = 63		46.0 [ 46.0 / 186254.0 / 186300.0 ]
Paths of length k = 64		45.0 [ 45.0 / 183552.0 / 183597.0 ]
Paths of length k = 65		44.0 [ 44.0 / 180896.0 / 180940.0 ]
Paths of length k = 66		43.0 [ 43.0 / 178285.0 / 178328.0 ]
Paths of length k = 67		42.0 [ 42.0 / 175718.0 / 175760.0 ]
Paths of length k = 68		40.0 [ 40.0 / 173195.0 / 173235.0 ]
Paths of length k = 69		37.0 [ 37.0 / 170715.0 / 170752.0 ]
Paths of length k = 70		38.0 [ 38.0 / 168271.0 / 168309.0 ]
Paths of length k = 71		38.0 [ 38.0 / 165865.0 / 165903.0 ]
Paths of length k = 72		38.0 [ 38.0 / 163497.0 / 163535.0 ]
Paths of length k = 73		38.0 [ 38.0 / 161167.0 / 161205.0 ]
Paths of length k = 74		38.0 [ 38.0 / 158875.0 / 158913.0 ]
Paths of length k = 75		33.0 [ 33.0 / 156626.0 / 156659.0 ]
Paths of length k = 76		33.0 [ 33.0 / 154410.0 / 154443.0 ]
Paths of length k = 77		30.0 [ 30.0 / 152230.0 / 152260.0 ]
Paths of length k = 78		31.0 [ 31.0 / 150079.0 / 150110.0 ]
Paths of length k = 79		28.0 [ 28.0 / 147962.0 / 147990.0 ]
Paths of length k = 80		30.0 [ 30.0 / 145871.0 / 145901.0 ]
Paths of length k = 81		29.0 [ 29.0 / 143811.0 / 143840.0 ]
Paths of length k = 82		29.0 [ 29.0 / 141780.0 / 141809.0 ]
Paths of length k = 83		32.0 [ 32.0 / 139775.0 / 139807.0 ]
Paths of length k = 84		30.0 [ 30.0 / 137804.0 / 137834.0 ]
Paths of length k = 85		27.0 [ 27.0 / 135866.0 / 135893.0 ]
Paths of length k = 86		24.0 [ 24.0 / 133958.0 / 133982.0 ]
Paths of length k = 87		23.0 [ 23.0 / 132075.0 / 132098.0 ]
Paths of length k = 88		24.0 [ 24.0 / 130214.0 / 130238.0 ]
Paths of length k = 89		24.0 [ 24.0 / 128377.0 / 128401.0 ]
Paths of length k = 90		25.0 [ 25.0 / 126563.0 / 126588.0 ]
Paths of length k = 91		25.0 [ 25.0 / 124774.0 / 124799.0 ]
Paths of length k = 92		25.0 [ 25.0 / 123010.0 / 123035.0 ]
Paths of length k = 93		26.0 [ 26.0 / 121270.0 / 121296.0 ]
Paths of length k = 94		23.0 [ 23.0 / 119559.0 / 119582.0 ]
Paths of length k = 95		25.0 [ 25.0 / 117869.0 / 117894.0 ]
Paths of length k = 96		25.0 [ 25.0 / 116204.0 / 116229.0 ]
Paths of length k = 97		23.0 [ 23.0 / 114566.0 / 114589.0 ]
Paths of length k = 98		24.0 [ 24.0 / 112950.0 / 112974.0 ]
Paths of length k = 99		19.0 [ 19.0 / 111363.0 / 111382.0 ]
Paths of length k = 100		20.0 [ 20.0 / 109794.0 / 109814.0 ]
Paths of length k = 101		21.0 [ 21.0 / 108244.0 / 108265.0 ]
Paths of length k = 102		20.0 [ 20.0 / 106716.0 / 106736.0 ]
Paths of length k = 103		19.0 [ 19.0 / 105209.0 / 105228.0 ]
Paths of length k = 104		20.0 [ 20.0 / 103720.0 / 103740.0 ]
Paths of length k = 105		18.0 [ 18.0 / 102253.0 / 102271.0 ]
Paths of length k = 106		18.0 [ 18.0 / 100804.0 / 100822.0 ]
Paths of length k = 107		18.0 [ 18.0 / 99373.0 / 99391.0 ]
Paths of length k = 108		18.0 [ 18.0 / 97960.0 / 97978.0 ]
Paths of length k = 109		18.0 [ 18.0 / 96565.0 / 96583.0 ]
Paths of length k = 110		18.0 [ 18.0 / 95188.0 / 95206.0 ]
Paths of length k = 111		19.0 [ 19.0 / 93828.0 / 93847.0 ]
Paths of length k = 112		18.0 [ 18.0 / 92488.0 / 92506.0 ]
Paths of length k = 113		19.0 [ 19.0 / 91165.0 / 91184.0 ]
Paths of length k = 114		19.0 [ 19.0 / 89861.0 / 89880.0 ]
Paths of length k = 115		19.0 [ 19.0 / 88576.0 / 88595.0 ]
Paths of length k = 116		19.0 [ 19.0 / 87310.0 / 87329.0 ]
Paths of length k = 117		19.0 [ 19.0 / 86063.0 / 86082.0 ]
Paths of length k = 118		19.0 [ 19.0 / 84835.0 / 84854.0 ]
Paths of length k = 119		19.0 [ 19.0 / 83626.0 / 83645.0 ]
Paths of length k = 120		19.0 [ 19.0 / 82436.0 / 82455.0 ]
Paths of length k = 121		19.0 [ 19.0 / 81265.0 / 81284.0 ]
Paths of length k = 122		19.0 [ 19.0 / 80113.0 / 80132.0 ]
Paths of length k = 123		18.0 [ 18.0 / 78981.0 / 78999.0 ]
Paths of length k = 124		18.0 [ 18.0 / 77867.0 / 77885.0 ]
Paths of length k = 125		18.0 [ 18.0 / 76771.0 / 76789.0 ]
Paths of length k = 126		17.0 [ 17.0 / 75694.0 / 75711.0 ]
Paths of length k = 127		16.0 [ 16.0 / 74635.0 / 74651.0 ]
Paths of length k = 128		16.0 [ 16.0 / 73592.0 / 73608.0 ]
Paths of length k = 129		16.0 [ 16.0 / 72565.0 / 72581.0 ]
Paths of length k = 130		16.0 [ 16.0 / 71554.0 / 71570.0 ]
Paths of length k = 131		15.0 [ 15.0 / 70560.0 / 70575.0 ]
Paths of length k = 132		14.0 [ 14.0 / 69582.0 / 69596.0 ]
Paths of length k = 133		14.0 [ 14.0 / 68618.0 / 68632.0 ]
Paths of length k = 134		13.0 [ 13.0 / 67669.0 / 67682.0 ]
Paths of length k = 135		13.0 [ 13.0 / 66733.0 / 66746.0 ]
Paths of length k = 136		13.0 [ 13.0 / 65810.0 / 65823.0 ]
Paths of length k = 137		15.0 [ 15.0 / 64898.0 / 64913.0 ]
Paths of length k = 138		13.0 [ 13.0 / 64003.0 / 64016.0 ]
Paths of length k = 139		15.0 [ 15.0 / 63119.0 / 63134.0 ]
Paths of length k = 140		13.0 [ 13.0 / 62252.0 / 62265.0 ]
Paths of length k = 141		15.0 [ 15.0 / 61396.0 / 61411.0 ]
Paths of length k = 142		12.0 [ 12.0 / 60558.0 / 60570.0 ]
Paths of length k = 143		15.0 [ 15.0 / 59729.0 / 59744.0 ]
Paths of length k = 144		12.0 [ 12.0 / 58918.0 / 58930.0 ]
Paths of length k = 145		15.0 [ 15.0 / 58116.0 / 58131.0 ]
Paths of length k = 146		12.0 [ 12.0 / 57332.0 / 57344.0 ]
Paths of length k = 147		15.0 [ 15.0 / 56557.0 / 56572.0 ]
Paths of length k = 148		10.0 [ 10.0 / 55802.0 / 55812.0 ]
Paths of length k = 149		13.0 [ 13.0 / 55054.0 / 55067.0 ]
Paths of length k = 150		11.0 [ 11.0 / 54321.0 / 54332.0 ]
Paths of length k = 151		13.0 [ 13.0 / 53597.0 / 53610.0 ]
Paths of length k = 152		11.0 [ 11.0 / 52888.0 / 52899.0 ]
Paths of length k = 153		12.0 [ 12.0 / 52189.0 / 52201.0 ]
Paths of length k = 154		9.0 [ 9.0 / 51505.0 / 51514.0 ]
Paths of length k = 155		11.0 [ 11.0 / 50828.0 / 50839.0 ]
Paths of length k = 156		7.0 [ 7.0 / 50166.0 / 50173.0 ]
Paths of length k = 157		10.0 [ 10.0 / 49508.0 / 49518.0 ]
Paths of length k = 158		7.0 [ 7.0 / 48863.0 / 48870.0 ]
Paths of length k = 159		10.0 [ 10.0 / 48222.0 / 48232.0 ]
Paths of length k = 160		7.0 [ 7.0 / 47594.0 / 47601.0 ]
Paths of length k = 161		10.0 [ 10.0 / 46970.0 / 46980.0 ]
Paths of length k = 162		7.0 [ 7.0 / 46359.0 / 46366.0 ]
Paths of length k = 163		10.0 [ 10.0 / 45752.0 / 45762.0 ]
Paths of length k = 164		7.0 [ 7.0 / 45158.0 / 45165.0 ]
Paths of length k = 165		10.0 [ 10.0 / 44568.0 / 44578.0 ]
Paths of length k = 166		7.0 [ 7.0 / 43991.0 / 43998.0 ]
Paths of length k = 167		10.0 [ 10.0 / 43418.0 / 43428.0 ]
Paths of length k = 168		7.0 [ 7.0 / 42858.0 / 42865.0 ]
Paths of length k = 169		11.0 [ 11.0 / 42301.0 / 42312.0 ]
Paths of length k = 170		7.0 [ 7.0 / 41759.0 / 41766.0 ]
Paths of length k = 171		10.0 [ 10.0 / 41221.0 / 41231.0 ]
Paths of length k = 172		7.0 [ 7.0 / 40696.0 / 40703.0 ]
Paths of length k = 173		10.0 [ 10.0 / 40175.0 / 40185.0 ]
Paths of length k = 174		7.0 [ 7.0 / 39667.0 / 39674.0 ]
Paths of length k = 175		8.0 [ 8.0 / 39165.0 / 39173.0 ]
Paths of length k = 176		4.0 [ 4.0 / 38675.0 / 38679.0 ]
Paths of length k = 177		4.0 [ 4.0 / 38189.0 / 38193.0 ]
Paths of length k = 178		4.0 [ 4.0 / 37707.0 / 37711.0 ]
Paths of length k = 179		4.0 [ 4.0 / 37229.0 / 37233.0 ]
Paths of length k = 180		3.0 [ 3.0 / 36756.0 / 36759.0 ]
Paths of length k = 181		3.0 [ 3.0 / 36286.0 / 36289.0 ]
Paths of length k = 182		3.0 [ 3.0 / 35819.0 / 35822.0 ]
Paths of length k = 183		4.0 [ 4.0 / 35354.0 / 35358.0 ]
Paths of length k = 184		4.0 [ 4.0 / 34893.0 / 34897.0 ]
Paths of length k = 185		5.0 [ 5.0 / 34435.0 / 34440.0 ]
Paths of length k = 186		3.0 [ 3.0 / 33984.0 / 33987.0 ]
Paths of length k = 187		5.0 [ 5.0 / 33534.0 / 33539.0 ]
Paths of length k = 188		2.0 [ 2.0 / 33092.0 / 33094.0 ]
Paths of length k = 189		3.0 [ 3.0 / 32651.0 / 32654.0 ]
Paths of length k = 190		2.0 [ 2.0 / 32214.0 / 32216.0 ]
Paths of length k = 191		3.0 [ 3.0 / 31778.0 / 31781.0 ]
Paths of length k = 192		2.0 [ 2.0 / 31346.0 / 31348.0 ]
Paths of length k = 193		3.0 [ 3.0 / 30915.0 / 30918.0 ]
Paths of length k = 194		2.0 [ 2.0 / 30488.0 / 30490.0 ]
Paths of length k = 195		3.0 [ 3.0 / 30062.0 / 30065.0 ]
Paths of length k = 196		3.0 [ 3.0 / 29639.0 / 29642.0 ]
Paths of length k = 197		3.0 [ 3.0 / 29219.0 / 29222.0 ]
Paths of length k = 198		3.0 [ 3.0 / 28802.0 / 28805.0 ]
Paths of length k = 199		3.0 [ 3.0 / 28388.0 / 28391.0 ]
Paths of length k = 200		3.0 [ 3.0 / 27977.0 / 27980.0 ]
Paths of length k = 201		3.0 [ 3.0 / 27569.0 / 27572.0 ]
Paths of length k = 202		3.0 [ 3.0 / 27164.0 / 27167.0 ]
Paths of length k = 203		3.0 [ 3.0 / 26762.0 / 26765.0 ]
Paths of length k = 204		3.0 [ 3.0 / 26363.0 / 26366.0 ]
Paths of length k = 205		3.0 [ 3.0 / 25967.0 / 25970.0 ]
Paths of length k = 206		3.0 [ 3.0 / 25574.0 / 25577.0 ]
Paths of length k = 207		3.0 [ 3.0 / 25184.0 / 25187.0 ]
Paths of length k = 208		3.0 [ 3.0 / 24797.0 / 24800.0 ]
Paths of length k = 209		3.0 [ 3.0 / 24413.0 / 24416.0 ]
Paths of length k = 210		3.0 [ 3.0 / 24032.0 / 24035.0 ]
Paths of length k = 211		3.0 [ 3.0 / 23654.0 / 23657.0 ]
Paths of length k = 212		3.0 [ 3.0 / 23279.0 / 23282.0 ]
Paths of length k = 213		3.0 [ 3.0 / 22907.0 / 22910.0 ]
Paths of length k = 214		3.0 [ 3.0 / 22538.0 / 22541.0 ]
Paths of length k = 215		3.0 [ 3.0 / 22172.0 / 22175.0 ]
Paths of length k = 216		3.0 [ 3.0 / 21809.0 / 21812.0 ]
Paths of length k = 217		3.0 [ 3.0 / 21449.0 / 21452.0 ]
Paths of length k = 218		3.0 [ 3.0 / 21092.0 / 21095.0 ]
Paths of length k = 219		3.0 [ 3.0 / 20738.0 / 20741.0 ]
Paths of length k = 220		3.0 [ 3.0 / 20387.0 / 20390.0 ]
Paths of length k = 221		3.0 [ 3.0 / 20039.0 / 20042.0 ]
Paths of length k = 222		3.0 [ 3.0 / 19694.0 / 19697.0 ]
Paths of length k = 223		3.0 [ 3.0 / 19352.0 / 19355.0 ]
Paths of length k = 224		3.0 [ 3.0 / 19013.0 / 19016.0 ]
Paths of length k = 225		3.0 [ 3.0 / 18677.0 / 18680.0 ]
Paths of length k = 226		3.0 [ 3.0 / 18344.0 / 18347.0 ]
Paths of length k = 227		3.0 [ 3.0 / 18014.0 / 18017.0 ]
Paths of length k = 228		3.0 [ 3.0 / 17687.0 / 17690.0 ]
Paths of length k = 229		3.0 [ 3.0 / 17363.0 / 17366.0 ]
Paths of length k = 230		3.0 [ 3.0 / 17042.0 / 17045.0 ]
Paths of length k = 231		3.0 [ 3.0 / 16724.0 / 16727.0 ]
Paths of length k = 232		3.0 [ 3.0 / 16409.0 / 16412.0 ]
Paths of length k = 233		3.0 [ 3.0 / 16097.0 / 16100.0 ]
Paths of length k = 234		3.0 [ 3.0 / 15788.0 / 15791.0 ]
Paths of length k = 235		3.0 [ 3.0 / 15482.0 / 15485.0 ]
Paths of length k = 236		3.0 [ 3.0 / 15179.0 / 15182.0 ]
Paths of length k = 237		3.0 [ 3.0 / 14879.0 / 14882.0 ]
Paths of length k = 238		3.0 [ 3.0 / 14582.0 / 14585.0 ]
Paths of length k = 239		3.0 [ 3.0 / 14288.0 / 14291.0 ]
Paths of length k = 240		3.0 [ 3.0 / 13997.0 / 14000.0 ]
Paths of length k = 241		3.0 [ 3.0 / 13709.0 / 13712.0 ]
Paths of length k = 242		3.0 [ 3.0 / 13424.0 / 13427.0 ]
Paths of length k = 243		3.0 [ 3.0 / 13142.0 / 13145.0 ]
Paths of length k = 244		3.0 [ 3.0 / 12863.0 / 12866.0 ]
Paths of length k = 245		3.0 [ 3.0 / 12587.0 / 12590.0 ]
Paths of length k = 246		3.0 [ 3.0 / 12314.0 / 12317.0 ]
Paths of length k = 247		3.0 [ 3.0 / 12044.0 / 12047.0 ]
Paths of length k = 248		3.0 [ 3.0 / 11777.0 / 11780.0 ]
Paths of length k = 249		3.0 [ 3.0 / 11513.0 / 11516.0 ]
Paths of length k = 250		3.0 [ 3.0 / 11252.0 / 11255.0 ]
Paths of length k = 251		3.0 [ 3.0 / 10994.0 / 10997.0 ]
Paths of length k = 252		3.0 [ 3.0 / 10739.0 / 10742.0 ]
Paths of length k = 253		3.0 [ 3.0 / 10487.0 / 10490.0 ]
Paths of length k = 254		3.0 [ 3.0 / 10238.0 / 10241.0 ]
Paths of length k = 255		3.0 [ 3.0 / 9992.0 / 9995.0 ]
Paths of length k = 256		3.0 [ 3.0 / 9749.0 / 9752.0 ]
Paths of length k = 257		3.0 [ 3.0 / 9509.0 / 9512.0 ]
Paths of length k = 258		3.0 [ 3.0 / 9272.0 / 9275.0 ]
Paths of length k = 259		3.0 [ 3.0 / 9038.0 / 9041.0 ]
Paths of length k = 260		3.0 [ 3.0 / 8807.0 / 8810.0 ]
Paths of length k = 261		3.0 [ 3.0 / 8579.0 / 8582.0 ]
Paths of length k = 262		3.0 [ 3.0 / 8354.0 / 8357.0 ]
Paths of length k = 263		3.0 [ 3.0 / 8132.0 / 8135.0 ]
Paths of length k = 264		3.0 [ 3.0 / 7913.0 / 7916.0 ]
Paths of length k = 265		3.0 [ 3.0 / 7697.0 / 7700.0 ]
Paths of length k = 266		3.0 [ 3.0 / 7484.0 / 7487.0 ]
Paths of length k = 267		3.0 [ 3.0 / 7274.0 / 7277.0 ]
Paths of length k = 268		3.0 [ 3.0 / 7067.0 / 7070.0 ]
Paths of length k = 269		3.0 [ 3.0 / 6863.0 / 6866.0 ]
Paths of length k = 270		3.0 [ 3.0 / 6662.0 / 6665.0 ]
Paths of length k = 271		3.0 [ 3.0 / 6464.0 / 6467.0 ]
Paths of length k = 272		3.0 [ 3.0 / 6269.0 / 6272.0 ]
Paths of length k = 273		3.0 [ 3.0 / 6077.0 / 6080.0 ]
Paths of length k = 274		3.0 [ 3.0 / 5888.0 / 5891.0 ]
Paths of length k = 275		3.0 [ 3.0 / 5702.0 / 5705.0 ]
Paths of length k = 276		3.0 [ 3.0 / 5519.0 / 5522.0 ]
Paths of length k = 277		3.0 [ 3.0 / 5339.0 / 5342.0 ]
Paths of length k = 278		3.0 [ 3.0 / 5162.0 / 5165.0 ]
Paths of length k = 279		3.0 [ 3.0 / 4988.0 / 4991.0 ]
Paths of length k = 280		3.0 [ 3.0 / 4817.0 / 4820.0 ]
Paths of length k = 281		3.0 [ 3.0 / 4649.0 / 4652.0 ]
Paths of length k = 282		3.0 [ 3.0 / 4484.0 / 4487.0 ]
Paths of length k = 283		3.0 [ 3.0 / 4322.0 / 4325.0 ]
Paths of length k = 284		3.0 [ 3.0 / 4163.0 / 4166.0 ]
Paths of length k = 285		3.0 [ 3.0 / 4007.0 / 4010.0 ]
Paths of length k = 286		3.0 [ 3.0 / 3854.0 / 3857.0 ]
Paths of length k = 287		3.0 [ 3.0 / 3704.0 / 3707.0 ]
Paths of length k = 288		3.0 [ 3.0 / 3557.0 / 3560.0 ]
Paths of length k = 289		3.0 [ 3.0 / 3413.0 / 3416.0 ]
Paths of length k = 290		3.0 [ 3.0 / 3272.0 / 3275.0 ]
Paths of length k = 291		3.0 [ 3.0 / 3134.0 / 3137.0 ]
Paths of length k = 292		3.0 [ 3.0 / 2999.0 / 3002.0 ]
Paths of length k = 293		3.0 [ 3.0 / 2867.0 / 2870.0 ]
Paths of length k = 294		3.0 [ 3.0 / 2738.0 / 2741.0 ]
Paths of length k = 295		3.0 [ 3.0 / 2612.0 / 2615.0 ]
Paths of length k = 296		3.0 [ 3.0 / 2489.0 / 2492.0 ]
Paths of length k = 297		3.0 [ 3.0 / 2369.0 / 2372.0 ]
Paths of length k = 298		3.0 [ 3.0 / 2252.0 / 2255.0 ]
Paths of length k = 299		3.0 [ 3.0 / 2138.0 / 2141.0 ]
Paths of length k = 300		3.0 [ 3.0 / 2027.0 / 2030.0 ]
Paths of length k = 301		3.0 [ 3.0 / 1919.0 / 1922.0 ]
Paths of length k = 302		3.0 [ 3.0 / 1814.0 / 1817.0 ]
Paths of length k = 303		3.0 [ 3.0 / 1712.0 / 1715.0 ]
Paths of length k = 304		3.0 [ 3.0 / 1613.0 / 1616.0 ]
Paths of length k = 305		3.0 [ 3.0 / 1517.0 / 1520.0 ]
Paths of length k = 306		3.0 [ 3.0 / 1424.0 / 1427.0 ]
Paths of length k = 307		3.0 [ 3.0 / 1334.0 / 1337.0 ]
Paths of length k = 308		3.0 [ 3.0 / 1247.0 / 1250.0 ]
Paths of length k = 309		3.0 [ 3.0 / 1163.0 / 1166.0 ]
Paths of length k = 310		3.0 [ 3.0 / 1082.0 / 1085.0 ]
Paths of length k = 311		3.0 [ 3.0 / 1004.0 / 1007.0 ]
Paths of length k = 312		3.0 [ 3.0 / 929.0 / 932.0 ]
Paths of length k = 313		3.0 [ 3.0 / 857.0 / 860.0 ]
Paths of length k = 314		3.0 [ 3.0 / 788.0 / 791.0 ]
Paths of length k = 315		3.0 [ 3.0 / 722.0 / 725.0 ]
Paths of length k = 316		3.0 [ 3.0 / 659.0 / 662.0 ]
Paths of length k = 317		3.0 [ 3.0 / 599.0 / 602.0 ]
Paths of length k = 318		3.0 [ 3.0 / 542.0 / 545.0 ]
Paths of length k = 319		3.0 [ 3.0 / 488.0 / 491.0 ]
Paths of length k = 320		3.0 [ 3.0 / 437.0 / 440.0 ]
Paths of length k = 321		3.0 [ 3.0 / 389.0 / 392.0 ]
Paths of length k = 322		3.0 [ 3.0 / 344.0 / 347.0 ]
Paths of length k = 323		3.0 [ 3.0 / 302.0 / 305.0 ]
Paths of length k = 324		3.0 [ 3.0 / 263.0 / 266.0 ]
Paths of length k = 325		3.0 [ 3.0 / 227.0 / 230.0 ]
Paths of length k = 326		3.0 [ 3.0 / 194.0 / 197.0 ]
Paths of length k = 327		3.0 [ 3.0 / 164.0 / 167.0 ]
Paths of length k = 328		3.0 [ 3.0 / 137.0 / 140.0 ]
Paths of length k = 329		3.0 [ 3.0 / 113.0 / 116.0 ]
Paths of length k = 330		2.0 [ 2.0 / 93.0 / 95.0 ]
Paths of length k = 331		2.0 [ 2.0 / 75.0 / 77.0 ]
Paths of length k = 332		2.0 [ 2.0 / 59.0 / 61.0 ]
Paths of length k = 333		2.0 [ 2.0 / 45.0 / 47.0 ]
Paths of length k = 334		2.0 [ 2.0 / 33.0 / 35.0 ]
Paths of length k = 335		2.0 [ 2.0 / 23.0 / 25.0 ]
Paths of length k = 336		2.0 [ 2.0 / 15.0 / 17.0 ]
Paths of length k = 337		0.0 [ 0.0 / 11.0 / 11.0 ]
Paths of length k = 338		1.0 [ 1.0 / 6.0 / 7.0 ]
Paths of length k = 339		3.0 [ 3.0 / 0.0 / 3.0 ]

While this should finish within a few seconds, we still get a selection of several thousand paths with varying path length, that we can use to generate higher-order models. We will use this approach, when we study real data in a later unit.

Higher-order clustering and visualisation of causal structures in temporal networks

An interesting application of higher-order models concerns the visualisation of time-aggregated representations of temporal networks. We demonstrate this in a temporal network synthetically generated to exhibit a specific pattern in the ordering of time-stamped edges. Let us load this example and visualise the first 250 time stamps:

**TODO:** Read the file `temporal_clusters.tedges` as a `TemporalNetwork`. Use the `pp.visualisations.plot()` method to visualise the temporal network. Use the parameter `max_time` to limit the visualisation to the first 250 time stamps.

In [16]:
t = pp.TemporalNetwork.read_file('../data/temporal_clusters.tedges')
style = {
    'max_time': 250,
    'ms_per_frame': 10,
    'ts_per_frame': 1
}
pp.visualisation.plot(t, **style)
t stop restart

What you probably cannot see in this visualisation is that this temporal network exhibits clusters in the causal topology, i.e. there are more causal paths between certain clusters of nodes than we would expect if links were independent (and paths were Markovian). We can get a vague idea of this by simulating a random walk in the temporal network, following the trajectory of a walker as it is moved through the nodes by dynamic edges.

**TODO:** Use the method `pp.algorithms.temporal_walk.generate_walk` to create a sequence of 500 random walk steps in the temporal network `t`. Use the method `pp.visualisation.plot_walk` to visualise the random walk trajectory in the (first-order) time-aggregated network.

In [17]:
walk = pp.algorithms.temporal_walk.generate_walk(t, 500)
style['ms_per_frame'] = 250
pp.visualisation.plot_walk(pp.Network.from_temporal_network(t), walk, **style)
[save svg]

Still, the pattern is difficult to see as the layout of nodes does not reflect the causal structures in the temporal network. With pathpy we can easily get around this problem. We can generate a time-aware layout that considers the causal topology of the temporal network that results from higher-order dependencies between time-stamped edges. The basic approach of calculating higher-order layouts for temporal networks is described in this preprint:

I Scholtes: Force-Directed Layout of Non-Markovian Temporal Networks, preprint, 2014

Generating such a time-aware layout in pathpy is actually trivial. We simply plot a HigherOrderNetwork model for the causal path in a temporal network, while setting a parameter plot_higher_order_nodes to False. Different from the previous visualisations, this will project the higher-order topology on the first-order nodes. Let us try this.

**TODO:** Generate a second-order model for causal paths in `t` assuming $\delta=1$. Use the `pp.visualisations.plot()` method to visualise the second-order model. Set the `plot_higher_order_nodes` parameter to `False`.

In [18]:
p = pp.path_extraction.paths_from_temporal_network_dag(t)
hon_2 = pp.HigherOrderNetwork(p, k=2)

clusters = { v: 'red' if len(v)<2 else ('green' if v.startswith('1') else 'blue') for v in p.nodes}

pp.visualisation.plot(hon_2, plot_higher_order_nodes=False, node_color = clusters)
Directed Acyclic Graph
Nodes:		89042
Roots:		29042
Leaves:		29042
Links:		60000
Acyclic:	None

[save svg]

We see that nodes automatically position themselves in groups that correspond to the natural cluster structure in the causal topology. In the visualisation above, we have additionally colored nodes based to their (synthetically generated) ground-truth clusters. With this layout of the graph, let us visualise again our random walk trajectory from above.

**TODO:** Visualise the random walk trajectory in the network layouted according to the second-order model.

In [19]:
pp.visualisation.plot_walk(hon_2, walk, **style, plot_higher_order_nodes=False)
[save svg]

We now see that the random walker indeed has a tendency to visit, in subsequent steps, nodes that belong to the same clusters. In this specific case, the cluster pattern in the layout actually disappears if we calculate a third-order layout.

**TODO:** Generate a third-order model for the causal topology of the temporal network. Visualise the third-order model like above, again setting the `plot_higher_order_nodes` parameter to `False`.

In [20]:
hon_3 = pp.HigherOrderNetwork(p, k=3)
pp.visualisation.plot(hon_3, plot_higher_order_nodes=False, node_color = clusters)
[save svg]

The reason for this is simple: This example exhibits correlations at correlation length two (i.e. for paths of length two), but there are no correlations at correlation length three. This highlights two important issues, that we will address in a moment:

  1. We need a method to determine the optimal order of the higher-order models that we use to analyse (or visualise) a given data set.
  2. As real systems are likely to exhibit multiple correlation length simultaneously, we need models that can combine multiple higher-order models.

But before move to these questions, let us spend some words on higher-order clustering in temporal networks. We have seen that correlations in the ordering of time-stamped edges can change the trajectory of a random walker. In particular, we observe clusters in the causal structure of a system that make the random walk subsequently visit nodes within the same cluster with higher probability. In the afternoon sessions of our tutorial, Daniel Edler will give an in-depth introduction to InfoMap, a popular information-theoretic approach to graph clustering that utilises this property of random walks.

Complementary to this part of our tutorial, here we briefly introduce another approach to higher-order clustering. The idea is to generalise spectral graph clustering algorithms to higher-order network models. These algorithms utilise graph Laplacians, a matrix representation of a graph where edges are represented by -1 entries, while the diagonal contains the degrees of nodes (and other entries are zero). The eigenvalues and eigenvectors of this matrix provide interesting insights about the topology of a graph, and about its influence on dynamical processes like random walks or diffusion. In particular, the second-smallest eigenvalue of the Laplacian matrix captures how well-connected a graph is, where small values close to zero indicate small cuts that can signify cluster structures. Moreover, the corresponding eigenvector, the so-called Fiedler vector can be used for a simple spectral clustering algorithm, where nodes in different clusters are represented by eigenvector entries falling to different value ranges.

An interesting prospect for higher-order network analytics is that we can generalise graph Laplacians to higher-order network models, which can then be used to study cluster structures in the causal topology of a temporal network. If you are interested in the mathematical details, check:

I Scholtes, N Wider, R Pfitzner, A Garas, CJ Tessone, F Schweitzer: Causality-driven slow-down and speed-up of diffusion in non-Markovian temporal networks, Nature Communications, Vol. 5, Article 5024, 2014

Let us try this in our synthetic data set:

**TODO:** Use the methods in `pp.algorithms.spectral` to calculate the algebraic connectivity of the second-order model for causal paths in the temporal network `t`. Compare the value to the the algebraic connectivity of (i) the corresponding second-order null model, and (ii) a first-order model of paths.

In [21]:
print('Second-order model: {0}'.format(pp.algorithms.spectral.algebraic_connectivity(hon_2)))

print('Second-order null model: {0}'.format(pp.algorithms.spectral.algebraic_connectivity(pp.HigherOrderNetwork(p, k=2, null_model=True))))
print('First-order model: {0}'.format(pp.algorithms.spectral.algebraic_connectivity(pp.HigherOrderNetwork(p, k=1))))
Second-order model: 0.051639993731413855
Second-order null model: 0.7890567809471654
First-order model: 0.7890567809471664

We clearly see that the algebraic connectivity of the second-order model is close to zero, thus indicating cluster structures that lead to a small cut in the causal topology of the system. This small value actually captures the "trapping" of the random walker within clusters. The algebraic connectivity of the second-order null model and the first-order model are actually identical (up to numerical imprecision).

Let us now go one step further and use the distribution of Fiedler vector entries to reveal the cluster structure in the causal topology.

**TODO:** Use the methods in `pp.algorithms.spectral` to calculate the fiedler vector of (i) the second-order model, and (ii) the second-order null model. Use a scatter plot to visually compare the distributions of the real parts of both eigenvectors.

In [22]:
%matplotlib inline
from matplotlib import pyplot as plt
import numpy as np

plt.xkcd()

plt.ylim(-.15, .15)
plt.title('Fiedler vector (second-order model)')
plt.scatter(range(hon_2.ncount()), np.real(pp.algorithms.spectral.fiedler_vector_dense(hon_2)))
plt.show()

plt.title('Fiedler vector (second-order null model)')
plt.ylim(-.15, .15)
plt.scatter(range(hon_2.ncount()), np.real(pp.algorithms.spectral.fiedler_vector_dense(pp.HigherOrderNetwork(p, k=2, null_model=True))))
plt.show()

The three clusters in the temporal network clearly show up as three different value ranges in the distribution of entries in the Fiedler vector. The lack of this structure in the null model confirms, that the cluster structure is only due to the chronological ordering of links, and neither due to their topology nor due their frequencies.

Bonus: Data-driven story-telling with custom visualisation templates

Finally, we briefly introduce custom visualisation templates, which you may find useful for data-driven and visual story-telling tasks. As an example, we will use a data set on character co-occurrences in the text of The Lord of the Rings. You can load it from the table lotr SQLite database. In this table, each row source, target, time captures that the characters source and target are mentioned within the same sentence, where time chronologically numbers sentences throughout all three novels.

In the following, we want to generate a nice interactive visualisation of this data set. For this, we will use the custom templating mechanism of pathpy. It allows you to define your own HTML templates, that you can derive from the default visualisation templates that we have used so far. This enables us to use the default pathpy visuals as a baseline, that we can tune to our needs.

Technically, such a template is nothing more than an HTML5 file with embedded JavaScript and CSS code. pathpy will use this template, and replace placeholder variables that we can set via the style parameter dictionary. We can tell pathpy to use an arbitrary custom template file by setting the entry style['template'] = filename. In this template, we can then use variables in the form $variable, which we can set from within python by setting style['variable'] = value.

In the custom template file data/custom_template.html we use all of pathpy's default style parameters, as well as two additional parameters chapter_data and character_classes. We will use the first to pass chapter marks to the visualisation, which are then shown in the top left part of the visualisation as the story unfolds. Moreover, we will visualise the different factions (Hobits, Elves, Fellowship, Dwarves, ...) to which characters belong, so we need to pass those to the template as well.

You can read the character and chapter data from the corresponding json-files in the data directory. Just use the json.load function in python's json file to read them into two dictionaries and pass those two dictionaries to the corresponding style parameters.

**TODO:** Use the `pp.visualisations.export_html()` method to create a visualisation of dynamic character interactions in The Lord of The Rings based on the table `lotr` in the SQLite database and the custom template file `custom_template.html` in the `data` folder.

In [23]:
import json

t_lotr = pp.TemporalNetwork.from_sqlite(
    con.execute('SELECT source, target, time FROM lotr'))
print(t)

# Load chapter marks from JSON file
with open('../data/lotr_chapters.json', 'r') as f:
    chapters = json.load(f)

# Load character classes from JSON file
with open('../data/lotr_characters.json', 'r') as f:
    characters = json.load(f)

style = {
    # some default parameters
    'width': 1200,
    'height': 1000,
    'look_ahead': 500,
    'look_behind': 1500,
    'ts_per_frame': 20, 
    'ms_per_frame': 50,
    'inactive_edge_width': 4.0,
    'active_edge_width': 6.0,
    'label_offset': [0,-16],    
    'node_size': 10,
    'label_size': '14px',
    
     # tell pathpy to use a user-provided custom template
    'template': '../data/custom_template.html',
    
    # add custom parameters defined in our custom template
    'chapter_data': chapters, 
    'character_classes': characters,    
}

# generate HTML based on our custom template
pp.visualisation.export_html(t_lotr, filename='../visualisations/4_demo_lotr.html', **style)
Nodes:			30
Time-stamped links:	60000
Links/Nodes:		2000.0
Observation period:	[0, 59999]
Observation length:	 59999 
Time stamps:		 60000 
Avg. inter-event dt:	 1.0
Min/Max inter-event dt:	 1/1

As a little distraction at the end of this session, open the generated file in your browser, lean back and enjoy watching the story unfold - as a temporal network :-)