networkx-temporal 1.0b9.post1

Python package to build and manipulate temporal NetworkX graphs.

networkx-temporal

Python package to build and manipulate temporal NetworkX graphs.

Requirements

• Python>=3.7
• networkx>=2.1
• pandas>=1.1.0

Install

Package is available to install on PyPI:

pip install networkx-temporal

Usage

Examples of usage below are also available as an interactive Jupyter notebook (open on Colab).

Basics

Build temporal graph

The TemporalGraph class extends NetworkX to temporal graphs, allowing easy manipulation of its internal data structure:

>>> TG = tx.TemporalGraph(t=4, directed=True, multigraph=False)
>>>
>>> TG[0].add_edge("a", "b")
>>> TG[1].add_edge("c", "b")
>>> TG[2].add_edge("d", "c")
>>> TG[2].add_edge("d", "e")
>>> TG[2].add_edge("a", "c")
>>> TG[3].add_edge("f", "e")
>>> TG[3].add_edge("f", "a")
>>> TG[3].add_edge("f", "b")
>>>
>>> print(TG)

TemporalDiGraph (t=4) with 12 nodes and 8 edges

>>> print(f"t = {len(TG)} time steps\n"
>>>       f"V = {TG.order()} nodes ({TG.temporal_order()} unique, {TG.total_nodes()} total)\n"
>>>       f"E = {TG.size()} edges ({TG.temporal_size()} unique, {TG.total_edges()} total)")

t = 4 time steps
V = [2, 2, 4, 4] nodes (6 unique, 12 total)
E = [1, 1, 3, 3] edges (8 unique, 8 total)

>>> draw_temporal_graph(TG, figsize=(8, 2))

Slice into temporal bins

Once initialized, a specified number of bins can be returned in a new object of the same type using slice:

>>> TG = TG.slice(bins=2)
>>> draw_temporal_graph(TG, figsize=(4, 2))

By default, created bins are composed of non-overlapping edges and might have uneven order and size.

To balance them, pass qcut=True:

>>> TG = TG.slice(bins=2, qcut=True)
>>> draw_temporal_graph(TG, figsize=(4, 2))

Note that in some cases qcut may not be able to split the graph into the number of bins requested and will instead return the maximum number of bins possible. Forcing a number of bins can be achieved by setting duplicates=True (allows duplicate edges in bins) or rank_first=True (balances snapshots considering the order of appearence of nodes/edges).

Convert to directed or undirected

We can easily convert the edge directions by calling the same methods available from networkx:

>>> TG.to_undirected()

TemporalGraph (t=4) with 12 nodes and 8 edges

>>> TG.to_directed()

TemporalDiGraph (t=4) with 12 nodes and 16 edges

---

Common metrics

All methods implemented by networkx, e.g., degree, are also available to be executed sequentially on the stored time slices.

A few additional methods that consider all time slices are also implemented for convenience, e.g., temporal_degree and temporal_neighbors.

Degree centrality

>>> TG.degree()
>>> # TG.in_degree()
>>> # TG.out_degree()

[DiDegreeView({'a': 2, 'b': 2}),
 DiDegreeView({'c': 2, 'b': 2}),
 DiDegreeView({'d': 4, 'c': 4, 'e': 2, 'a': 2}),
 DiDegreeView({'f': 6, 'e': 2, 'a': 2, 'b': 2})]

>>> TG.temporal_degree()
>>> # TG.temporal_in_degree()
>>> # TG.temporal_out_degree()

{'e': 4, 'b': 6, 'f': 6, 'a': 6, 'd': 4, 'c': 6}

Or to obtain the degree of a specific node:

>>> TG[0].degree("a")
>>> # TG[0].in_degree("a")
>>> # TG[0].out_degree("a")

2

>>> TG.temporal_degree("a")
>>> # TG.temporal_in_degree("a")
>>> # TG.temporal_out_degree("a")

6

Node neighborhoods

>>> TG.neighbors("c")

[[], ['b'], ['d', 'a'], []]

To obtain the neighborhood of a node considering all time steps, use the method temporal_neighbors:

>>> TG.temporal_neighbors("c")

{'a', 'b', 'd'}

Order and size

To get the number of nodes and edges in each step:

>>> print("Order:", TG.order())
>>> print("Size:", TG.size())

Order: [2, 2, 4, 4]
Size: [2, 2, 6, 6]

