networkx_temporal.algorithms

Algorithms and metrics for temporal graphs.

Node-level metrics - Summary

degree(TG[, nbunch, weight])

Returns node degrees.

in_degree(TG[, nbunch, weight])

Returns node in-degrees.

out_degree(TG[, nbunch, weight])

Returns node out-degrees.

degree_centrality(TG[, nbunch])

Returns node degree centralities.

in_degree_centrality(TG[, nbunch])

Returns node in-degree centralities.

out_degree_centrality(TG[, nbunch])

Returns node out-degree centralities.

bridging_centrality(TG[, betweenness])

Returns bridging centrality of nodes.

brokering_centrality(TG[, clustering_coef])

Returns brokering centrality of nodes.

Graph-level metrics - Summary

centralization(centrality[, scalar])

Returns the centralization of a graph.

degree_centralization(TG[, self_loops, isolates])

Returns the degree centralization of a graph.

in_degree_centralization(TG[, self_loops, ...])

Returns the in-degree centralization of a graph.

out_degree_centralization(TG[, self_loops, ...])

Returns the out-degree centralization of a graph.

conductance(TG, communities[, weight])

Returns the conductance of a graph.

modularity(TG, communities[, weight, ...])

Returns the modularity of a graph.

multislice_modularity(TG, communities[, ...])

Returns the MS-modularity of a temporal graph.

spectral_modularity(A, communities[, ...])

Calculates modularity based on the graph spectrum.

Functions

degree(TG: TemporalGraph | Graph, nbunch: Any | None = None, weight: str | None = None) → dict | int[source]

Returns node degrees. Defined [1] for temporal graphs as the degree sum over time:

\[\text{deg}(i) = \sum_{G \in \mathcal{G}} \sum_{j \in \mathcal{N}(i)} \mathbf{A}_{ij} + \mathbf{A}_{ji},\]

where \(i\) is a node, \(j\) is a node in the neighborhood \(\mathcal{N}(i)\), \(G\) is a snapshot in the temporal graph \(\mathcal{G}\), and \(\mathbf{A}\) is the adjacency matrix, optionally weighted by an edge-level weight attribute. For multigraphs, adjacencies are weighted by the number of parallel edges, unless weight=False.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • nbunch (Any | None) – One or more nodes to return. Optional.

  • weight (str | None) – Edge attribute key to consider. Optional.

Note:

Aliases: degree() and total_degree().

Return type:

dict | int

in_degree(TG: TemporalGraph | Graph, nbunch: Any | None = None, weight: str | None = None) → dict | int[source]

Returns node in-degrees. Defined [1] for temporal graphs as the in-degree sum over time:

\[\text{deg}_{\text{in}}(i) = \sum_{G \in \mathcal{G}} \sum_{j \in \mathcal{N}(i)} \mathbf{A}_{ji},\]

where \(i\) is a node, \(j\) is a node in the neighborhood \(\mathcal{N}(i)\), \(G\) is a snapshot in the temporal graph \(\mathcal{G}\), and \(\mathbf{A}\) is the adjacency matrix, optionally weighted by an edge-level weight attribute. For multigraphs, adjacencies are weighted by the number of parallel edges, unless weight=False.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • nbunch (Any | None) – One or more nodes to return. Optional.

  • weight (str | None) – Edge attribute key to consider. Optional.

Note:

Aliases: in_degree() and total_in_degree().

Return type:

dict | int

out_degree(TG: TemporalGraph | Graph, nbunch: Any | None = None, weight: str | None = None) → dict | int[source]

Returns node out-degrees. Defined [1] for temporal graphs as the out-degree sum over time:

\[\text{deg}_{\text{out}}(i) = \sum_{G \in \mathcal{G}} \sum_{j \in \mathcal{N}(i)} \mathbf{A}_{ij},\]

