statistics

Functions to compute various graph statistics.

The functions in this module allow to compute various statistics on graphs

Example

import pathpyG as pp

# Generate a toy example graph.
g = pp.Graph.from_edge_list([("b", "c"), ("a", "b"), ("c", "d"), ("d", "a"), ("b", "d")])

# Calculate degree distribution and raw moments
d_dist = pp.statistics.degree_distribution(g)
k_1 = pp.statistics.degree_raw_moment(g, k=1)
k_2 = pp.statistics.degree_raw_moment(g, k=2)

avg_clustering_coefficient

Calculates the average clustering coefficient \(C\) of the graph \(G=(V, E)\).

Given the local clustering coefficients \(C_u\) for all nodes \(u \in V\), the average clustering coefficient is defined as their mean:

\[ C = \frac{1}{n} \sum_{u \in V} C_u \]

Warning

This measurement of global clustering should not be confused with the global clustering coefficient defined as the fraction of closed paths of length two over all paths of length two in the graph.

Reference

Proposed by Watts and Strogatz in their seminal paper on "Collective dynamics of 'small-world' networks"¹. Further details can be found in in Chapter 7.3 in Networks² by Mark Newman.

---

1. Watts, D. J. & Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature 393, 440-442 (1998). ↩

2. Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001. ↩

Parameters:

Name	Type	Description	Default
g	pathpyG.core.graph.Graph	The graph in which to calculate the average clustering coefficient.	required

Returns:

Name	Type	Description
float	float	The average clustering coefficient of the graph.

Source code in src/pathpyG/statistics/clustering.py

def avg_clustering_coefficient(g: Graph) -> float:
    r"""Calculates the average clustering coefficient $C$ of the [graph][pathpyG.core.graph.Graph] $G=(V, E)$.

    Given the local clustering coefficients $C_u$ for all nodes $u \in V$,
    the average clustering coefficient is defined as their mean:

    $$
    C = \frac{1}{n} \sum_{u \in V} C_u
    $$

    Warning:
        This measurement of global clustering should not be confused with the global clustering coefficient
        defined as the fraction of closed paths of length two over all paths of length two in the graph.

    ??? reference
        Proposed by Watts and Strogatz in their seminal paper on "Collective dynamics of 'small-world' networks"[^1].
        Further details can be found in in Chapter 7.3 in *Networks*[^2] by Mark Newman.

    [^1]: *Watts, D. J. & Strogatz, S. H. Collective dynamics of 'small-world' networks. Nature 393, 440-442 (1998).*
    [^2]: *Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001.*

    Args:
        g (Graph): The graph in which to calculate the average clustering coefficient.

    Returns:
        float: The average clustering coefficient of the graph.
    """
    return torch.mean(torch.tensor([local_clustering_coefficient(g, v) for v in g.nodes], dtype=torch.float32)).item()

closed_triads

Calculates the set of edges that represent a closed triad around a given node \(v\).

Parameters:

Name	Type	Description	Default
g	pathpyG.core.graph.Graph	The graph in which to calculate the list of closed triads.	required
v	str	The node around which to calculate the closed triads.	required

Source code in src/pathpyG/statistics/clustering.py

def closed_triads(g: Graph, v: str) -> Set:
    """Calculates the set of edges that represent a closed triad around a given node $v$.

    Args:
        g (Graph): The graph in which to calculate the list of closed triads.
        v (str): The node around which to calculate the closed triads.
    """
    c_triads: set = set()
    edges = set()

    # Collect all edges of successors
    for x in g.successors(v):
        for y in g.successors(x):
            edges.add((x, y))

    for x, y in edges:
        if y in g.successors(v):
            c_triads.add((x, y))
    return c_triads

degree_assortativity

Calculate the degree assortativity coefficient of the graph.

The degree assortativity coefficient \(r\) of a graph \(G=(V, E)\) is defined as

