~tfardet: 1 Backend: add harmonic centrality with igraph 6 files changed, 74 insertions(+), 104 deletions(-)
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 -3Learn more about email & git
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 <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