~tfardet/nngt-developers

NNGT: Backend: add harmonic centrality with igraph v1 APPLIED

~tfardet
~tfardet: 1
 Backend: add harmonic centrality with igraph

 6 files changed, 74 insertions(+), 104 deletions(-)
#601916 .build.yml success
Export patchset (mbox)
How do I use this?

Copy & paste the following snippet into your terminal to import this patchset into git:

curl -s https://lists.sr.ht/~tfardet/nngt-developers/patches/25543/mbox | git am -3
Learn more about email & git
View this thread in the archives

[PATCH NNGT] Backend: add harmonic centrality with igraph Export this patch

~tfardet
From: Tanguy Fardet <tanguyfardet@protonmail.com>

---
 doc/user/graph-analysis.rst      | 41 ++++++++++-------
 nngt/analysis/graph_analysis.py  | 13 ++----
 nngt/analysis/gt_functions.py    | 11 ++---
 nngt/analysis/ig_functions.py    | 26 +++++------
 nngt/analysis/nx_functions.py    | 11 ++---
 testing/library_compatibility.py | 76 ++++++++++++--------------------
 6 files changed, 74 insertions(+), 104 deletions(-)

diff --git a/doc/user/graph-analysis.rst b/doc/user/graph-analysis.rst
index 4b7b0b0..663c49d 100644
--- a/doc/user/graph-analysis.rst
+++ b/doc/user/graph-analysis.rst
@@ -50,17 +50,17 @@ Methods that are not defined for weighted or directed graphs are marked by NA.
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.betweenness_distrib`         |    gt, nx, ig         |   gt, nx, ig        |   gt, nx, ig        |   gt, nx, ig       |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.closeness` [2]_              |    gt, nx, (ig)       |   gt, nx, (ig)      |   gt, nx, (ig)      |   gt, nx, (ig)     |
| :func:`~nngt.analysis.closeness`                   |    gt, nx, ig         |   gt, nx, ig        |   gt, nx, ig        |   gt, nx, ig       |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.connected_components`        |    gt, nx, ig         |   gt, nx, ig        |   gt, nx, ig        |   gt, nx, ig       |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.degree_distrib`              |    gt, nx, ig, nngt   |   gt, nx, ig, nngt  |   gt, nx, ig, nngt  |   gt, nx, ig, nngt |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.diameter` [3]_               |    gt, nx, ig         |   gt, nx, ig        |   gt, nx, ig        |   gt, nx, ig       |
| :func:`~nngt.analysis.diameter` [2]_               |    gt, nx, ig         |   gt, nx, ig        |   gt, nx, ig        |   gt, nx, ig       |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.global_clustering`           |    gt, nx, ig, nngt   |   nngt              |   nngt              |   nngt             |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.local_clustering` [4]_       |    gt, nx, ig, nngt   |   nngt              |   nngt              |   nngt             |
| :func:`~nngt.analysis.local_clustering` [3]_       |    gt, nx, ig, nngt   |   nngt              |   nngt              |   nngt             |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.reciprocity`                 |    gt, nx, ig, nngt   |   gt, nx, ig, nngt  |   NA                |   NA               |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
@@ -72,23 +72,19 @@ Methods that are not defined for weighted or directed graphs are marked by NA.
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.subgraph_centrality`         |    nngt               |   nngt              |   nngt              |   nngt             |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+
| :func:`~nngt.analysis.transitivity` [5]_           |    gt, nx, ig, nngt   |   nngt              |   nngt              |   nngt             |
| :func:`~nngt.analysis.transitivity` [4]_           |    gt, nx, ig, nngt   |   nngt              |   nngt              |   nngt             |
+----------------------------------------------------+-----------------------+---------------------+---------------------+--------------------+


.. [1] networkx could be used via a workaround but `an issue
       <https://github.com/networkx/networkx/issues/3917>`_ has been raised to
       find out how to best deal with this.
.. [2] since definitions of the maximum distances differ between libraries,
       igraph is currently not usable if the in- or out-degree of any of the
       nodes is zero; it also does not provide an implementation for the
       harmonic closeness.
.. [3] the implementation of the diameter for graph-tool is approximmate so
.. [2] the implementation of the diameter for graph-tool is approximmate so
       results may occasionaly be inexact with this backend.