\[ r = \frac{\sum_{i,j} \left(A_{ij} - d_i d_j / (2m)\right) d_i d_j}{\sum_{i,j} \left(d_i \delta_{ij} - d_i d_j / (2m)\right) d_i d_j} \]

with the adjacency matrix \(A\), the degree \(d_i\) of node \(i\), the number of edges \(m\) and the Kronecker delta \(\delta_{ij}\).

For computational reasons, we calculate the coefficient as follows:

\[ r = \frac{S_1S_e - S_2^2}{S_1S_3 - S_2^2} \]

where \(S_l = \sum_{i} d_i^l\) for \(l=1,2,3\) and \(S_e = \sum_{(i,j) \in E} d_i d_j\).

Reference

You can find the defintions above with further explanations in Equations (10.27) and (10.28) in Chapter 10.7 in Networks¹ by Mark Newman.

---

1. Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001. ↩

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The graph for which to calculate the degree assortativity	required
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'

Returns:

Name	Type	Description
float	float	The degree assortativity coefficient of the graph

Source code in src/pathpyG/statistics/degrees.py

def degree_assortativity(graph: Graph, mode: str = "total") -> float:
    r"""Calculate the degree assortativity coefficient of the [graph][pathpyG.core.graph.Graph].

    The degree assortativity coefficient $r$ of a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ is defined as

    $$
    r = \frac{\sum_{i,j} \left(A_{ij} - d_i d_j / (2m)\right) d_i d_j}{\sum_{i,j} \left(d_i \delta_{ij} - d_i d_j / (2m)\right) d_i d_j}
    $$

    with the adjacency matrix $A$, the degree $d_i$ of node $i$, the number of edges [$m$][pathpyG.core.graph.Graph.m] and the Kronecker delta $\delta_{ij}$.

    For computational reasons, we calculate the coefficient as follows:

    $$
    r = \frac{S_1S_e - S_2^2}{S_1S_3 - S_2^2}
    $$

    where $S_l = \sum_{i} d_i^l$ for $l=1,2,3$ and $S_e = \sum_{(i,j) \in E} d_i d_j$.

    ??? reference
        You can find the defintions above with further explanations in Equations (10.27) and (10.28) in Chapter 10.7 in *Networks*[^1] by Mark Newman.

    [^1]: *Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001.*

    Args:
        graph: The graph for which to calculate the degree assortativity
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs

    Returns:
        float: The degree assortativity coefficient of the graph
    """
    degree_seq = degree_sequence(graph, mode=mode).float()
    S_1 = torch.sum(degree_seq).item()
    S_2 = torch.sum(degree_seq**2).item()
    S_3 = torch.sum(degree_seq**3).item()
    S_e = torch.sum(degree_seq[graph.data.edge_index[0]] * degree_seq[graph.data.edge_index[1]]).item()

    numerator = S_1 * S_e - S_2**2
    denominator = S_1 * S_3 - S_2**2

    return numerator / denominator

degree_central_moment

Calculates the k-th central moment of the degree distribution.

The k-th central moment \(\mu_k\) of the degree distribution \(P_{mode}(d)\) of a graph \(G=(V, E)\) is defined as

\[ \mu_k = \sum_d (d - \langle d_{mode} \rangle)^k P_{mode}(d). \]

where \(\langle d_{mode} \rangle\) is the mean degree of the graph and \(P_{mode}(d)\) is the degree distribution.

Note

The 2^nd central moment corresponds to the variance of the degree distribution.

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The graph for which to calculate the k-th central moment	required
k	int	The order of the moment to calculate	1
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'

Returns:

Name	Type	Description
float	float	The k-th central moment of the degree distribution

Source code in src/pathpyG/statistics/degrees.py