Temporal order and size

The temporal order and size are respectively defined as the length of TG.temporal_nodes(), i.e., unique nodes in all time steps, and the length of TG.temporal_size(), i.e., sum of edges or interactions across all time steps.

>>> print("Temporal nodes:", TG.temporal_order())
>>> print("Temporal edges:", TG.temporal_size())

Temporal nodes: 6
Temporal edges: 16

Total number of nodes and edges

To get the actual number of nodes and edges across all time steps:

Note that the temporal size of a graph will always be equal to its total number of edges, i.e., TG.temporal_size() == TG.total_edges().

>>> print("Total nodes:", TG.total_nodes())  # TG.total_nodes() != TG.temporal_order()
>>> print("Total edges:", TG.total_edges())  # TG.total_edges() == TG.temporal_size()

Total nodes: 12
Total edges: 16

---

Convert from static to temporal graph

Static graphs can carry temporal information in either the node- or edge-level attributes.

Slicing a graph into bins usually result in the same number of edges, but a higher number of nodes, as they may appear in more than one snapshot.

In the example below, we create a static multigraph in which both nodes and edges are attributed with the time step t in which they are observed:

>>> G = nx.MultiDiGraph()
>>>
>>> G.add_nodes_from([
>>>     ("a", {"time": 0}),
>>>     ("b", {"time": 0}),
>>>     ("c", {"time": 1}),
>>>     ("d", {"time": 2}),
>>>     ("e", {"time": 3}),
>>>     ("f", {"time": 3}),
>>> ])
>>>
>>> G.add_edges_from([
>>>     ("a", "b", {"time": 0}),
>>>     ("c", "b", {"time": 1}),
>>>     ("d", "c", {"time": 2}),
>>>     ("d", "e", {"time": 2}),
>>>     ("a", "c", {"time": 2}),
>>>     ("f", "e", {"time": 3}),
>>>     ("f", "a", {"time": 3}),
>>>     ("f", "b", {"time": 3}),
>>> ])
>>>
>>> print(G)

MultiDiGraph with 6 nodes and 8 edges

Node-level time attributes

