Source code for graspologic.partition.modularity

# Copyright (c) Microsoft Corporation.
# Licensed under the MIT license.

import math
import networkx as nx
from collections import defaultdict
from typing import Any, Dict


def _modularity_component(
    intra_community_degree: float,
    total_community_degree: float,
    network_degree_sum: float,
    resolution: float,
) -> float:
    community_degree_ratio = math.pow(total_community_degree, 2.0) / (
        2.0 * network_degree_sum
    )
    return (intra_community_degree - resolution * community_degree_ratio) / (
        2.0 * network_degree_sum
    )


def _assertions(
    graph: nx.Graph,
    partitions: Dict[Any, int],
    weight_attribute: str,
    resolution: float,
):
    if not isinstance(graph, nx.Graph):
        raise TypeError("graph must be a networkx undirected graph")
    if graph.is_directed():
        raise ValueError("The graph must be an undirected graph")
    if graph.is_multigraph():
        raise ValueError(
            "Multigraphs must be provided in the form of a non multigraph."
        )
    if not nx.is_weighted(graph, weight=weight_attribute):
        raise ValueError(
            f"weight_attribute {weight_attribute} not found on every edge in the provided graph"
        )
    if not isinstance(partitions, dict):
        raise TypeError("partitions must be a dictionary")
    if not isinstance(resolution, float):
        raise TypeError("resolution must be a float")


[docs]def modularity( graph: nx.Graph, partitions: Dict[Any, int], weight_attribute: str = "weight", resolution: float = 1.0, ) -> float: """ Given an undirected graph and a dictionary of vertices to community ids, calculate the modularity. Parameters ---------- graph : nx.Graph An undirected graph partitions : Dict[Any, int] A dictionary representing a community partitioning scheme with the keys being the vertex and the value being a community id. weight_attribute : str The edge data attribute on the graph that contains a float weight for the edge. resolution : float The resolution to use when calculating the modularity. Returns ------- Dict[int, float] A dictionary of the community id to the modularity component of that community Raises ------ TypeError If ``graph`` is not a networkx Graph or If ``partitions`` is not a dictionary or If ``resolution`` is not a float ValueError If ``graph`` is unweighted If ``graph`` is directed If ``graph`` is a multigraph References ---------- .. [1] https://en.wikipedia.org/wiki/Modularity_(networks) """ _assertions(graph, partitions, weight_attribute, resolution) components = modularity_components(graph, partitions, weight_attribute, resolution) return sum(components.values())
[docs]def modularity_components( graph: nx.Graph, partitions: Dict[Any, int], weight_attribute: str = "weight", resolution: float = 1.0, ) -> Dict[int, float]: """ Given an undirected, weighted graph and a community partition dictionary, calculates a modularity quantum for each community ID. The sum of these quanta is the modularity of the graph and partitions provided. Parameters ---------- graph : nx.Graph An undirected graph partitions : Dict[Any, int] A dictionary representing a community partitioning scheme with the keys being the vertex and the value being a community id. weight_attribute : str The edge data attribute on the graph that contains a float weight for the edge. resolution : float The resolution to use when calculating the modularity. Returns ------- Dict[int, float] A dictionary of the community id to the modularity component of that community Raises ------ TypeError If ``graph`` is not a networkx Graph or If ``partitions`` is not a dictionary or If ``resolution`` is not a float ValueError If ``graph`` is unweighted If ``graph`` is directed If ``graph`` is a multigraph """ _assertions(graph, partitions, weight_attribute, resolution) total_edge_weight = 0.0 communities = set(partitions.values()) degree_sums_within_community: Dict[int, float] = defaultdict(lambda: 0.0) degree_sums_for_community: Dict[int, float] = defaultdict(lambda: 0.0) for vertex, neighbor_vertex, weight in graph.edges(data=weight_attribute): vertex_community = partitions[vertex] neighbor_community = partitions[neighbor_vertex] if vertex_community == neighbor_community: if vertex == neighbor_vertex: degree_sums_within_community[vertex_community] += weight else: degree_sums_within_community[vertex_community] += weight * 2.0 degree_sums_for_community[vertex_community] += weight degree_sums_for_community[neighbor_community] += weight total_edge_weight += weight return { comm: _modularity_component( degree_sums_within_community[comm], degree_sums_for_community[comm], total_edge_weight, resolution, ) for comm in communities }