def degree_central_moment(graph: Graph, k: int = 1, mode: str = "total") -> float:
    r"""Calculates the k-th central moment of the [degree distribution][pathpyG.statistics.degrees.degree_distribution].

    The k-th central moment $\mu_k$ of the [degree distribution][pathpyG.statistics.degrees.degree_distribution] $P_{mode}(d)$ of a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ is defined as

    $$
    \mu_k = \sum_d (d - \langle d_{mode} \rangle)^k P_{mode}(d).
    $$

    where $\langle d_{mode} \rangle$ is the [mean degree][pathpyG.statistics.degrees.mean_degree] of the graph and $P_{mode}(d)$ is the [degree distribution][pathpyG.statistics.degrees.degree_distribution].

    Note:
        The 2nd central moment corresponds to the variance of the degree distribution.

    Args:
        graph: The graph for which to calculate the k-th central moment
        k: The order of the moment to calculate
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs

    Returns:
        float: The k-th central moment of the degree distribution
    """
    p_k = degree_distribution(graph, mode=mode)
    mean = mean_degree(graph, mode=mode)
    x = torch.arange(len(p_k), dtype=torch.float32)
    m = torch.sum((x - mean) ** k * p_k).item()
    return m

degree_distribution

Calculates the (unweighted) degree distribution of a graph.

The degree distribution \(P_{mode}(d)\) of a graph \(G=(V, E)\) is defined as

\[ P_{mode}(d) = \frac{N_d}{n} \]

with \(N_d = |\{v_i \in V : d_{mode}(v_i) = d\}|\) being the number of nodes with degree \(d\) and \(n\) being the total number of nodes in the graph. The modes are defined as follows:

• 'in': In-degree \(d_{in}(v_i)\) of node \(v_i\), i.e. the number of incoming edges \(|\{(v_j, v_i) \in E\}|\) from any other node \(v_j\)
• 'out': Out-degree \(d_{out}(v_i)\) of node \(v_i\), i.e. the number of outgoing edges \(|\{(v_i, v_j) \in E\}|\) to any other node \(v_j\)
• 'total': Total degree \(d_{total}(v_i)\) of node \(v_i\), i.e. the sum of in-degree and out-degree \(d_{in}(v_i) + d_{out}(v_i)\)

The degree distribution is returned as a torch.Tensor of shape (d_max + 1,) where d_max is the maximum degree in the graph.

Reference

For further reading, see Chapter 10.3 in Networks¹ by Mark Newman.

---

1. Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001. ↩

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The Graph object for which the degree distribution is calculated	required
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'

Returns:

Type	Description
torch.Tensor	torch.Tensor: A tensor containing the degree distribution

Source code in src/pathpyG/statistics/degrees.py

def degree_distribution(graph: Graph, mode: str = "total") -> torch.Tensor:
    r"""Calculates the (unweighted) degree distribution of a [graph][pathpyG.core.graph.Graph].

    The degree distribution $P_{mode}(d)$ of a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ is defined as

    $$
    P_{mode}(d) = \frac{N_d}{n}
    $$

    with $N_d = |\{v_i \in V : d_{mode}(v_i) = d\}|$ being the number of nodes with degree $d$ and $n$ being the total number of nodes in the graph.
    The modes are defined as follows:

    - 'in': In-degree $d_{in}(v_i)$ of node $v_i$, i.e. the number of incoming edges $|\{(v_j, v_i) \in E\}|$ from any other node $v_j$
    - 'out': Out-degree $d_{out}(v_i)$ of node $v_i$, i.e. the number of outgoing edges $|\{(v_i, v_j) \in E\}|$ to any other node $v_j$
    - 'total': Total degree $d_{total}(v_i)$ of node $v_i$, i.e. the sum of in-degree and out-degree $d_{in}(v_i) + d_{out}(v_i)$

    The degree distribution is returned as a `torch.Tensor` of shape `(d_max + 1,)` where `d_max` is the maximum degree in the graph.

    ??? reference
        For further reading, see Chapter 10.3 in *Networks*[^1] by Mark Newman.

    [^1]: *Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001.*

    Args:
        graph: The `Graph` object for which the degree distribution is calculated
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs

    Returns:
        torch.Tensor: A tensor containing the degree distribution
    """
    return degree_sequence(graph, mode=mode).bincount() / graph.n

