boundary_expansion#
- boundary_expansion(G, S)[source]#
Returns the boundary expansion of the set
S
.The boundary expansion of a set
S
is the ratio between the size of its node boundary and the cardinality of the set itself [1] .- Parameters:
- GNetworkX graph
The input graph.
- Scollection
A collection of nodes in
G
.
- Returns:
- number
The boundary expansion ratio: size of node boundary / size of
S
.
Notes
The node boundary is defined as all nodes not in
S
that are adjacent to nodes inS
.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>
Examples
The node boundary is {2, 3} (size 2), divided by
|S|=2
:>>> G = nx.cycle_graph(4) >>> S = {0, 1} >>> nx.boundary_expansion(G, S) 1.0
For disconnected sets, e.g. here where the node boundary is
{1, 3, 5}
:>>> G = nx.cycle_graph(6) >>> S = {0, 2, 4} >>> nx.boundary_expansion(G, S) 1.0 ----
Additional backends implement this function
graphblas : OpenMP-enabled sparse linear algebra backend.