.. [4] for directed and weighted networks, definitions and implementations
.. [3] for directed and weighted networks, definitions and implementations
       differ between graph libraries, so generic implementations are provided
       in NNGT. See ":ref:`clustering`" for details.
.. [5] identical to ``global_clustering``.
.. [4] identical to ``global_clustering``.


.. _clustering:
@@ -96,7 +92,7 @@ Methods that are not defined for weighted or directed graphs are marked by NA.
Clustering in weighted and directed networks
--------------------------------------------

For directed clustering, NNGT provides the total clustering porposed in
For directed clustering, NNGT provides the total clustering proposed in
[Fagiolo2007]_

.. math::
@@ -106,7 +102,8 @@ For directed clustering, NNGT provides the total clustering porposed in
with :math:`d_i^{\leftrightarrow} = A^2_{ii}` is the reciprocal degree.

For undirected weighted clustering, NNGT provides the definition proposed in
[Barrat2004]_, [Onnela2005]_ as well as a new continuous definition.
[Barrat2004]_, [Onnela2005]_, [Zhang2005]_ as well as a new continuous definition
[Fardet2021]_.

.. math::

@@ -116,6 +113,10 @@ For undirected weighted clustering, NNGT provides the definition proposed in

    C_{O,i}^u = \frac{(W^{\left[\frac{1}{3}\right]})^3_{ii}}{d_i (d_i - 1)}

.. math::

    C_{Z,i}^u = \frac{(W^3)_{ii}}{\sum_{j \neq k} w_{ij} w_{ik}}

.. math::

    C_{c,i}^u = \frac{\left(W^{\left[\frac{2}{3}\right]}\right)^3_{ii}}{\left(s^{\left[\frac{1}{2}\right]}_i\right)^2 - s_i}
@@ -124,8 +125,10 @@ with :math:`s^{\left[\frac{1}{2}\right]}` the generalized strength associated to
matrix :math:`W^{\left[\frac{1}{2}\right]} = \{\sqrt{w_{ij}}\}`.

For directed weighted clustering, the generalization of Barrat from
[Clemente2018]_ is provided, as well as a generalization of Onnela and of the
continuous clustering:
[Clemente2018]_ is provided, as well as a generalization of Onnela,
Zhang--Horvath, and of the continuous clustering [Fardet2020]_, for all four
directed modes (middleman, cycle, fan-in, and fan-out), as well as their sum,
the total clustering:

.. math::

@@ -139,6 +142,10 @@ reciprocal strength,

    C_{O,i}^d = \frac{\frac{1}{2}(W^{\left[\frac{1}{3}\right]} + (W^{\left[\frac{1}{3}\right]})^T)^3_{ii}}{d_i^{tot}(d_i^{tot} - 1) - d_i^{\leftrightarrow}}

.. math::

    C_{Z,i}^d = \frac{(W + W^T)^3_{ii}}{\sum_{j \neq k} (w_{ij} + w_{ji})(w_{ik} + w_{ki})}

.. math::

    C_{c,i}^d = \frac{\frac{1}{2}\left(W^{\left[\frac{2}{3}\right]} + W^{\left[\frac{2}{3}\right],T}\right)^3_{ii}}{\left(s^{\left[\frac{1}{2}\right]}_i\right)^2 - 2s^{\leftrightarrow}_i - s_i}
@@ -181,6 +188,10 @@ References
    `PDF <https://dibernardo.tigem.it/files/papers/2008/
    zhangbin-statappsgeneticsmolbio.pdf>`_.

.. [Fardet2021] Fardet, Levina. Weighted directed clustering: interpretations
    and requirements for heterogeneous, inferred, and measured networks. 2021.
    :arxiv:`2105.06318`.


----