degree_generating_function

Returns the generating function of the degree distribution of a graph.

Returns \(f(x)\) where \(f\) is the probability generating function for the degree distribution \(P_{mode}(d)\) for a graph \(G=(V, E)\) defined as

\[ f(x) = \sum_d P_{mode}(d) x^d. \]

The function is defined in the interval \(\left[0,1\right]\). The following properties hold:

1. The values of the degree distribution \(P_{mode}(d)\) can be retrieved from the generating function via $$ P_{mode}(d) = \left[\frac{1}{d!} \frac{d^d f}{dx^d}\right]_{x=0} $$

   with \(\frac{d^d}{dx^d} f\) being the d-th derivative of \(f\) by \(x\).

2. The \(k\)-th raw moment of the degree distribution can be retrieved from the generating function with

   \[ \left[\left(x \frac{d}{dx}\right)^k f\right]_{x=1} = \langle d_{mode}^k \rangle. \]

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The graph for which the generating function shall be computed	required
x	float | list[float] | numpy.ndarray | torch.Tensor	float, list, numpy.ndarray, or torch.Tensor The argument(s) for which value(s) \(f(x)\) shall be computed.	required
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'

Returns:

Type	Description
float | torch.Tensor	float or torch.Tensor: The value(s) of the generating function at x

Examples:

Generate simple network:

>>> import pathpyG as pp
>>>
>>> g = pp.Graph.from_edge_list(
...         [('a', 'b'), ('b', 'c'), ('a', 'c'), ('c', 'd'), ('d', 'e'), ('d', 'f'), ('e', 'f')]
...     ).to_undirected()

Return single function value:

>>> val = pp.statistics.degree_generating_function(g, 0.3)
>>> print(val)
0.069...

Plot generating function of degree distribution

>>> x = list(range(10))
>>> y = pp.statistics.degree_generating_function(g, x)
>>> print(y)
tensor([  0.0000,   1.0000,   5.3333,  15.0000,  32.0000,  58.3333,  96.0000,
147.0000, 213.3333, 297.0000])

Source code in src/pathpyG/statistics/degrees.py

def degree_generating_function(
    graph: Graph, x: float | list[float] | _np.ndarray | torch.Tensor, mode: str = "total"
) -> float | torch.Tensor:
    r"""Returns the generating function of the degree distribution of a [graph][pathpyG.core.graph.Graph].

    Returns $f(x)$ where $f$ is the probability generating function for the degree
    distribution $P_{mode}(d)$ for a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ defined as

    $$
    f(x) = \sum_d P_{mode}(d) x^d.
    $$

    The function is defined in the interval $\left[0,1\right]$. The following properties hold:

    1. The values of the [degree distribution][pathpyG.statistics.degrees.degree_distribution] $P_{mode}(d)$ can be retrieved from the generating function via
        $$
        P_{mode}(d) = \left[\frac{1}{d!} \frac{d^d f}{dx^d}\right]_{x=0}
        $$

        with $\frac{d^d}{dx^d} f$ being the d-th derivative of $f$ by $x$.

    2. The $k$-th raw moment of the degree distribution can be retrieved from the generating function with

        $$
        \left[\left(x \frac{d}{dx}\right)^k f\right]_{x=1} = \langle d_{mode}^k \rangle.
        $$

    Args:
        graph: The [graph][pathpyG.core.graph.Graph] for which the generating function shall be computed
        x:  float, list, numpy.ndarray, or torch.Tensor
            The argument(s) for which value(s) $f(x)$ shall be computed.
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs

    Returns:
        float or torch.Tensor: The value(s) of the generating function at x

    Examples:
        Generate simple network:

        >>> import pathpyG as pp
        >>>
        >>> g = pp.Graph.from_edge_list(
        ...         [('a', 'b'), ('b', 'c'), ('a', 'c'), ('c', 'd'), ('d', 'e'), ('d', 'f'), ('e', 'f')]
        ...     ).to_undirected()

        Return single function value:

        >>> val = pp.statistics.degree_generating_function(g, 0.3)
        >>> print(val)
        0.069...

        Plot generating function of degree distribution

        >>> x = list(range(10))
        >>> y = pp.statistics.degree_generating_function(g, x)
        >>> print(y)
        tensor([  0.0000,   1.0000,   5.3333,  15.0000,  32.0000,  58.3333,  96.0000,
        147.0000, 213.3333, 297.0000])
    """
    p_k = degree_distribution(graph, mode=mode)

    if isinstance(x, float):
        x_range = torch.tensor([x])
    elif isinstance(x, list) or isinstance(x, _np.ndarray):
        x_range = torch.tensor(x, dtype=torch.float32)
    elif isinstance(x, torch.Tensor):
        x_range = x.float()
    else:
        raise TypeError("x must be a float, list, numpy.ndarray, or torch.Tensor")

    # Via broadcasting, compute f(x) for all x in x_range defined as f(x) = sum_k p_k * x^k
    values = torch.sum(p_k.unsqueeze(1) * (x_range.unsqueeze(0) ** torch.arange(p_k.size(0)).unsqueeze(1)), dim=0)

    if isinstance(x, float):
        return values[0].item()
    else:
        return values

