Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.algorithms.cuts

# -*- coding: utf-8 -*-
# cuts.py - functions for computing and evaluating cuts
#
# Copyright 2011 Ben Edwards <bedwards@cs.unm.edu>.
# Copyright 2011 Aric Hagberg <hagberg@lanl.gov>.
# Copyright 2015 NetworkX developers.
#
# This file is part of NetworkX.
#
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
# information.
"""Functions for finding and evaluating cuts in a graph.

"""
from __future__ import division

from itertools import chain

import networkx as nx

__all__ = ['boundary_expansion', 'conductance', 'cut_size', 'edge_expansion',
           'mixing_expansion', 'node_expansion', 'normalized_cut_size',
           'volume']


# TODO STILL NEED TO UPDATE ALL THE DOCUMENTATION!

[docs]def cut_size(G, S, T=None, weight=None): """Returns the size of the cut between two sets of nodes. A *cut* is a partition of the nodes of a graph into two sets. The *cut size* is the sum of the weights of the edges "between" the two sets of nodes. Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. T : sequence A sequence of nodes in `G`. If not specified, this is taken to be the set complement of `S`. weight : object Edge attribute key to use as weight. If not specified, edges have weight one. Returns ------- number Total weight of all edges from nodes in set `S` to nodes in set `T` (and, in the case of directed graphs, all edges from nodes in `T` to nodes in `S`). Examples -------- In the graph with two cliques joined by a single edges, the natural bipartition of the graph into two blocks, one for each clique, yields a cut of weight one:: >>> G = nx.barbell_graph(3, 0) >>> S = {0, 1, 2} >>> T = {3, 4, 5} >>> nx.cut_size(G, S, T) 1 Each parallel edge in a multigraph is counted when determining the cut size:: >>> G = nx.MultiGraph(['ab', 'ab']) >>> S = {'a'} >>> T = {'b'} >>> nx.cut_size(G, S, T) 2 Notes ----- In a multigraph, the cut size is the total weight of edges including multiplicity. """ edges = nx.edge_boundary(G, S, T, data=weight, default=1) if G.is_directed(): edges = chain(edges, nx.edge_boundary(G, T, S, data=weight, default=1)) return sum(weight for u, v, weight in edges)
[docs]def volume(G, S, weight=None): """Returns the volume of a set of nodes. The *volume* of a set *S* is the sum of the (out-)degrees of nodes in *S* (taking into account parallel edges in multigraphs). [1] Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. weight : object Edge attribute key to use as weight. If not specified, edges have weight one. Returns ------- number The volume of the set of nodes represented by `S` in the graph `G`. See also -------- conductance cut_size edge_expansion edge_boundary normalized_cut_size References ---------- .. [1] David Gleich. *Hierarchical Directed Spectral Graph Partitioning*. <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf> """ degree = G.out_degree if G.is_directed() else G.degree return sum(d for v, d in degree(S, weight=weight))
[docs]def normalized_cut_size(G, S, T=None, weight=None): """Returns the normalized size of the cut between two sets of nodes. The *normalized cut size* is the cut size times the sum of the reciprocal sizes of the volumes of the two sets. [1] Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. T : sequence A sequence of nodes in `G`. weight : object Edge attribute key to use as weight. If not specified, edges have weight one. Returns ------- number The normalized cut size between the two sets `S` and `T`. Notes ----- In a multigraph, the cut size is the total weight of edges including multiplicity. See also -------- conductance cut_size edge_expansion volume References ---------- .. [1] David Gleich. *Hierarchical Directed Spectral Graph Partitioning*. <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf> """ if T is None: T = set(G) - set(S) num_cut_edges = cut_size(G, S, T=T, weight=weight) volume_S = volume(G, S, weight=weight) volume_T = volume(G, T, weight=weight) return num_cut_edges * ((1 / volume_S) + (1 / volume_T))
[docs]def conductance(G, S, T=None, weight=None): """Returns the conductance of two sets of nodes. The *conductance* is the quotient of the cut size and the smaller of the volumes of the two sets. [1] Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. T : sequence A sequence of nodes in `G`. weight : object Edge attribute key to use as weight. If not specified, edges have weight one. Returns ------- number The conductance between the two sets `S` and `T`. See also -------- cut_size edge_expansion normalized_cut_size volume References ---------- .. [1] David Gleich. *Hierarchical Directed Spectral Graph Partitioning*. <https://www.cs.purdue.edu/homes/dgleich/publications/Gleich%202005%20-%20hierarchical%20directed%20spectral.pdf> """ if T is None: T = set(G) - set(S) num_cut_edges = cut_size(G, S, T, weight=weight) volume_S = volume(G, S, weight=weight) volume_T = volume(G, T, weight=weight) return num_cut_edges / min(volume_S, volume_T)
[docs]def edge_expansion(G, S, T=None, weight=None): """Returns the edge expansion between two node sets. The *edge expansion* is the quotient of the cut size and the smaller of the cardinalities of the two sets. [1] Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. T : sequence A sequence of nodes in `G`. weight : object Edge attribute key to use as weight. If not specified, edges have weight one. Returns ------- number The edge expansion between the two sets `S` and `T`. See also -------- boundary_expansion mixing_expansion node_expansion References ---------- .. [1] Fan Chung. *Spectral Graph Theory*. (CBMS Regional Conference Series in Mathematics, No. 92), American Mathematical Society, 1997, ISBN 0-8218-0315-8 <http://www.math.ucsd.edu/~fan/research/revised.html> """ if T is None: T = set(G) - set(S) num_cut_edges = cut_size(G, S, T=T, weight=weight) return num_cut_edges / min(len(S), len(T))
[docs]def mixing_expansion(G, S, T=None, weight=None): """Returns the mixing expansion between two node sets. The *mixing expansion* is the quotient of the cut size and twice the number of edges in the graph. [1] Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. T : sequence A sequence of nodes in `G`. weight : object Edge attribute key to use as weight. If not specified, edges have weight one. Returns ------- number The mixing expansion between the two sets `S` and `T`. See also -------- boundary_expansion edge_expansion node_expansion References ---------- .. [1] Vadhan, Salil P. "Pseudorandomness." *Foundations and Trends in Theoretical Computer Science* 7.1–3 (2011): 1–336. <https://doi.org/10.1561/0400000010> """ num_cut_edges = cut_size(G, S, T=T, weight=weight) num_total_edges = G.number_of_edges() return num_cut_edges / (2 * num_total_edges)
# TODO What is the generalization to two arguments, S and T? Does the # denominator become `min(len(S), len(T))`?
[docs]def node_expansion(G, S): """Returns the node expansion of the set `S`. The *node expansion* is the quotient of the size of the node boundary of *S* and the cardinality of *S*. [1] Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. Returns ------- number The node expansion of the set `S`. See also -------- boundary_expansion edge_expansion mixing_expansion References ---------- .. [1] Vadhan, Salil P. "Pseudorandomness." *Foundations and Trends in Theoretical Computer Science* 7.1–3 (2011): 1–336. <https://doi.org/10.1561/0400000010> """ neighborhood = set(chain.from_iterable(G.neighbors(v) for v in S)) return len(neighborhood) / len(S)
# TODO What is the generalization to two arguments, S and T? Does the # denominator become `min(len(S), len(T))`?
[docs]def boundary_expansion(G, S): """Returns the boundary expansion of the set `S`. The *boundary expansion* is the quotient of the size of the edge boundary and the cardinality of *S*. [1] Parameters ---------- G : NetworkX graph S : sequence A sequence of nodes in `G`. Returns ------- number The boundary expansion of the set `S`. See also -------- edge_expansion mixing_expansion node_expansion References ---------- .. [1] Vadhan, Salil P. "Pseudorandomness." *Foundations and Trends in Theoretical Computer Science* 7.1–3 (2011): 1–336. <https://doi.org/10.1561/0400000010> """ return len(nx.node_boundary(G, S)) / len(S)