where \(i\) is a node, \(j\) is a node in the neighborhood \(\mathcal{N}(i)\), \(G\) is a snapshot in the temporal graph \(\mathcal{G}\), and \(\mathbf{A}\) is the adjacency matrix, optionally weighted by an edge-level weight attribute. For multigraphs, adjacencies are weighted by the number of parallel edges, unless weight=False.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • nbunch (Any | None) – One or more nodes to return. Optional.

  • weight (str | None) – Edge attribute key to consider. Optional.

Note:

Aliases: out_degree() and total_out_degree().

Return type:

dict | int

degree_centrality(TG: TemporalGraph | Graph, nbunch: Any | None = None) → dict | int[source]

Returns node degree centralities. Defined [1] as the fraction of connected nodes, i.e.,

\[c_{\text{deg}}(i) = \frac{\sum_{G \in \mathcal{G}} \sum_{j \in \mathcal{N}(i)} \mathbf{A}_{ij} + \mathbf{A}_{ji}} {|\mathcal{V}|},\]

where \(c_{\text{deg}}(i)\) is the degree centrality of node \(i\),, \(G\) is a snapshot in the temporal graph \(\mathcal{G}\), \(j\) is a node in the neighborhood \(\mathcal{N}(i)\), \(\mathbf{A}\) is the adjacency matrix, and \(|\mathcal{V}|\) is the order of the graph \(\mathcal{G}\). Note that this function does not consider node copies or edge weights in the adjacency matrix.

Parameters:

  • nbunch (Any | None) – One or more nodes to return. Optional.

  • TG (TemporalGraph | Graph)

Return type:

dict | int

in_degree_centrality(TG: TemporalGraph | Graph, nbunch: Any | None = None) → dict | int[source]

Returns node in-degree centralities. Defined [1] as the fraction of connected nodes, i.e.,

\[c_{\text{in}}(i) = \frac{\sum_{G \in \mathcal{G}} \sum_{j \in \mathcal{N}(i)} \mathbf{A}_{ji}} {|\mathcal{V}|},\]

where \(c_{\text{in}}(i)\) is the degree centrality of node \(i\), \(G\) is a snapshot in the temporal graph \(\mathcal{G}\), \(j\) is a node in the neighborhood \(\mathcal{N}(i)\), \(\mathbf{A}\) is the adjacency matrix, and \(|\mathcal{V}|\) is the order of the graph \(\mathcal{G}\). Note that this function does not consider node copies or edge weights in the adjacency matrix.

Parameters:

  • nbunch (Any | None) – One or more nodes to return. Optional.

  • TG (TemporalGraph | Graph)

Return type:

dict | int

out_degree_centrality(TG: TemporalGraph | Graph, nbunch: Any | None = None) → dict | int[source]

Returns node out-degree centralities. Defined [1] as the fraction of connected nodes, i.e.,

\[c_{\text{out}}(i) = \frac{\sum_{G \in \mathcal{G}} \sum_{j \in \mathcal{N}(i)} \mathbf{A}_{ij}} {|\mathcal{V}|},\]

where \(c_{\text{in}}(i)\) is the degree centrality of node \(i\), \(G\) is a snapshot in the temporal graph \(\mathcal{G}\), \(j\) is a node in the neighborhood \(\mathcal{N}(i)\), \(\mathbf{A}\) is the adjacency matrix, and \(|\mathcal{V}|\) is the order of the graph \(\mathcal{G}\). Note that this function does not consider node copies or edge weights in the adjacency matrix.

Parameters:

  • nbunch (Any | None) – One or more nodes to return. Optional.

  • TG (TemporalGraph | Graph)

Return type:

dict | int

bridging_centrality(TG: TemporalGraph | Graph, betweenness: dict | List[dict] | None = None) → dict | List[dict][source]

Returns bridging centrality of nodes.

Bridging centrality measures the importance of a node in connecting different parts of a network, and is defined [2] as the product of betweenness centrality and bridging coefficient:

\[c_{\text{bri}}(i) = c_{\text{bet}}(i) \times \text{bri}(i),\]

where \(c_{\text{bet}}(i)\) is the betweenness centrality of node \(i\), and \(\text{bri}(i)\) its bridging coefficient, i.e.,

\[\text{bri}(i) = \frac{\text{deg}(i)^{-1}}{\sum_{j \in N(i)} \text{deg}(j)^{-1}},\]

being \(\text{deg}(i)^{-1}\) the inverse degree of node \(i\), and \(N(i)\) its set of neighbors \(j \in N(i)\).

Returns zero for isolated nodes, i.e., with no neighbors. If betweenness is not provided, the bridging coefficient of nodes is returned instead, that is, consider \(c_{\text{bet}}(i) = 1\) for all nodes.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • betweenness (dict | List[dict] | None) – Dictionary of node betweenness centrality values. Returns bridging coefficient if not provided. Optional.

Return type:

dict | List[dict]

brokering_centrality(TG: TemporalGraph | Graph, clustering_coef: dict | List[dict] | None = None) → dict | List[dict][source]

Returns brokering centrality of nodes.

Brokering centrality [3] is a measure of the node’s ability to connect different parts of the network and is useful for identifying nodes that play a key role in the network’s structure. It is defined as:

\[\text{bro}(i) = \text{deg}(i) \times \text{clu}(i),\]

where \(\text{deg}(i)\) is the degree centrality of node \(i\), and \(\text{clu}(i)\) is its clustering coefficient.

Clustering coefficient works as a measure of interconnectivity in a node’s neighborhood and may be defined [4] as the the number of edges between a node’s neighbors divided by the number of possible edges between them. If clustering_coef is not provided, it is computed as:

\[\text{clu}(i) = \frac{2n}{|N_i| \, (|N_i| - 1)},\]

where \(\text{clu}(i)\) is the clustering coefficient of node \(i\), \(n\) is the number of edges between its neighbors, and \(|N_i|\) is its number of neighbors. Lower values indicate nodes part of a loosely connected groups, while higher values indicate nodes at the center of fully connected clusters.

Attention

In directed graphs, connections are not necessarily reciprocal, affecting the coefficients.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • clustering_coef (dict | List[dict] | None) – Dictionary of precomputed clustering coefficient values. Optional.

Return type:

dict | List[dict]

centralization(centrality: list | dict, scalar: int | float | list | dict = None) → float | List[float][source]

Returns the centralization of a graph.

Centralization [5] is defined as the sum of differences between the most central node’s centrality and each of the other nodes’ centralities, divided by the maximum theoretical sum of values in a graph with the same properties, such as order, size, and edge directionality. It is calculated as:

\[C(G) = \frac {\sum_{i \in V}\big(\text{centrality}_{\text{max}} - \text{centrality}(i) \big)} {\sum_{i \in V}\big(\text{theoretical}_{\text{max}} - \text{theoretical}(i) \big)},\]

where \(\text{centrality}_{\text{max}}\) is the maximum node centrality in \(G\), \(\text{centrality}(i)\) is the centrality of node \(i \in V\), and \({\text{theoretical}}_{\text{max}}\) and \({\text{theoretical}}(i)\) refer to node centralities of a theoretical likewise graph for which the sum of differences equals the highest possible scalar value.

Example

Calculating the degree centralization of a simple graph (no parallel edges, self-loops or isolates):

>>> import networkx as nx
>>> import networkx_temporal as tx
>>>
>>> G = nx.Graph()
>>>
>>> G.add_edges_from([
...     (1, 0),
...     (2, 0),
...     (3, 0),
... ])
>>>
>>> centrality = G.degree()  # Node degree values.
>>> maximum = G.order() - 1  # Highest possible degree.
>>> minimum = 1              # Minimum possible degree.
>>>
>>> # Highest theoretical sum of values in a simple star-like graph.
>>> scalar = sum(maximum - minimum for n in range(G.order()-1))
>>>
>>> tx.centralization(centrality=centrality, scalar=scalar)