degree_raw_moment

Calculates the k-th raw moment of the degree distribution of a graph.

The k-th raw moment \(\langle d^k \rangle\) of the degree distribution \(P_{mode}(d)\) of a graph \(G=(V, E)\) is defined as

\[ \langle d_{mode}^k \rangle = \sum_d d^k P_{mode}(d). \]

Reference

For further reading, see Equation 10.20 in Chapter 10.4 in Networks¹ by Mark Newman.

---

1. Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001. ↩

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The graph in which to calculate the k-th raw moment	required
k	int	The order of the moment to calculate	1
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'

Returns:

Name	Type	Description
float	float	The k-th raw moment of the degree distribution

Source code in src/pathpyG/statistics/degrees.py

def degree_raw_moment(graph: Graph, k: int = 1, mode: str = "total") -> float:
    r"""Calculates the k-th raw moment of the degree distribution of a [graph][pathpyG.core.graph.Graph].

    The k-th raw moment $\langle d^k \rangle$ of the [degree distribution][pathpyG.statistics.degrees.degree_distribution] $P_{mode}(d)$ of a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ is defined as

    $$
    \langle d_{mode}^k \rangle = \sum_d d^k P_{mode}(d).
    $$

    ??? reference
        For further reading, see Equation 10.20 in Chapter 10.4 in *Networks*[^1] by Mark Newman.

    [^1]: *Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001.*

    Args:
        graph:  The graph in which to calculate the k-th raw moment
        k: The order of the moment to calculate
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs

    Returns:
        float: The k-th raw moment of the degree distribution
    """
    p_k = degree_distribution(graph, mode=mode)
    x = torch.arange(len(p_k), dtype=torch.float32)
    m = torch.sum((x**k) * p_k).item()
    return m

degree_sequence

Calculates the (unweighted) degree sequence of a graph.

Returns the degree sequence of a graph \(G=(V, E)\) defined as

\[ \left\{d_{mode}(v_1), d_{mode}(v_2), \ldots, d_{mode}(v_n)\right\} \text{ for all nodes } v_i \in V \]

with \(d_{mode}(v_i)\) being the degree of node \(v_i\) in mode 'in', 'out' or 'total'. The modes are defined as follows:

