Repository: martinfleis/momepy
Pull request #71 (2019-09-06 14:45:42)

ENH: Multiple centrality assessment
Add Betweenness, straightness and global closeness centrality. Betweenness can be calculated on both nodes and edges. Rest on nodes, could be approximated on edges using `mean_nodes`.

codecov[bot]: # [Codecov](https://codecov.io/gh/martinfleis/momepy/pull/71?src=pr&el=h1) Report
> Merging [#71](https://codecov.io/gh/martinfleis/momepy/pull/71?src=pr&el=desc) into [master](https://codecov.io/gh/martinfleis/momepy/commit/ee343addb112f292da6fa721f37c1d46b11cccf6?src=pr&el=desc) will **increase** coverage by `0.03%`.
> The diff coverage is `95%`.

[![Impacted file tree graph](https://codecov.io/gh/martinfleis/momepy/pull/71/graphs/tree.svg?width=650&token=i04999UxkK&height=150&src=pr)](https://codecov.io/gh/martinfleis/momepy/pull/71?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master      #71      +/-   ##
==========================================
+ Coverage   93.09%   93.12%   +0.03%     
==========================================
  Files           9        9              
  Lines        2201     2256      +55     
==========================================
+ Hits         2049     2101      +52     
- Misses        152      155       +3
```


| [Impacted Files](https://codecov.io/gh/martinfleis/momepy/pull/71?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [momepy/graph.py](https://codecov.io/gh/martinfleis/momepy/pull/71/diff?src=pr&el=tree#diff-bW9tZXB5L2dyYXBoLnB5) | `97.73% <95%> (-1.06%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/martinfleis/momepy/pull/71?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/martinfleis/momepy/pull/71?src=pr&el=footer). Last update [ee343ad...45a177a](https://codecov.io/gh/martinfleis/momepy/pull/71?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).


Patch:
diff --git a/.travis.yml b/.travis.yml
index 6147539..ec6d7e2 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -27,6 +27,8 @@ install:
   - source activate test
   - if [ "$DEV" ]; then pip install git+https://github.com/geopandas/geopandas.git; fi
   - if [ "$DEV" ]; then pip install git+https://github.com/pysal/libpysal.git; fi
+  - if [ "$DEV" ]; then pip install git+https://github.com/networkx/networkx.git; fi
+
   - python setup.py install
   - conda list
   - black --check .
diff --git a/docs/api.rst b/docs/api.rst
index 7f67f20..45051ea 100644
--- a/docs/api.rst
+++ b/docs/api.rst
@@ -96,17 +96,21 @@ graph
 .. autosummary::
    :toctree: generated/
 
+   betweenness_centrality
    cds_length
    clustering
    cyclomatic
    edge_node_ratio
    gamma
-   local_closeness
+   global_closeness_centrality
+   local_closeness_centrality
    mean_node_degree
    mean_node_dist
+   mean_nodes
    meshedness
    node_degree
    proportion
+   straightness_centrality
    subgraph
 
 diversity
diff --git a/momepy/graph.py b/momepy/graph.py
index eb1c95b..00c51c6 100644
--- a/momepy/graph.py
+++ b/momepy/graph.py
@@ -6,6 +6,7 @@
 import networkx as nx
 from tqdm import tqdm
 import numpy as np
+import math
 
 
 def node_degree(graph, name="degree"):
@@ -537,7 +538,41 @@ def gamma(graph, radius=5, name="gamma", distance=None):
     return netx
 
 
-def _closeness_centrality(G, u=None, distance=None, wf_improved=True, len_graph=None):
+def clustering(graph, name="cluster"):
+    """
+    Calculates the squares clustering coefficient for nodes.
+
+    Wrapper around ``networkx.square_clustering``.
+
+    .. math::
+
+
+    Parameters
+    ----------
+    graph : networkx.Graph
+        Graph representing street network.
+        Ideally genereated from GeoDataFrame using :py:func:`momepy.gdf_to_nx`
+    name : str, optional
+        calculated attribute name
+
+    Returns
+    -------
+    Graph
+        networkx.Graph
+
+    Examples
+    --------
+    >>> network_graph = mm.clustering(network_graph)
+    """
+    netx = graph.copy()
+
+    vals = nx.square_clustering(netx)
+    nx.set_node_attributes(netx, vals, name)
+
+    return netx
+
+
+def _closeness_centrality(G, u=None, length=None, wf_improved=True, len_graph=None):
     r"""Compute closeness centrality for nodes. Slight adaptation of networkx
     `closeness_centrality` to allow normalisation for local closeness.
     Adapted script used in networkx.
@@ -598,12 +633,12 @@ def _closeness_centrality(G, u=None, distance=None, wf_improved=True, len_graph=
        Cambridge University Press.
     """
 
-    if distance is not None:
+    if length is not None:
         import functools
 
         # use Dijkstra's algorithm with specified attribute as edge weight
         path_length = functools.partial(
-            nx.single_source_dijkstra_path_length, weight=distance
+            nx.single_source_dijkstra_path_length, weight=length
         )
     else:
         path_length = nx.single_source_shortest_path_length
@@ -624,8 +659,8 @@ def _closeness_centrality(G, u=None, distance=None, wf_improved=True, len_graph=
     return closeness_centrality[u]
 
 
-def local_closeness(
-    graph, radius=5, name="closeness", distance=None, closeness_distance=None
+def local_closeness_centrality(
+    graph, radius=5, name="closeness", distance=None, length=None
 ):
     """
     Calculates local closeness for each node based on the defined distance.
@@ -650,7 +685,7 @@ def local_closeness(
         Use specified edge data key as distance.
         For example, setting distance=’weight’ will use the edge weight to
         measure the distance from the node n.
-    closeness_distance : str, optional
+    length : str, optional
       Use the specified edge attribute as the edge distance in shortest
       path calculations in closeness centrality algorithm
 
@@ -666,7 +701,7 @@ def local_closeness(
 
     Examples
     --------
-    >>> network_graph = mm.local_closeness(network_graph, radius=400, distance='edge_length')
+    >>> network_graph = mm.local_closeness_centrality(network_graph, radius=400, distance='edge_length')
 
     """
     netx = graph.copy()
@@ -676,15 +711,17 @@ def local_closeness(
             netx, n, radius=radius, undirected=True, distance=distance
         )  # define subgraph of steps=radius
         netx.nodes[n][name] = _closeness_centrality(
-            sub, n, distance=closeness_distance, len_graph=lengraph
+            sub, n, length=length, len_graph=lengraph
         )
 
     return netx
 
 
-def clustering(graph, name="cluster"):
+def global_closeness_centrality(graph, name="closeness", length="mm_len", **kwargs):
     """
-    Calculates the squares clustering coefficient for nodes.
+    Calculates the closeness centrality for nodes.
+
+    Wrapper around ``networkx.closeness_centrality``.
 
     .. math::
 
@@ -696,6 +733,10 @@ def clustering(graph, name="cluster"):
         Ideally genereated from GeoDataFrame using :py:func:`momepy.gdf_to_nx`
     name : str, optional
         calculated attribute name
+    length : str (default 'mm_len')
+        attribute holding length of edge
+    **kwargs
+        kwargs for ``networkx.closeness_centrality``
 
     Returns
     -------
@@ -704,11 +745,152 @@ def clustering(graph, name="cluster"):
 
     Examples
     --------
-    >>> network_graph = mm.clustering(network_graph)
+    >>> network_graph = mm.global_closeness_centrality(network_graph)
     """
     netx = graph.copy()
 
-    vals = nx.square_clustering(netx)
+    vals = nx.closeness_centrality(netx, distance=length, **kwargs)
+    nx.set_node_attributes(netx, vals, name)
+
+    return netx
+
+
+def betweenness_centrality(
+    graph, name="betweenness", mode="nodes", length="mm_len", **kwargs
+):
+    """
+    Calculates the shortest-path betweenness centrality for nodes.
+
+    .. math::
+
+
+    Parameters
+    ----------
+    graph : networkx.Graph
+        Graph representing street network.
+        Ideally genereated from GeoDataFrame using :py:func:`momepy.gdf_to_nx`
+    name : str, optional
+        calculated attribute name
+    mode : str, default 'nodes'
+        mode of betweenness calculation. 'node' for node-based, 'edges' for edge-based
+    length : str (default 'mm_len')
+        attribute holding length of edge
+    **kwargs
+        kwargs for ``networkx.betweenness_centrality`` or ``networkx.edge_betweenness_centrality``
+
+    Returns
+    -------
+    Graph
+        networkx.Graph
+
+    References
+    ----------
+    Porta S, Crucitti P and Latora V (2006) The network analysis of urban streets: A primal approach.
+    Environment and Planning B: Planning and Design 33(5): 705–725.
+
+    Examples
+    --------
+    >>> network_graph = mm.betweenness_centrality(network_graph)
+    """
+    netx = graph.copy()
+
+    # has to be Graph not MultiGraph as MG is not supported by networkx2.4
+    G = nx.Graph()
+    for u, v, k, data in netx.edges(data=True, keys=True):
+        if G.has_edge(u, v):
+            if G[u][v][length] > netx[u][v][k][length]:
+                nx.set_edge_attributes(G, {(u, v): data})
+        else:
+            G.add_edge(u, v, **data)
+
+    if mode == "nodes":
+        vals = nx.betweenness_centrality(G, **kwargs)
+        nx.set_node_attributes(netx, vals, name)
+    elif mode == "edges":
+        vals = nx.edge_betweenness_centrality(G, **kwargs)
+        for u, v, k in netx.edges(keys=True):
+            try:
+                val = vals[u, v]
+            except KeyError:
+                val = vals[v, u]
+            netx[u][v][k][name] = val
+    else:
+        raise ValueError(
+            "Mode {} is not supported. Use 'nodes' or 'edges'.".format(mode)
+        )
+
+    return netx
+
+
+def _euclidean(n, m):
+    """helper for straightness"""
+    return math.sqrt((n[0] - m[0]) ** 2 + (n[1] - m[1]) ** 2)
+
+
+def _straightness_centrality(G, distance, normalized=True):
+    """
+    Calculates straightness centrality.
+    """
+    straightness_centrality = {}
+
+    for n in tqdm(G.nodes(), total=G.number_of_nodes()):
+        straightness = 0
+        sp = nx.single_source_dijkstra_path_length(G, n, weight=distance)
+
+        if len(sp) > 0 and len(G) > 1:
+            for target in sp:
+                if n != target:
+                    network_dist = sp[target]
+                    euclidean_dist = _euclidean(n, target)
+                    straightness = straightness + (euclidean_dist / network_dist)
+            straightness_centrality[n] = straightness * (1.0 / (len(G) - 1.0))
+            # normalize to number of nodes-1 in connected part
+            if normalized:
+                s = (len(G) - 1.0) / (len(sp) - 1.0)
+                straightness_centrality[n] *= s
+        else:
+            straightness_centrality[n] = 0.0
+    return straightness_centrality
+
+
+def straightness_centrality(
+    graph, length="mm_len", normalized=True, name="straightness"
+):
+    """
+    Calculates the straightness centrality for nodes.
+
+    .. math::
+
+
+    Parameters
+    ----------
+    graph : networkx.Graph
+        Graph representing street network.
+        Ideally genereated from GeoDataFrame using :py:func:`momepy.gdf_to_nx`
+    length : str (default 'mm_len')
+        attribute holding length of edge
+    normalized : bool
+        normalize to number of nodes-1 in connected part
+    name : str, optional
+        calculated attribute name
+
+    Returns
+    -------
+    Graph
+        networkx.Graph
+
+    References
+    ----------
+    Porta S, Crucitti P and Latora V (2006) The network analysis of urban streets: A primal approach.
+    Environment and Planning B: Planning and Design 33(5): 705–725.
+
+    Examples
+    --------
+    >>> network_graph = mm.straightness_centrality(network_graph)
+    """
+    netx = graph.copy()
+
+    vals = _straightness_centrality(netx, distance=length, normalized=normalized)
     nx.set_node_attributes(netx, vals, name)
 
     return netx
@@ -729,7 +911,7 @@ def subgraph(
     edge_node_ratio=True,
     gamma=True,
     local_closeness=True,
-    closeness_distance=None,
+    closeness_length=None,
 ):
     """
     Calculates all subgraph-based characters.
@@ -772,7 +954,7 @@ def subgraph(
         Calculate gamma index (True/False)
     local_closeness : bool, default True
         Calculate local closeness centrality (True/False)
-    closeness_distance : str, optional
+    closeness_length : str, optional
       Use the specified edge attribute as the edge distance in shortest
       path calculations in closeness centrality algorithm
 
@@ -830,7 +1012,16 @@ def subgraph(
         if local_closeness:
             lengraph = len(netx)
             netx.nodes[n]["local_closeness"] = _closeness_centrality(
-                sub, n, distance=closeness_distance, len_graph=lengraph
+                sub, n, length=closeness_length, len_graph=lengraph
             )
 
     return netx
+
+
+def mean_nodes(G, attr):
+    """
+    Calculates mean value of nodes attr for each edge.
+    """
+    for u, v, k in tqdm(G.edges(keys=True), total=G.number_of_edges()):
+        mean = (G.nodes[u][attr] + G.nodes[v][attr]) / 2
+        G[u][v][k][attr] = mean


Test patch:
diff --git a/tests/test_graph.py b/tests/test_graph.py
index a90d83e..bb45e20 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -72,15 +72,60 @@ class TestGraph:
         assert net.nodes[(1603650.450422848, 6464368.600601688)]["gamma"] == check
 
     def test_local_closeness(self):
-        net = mm.local_closeness(self.network)
+        net = mm.local_closeness_centrality(self.network)
         check = 0.27557319223985893
         assert net.nodes[(1603650.450422848, 6464368.600601688)]["closeness"] == check
+        net2 = mm.local_closeness_centrality(self.network, length="mm_len")
+        check2 = 0.0015544070362478774
+        assert net2.nodes[(1603650.450422848, 6464368.600601688)]["closeness"] == check2
 
-    def test_local_closeness_distance(self):
-        net = mm.local_closeness(self.network, closeness_distance="mm_len")
-        check = 0.0015544070362478774
+    def test_global_closeness_centrality(self):
+        net = mm.global_closeness_centrality(self.network, length="mm_len")
+        check = 0.0016066095164175716
         assert net.nodes[(1603650.450422848, 6464368.600601688)]["closeness"] == check
 
+    def test_betweenness_centrality(self):
+        net = mm.betweenness_centrality(self.network)
+        net2 = mm.betweenness_centrality(self.network, mode="edges")
+        with pytest.raises(ValueError):
+            mm.betweenness_centrality(self.network, mode="nonexistent")
+        node = 0.15806878306878305
+        edge = 0.20320197044334976
+        assert net.nodes[(1603650.450422848, 6464368.600601688)]["betweenness"] == node
+        assert (
+            net2.edges[
+                (1603226.9576840235, 6464160.158361825),
+                (1603039.9632033885, 6464087.491175889),
+                8,
+            ]["betweenness"]
+            == edge
+        )
+
+    def test_straightness_centrality(self):
+        net = mm.straightness_centrality(self.network)
+        net2 = mm.straightness_centrality(
+            self.network, normalized=False, name="nonnorm"
+        )
+        check = 0.8574045143712158
+        nonnorm = 0.8574045143712158
+        assert (
+            net.nodes[(1603650.450422848, 6464368.600601688)]["straightness"] == check
+        )
+        assert net2.nodes[(1603650.450422848, 6464368.600601688)]["nonnorm"] == nonnorm
+
+    def test_mean_nodes(self):
+        net = mm.straightness_centrality(self.network)
+        mm.mean_nodes(net, "straightness")
+        edge = 0.8777302256084243
+        assert (
+            net.edges[
+                (1603226.9576840235, 6464160.158361825),
+                (1603039.9632033885, 6464087.491175889),
+                8,
+            ]["straightness"]
+            == edge
+        )
+
     def test_clustering(self):
         net = mm.clustering(self.network)
         check = 0.09090909090909091