1.0

Alternatively, passing a list of theoretical centrality values:

>>> theoretical_centrality = [3, 1, 1, 1]  # Theoretical degree values.
>>> tx.centralization(centrality=centrality, scalar=theoretical_centrality)

1.0
Parameters:

  • centrality (list | dict) – List or dictionary of node centralities.

  • scalar (int | float | list | dict) – Maximum theoretical sum of values. Accepts a value, list, or dictionary with node centrality degrees values. Optional.

Return type:

float | List[float]

degree_centralization(TG: TemporalGraph | Graph, self_loops: bool | None = None, isolates: bool | None = None) → float | List[float][source]

Returns the degree centralization of a graph.

The degree centralization [1] of a graph is the sum of differences between the centrality of the most central node and each of the other nodes’ centralities, divided by the maximum theoretical sum of values in a graph with the same order, size, and edge directionality, i.e., a star graph.

The degree centralization \(C_\text{deg}\) of a simple graph without self-loops \(G\) corresponds to:

\[C_\text{deg}(G) = \frac{\sum_{i \in V} \big(\text{deg}_{\text{max}} - \text{deg}(i) \big)} {(|V|-1)(\text{deg}^\star_{\text{max}} - 1)},\]

where \(|V|\) is the number of nodes, \(\text{deg}_{\text{max}}\) is the highest node degree in \(G\), \(\text{deg}(i)\) is the degree of node \(i \in V\), and \(\text{deg}^\star_{\text{max}} = |V|-1\) the maximum theoretical node degree.

See also

The igraph R manual pages - Centralization of a graph (package version 1.3.5).

Example

>>> import networkx as nx
>>> import networkx_temporal as tx
>>>
>>> TG = tx.TemporalGraph(t=2)
>>>
>>> TG[0].add_edges_from([
...     (0, 1),
...     (0, 2),
... ])
>>> TG[1].add_edges_from([
...     (0, 1),
...     (1, 2),
...     (2, 0),
... ])
>>> tx.degree_centralization(TG)

[1.0, 0.75]
Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • self_loops (bool) – If True, self-loops are considered in the calculation. Defaults to False.

  • isolates (bool) – If True, node isolates are considered in the calculation. Defaults to False.

Return type:

float | List[float]

in_degree_centralization(TG: TemporalGraph | Graph, self_loops: bool | None = None, isolates: bool | None = None) → float | List[float][source]

Returns the in-degree centralization of a graph.

The in-degree centralization \(C_\text{in}\) of a simple graph without self-loops \(G\) corresponds to:

\[C_\text{in}(G) = \frac{\sum_{i \in V} \big(\text{in}_{\text{max}} - \text{in}(i) \big)} {(|V|-1)(\text{in}^\star_{\text{max}} - 1)},\]

where \(|V|\) is the number of nodes, \(\text{in}_{\text{max}}\) is the highest node in-degree in \(G\), \(\text{in}(i)\) is the in-degree of node \(i \in V\), and \(\text{in}^\star_{\text{max}} = |V|-1\) the maximum theoretical node in-degree.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • self_loops (bool) – If True, self-loops are considered in the calculation. Defaults to False.

  • isolates (bool) – If True, node isolates are considered in the calculation. Defaults to False.

Return type:

float | List[float]

out_degree_centralization(TG: TemporalGraph | Graph, self_loops: bool | None = None, isolates: bool | None = None) → float | List[float][source]

Returns the out-degree centralization of a graph.

The out-degree centralization \(C_\text{out}\) of a simple graph without self-loops \(G\) corresponds to:

\[C_\text{out}(G) = \frac{\sum_{i \in V} \big(\text{out}_{\text{max}} - \text{out}(i) \big)} {(|V|-1)(\text{out}^\star_{\text{max}} - 1)},\]