• 'in': In-degree \(d_{in}(v_i)\) of node \(v_i\), i.e. the number of incoming edges \(|\{(v_j, v_i) \in E\}|\) from any other node \(v_j\)
• 'out': Out-degree \(d_{out}(v_i)\) of node \(v_i\), i.e. the number of outgoing edges \(|\{(v_i, v_j) \in E\}|\) to any other node \(v_j\)
• 'total': Total degree \(d_{total}(v_i)\) of node \(v_i\), i.e. the sum of in-degree and out-degree \(d_{in}(v_i) + d_{out}(v_i)\)

The degree sequence is returned as a torch.Tensor of shape (n,) where \(n\) is the number of nodes in the graph. The order of the degree sequence corresponds to the indexing of the nodes in the graph and the index of a node \(v_i\) given by its label can be accessed via graph.mapping.to_idx(v_i).

Reference

For further reading, see Chapter 10.3 in Networks¹ by Mark Newman.

---

1. Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001. ↩

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The Graph object for which degrees are calculated	required
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'

Returns:

Type	Description
torch.Tensor	torch.Tensor: A tensor containing the degree sequence

Source code in src/pathpyG/statistics/degrees.py

def degree_sequence(graph: Graph, mode: str = "total") -> torch.Tensor:
    r"""Calculates the (unweighted) degree sequence of a [graph][pathpyG.core.graph.Graph].

    Returns the degree sequence of a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ defined as

    $$
    \left\{d_{mode}(v_1), d_{mode}(v_2), \ldots, d_{mode}(v_n)\right\} \text{ for all nodes } v_i \in V
    $$

    with $d_{mode}(v_i)$ being the degree of node $v_i$ in mode 'in', 'out' or 'total'.
    The modes are defined as follows:

    - 'in': In-degree $d_{in}(v_i)$ of node $v_i$, i.e. the number of incoming edges $|\{(v_j, v_i) \in E\}|$ from any other node $v_j$
    - 'out': Out-degree $d_{out}(v_i)$ of node $v_i$, i.e. the number of outgoing edges $|\{(v_i, v_j) \in E\}|$ to any other node $v_j$
    - 'total': Total degree $d_{total}(v_i)$ of node $v_i$, i.e. the sum of in-degree and out-degree $d_{in}(v_i) + d_{out}(v_i)$

    The degree sequence is returned as a `torch.Tensor` of shape `(n,)` where $n$ is the number of nodes in the graph.
    The order of the degree sequence corresponds to the indexing of the nodes in the graph and
    the index of a node $v_i$ given by its label can be accessed via [`graph.mapping.to_idx(v_i)`][pathpyG.core.index_map.IndexMap.to_idx].

    ??? reference
        For further reading, see Chapter 10.3 in *Networks*[^1] by Mark Newman.

    [^1]: *Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001.*

    Args:
        graph: The `Graph` object for which degrees are calculated
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs

    Returns:
        torch.Tensor: A tensor containing the degree sequence
    """
    if mode == "total":
        if graph.is_directed():
            return graph.degrees(mode="in", return_tensor=True) + graph.degrees(mode="out", return_tensor=True)  # type: ignore[operator]
        else:
            return graph.degrees(mode="in", return_tensor=True)  # type: ignore[return-value]
    else:
        return graph.degrees(mode, return_tensor=True)  # type: ignore[return-value]

local_clustering_coefficient

Calculates the local clustering coefficient \(C_u\) for a given node \(u\) from a graph \(G=(V, E)\).

The local clustering coefficient is defined as the fraction of closed triads around node \(u\) over the number of possible triads.

Parameters:

Name	Type	Description	Default
g	pathpyG.core.graph.Graph	The graph in which to calculate the clustering coefficient.	required
u	str	The node for which to calculate the clustering coefficient.	required

Returns:

Name	Type	Description
float	float	The local clustering coefficient of node u.

Source code in src/pathpyG/statistics/clustering.py