Converting a static graph with node-level temporal data to a temporal graph object (node_level considers the source node's time by default when slicing edges):

>>> TG = tx.from_static(G).slice(attr="time", attr_level="node", node_level="source", bins=None, qcut=None)
>>> draw_temporal_graph(TG, figsize=(8, 2))

Note that considering node-level attributes resulted in placing the edge (a, c, 2) in $t=0$ instead, as the source node a attribute is set to t=0:

>>> G.nodes(data="time")["a"]

0

Edge-level time attributes

Converting a static graph with edge-level temporal data to a temporal graph object (edge's time applies to both source and target nodes):

>>> TG = tx.from_static(G).slice(attr="time", attr_level="edge", bins=None, qcut=None)
>>> draw_temporal_graph(TG, figsize=(8, 2))

In this case, considering edge-level attributes results in placing the edge (a, c, 2) in $t=2$, as expected.

---

Transform temporal graph

Once a temporal graph is instantiated, the following methods allow returning static graphs, snapshots, events or unified representations.

Due to the way the underlying data is represented, some of these objects (i.e., those with unique nodes) do not allow dynamic node attributes.

Note that the total number of nodes $V$ and edges $E$ of the returned object might differ from the number of temporal nodes $V_T$ and edges $E_T$.

Method	Order	Size	Dynamic node attributes	Dynamic edge attributes
to_static	$V = V_T$	$E = E_T$	❌	✅
to_snapshots	$V \ge V_T$	$E = E_T$	✅	✅
to_events	$V = V_T$	$E = E_T$	❌	❌
to_unified	$V \ge V_T$	$E \ge E_T$	✅	✅

Convert to different object type

Temporal graphs may be converted to a different object type by calling convert or passing to={parameter} to the above methods.

Format	Parameter (Package)	Parameter (Alias)
Deep Graph Library	dgl	-
graph-tool	graph_tool	gt
igraph	igraph	ig
NetworKit	networkit	nk
PyTorch Geometric	torch_geometric	pyg
Teneto	teneto	-

>>> tx.convert(G, "igraph")

<igraph.Graph at 0x7fc242f76050>

Static graph

Builds a static or flattened graph containing all the edges found at each time step:

>>> G = TG.to_static()
>>> draw_temporal_graph(G, suptitle="Static Graph")

Snapshot-based temporal graph

The snapshot-based temporal graph (STG) is a list of graphs directly accessible under data in the temporal graph object:

>>> STG = TG.to_snapshots()

Event-based temporal graph

An event-based temporal graph (ETG) is a sequence of 3- or 4-tuple edge-based events.

• 3-tuples ($u, v, t$), where elements are the source node, target node, and time step of the observed event (also known as a stream graph);

• 4-tuples ($u, v, t, \epsilon$), where $\epsilon$ is either a positive (1) or negative (-1) unity representing edge addition and deletion events, respectively.

Depending on the temporal graph data, one of these may allow a more compact representation than the other.

>>> ETG = TG.to_events()  # stream=True (default)
>>> ETG

[('a', 'b', 0),
 ('c', 'b', 1),
 ('a', 'c', 2),
 ('d', 'c', 2),
 ('d', 'e', 2),
 ('f', 'e', 3),
 ('f', 'a', 3),
 ('f', 'b', 3)]

>>> ETG = TG.to_events(stream=False)
>>> ETG

[('a', 'b', 0, 1),
 ('c', 'b', 1, 1),
 ('a', 'b', 1, -1),
 ('a', 'c', 2, 1),
 ('d', 'c', 2, 1),
 ('d', 'e', 2, 1),
 ('c', 'b', 2, -1),
 ('f', 'e', 3, 1),
 ('f', 'a', 3, 1),
 ('f', 'b', 3, 1),
 ('a', 'c', 3, -1),
 ('d', 'c', 3, -1),
 ('d', 'e', 3, -1)]

Unified temporal graph

The unified temporal graph (UTG) is a single graph that contains the original data plus proxy nodes and edge couplings connecting sequential temporal nodes.

>>> UTG = TG.to_unified(add_couplings=True)
>>> print(UTG)

MultiDiGraph named 'UTG (t=4, proxy_nodes=6, edge_couplings=2)' with 12 nodes and 14 edges

>>> nodes = sorted(TG.temporal_nodes())
>>> pos = {node: (nodes.index(node.rsplit("_")[0]), -int(node.rsplit("_")[1])) for node in UTG.nodes()}
>>> draw_temporal_graph(UTG, pos=pos, figsize=(4, 4), connectionstyle="arc3,rad=0.25", suptitle="Unified Temporal Graph")

Convert back to TemporalGraph object

Functions to convert a newly created STG, ETG, or UTG back to a temporal graph object are also implemented.

>>> tx.from_snapshots(STG)

TemporalMultiDiGraph (t=4) with 12 nodes and 8 edges

>>> tx.from_events(ETG, directed=True, multigraph=True)

TemporalDiGraph (t=4) with 12 nodes and 8 edges

>>> tx.from_unified(UTG)

TemporalMultiDiGraph (t=4) with 12 nodes and 8 edges

---

Community detection

As a toy example, let's first use a Stochastic Block Model to generate 4 snapshots, in which each of the 5 clusters of 4 nodes each continuously mix together:

>>> snapshots = 4   # Temporal graphs to generate.
>>> clusters = 5    # Number of clusters/communities.
>>> order = 5       # Nodes in each cluster.
>>> intra = .9      # High initial probability of intra-community edges.
>>> inter = .1      # Low initial probability of inter-community edges.
>>> change = .125   # Change in intra- and inter-community edges over time.
>>>
>>> # Get probability matrix for each snapshot.
>>> probs = [[[
>>>     (intra if i == j else inter) + (t * change * (-1 if i == j else 1))
>>>     for j in range(clusters)]
>>>     for i in range(clusters)]
>>>     for t in range(snapshots)]
>>>
>>> # Create graphs from probabilities.
>>> graphs = {}
>>> for t in range(snapshots):
>>>     graphs[t] = nx.stochastic_block_model(clusters*[order], probs[t], seed=10)
>>>     graphs[t].name = t
>>>
>>> # Create temporal graph from snapshots.
>>> TG = tx.from_snapshots(graphs)

Let's plot the temporal graph snapshots, with colors representing the ground truths and highlighting intra-community edges.

>>> import matplotlib.pyplot as plt
>>>
>>> def get_edge_color(edges: list, node_color: dict):
>>>     return [node_color[u] if node_color[u] == node_color[v] else "#00000035" for u, v in edges]
>>>
>>> c = plt.cm.tab10.colors
>>>
>>> # Node positions.
>>> pos = nx.circular_layout(TG.to_static())
>>>
>>> # Community ground truths.
>>> node_color = [c[i // clusters] for i in range(TG.temporal_order())]
>>>
>>> # Colorize intra-community edges.
>>> temporal_opts = {t: {"edge_color": get_edge_color(TG[t].edges(), node_color)} for t in range(len(TG))}
>>>
>>> # Plot snapshots with community ground truths.
>>> draw_temporal_graph(
>>>     TG,
>>>     pos=pos,
>>>     figsize=(14, 4),
>>>     node_color=node_color,
>>>     temporal_opts=temporal_opts,
>>>     connectionstyle="arc3,rad=0.1",
>>>     suptitle="Ground truth")

Modularity: on static graph

The leidenalg package implements optimization algorithms for community detection that may be applied on snapshot-based temporal graphs.

Such algorithms may help with descriptive or exploratory tasks and post-hoc network analysis, although they lack statistical rigor for inference purposes.

For example, depending on the initial node community assigments (e.g., with seed=0 below), modularity fails to retrieve the true communities:

>>> import leidenalg as la
>>>
>>> membership = la.find_partition(
>>>     TG.to_static("igraph"),
>>>     la.ModularityVertexPartition,
>>>     n_iterations=-1,
>>>     seed=0,
>>> )
>>>
>>> node_color = [c[m] for m in membership.membership]
>>> edge_color = get_edge_color(TG.to_static().edges(), node_color)
>>>
>>> draw_temporal_graph(
>>>     TG.to_static(),
>>>     pos=pos,
>>>     figsize=(4, 4),
>>>     node_color=node_color,
>>>     edge_color=edge_color,
>>>     connectionstyle="arc3,rad=0.1",
>>>     suptitle="Communities found by modularity on static graph")

Modularity: on each snapshot

Running the same algorithm separately on each of the generated snapshots retrieves the correct clusters only on the first ($t=0$).

In addition, community indices/colors along snapshots are not fixed, which makes understanding their mesoscale dynamics harder.

>>> temporal_opts = {}
>>>
>>> for t in range(len(TG)):
>>>     membership = la.find_partition(
>>>         TG[t:t+1].to_static("igraph"),
>>>         la.ModularityVertexPartition,
>>>         n_iterations=-1,
>>>         seed=0,
>>>     )
>>>     node_color = [c[m] for m in membership.membership]
>>>     edge_color = get_edge_color(TG[t].edges(), node_color)
>>>     temporal_opts[t] = {"node_color": node_color, "edge_color": edge_color}
>>>
>>> draw_temporal_graph(
>>>     TG,
>>>     pos=pos,
>>>     figsize=(14, 4),
>>>     temporal_opts=temporal_opts,
>>>     connectionstyle="arc3,rad=0.1",
>>>     suptitle="Communities found by modularity on snapshots")

Modularity: on temporal graph

Coupling temporal nodes allows the same algorithm to correctly retrieve the ground truths in this case, and maintain community indices/colors fixed.

Note that the interslice_weight among temporal nodes in a sequence of snapshots defaults to 1.0, but may be adjusted accordingly.

>>> temporal_opts = {}
>>>
>>> temporal_membership, improvement = la.find_partition_temporal(
>>>     TG.to_snapshots("igraph"),
>>>     la.ModularityVertexPartition,
>>>     interslice_weight=1.0,
>>>     n_iterations=-1,
>>>     seed=0,
>>>     vertex_id_attr="_nx_name"
>>> )
>>>
>>> for t in range(len(TG)):
>>>     node_color = [c[m] for m in membership.membership]
>>>     edge_color = get_edge_color(TG[t].edges(), node_color)
>>>     temporal_opts[t] = {"node_color": node_color, "edge_color": edge_color}
>>>
>>> draw_temporal_graph(
>>>     TG,
>>>     figsize=(14, 4),
>>>     pos=pos,
>>>     temporal_opts=temporal_opts,
>>>     connectionstyle="arc3,rad=0.1",
>>>     suptitle="Communities found by modularity on temporal graph")

---

References

• Deep Graph Library
• graph-tool
• igraph
• Leiden
• NetworKit
• NetworkX
• Pandas
• PyTorch Geometric
• Teneto