diff --git a/nngt/analysis/graph_analysis.py b/nngt/analysis/graph_analysis.py
index 9437aa8..e39e73a 100755
--- a/nngt/analysis/graph_analysis.py
+++ b/nngt/analysis/graph_analysis.py
@@ -616,7 +616,7 @@ def average_path_length(g, sources=None, targets=None, directed=None,
# Centralities #
# ------------ #

def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
def closeness(g, weights=None, nodes=None, mode="out", harmonic=True,
              default=np.NaN):
    r'''
    Returns the closeness centrality of some `nodes`.
@@ -661,20 +661,15 @@ def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
    mode : str, optional (default: "out")
        For directed graphs, whether the distances are computed from ("out") or
        to ("in") each of the nodes.
    harmonic : bool, optional (default: False)
        Whether the arithmetic (default) or the harmonic (recommended) version
        of the closeness should be used.
    harmonic : bool, optional (default: True)
        Whether the arithmetic or the harmonic (recommended) version of the
        closeness should be used.

    Returns
    -------
    c : :class:`numpy.ndarray`
        The list of closeness centralities, on per node.

    .. warning ::
        For compatibility reasons (harmonic closeness is not implemented for
        igraph), the arithmetic version is used by default; however, it is
        recommended to use the harmonic version instead whenever possible.

    References
    ----------
    .. [gt-closeness] :gtdoc:`centrality.closeness`
diff --git a/nngt/analysis/gt_functions.py b/nngt/analysis/gt_functions.py
index 8d40915..8c72de3 100644
--- a/nngt/analysis/gt_functions.py
+++ b/nngt/analysis/gt_functions.py
@@ -161,7 +161,7 @@ def reciprocity(g):
    return gtt.edge_reciprocity(g.graph)


def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
def closeness(g, weights=None, nodes=None, mode="out", harmonic=True,
              default=np.NaN):
    r'''
    Returns the closeness centrality of some `nodes`.
@@ -204,8 +204,8 @@ def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
    mode : str, optional (default: "out")
        For directed graphs, whether the distances are computed from ("out") or
        to ("in") each of the nodes.
    harmonic : bool, optional (default: False)
        Whether the arithmetic (default) or the harmonic (recommended) version
    harmonic : bool, optional (default: True)
        Whether the arithmetic or the harmonic (recommended) version
        of the closeness should be used.

    Returns
@@ -213,11 +213,6 @@ def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
    c : :class:`np.ndarray`
        The list of closeness centralities, on per node.

    .. warning ::
        For compatibility reasons (harmonic closeness is not implemented for
        igraph), the arithmetic version is used by default; however, it is
        recommended to use the harmonic version instead whenever possible.

    References
    ----------
    .. [gt-closeness] :gtdoc:`centrality.closeness`
diff --git a/nngt/analysis/ig_functions.py b/nngt/analysis/ig_functions.py
index 95e438a..fc619bc 100644
--- a/nngt/analysis/ig_functions.py
+++ b/nngt/analysis/ig_functions.py
@@ -141,7 +141,7 @@ def reciprocity(g):
    return g.graph.reciprocity(ignore_loops=True, mode="default")


def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
def closeness(g, weights=None, nodes=None, mode="out", harmonic=True,
              default=np.NaN):
    r'''
    Returns the closeness centrality of some `nodes`.
@@ -184,20 +184,15 @@ def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
    mode : str, optional (default: "out")
        For directed graphs, whether the distances are computed from ("out") or
        to ("in") each of the nodes.
    harmonic : bool, optional (default: False)
        Whether the arithmetic (default) or the harmonic (recommended) version
        of the closeness should be used.
    harmonic : bool, optional (default: True)
        Whether the arithmetic or the harmonic (recommended) version of the
        closeness centrality should be used.

    Returns
    -------
    c : :class:`numpy.ndarray`
        The list of closeness centralities, on per node.

    .. warning ::
        For compatibility reasons (harmonic closeness is not implemented for
        igraph), the arithmetic version is used by default; however, it is
        recommended to use the harmonic version instead whenever possible.

    Note
    ----
    When requesting a subset of nodes, check whether it is faster to use
@@ -208,16 +203,17 @@ def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
    .. [ig-closeness] :igdoc:`closeness`
    '''
    if harmonic:
        raise NotImplementedError("`harmonic` closeness is not available with "
                                  "igraph backend.")
        ww = _get_ig_weights(g, weights)

    if not np.all(g.get_degrees("in")) or not np.all(g.get_degrees("out")):
        raise RuntimeError("igraph backend does not support closeness for "
                           "graphs containing nodes with zero in/out-degree.")
        try:
            return np.asarray(g.graph.harmonic_centrality(nodes, mode=mode,
                                                          weights=ww))
        except:
            raise RuntimeError("This function requires igraph >= 0.9.0.")

    ww = _get_ig_weights(g, weights)

    return g.graph.closeness(nodes, mode=mode, weights=ww)
    return np.asarray(g.graph.closeness(nodes, mode=mode, weights=ww))


def betweenness(g, btype="both", weights=None):
diff --git a/nngt/analysis/nx_functions.py b/nngt/analysis/nx_functions.py
index f894d84..c17d8b9 100644
--- a/nngt/analysis/nx_functions.py
+++ b/nngt/analysis/nx_functions.py
@@ -149,7 +149,7 @@ def reciprocity(g):
    return nx.overall_reciprocity(g.graph)


def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
def closeness(g, weights=None, nodes=None, mode="out", harmonic=True,
              default=np.NaN):
    r'''
    Returns the closeness centrality of some `nodes`.
@@ -192,8 +192,8 @@ def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
    mode : str, optional (default: "out")
        For directed graphs, whether the distances are computed from ("out") or
        to ("in") each of the nodes.
    harmonic : bool, optional (default: False)
        Whether the arithmetic (default) or the harmonic (recommended) version
    harmonic : bool, optional (default: True)
        Whether the arithmetic or the harmonic (recommended) version
        of the closeness should be used.

    Returns
@@ -201,11 +201,6 @@ def closeness(g, weights=None, nodes=None, mode="out", harmonic=False,
    c : :class:`numpy.ndarray`
        The list of closeness centralities, on per node.

    .. warning ::
        For compatibility reasons (harmonic closeness is not implemented for
        igraph), the arithmetic version is used by default; however, it is
        recommended to use the harmonic version instead whenever possible.

    References
    ----------
    .. [nx-harmonic] :nxdoc:`algorithms.centrality.harmonic_centrality`
diff --git a/testing/library_compatibility.py b/testing/library_compatibility.py
index 2626024..3002dbd 100644
--- a/testing/library_compatibility.py
+++ b/testing/library_compatibility.py
@@ -206,48 +206,28 @@ def test_closeness():
        g = nngt.Graph(nodes=num_nodes, directed=True)
        g.new_edges(edge_list, attributes={"weight": weights})

        if bckd == "igraph":
            # assert igraph fails as expected
            try:
                print(nngt.analyze_graph["closeness"](g, harmonic=True))
                errored = False
            except NotImplementedError:
                errored = True

            assert errored

            try:
                nngt.analyze_graph["closeness"](g, harmonic=False)
                runtime_error = False
            except RuntimeError:
                runtime_error = True

            assert runtime_error
        else:
            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, harmonic=True), harmonic))

            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, harmonic=False), arithmetic,
                equal_nan=True))

            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, mode="in", harmonic=True),
                harmonic_in))

            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, mode="in", harmonic=False),
                arithmetic_in, equal_nan=True))

            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, weights=True,
                                                harmonic=True),
                harmonic_wght))

            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, weights=True,
                                                harmonic=False),
                arithmetic_wght, equal_nan=True))
        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, harmonic=True), harmonic))

        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, harmonic=False), arithmetic,
            equal_nan=True))

        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, mode="in", harmonic=True),
            harmonic_in))

        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, mode="in", harmonic=False),
            arithmetic_in, equal_nan=True))

        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, weights=True, harmonic=True),
            harmonic_wght))

        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, weights=True, harmonic=False),
            arithmetic_wght, equal_nan=True))

    # UNDIRECTED
    harmonic   = [7/8, 3/4, 7/8, 1., 3/4]
@@ -262,14 +242,12 @@ def test_closeness():
        g = nngt.Graph(nodes=num_nodes, directed=False)
        g.new_edges(edge_list, attributes={"weight": weights})

        if bckd != "igraph":
            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, harmonic=True), harmonic))
        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, harmonic=True), harmonic))

            assert np.all(np.isclose(
                nngt.analyze_graph["closeness"](g, weights=True,
                                                harmonic=True),
                harmonic_wght))
        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, weights=True, harmonic=True),
            harmonic_wght))

        assert np.all(np.isclose(
            nngt.analyze_graph["closeness"](g, harmonic=False), arithmetic,
-- 
2.32.0
builds.sr.ht
NNGT/patches/.build.yml: SUCCESS in 26m33s

[Backend: add harmonic centrality with igraph][0] from [~tfardet][1]

[0]: https://lists.sr.ht/~tfardet/nngt-developers/patches/25543
[1]: mailto:tanguyfardet@protonmail.com

✓ #601916 SUCCESS NNGT/patches/.build.yml https://builds.sr.ht/~tfardet/job/601916