def local_clustering_coefficient(g: Graph, u: str) -> float:
    """Calculates the local clustering coefficient $C_u$ for a given node $u$ from a [graph][pathpyG.core.graph.Graph] $G=(V, E)$.

    The local clustering coefficient is defined as the fraction of closed
    triads around node $u$ over the number of possible triads.

    Args:
        g (Graph): The graph in which to calculate the clustering coefficient.
        u (str): The node for which to calculate the clustering coefficient.

    Returns:
        float: The local clustering coefficient of node u.
    """
    # Compute number of directly connected neighbour pairs
    k_u = float(len(closed_triads(g, u)))

    # Normalise fraction based on number of possible edges
    if g.is_directed():
        if g.out_degrees[u] > 1:
            return k_u / (g.out_degrees[u] * (g.out_degrees[u] - 1))
        else:
            return 0.0
    else:
        k_u /= 2.0
        if g.degrees()[u] > 1:  # type: ignore[index]
            return 2.0 * k_u / (g.degrees()[u] * (g.degrees()[u] - 1))  # type: ignore[index]
        else:
            return 0.0

mean_degree

Calculates the mean degree of a graph.

The mean degree \(\langle d \rangle\) of a graph \(G=(V, E)\) is defined as

\[ \langle d_{mode} \rangle = \frac{1}{n} \sum_{i=1}^{n} d_{mode}(v_i) \]

with \(d_{mode}(v_i)\) being the degree of node \(v_i\) in mode 'in', 'out' or 'total'. The modes are defined as follows:

• 'in': In-degree \(d_{in}(v_i)\) of node \(v_i\), i.e. the number of incoming edges \(|\{(v_j, v_i) \in E\}|\) from any other node \(v_j\)
• 'out': Out-degree \(d_{out}(v_i)\) of node \(v_i\), i.e. the number of outgoing edges \(|\{(v_i, v_j) \in E\}|\) to any other node \(v_j\)
• 'total': Total degree \(d_{total}(v_i)\) of node \(v_i\), i.e. the sum of in-degree and out-degree \(d_{in}(v_i) + d_{out}(v_i)\)

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The graph for which to calculate the mean degree	required
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'

Returns:

Name	Type	Description
float	float	The mean degree of the graph

Source code in src/pathpyG/statistics/degrees.py

def mean_degree(graph: Graph, mode: str = "total") -> float:
    r"""Calculates the mean degree of a [graph][pathpyG.core.graph.Graph].

    The mean degree $\langle d \rangle$ of a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ is defined as

    $$
    \langle d_{mode} \rangle = \frac{1}{n} \sum_{i=1}^{n} d_{mode}(v_i)
    $$

    with $d_{mode}(v_i)$ being the degree of node $v_i$ in mode 'in', 'out' or 'total'.
    The modes are defined as follows:

    - 'in': In-degree $d_{in}(v_i)$ of node $v_i$, i.e. the number of incoming edges $|\{(v_j, v_i) \in E\}|$ from any other node $v_j$
    - 'out': Out-degree $d_{out}(v_i)$ of node $v_i$, i.e. the number of outgoing edges $|\{(v_i, v_j) \in E\}|$ to any other node $v_j$
    - 'total': Total degree $d_{total}(v_i)$ of node $v_i$, i.e. the sum of in-degree and out-degree $d_{in}(v_i) + d_{out}(v_i)$

    Args:
        graph: The graph for which to calculate the mean degree
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs

    Returns:
        float: The mean degree of the graph
    """
    return torch.mean(degree_sequence(graph, mode=mode).float()).item()

mean_neighbor_degree

Calculates the mean neighbor degree of a graph.

The mean neighbor degree \(\langle d_{\mathcal{N}} \rangle\) of a graph \(G=(V, E)\) is defined as

\[ \langle d_{\mathcal{N}} \rangle = \frac{1}{m} \sum_{v_i \in V} \sum_{v_j \in \mathcal{N}(v_i)} d_{mode}(v_j) \]

with the number of edges \(m\) (1), the set of neighbors \(\mathcal{N}(v_i)\) of node \(v_i\) and \(d_{mode}(v_j)\) being the degree of neighbor node \(v_j \in \mathcal{N}(v_i)\) in mode 'in', 'out' or 'total'.