where \(|V|\) is the number of nodes, \(\text{out}_{\text{max}}\) is the highest node out-degree in \(G\), \(\text{out}(i)\) is the out-degree of node \(i \in V\), and \(\text{out}^\star_{\text{max}} = |V|-1\) the maximum theoretical node out-degree.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • self_loops (bool) – If True, self-loops are considered in the calculation. Defaults to False.

  • isolates (bool) – If True, node isolates are considered in the calculation. Defaults to False.

Return type:

float | List[float]

conductance(TG: TemporalGraph | Graph, communities: str | list | dict, weight: str | None = 'weight') → float | List[float][source]

Returns the conductance of a graph.

Conductance [6] measures the fraction of edges that falls within a community compared to those leaving it. Lower values indicate well-defined internal community structures, weakly connected to the rest of the graph. For a set of communities, it is defined as their average:

\[\phi(G, C) = \frac {\sum_{S \in C} \min_{S \subseteq V} \phi (S)} {|C|},\]

where \(G\) is a graph, \(C\) is a set of disjoint node partitions, \(V\) is the set of all nodes, and \(\phi(S)\) is the conductance of each node subset \(S \in C\). The latter is defined as:

\[\phi(S) = \frac{\text{cut}(S, \bar{S})}{\min(\text{vol}(S), \text{vol}(\bar{S}))},\]

where \(\text{cut}(S, \bar{S})\) is the total weight of edges connecting \(S\) to its complement \(\bar{S}\), and \(\text{vol}(S)\) is the volume of \(S\), i.e., the total weight of all edges starting at the node subset.

Parameters:

  • G (object) – TemporalGraph or static NetworkX graph object.

  • communities (str | list | dict) – List of community assignments for each node, or a list of lists in case of temporal graphs, one per snapshot.

  • weight (str | None) – The edge attribute key used to compute edge weights. If None (default), all edge weights are considered as 1.

  • TG (TemporalGraph | Graph)

Note:

Wrapper around NetworkX’s conductance function.

Return type:

float | List[float]

modularity(TG: TemporalGraph | Graph, communities: str | list | dict, weight: str | None = 'weight', resolution: float | None = 1, spectral: bool = False) → float | List[float][source]

Returns the modularity of a graph.

Modularity [7] measures the fraction of edges in a graph that fall within communities, compared to their expected number in a random graph with the same degree sequence. Higher values may indicate more internal connections than expected by chance. It is commonly defined as:

\[Q = \frac{1}{2m} \sum_{(i,j) \in V^2} \left[ A_{ij} - \gamma \frac{d_i^{out} \, d_j^{in}}{2m} \right] \delta(c_i, c_j),\]

where \(m\) is the number of edges in the graph, \((i,j) \in V^2\) are node pairs, \(\mathbf{A}\) is the adjacency matrix, \(d\) are node in/out-degrees, \(c\) are their communities, and \(\gamma = 1\) (default) is the resolution parameter [4], where smaller values favor larger communities, including negative values.

This can be reduced to a summation over communities, which is more efficient to compute:

\[Q = \sum_{c \in C} \left[ \frac{L_c}{m} - \gamma \left( \frac{d_c}{2m} \right)^2 \right],\]

where \(L_c\) is the number of within-community edges and \(d_c\) is the sum of degrees of nodes in community \(c\). If spectral=True, modularity is computed using spectral_modularity() instead.

See also

The multislice_modularity() function for a temporal generalization of the metric.

Parameters:

  • TG (object) – A TemporalGraph or static NetworkX graph object.

  • communities (str | list | dict) – String (node attribute name), list of community assignments,

  • resolution (float | None) – The resolution parameter. Defaults to 1.

  • weight (str | None) – The edge attribute key used to compute edge weights (default: 'weight'). If None, all edge weights are considered as 1.

  • spectral (bool) – Whether to use the spectral method to compute modularity. If False, use NetworkX modularity (default).

