topobench.transforms.liftings.graph2hypergraph.expander_graph_lifting module#
This module implements the ExpanderGraphLifting class.
- class ExpanderGraphLifting(node_degree, **kwargs)#
Bases:
Graph2HypergraphLiftingLift graphs to expander (hyper)graph. More precisely, the expander is a random Ramanujan graph.
- Parameters:
- node_degreeint
The desired node degree of the expander graph. Must be even.
- **kwargsoptional
Additional arguments for the class.
- __init__(node_degree, **kwargs)#
- lift_topology(data)#
Lift the topology of a graph to an expander hypergraph.
- Parameters:
- datatorch_geometric.data.Data
The input data to be lifted.
- Returns:
- dict
The lifted topology.
- class Graph2HypergraphLifting(**kwargs)#
Bases:
GraphLiftingAbstract class for lifting graphs to hypergraphs.
- Parameters:
- **kwargsoptional
Additional arguments for the class.
- __init__(**kwargs)#
- maybe_regular_expander(n, d, *, create_using=None, max_tries=100, seed=None)#
Utility for creating a random regular expander.
Returns a random $d$-regular graph on $n$ nodes which is an expander graph with very good probability.
- Parameters:
- nint
The number of nodes.
- dint
The degree of each node.
- create_usingGraph Instance or Constructor
Indicator of type of graph to return. If a Graph-type instance, then clear and use it. If a constructor, call it to create an empty graph. Use the Graph constructor by default.
- max_triesint. (default: 100)
The number of allowed loops when generating each independent cycle
- seed(default: None)
Seed used to set random number generation state. See :ref`Randomness<randomness>`.
- Returns:
- Ggraph
The constructed undirected graph.
- Raises:
- NetworkXError
If $d % 2 != 0$ as the degree must be even. If $n - 1$ is less than $ 2d $ as the graph is complete at most. If max_tries is reached
See also
is_regular_expanderrandom_regular_expander_graph
Notes
The nodes are numbered from $0$ to $n - 1$.
The graph is generated by taking $d / 2$ random independent cycles.
Joel Friedman proved that in this model the resulting graph is an expander with probability $1 - O(n^{-tau})$ where $tau = lceil (sqrt{d - 1}) / 2 rceil - 1$. [1]
References
[1]Joel Friedman, A Proof of Alon’s Second Eigenvalue Conjecture and Related Problems, 2004 https://arxiv.org/abs/cs/0405020
Examples
>>> G = nx.maybe_regular_expander(n=200, d=6, seed=8020)