1. This definition is for directed graphs. For undirected graphs, the denominator is \(2m\).

The modes are defined as follows:

• 'in': In-degree \(d_{in}(v_i)\) of node \(v_i\), i.e. the number of incoming edges \(|\{(v_j, v_i) \in E\}|\) from any other node \(v_j\)
• 'out': Out-degree \(d_{out}(v_i)\) of node \(v_i\), i.e. the number of outgoing edges \(|\{(v_i, v_j) \in E\}|\) to any other node \(v_j\)
• 'total': Total degree \(d_{total}(v_i)\) of node \(v_i\), i.e. the sum of in-degree and out-degree \(d_{in}(v_i) + d_{out}(v_i)\)

Reference

For further reading, see Chapter 12.2 in Networks¹ by Mark Newman.

---

1. Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001. ↩

Parameters:

Name	Type	Description	Default
graph	pathpyG.core.graph.Graph	The graph for which to calculate the mean neighbor degree	required
mode	str	'in', 'out' or 'total' for directed graphs, ignored for undirected graphs	'total'
exclude_backlink	bool	Whether to exclude the backlink to the original node when calculating neighbor degrees	False

Returns:

Name	Type	Description
float	float	The mean neighbor degree of the graph

Source code in src/pathpyG/statistics/degrees.py

def mean_neighbor_degree(graph: Graph, mode: str = "total", exclude_backlink: bool = False) -> float:
    r"""Calculates the mean neighbor degree of a [graph][pathpyG.core.graph.Graph].

    The mean neighbor degree $\langle d_{\mathcal{N}} \rangle$ of a [graph][pathpyG.core.graph.Graph] $G=(V, E)$ is defined as

    $$
    \langle d_{\mathcal{N}} \rangle = \frac{1}{m} \sum_{v_i \in V} \sum_{v_j \in \mathcal{N}(v_i)} d_{mode}(v_j)
    $$


    with the number of edges [$m$][pathpyG.core.graph.Graph.m] (1), the set of neighbors $\mathcal{N}(v_i)$ of node $v_i$ and $d_{mode}(v_j)$ being the degree of neighbor node $v_j \in \mathcal{N}(v_i)$ in mode 'in', 'out' or 'total'.
    { .annotate }

    1. This definition is for directed graphs. For undirected graphs, the denominator is $2m$.

    The modes are defined as follows:

    - 'in': In-degree $d_{in}(v_i)$ of node $v_i$, i.e. the number of incoming edges $|\{(v_j, v_i) \in E\}|$ from any other node $v_j$
    - 'out': Out-degree $d_{out}(v_i)$ of node $v_i$, i.e. the number of outgoing edges $|\{(v_i, v_j) \in E\}|$ to any other node $v_j$
    - 'total': Total degree $d_{total}(v_i)$ of node $v_i$, i.e. the sum of in-degree and out-degree $d_{in}(v_i) + d_{out}(v_i)$

    ??? reference
        For further reading, see Chapter 12.2 in *Networks*[^1] by Mark Newman.

    [^1]: *Newman, M. E. J. Networks. (Oxford University Press, 2018). doi:10.1093/oso/9780198805090.001.0001.*

    Args:
        graph: The graph for which to calculate the mean neighbor degree
        mode:  'in', 'out' or 'total' for directed graphs, ignored for undirected graphs
        exclude_backlink: Whether to exclude the backlink to the original node when calculating neighbor degrees

    Returns:
        float: The mean neighbor degree of the graph
    """
    in_degree = degree_sequence(graph, mode="in")
    degree_seq = degree_sequence(graph, mode=mode)
    if exclude_backlink:
        degree_seq = degree_seq - 1
    return torch.sum(in_degree * degree_seq).item() / (2 * graph.m if graph.is_undirected() else graph.m)