Return type:

float | List[float]

multislice_modularity(TG: TemporalGraph, communities: list | str | dict, resolution: float | None = 1, interslice_weight: float | None = 1, weight: str | None = 'weight', spectral: bool = False) → float[source]

Returns the MS-modularity of a temporal graph.

Multislice modularity [8] is a generalization of the metric for multiplex graphs, where each layer corresponds to a temporal graph snapshot. Temporal node copies are connected across time by interlayer edges (‘’couplings’’), as in an unrolled graph, so the expected fraction of intra-layer edges is adjusted to account for these added connections. It may be defined as:

\[Q_{\textnormal{MS}} = \frac{1}{2 \mu} \sum_{G_t \in \mathcal{G}} \left[ \sum_{(i,j) \in V^2} \left( A_{ij} - \gamma \frac{d_i^{out} \, d_j^{in}}{2m} \delta(c_i, c_j) \right) + \sum_{i \in V} \omega \, \delta(c_{i}^{(t)}, c_{i}^{(t+1)}) \right],\]

where \(\mu\) is the total number of intra- and inter-layer edges in the temporal graph, \(G_t \in \mathcal{G}\) are graph snapshots (slices/layers), \((i,j) \in V^2\) are node pairs, \(\mathbf{A}\) is the adjacency matrix, \(d\) are node degrees, \(c\) are their communities, and \(t\) is the time or snapshot index. Additional term \(\gamma = 1\) (default) is the community resolution and \(\omega = 1\) (default) is the interlayer edge weight.

Note that if spectral=True, modularity is computed using spectral_modularity() instead.

Parameters:

  • TG (object) – A TemporalGraph object.

  • communities (list | str | dict) – String (node attribute name), list of community assignments, or list of such lists (for temporal graphs).

  • resolution (float | None) – The resolution parameter. Defaults to 1.

  • interslice_weight (float | None) – The interlayer edge weight. Default is 1.

  • weight (str | None) – The edge attribute key used to compute edge weights (default: 'weight'). If None, all edge weights are considered as 1.

  • spectral (bool) – Whether to use the spectral method to compute modularity. If False (default), use NetworkX modularity.

Return type:

float

spectral_modularity(A: array | csr_array, communities: array | csr_array, resolution: float | None = 1, directed: bool | None = True, weight: str | bool | None = True) → float[source]

Calculates modularity based on the graph spectrum.

Spectral modularity [9] defines the value of modularity \(Q\) as:

\[Q = \frac{1}{2m} \mathbf{C}^\text{T} \mathbf{B} \mathbf{C}, \quad \text{with} \quad \mathbf{B} = \mathbf{A} - \gamma \frac{\mathbf{d_{out}} \, \mathbf{d_{in}}^\text{T}}{2m},\]

where \(m\) is the total number of edges, \(\mathbf{B}\) is the modularity matrix, \(\mathbf{A}\) is the (optionally sparse) adjacency matrix, \(\mathbf{C}\) is the \(n \times k\) community assignment matrix with \(n\) as the number of nodes and \(k\) the number of communities, \(\mathbf{d_{in}}\) and \(\mathbf{d_{out}}\) are the node in- and out-degree vectors, and \(\gamma = 1\) (default) is the resolution parameter. Note that this formulation naturally extends to mixed memberships, where nodes may belong to different communities with different weights.

Parameters:

  • A (object) – Adjacency matrix (dense numpy array or sparse scipy matrix). If A is a temporal or static graph, convert it automatically.

  • communities (array | csr_array) – Community assignment matrix with shape (n_nodes, k_communities), a or vector of length n_nodes.

  • resolution (float | None) – The resolution parameter. Default is 1.

  • directed (bool | None) – Whether the graph is directed. Default is True.

  • weight (str | bool | None) – Whether to consider edge weights. If a string is provided, it is used as the edge attribute key. Default is True.

Return type:

float