#!/usr/bin/env python # connectivity.py # definitions of connectivity characters import collections import math from typing import Any import networkx as nx import numpy as np from pandas import Series from tqdm.auto import tqdm __all__ = [ "node_degree", "meshedness", "mean_node_dist", "cds_length", "mean_node_degree", "proportion", "cyclomatic", "edge_node_ratio", "gamma", "clustering", "closeness_centrality", "betweenness_centrality", "straightness_centrality", "subgraph", "mean_nodes", "node_density", ] def node_degree(graph: nx.Graph, name: str = "degree") -> nx.Graph: """ Calculates node degree for each node. Wrapper around ``networkx.degree()``. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. name : str (default 'degree') The calculated attribute name. Returns ------- netx : Graph A networkx.Graph object . Examples -------- >>> network_graph = mm.node_degree(network_graph) """ netx = graph.copy() degree = dict(nx.degree(netx)) nx.set_node_attributes(netx, degree, name) return netx def _meshedness(graph: nx.Graph) -> float: """Calculates meshedness of a graph.""" e = graph.number_of_edges() v = graph.number_of_nodes() return (e - v + 1) / (2 * v - 5) def meshedness( graph: nx.Graph, radius: int = 5, name: str = "meshedness", distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates meshedness for subgraph around each node if radius is set, or for whole graph, if ``radius=None``. A subgraph is generated around each node within set radius. If ``distance=None``, radius will define topological distance, otherwise it uses values in distance attribute. .. math:: \\alpha=\\frac{e-v+1}{2 v-5} where :math:`e` is the number of edges in a subgraph and :math:`v` is the number of nodes in a subgraph. Adapted from :cite:`feliciotti2018`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int, optional Include all neighbors of distance <= radius from ``n``. name : str, optional The calculated attribute name. distance : str, optional 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``. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object if ``radius`` is set. float The meshedness for the graph if ``radius=None``. Examples -------- >>> network_graph = mm.meshedness(network_graph, radius=800, distance='edge_length') """ netx = graph.copy() if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _meshedness( sub ) # save value calulated for subgraph to node return netx return _meshedness(netx) def mean_node_dist( graph: nx.Graph, name: str = "meanlen", length: str = "mm_len", verbose: bool = True ) -> nx.Graph: """ Calculates mean distance to neighbouring nodes. Mean of values in ``length`` attribute. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. name : str, optional The calculated attribute name. length : str, optional The name of the attribute of segment length (geographical). verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object. Examples -------- >>> network_graph = mm.mean_node_dist(network_graph) """ netx = graph.copy() for n, nbrs in tqdm(netx.adj.items(), total=len(netx), disable=not verbose): lengths = [] for _nbr, keydict in nbrs.items(): for _key, eattr in keydict.items(): lengths.append(eattr[length]) netx.nodes[n][name] = np.mean(lengths) return netx def _cds_length(graph: nx.Graph, mode, length): """Calculates cul-de-sac length in a graph.""" lens = [] for u, v, k, cds in graph.edges.data("cdsbool", keys=True): if cds: lens.append(graph[u][v][k][length]) if mode == "sum": return sum(lens) if mode == "mean": return np.mean(lens) raise ValueError(f"Mode '{mode}' is not supported. Use 'sum' or 'mean'.") def cds_length( graph: nx.Graph, radius: int = 5, mode: str = "sum", name: str = "cds_len", degree: str = "degree", length: str = "mm_len", distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates length of cul-de-sacs for subgraph around each node if radius is set, or for whole graph, if ``radius=None``. A subgraph is generated around each node within set radius. If ``distance=None``, radius will define topological distance, otherwise it uses values in distance attribute. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius : int Include all neighbors of distance <= radius from ``n``. mode : str (default 'sum') If ``'sum'``, calculate total length, if ``'mean'`` calculate mean length. name : str, optional The calculated attribute name. degree : str The name of attribute of node degree (:py:func:`momepy.node_degree`). length : str, optional The name of the attribute of segment length (geographical). distance : str, optional 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``. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object if ``radius`` is set. float The length of cul-de-sacs for the graph if ``radius=None``. Examples -------- >>> network_graph = mm.cds_length(network_graph, radius=9, mode='mean') """ # node degree needed beforehand netx = graph.copy() for u, v, k in netx.edges(keys=True): if netx.nodes[u][degree] == 1 or netx.nodes[v][degree] == 1: netx[u][v][k]["cdsbool"] = True else: netx[u][v][k]["cdsbool"] = False if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _cds_length( sub, mode=mode, length=length ) # save value calculated for subgraph to node return netx return _cds_length(netx, mode=mode, length=length) def _mean_node_degree(graph: nx.Graph, degree): """Calculates mean node degree in a graph.""" return np.mean(list(dict(graph.nodes(degree)).values())) def mean_node_degree( graph: nx.Graph, radius: int = 5, name: str = "mean_nd", degree: str = "degree", distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates mean node degree for subgraph around each node if radius is set, or for whole graph, if ``radius=None``. A subgraph is generated around each node within set radius. If ``distance=None``, radius will define topological distance, otherwise it uses values in ``distance`` attribute. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int Include all neighbors of distance <= radius from ``n``. name : str, optional The calculated attribute name. degree : str The name of attribute of node degree (:py:func:`momepy.node_degree`). distance : str, optional 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``. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object if ``radius`` is set. float The mean node degree for the graph if ``radius=None``. Examples -------- >>> network_graph = mm.mean_node_degree(network_graph, radius=3) """ netx = graph.copy() if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _mean_node_degree(sub, degree=degree) return netx return _mean_node_degree(netx, degree=degree) def _proportion(graph: nx.Graph, degree): """Calculates the proportion of intersection types in a graph.""" counts = collections.Counter(dict(graph.nodes(degree)).values()) return counts def proportion( graph: nx.Graph, radius: int = 5, three: str | None = None, four: str | None = None, dead: str | None = None, degree: str = "degree", distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates the proportion of intersection types for subgraph around each node if radius is set, or for whole graph, if ``radius=None``. A subgraph is generated around each node within set radius. If ``distance=None``, the radius will define topological distance, otherwise it uses values in ``distance`` attribute. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int Include all neighbors of distance <= radius from ``n``. three : str, optional The attribute name for 3-way intersections proportion. four : str, optional The attribute name for 4-way intersections proportion. dead : str, optional The attribute name for deadends proportion. degree : str The name of attribute of node degree (:py:func:`momepy.node_degree`). distance : str, optional 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``. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object if ``radius`` is set. result : dict A dict with proportions for the graph if ``radius=None``. Examples -------- >>> network_graph = mm.proportion( ... network_graph, three='threeway', four='fourway', dead='deadends' ... ) # noqa """ if not three and not four and not dead: raise ValueError( "Nothing to calculate. Define names for at least " "one proportion to be calculated." ) netx = graph.copy() if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius counts = _proportion(sub, degree=degree) if three: netx.nodes[n][three] = counts[3] / len(sub) if four: netx.nodes[n][four] = counts[4] / len(sub) if dead: netx.nodes[n][dead] = counts[1] / len(sub) return netx # add example to docs explaining keys counts = _proportion(netx, degree=degree) result = {} if three: result[three] = counts[3] / len(netx) if four: result[four] = counts[4] / len(netx) if dead: result[dead] = counts[1] / len(netx) return result def _cyclomatic(graph: nx.Graph) -> int: """Calculates the cyclomatic complexity of a graph.""" e = graph.number_of_edges() v = graph.number_of_nodes() return e - v + 1 def cyclomatic( graph: nx.Graph, radius: int = 5, name: str = "cyclomatic", distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates cyclomatic complexity for subgraph around each node if radius is set, or for whole graph, if ``radius=None``. A subgraph is generated around each node within set radius. If ``distance=None``, radius will define topological distance, otherwise it uses values in ``distance`` attribute. .. math:: \\alpha=e-v+1 where :math:`e` is the number of edges in subgraph and :math:`v` is the number of nodes in subgraph. Adapted from :cite:`bourdic2012`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int Include all neighbors of distance <= radius from ``n``. name : str, optional The calculated attribute name. distance : str, optional 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``. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object if ``radius`` is set. float The cyclomatic complexity for the graph if ``radius=None``. Examples -------- >>> network_graph = mm.cyclomatic(network_graph, radius=3) """ netx = graph.copy() if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _cyclomatic( sub ) # save value calulated for subgraph to node return netx return _cyclomatic(netx) def _edge_node_ratio(graph: nx.Graph) -> float: """Calculates edge / node ratio of a graph.""" e = graph.number_of_edges() v = graph.number_of_nodes() return e / v def edge_node_ratio( graph: nx.Graph, radius: int = 5, name: str = "edge_node_ratio", distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates edge / node ratio for subgraph around each node if radius is set, or for whole graph, if ``radius=None``. A subgraph is generated around each node within set radius. If ``distance=None``, radius will define topological distance, otherwise it uses values in ``distance`` attribute. .. math:: \\alpha=e/v where :math:`e` is the number of edges in subgraph and :math:`v` is the number of nodes in subgraph. Adapted from :cite:`dibble2017`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int Include all neighbors of distance <= radius from ``n``. name : str, optional The calculated attribute name. distance : str, optional 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``. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object if ``radius`` is set. float The edge / node ratio for the graph if ``radius=None``. Examples -------- >>> network_graph = mm.edge_node_ratio(network_graph, radius=3) """ netx = graph.copy() if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _edge_node_ratio( sub ) # save value calulated for subgraph to node return netx return _edge_node_ratio(netx) def _gamma(graph: nx.Graph): """Calculates gamma index of a graph.""" e = graph.number_of_edges() v = graph.number_of_nodes() if v == 2: return np.nan return e / (3 * (v - 2)) # save value calulated for subgraph to node def gamma( graph: nx.Graph, radius: int = 5, name: str = "gamma", distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates connectivity gamma index for subgraph around each node if radius is set, or for whole graph, if ``radius=None``. A subgraph is generated around each node within set radius. If ``distance=None``, radius will define topological distance, otherwise it uses values in ``distance`` attribute. .. math:: \\alpha=\\frac{e}{3(v-2)} where :math:`e` is the number of edges in subgraph and :math:`v` is the number of nodes in subgraph. Adapted from :cite:`dibble2017`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int Include all neighbors of distance <= radius from ``n``. name : str, optional The calculated attribute name. distance : str, optional 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``. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object if ``radius`` is set. float The gamma index for the graph if ``radius=None``. Examples -------- >>> network_graph = mm.gamma(network_graph, radius=3) """ netx = graph.copy() if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _gamma(sub) return netx return _gamma(netx) def clustering(graph: nx.Graph, name: str = "cluster") -> nx.Graph: """ Calculates the squares clustering coefficient for nodes. Wrapper around ``networkx.square_clustering``. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. name : str, optional The calculated attribute name. Returns ------- netx : Graph A networkx.Graph object. 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(graph: nx.Graph, u=None, length=None, 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. The closeness centrality [1]_ of a node `u` is the reciprocal of the average shortest path distance to `u` over all `n-1` reachable nodes. .. math:: C(u) = \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}, where `d(v, u)` is the shortest-path distance between `v` and `u`, and `n` is the number of nodes that can reach `u`. Notice that the closeness distance function computes the incoming distance to `u` for directed graphs. To use outward distance, act on `graph.reverse()`. Notice that higher values of closeness indicate higher centrality. Wasserman and Faust propose an improved formula for graphs with more than one connected component. The result is "a ratio of the fraction of actors in the group who are reachable, to the average distance" from the reachable actors [2]_. You might think this scale factor is inverted but it is not. As is, nodes from small components receive a smaller closeness value. Letting `N` denote the number of nodes in the graph, .. math:: C_{WF}(u) = \frac{n-1}{N-1} \frac{n - 1}{\sum_{v=1}^{n-1} d(v, u)}, Parameters ---------- G : graph A NetworkX graph. u : node, optional Return only the value for node ``u``. distance : edge attribute key, optional (default=None) Use the specified edge attribute as the edge distance in shortest path calculations. len_graph : int The length of the complete graph. Returns ------- nodes : dict Dictionary of nodes with closeness centrality as the value. References ---------- .. [1] Linton C. Freeman: Centrality in networks: I. Conceptual clarification. Social Networks 1:215-239, 1979. http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf .. [2] pg. 201 of Wasserman, S. and Faust, K., Social Network Analysis: Methods and Applications, 1994, Cambridge University Press. """ 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=length ) else: path_length = nx.single_source_shortest_path_length nodes = [u] closeness_centrality_ = dict.fromkeys(nodes, 0.0) for n in nodes: sp = dict(path_length(graph, n)) totsp = sum(sp.values()) if totsp > 0 and len(graph) > 1: closeness_centrality_[n] = (len(sp) - 1) / totsp # normalize to number of nodes-1 in connected part s = (len(sp) - 1) / (len_graph - 1) closeness_centrality_[n] *= s return closeness_centrality_[u] def closeness_centrality( graph: nx.Graph, name: str = "closeness", weight: str = "mm_len", radius: int | None = None, distance: Any | None = None, verbose: bool = True, **kwargs, ) -> nx.Graph: """ Calculates the closeness centrality for nodes. Wrapper around ``networkx.closeness_centrality``. Closeness centrality of a node `u` is the reciprocal of the average shortest path distance to `u` over all `n-1` nodes within reachable nodes. .. math:: C(u) = \\frac{n - 1}{\\sum_{v=1}^{n-1} d(v, u)}, where :math:`d(v, u)` is the shortest-path distance between :math:`v` and :math:`u`, and :math:`n` is the number of nodes that can reach :math:`u`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. name : str, optional The calculated attribute name. weight : str (default 'mm_len') The attribute holding the weight of edge (e.g. length, angle). radius: int Include all neighbors of distance <= radius from ``n``. distance : str, optional 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`` during ``ego_graph`` generation. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. **kwargs : dict Keyword arguments for ``networkx.closeness_centrality``. Returns ------- netx : Graph A networkx.Graph object. Examples -------- >>> network_graph = mm.closeness_centrality(network_graph) """ netx = graph.copy() if radius: lengraph = len(netx) for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _closeness_centrality( sub, n, length=weight, len_graph=lengraph ) else: vals = nx.closeness_centrality(netx, distance=weight, **kwargs) nx.set_node_attributes(netx, vals, name) return netx def betweenness_centrality( graph: nx.Graph, name: str = "betweenness", mode: str = "nodes", weight: str = "mm_len", endpoints: bool = True, radius: int | None = None, distance: Any | None = None, normalized: bool = False, verbose: bool = True, **kwargs, ) -> nx.Graph: """ Calculates the shortest-path betweenness centrality for nodes. Wrapper around ``networkx.betweenness_centrality`` or ``networkx.edge_betweenness_centrality``. Betweenness centrality of a node `v` is the sum of the fraction of all-pairs shortest paths that pass through `v` .. math:: c_B(v) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|v)}{\\sigma(s, t)} where `V` is the set of nodes, :math:`\\sigma(s, t)` is the number of shortest :math:`(s, t)`-paths, and :math:`\\sigma(s, t|v)` is the number of those paths passing through some node `v` other than `s, t`. If `s = t`, :math:`\\sigma(s, t) = 1`, and if `v` in `{s, t}``, :math:`\\sigma(s, t|v) = 0`. Betweenness centrality of an edge `e` is the sum of the fraction of all-pairs shortest paths that pass through `e` .. math:: c_B(e) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|e)}{\\sigma(s, t)} where `V` is the set of nodes, :math:`\\sigma(s, t)` is the number of shortest :math:`(s, t)`-paths, and :math:`\\sigma(s, t|e)` is the number of those paths passing through edge `e`. Adapted from :cite:`porta2006`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. name : str, optional The calculated attribute name. mode : str, default 'nodes' The mode of betweenness calculation. ``'node'`` for node-based or ``'edges'`` for edge-based. weight : str (default 'mm_len') The attribute holding the weight of edge (e.g. length, angle). radius: int Include all neighbors of distance <= radius from ``n``. distance : str, optional 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`` during ``ego_graph`` generation. normalized : bool, optional If ``True`` the betweenness values are normalized by `2/((n-1)(n-2))`, where ``n`` is the number of nodes in a subgraph. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. **kwargs : dict Keyword argument for ``networkx.betweenness_centrality`` or ``networkx.edge_betweenness_centrality``. Returns ------- netx : Graph A networkx.Graph object. Examples -------- >>> network_graph = mm.betweenness_centrality(network_graph) Notes ----- In case of angular betweenness, implementation is based on "Tasos Implementation". """ netx = graph.copy() # has to be Graph not MultiGraph as MG is not supported by networkx2.4 graph = nx.Graph() for u, v, k, data in netx.edges(data=True, keys=True): if graph.has_edge(u, v): if graph[u][v][weight] > netx[u][v][k][weight]: nx.set_edge_attributes(graph, {(u, v): data}) else: graph.add_edge(u, v, **data) if radius: for n in tqdm(graph, total=len(graph), disable=not verbose): sub = nx.ego_graph( graph, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = nx.betweenness_centrality( sub, weight=weight, normalized=normalized, **kwargs )[n] elif mode == "nodes": vals = nx.betweenness_centrality( graph, weight=weight, endpoints=endpoints, **kwargs ) nx.set_node_attributes(netx, vals, name) elif mode == "edges": vals = nx.edge_betweenness_centrality(graph, weight=weight, **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(f"Mode '{mode}' is not supported. Use 'nodes' or 'edges'.") 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(graph: nx.Graph, weight, normalized=True): """Calculates straightness centrality.""" straightness_centrality_ = dict.fromkeys(graph.nodes(), 0.0) for n in graph.nodes(): sp = nx.single_source_dijkstra_path_length(graph, n, weight=weight) if len(sp) > 0 and len(graph) > 1: straightness = 0 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 / (len(graph) - 1)) # normalize to number of nodes-1 in connected part if normalized and len(sp) > 1: s = (len(graph) - 1) / (len(sp) - 1) straightness_centrality_[n] *= s return straightness_centrality_ def straightness_centrality( graph: nx.Graph, weight: str = "mm_len", normalized: bool = True, name: str = "straightness", radius: int | None = None, distance: Any | None = None, verbose: bool = True, ) -> nx.Graph: """ Calculates the straightness centrality for nodes. .. math:: C_{S}(i)=\\frac{1}{n-1} \\sum_{j \\in V, j \\neq i} \\frac{d_{i j}^{E u}} {d_{i j}} where :math:`\\mathrm{d}^{\\mathrm{E} \\mathrm{u}}_{\\mathrm{ij}}` is the Euclidean distance between nodes `i` and `j` along a straight line. Adapted from :cite:`porta2006`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. weight : str (default 'mm_len') The attribute holding length of edge. normalized : bool Normalize to the number of ``nodes-1`` in the connected part (for local straightness it is recommended to set to ``normalized=False``). name : str, optional The calculated attribute name. radius: int Include all neighbors of distance <= radius from ``n``. distance : str, optional 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`` during ``ego_graph`` generation. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object. Examples -------- >>> network_graph = mm.straightness_centrality(network_graph) """ netx = graph.copy() if radius: for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius netx.nodes[n][name] = _straightness_centrality( sub, weight=weight, normalized=normalized )[n] else: vals = _straightness_centrality(netx, weight=weight, normalized=normalized) nx.set_node_attributes(netx, vals, name) return netx def node_density( graph: nx.Graph, radius: int, length: str = "mm_len", distance: str | None = None, verbose: bool = True, ) -> nx.Graph: """Calculate the density of a node's neighbours (for all nodes) on the street network defined in ``graph``. Calculated as the number of neighbouring nodes / cumulative length of street network within neighbours. Returns two values - an unweighted and weighted density unweighted is calculated based on the number of neigbhouring nodes, whereas weighted density will take into account node degree as ``k-1``. Adapted from :cite:`dibble2017`. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int Include all neighbors of distance <= radius from ``n``. length : str, default `mm_len` The name of the attribute of segment length (geographical). distance : str, optional 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`` during ``ego_graph`` generation. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object. Examples -------- >>> network_graph = mm.node_density(network_graph, radius: int=5) """ netx = graph.copy() orig_nodes_degree = Series(nx.get_node_attributes(netx, "degree")) for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius unweighted, weighted = _node_density( sub, length=length, orig_nodes_degree=orig_nodes_degree ) netx.nodes[n]["node_density"] = unweighted netx.nodes[n]["node_density_weighted"] = weighted return netx def _node_density(sub, length, orig_nodes_degree): """Calculates node density for a subgraph.""" length_sum = sub.size(length) weighted_node_data = orig_nodes_degree[list(sub.nodes)] - 1 unweighted_node_data = Series(1, index=weighted_node_data) unweighted = (unweighted_node_data.sum() / length_sum) if length_sum else 0 weighted = (weighted_node_data.sum() / length_sum) if length_sum else 0 return unweighted, weighted def subgraph( graph: nx.Graph, radius: int = 5, distance: Any | None = None, meshedness: bool = True, cds_length: bool = True, mode: str = "sum", degree: str = "degree", length: str = "mm_len", mean_node_degree: bool = True, proportion: dict = {3: True, 4: True, 0: True}, cyclomatic: bool = True, edge_node_ratio: bool = True, gamma: bool = True, local_closeness: bool = True, closeness_weight: Any | None = None, node_density: bool = True, verbose: bool = True, ) -> nx.Graph: """ Calculates all subgraph-based characters. Generating subgraph might be a time consuming activity. If we want to use the same subgraph for more characters, ``subgraph`` allows this by generating subgraph and then analysing it using selected options. Parameters ---------- graph : networkx.Graph A Graph representing a street network. Ideally generated from GeoDataFrame using :func:`momepy.gdf_to_nx`. radius: int Include all neighbors of distance <= radius from ``n``. distance : str, optional 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``. meshedness : bool, default True Calculate meshedness (``True or ``False``). cds_length : bool, default True Calculate cul-de-sac length (``True or ``False``). mode : str (defualt 'sum') If ``'sum'``, calculate total ``cds_length``, if ``'mean'`` calculate mean ``cds_length``. degree : str The name of attribute of node degree (:py:func:`momepy.node_degree`). length : str, default `mm_len` The name of the attribute of segment length (geographical). mean_node_degree : bool, default True Calculate mean node degree (``True or ``False``). proportion : dict, default {3: True, 4: True, 0: True} Calculate proportion ``{3: True/False, 4: True/False, 0: True/False}``. cyclomatic : bool, default True Calculate cyclomatic complexity (``True or ``False``). edge_node_ratio : bool, default True Calculate edge node ratio (``True or ``False``). gamma : bool, default True Calculate gamma index (``True or ``False``). local_closeness : bool, default True Calculate local closeness centrality (``True or ``False``). closeness_weight : str, optional Use the specified edge attribute as the edge distance in shortest path calculations in closeness centrality algorithm. verbose : bool (default True) If ``True``, shows progress bars in loops and indication of steps. Returns ------- netx : Graph A networkx.Graph object. Examples -------- >>> network_graph = mm.subgraph(network_graph) """ netx = graph.copy() if node_density: orig_nodes_degree = Series(nx.get_node_attributes(netx, "degree")) for n in tqdm(netx, total=len(netx), disable=not verbose): sub = nx.ego_graph( netx, n, radius=radius, distance=distance ) # define subgraph of steps=radius if meshedness: netx.nodes[n]["meshedness"] = _meshedness(sub) if cds_length: for u, v, k in netx.edges(keys=True): if netx.nodes[u][degree] == 1 or netx.nodes[v][degree] == 1: netx[u][v][k]["cdsbool"] = True else: netx[u][v][k]["cdsbool"] = False netx.nodes[n]["cds_length"] = _cds_length(sub, mode=mode, length=length) if mean_node_degree: netx.nodes[n]["mean_node_degree"] = _mean_node_degree(sub, degree=degree) if proportion: counts = _proportion(sub, degree=degree) if proportion[3]: netx.nodes[n]["proportion_3"] = counts[3] / len(sub) if proportion[4]: netx.nodes[n]["proportion_4"] = counts[4] / len(sub) if proportion[0]: netx.nodes[n]["proportion_0"] = counts[1] / len(sub) if cyclomatic: netx.nodes[n]["cyclomatic"] = _cyclomatic(sub) if edge_node_ratio: netx.nodes[n]["edge_node_ratio"] = _edge_node_ratio(sub) if gamma: netx.nodes[n]["gamma"] = _gamma(sub) if local_closeness: lengraph = len(netx) netx.nodes[n]["local_closeness"] = _closeness_centrality( sub, n, length=closeness_weight, len_graph=lengraph ) if node_density: unweighted, weighted = _node_density( sub, length=length, orig_nodes_degree=orig_nodes_degree ) netx.nodes[n]["node_density"] = unweighted netx.nodes[n]["node_density_weighted"] = weighted return netx def mean_nodes(graph: nx.Graph, attr: Any): """Calculates mean value of nodes attr for each edge.""" for u, v, k in graph.edges(keys=True): mean = (graph.nodes[u][attr] + graph.nodes[v][attr]) / 2 graph[u][v][k][attr] = mean