Analysis of rates#
By combining elements from graph theory, convex optimization, and linear algebra, we can have powerful results on the stability of a stochastic system and its set of feasible rates.
stochastic matching provides the following information (cf https://hal.archives-ouvertes.fr/hal-03502084 for details):
Graph type: injective-only, surjective-only, bijective, ``nonjective’’;
Kernel structure (for node and edge kernels);
For given arrival rates:
stability of the matching model;
Maximin and Moore-Penrose solutions of the conservation equation;
if relevant, a complete description of the vertices of \(\Lambda_{\geqslant 0}\).
The purpose of this notebook is to give a tour of these analysis on some examples.
[1]:
import stochastic_matching as sm
from stochastic_matching.display import VIS_OPTIONS
VIS_OPTIONS["height"] = "200px"
[2]:
VIS_OPTIONS
[2]:
{'interaction': {'navigationButtons': False},
'width': '100%',
'height': '200px'}
Tadpole#
Bijective tadpole#
Consider a tadpole \(T_{5, 3}\) with uniform arrival rates. Side note: if no rate is specified, degree-proportional rates are assumed, which ensure that the model is stabilizable if the graph is surjective.
[3]:
tadpole = sm.Tadpole(m=5, n=3, rates="uniform")
tadpole.show_graph()
Its kernels are trivial: the graph is bijective.
[4]:
tadpole.kernel
[4]:
Kernels of a graph with 8 nodes and 8 edges.
Node dimension is 0.
Edge dimension is 0
Type: Bijective
Node kernel:
[]
Edge kernel:
[]
Let see the unique solution of the conservation equation:
[5]:
tadpole.show_flow()
This does not sound very stable…
[6]:
tadpole.stabilizable
[6]:
False
Let’s change the arrival rates to have something nicer.
[7]:
tadpole.rates = [1, 1, 1, 1, 2, 2, 2, 1]
tadpole.show_flow()
Sounds better…
[8]:
tadpole.stabilizable
[8]:
True
Nonjective tadpole#
We now consider the bipartite tadpole \(T_{4, 1}\), again with uniform arrival rates.
[9]:
tadpole = sm.Tadpole(m=4, n=1, rates="uniform")
tadpole.show_graph()
Look at the kernel.
[10]:
tadpole.kernel
[10]:
Kernels of a graph with 5 nodes and 5 edges.
Node dimension is 1.
Edge dimension is 1
Type: Nonjective
Node kernel:
[[ 1]
[-1]
[ 1]
[-1]
[ 1]]
Edge kernel:
[[ 1 -1 -1 1 0]]
The node kernel shows the bipartite repartition of the nodes (positive and negative nodes).
The edge kernel shows how the rate flow can slide between edges. It can be displayed:
[11]:
tadpole.show_kernel()
Note the black edge above: it indicates that the specific edge is unaffected by the kernel.
Let see the (attempt) solution of the conservation equation:
[12]:
tadpole.show_flow()
The red nodes indicate that the conservation equation is not satisfied. This is not surprising, as the total arrival rates on positive nodes, 3, is distinct from the total arrival rates on negative nodes, 2.
We can change the rates in order to equalize the arrival rates.
[13]:
tadpole.rates = [1, 1, 1, 2, 1]
tadpole.show_flow()
Note that the respect of the conservation law is not sufficient for stability: the fact that the graph is not surjective forbids stability.
[14]:
tadpole.stabilizable
[14]:
False
This does not forbid considering the vertices of the positive solutions.
[15]:
tadpole.vertices
[15]:
[{'kernel_coordinates': array([-0.5]),
'edge_coordinates': array([0., 1., 1., 0., 1.]),
'null_edges': [0, 3],
'bijective': False},
{'kernel_coordinates': array([0.5]),
'edge_coordinates': array([1., 0., 0., 1., 1.]),
'null_edges': [1, 2],
'bijective': False}]
[16]:
for i in range(len(tadpole.vertices)):
tadpole.show_vertex(i, disp_rates=False)
The diamond graph#
Consider the following diamond:
[17]:
diamond = sm.CycleChain(rates="uniform")
diamond.show_graph()
The graph structure is as follows:
[18]:
diamond.kernel
[18]:
Kernels of a graph with 4 nodes and 5 edges.
Node dimension is 0.
Edge dimension is 1
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[ 1 -1 0 -1 1]]
We can look at the kernel structure.
[19]:
diamond.show_kernel(disp_flow=True)
We observe a null edge. As it is black (outside the edge kernel), it will remain null in all solutions of the conservation equation. In other words, the model is not stabilizable.
[20]:
diamond.stabilizable
[20]:
False
Let make it stabilizable.
[21]:
diamond.rates = [2, 3, 2, 1]
[22]:
diamond.show_kernel(disp_flow=True)
Better! Note that the represented base flow is the Moore-Penrose inverse. We can use the maximin flow if we prefer.
[23]:
diamond.show_kernel(disp_flow=True, flow=diamond.maximin)
Another feature: looking the incompressible flow, which is the minimal rate achieved in any positive solution.
[24]:
diamond.show_flow(flow=diamond.incompressible_flow(), check_flow=False, disp_zero=False)
To finish, let have a look at the vertices.
[25]:
diamond.vertices
[25]:
[{'kernel_coordinates': array([-0.25]),
'edge_coordinates': array([1., 1., 1., 1., 0.]),
'null_edges': [4],
'bijective': True},
{'kernel_coordinates': array([0.75]),
'edge_coordinates': array([2., 0., 1., 0., 1.]),
'null_edges': [1, 3],
'bijective': False}]
[26]:
for i in range(len(tadpole.vertices)):
diamond.show_vertex(i)
Not connected simple graphs#
The package deals with simple graphs even if they are not connected. Consider a graph made of a square, a complete graph of size 4, a diamond, a paw and a three-edged star:
[27]:
VIS_OPTIONS["height"] = 600
sample = sm.concatenate(
[sm.Cycle(4), sm.Complete(4), sm.CycleChain(), sm.Tadpole(), sm.Star()], 0
)
sample.show_graph()
The kernel will display global information:
[28]:
sample.kernel
[28]:
Kernels of a graph with 20 nodes and 22 edges.
Node dimension is 2.
Edge dimension is 4
Type: Nonjective
Node kernel:
[[ 0 -1]
[ 0 1]
[ 0 -1]
[ 0 1]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[ 0 0]
[-1 0]
[ 1 0]
[ 1 0]
[ 1 0]]
Edge kernel:
[[ 1 -1 -1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 1 -1 0 0 -1 1 0 0 0 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 -1 1 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0]
[ 0 0 0 0 0 0 0 0 0 0 1 -1 0 -1 1 0 0 0 0 0 0 0]]
The two node vectors point to the bipartite connected components (the square and the star).
The four edge vectors point to the even cycles from the square, complete graph, and diamond.
If we want further information, we can look at the connected_components attribute.
[29]:
sample.connected_components
[29]:
[{'nodes': {0, 1, 2, 3},
'edges': {0, 1, 2, 3},
'spanner': {0, 1, 2},
'pivot': False,
'seeds': {3},
'type': 'Bipartite with cycle(s)'},
{'nodes': {4, 5, 6, 7},
'edges': {4, 5, 6, 7, 8, 9},
'spanner': {4, 5, 6},
'pivot': 8,
'seeds': {7, 9},
'type': 'Non-bipartite polycyclic'},
{'nodes': {8, 9, 10, 11},
'edges': {10, 11, 12, 13, 14},
'spanner': {10, 11, 13},
'pivot': 12,
'seeds': {14},
'type': 'Non-bipartite polycyclic'},
{'nodes': {12, 13, 14, 15},
'edges': {15, 16, 17, 18},
'spanner': {15, 16, 18},
'pivot': 17,
'seeds': set(),
'type': 'Non-bipartite monocyclic'},
{'nodes': {16, 17, 18, 19},
'edges': {19, 20, 21},
'spanner': {19, 20, 21},
'pivot': False,
'seeds': set(),
'type': 'Tree'}]
Connected components give the following information for each connected component:
The nodes and edges that belong to that component (or more accurately their index);
A spanner of the component, e.g. a set of edges that form a spanning tree for the component;
If the component is surjective, a pivot, e.g. an edge that makes the spanner non-bipartite if we add it;
Seeds, which are a set of edges that can be used to build a edge kernel basis made of cycles and kayak paddles.
The type of the component. For example, for a connected component, injective-only is a synonym for tree.
All operations that were previously performed can be done on graphs that are not connected.
[30]:
sample.show_kernel(disp_flow=True)
Hypergraphs#
Candy#
The candy is a simple example of true hypergraph.
[31]:
candy = sm.HyperPaddle()
candy.show_graph()
It is a bijective graph.
[32]:
candy.kernel
[32]:
Kernels of a graph with 7 nodes and 7 edges.
Node dimension is 0.
Edge dimension is 0
Type: Bijective
Node kernel:
[]
Edge kernel:
[]
With degree-proportional arrival rates, it is stabilizable.
[33]:
candy.stabilizable
[33]:
True
With uniform arrival rates, it is not stabilizable.
[34]:
candy.rates = "uniform"
candy.stabilizable
[34]:
False
[35]:
candy.show_flow()
Fans#
Fans yield nice examples of hypergraphs with cool kernels. The basic fan is called a clover.
[36]:
clover = sm.Fan()
clover.show_graph()
[37]:
clover.kernel
[37]:
Kernels of a graph with 9 nodes and 10 edges.
Node dimension is 0.
Edge dimension is 1
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[-0.2773501 -0.2773501 0.2773501 -0.2773501 -0.2773501 0.2773501
-0.2773501 -0.2773501 0.2773501 0.5547002]]
[38]:
clover.show_kernel()
The double fan expands the kernel dimension.
[39]:
double = sm.Fan(hyperedges=2)
double.show_graph()
[40]:
double.kernel
[40]:
Kernels of a graph with 9 nodes and 11 edges.
Node dimension is 0.
Edge dimension is 2
Type: Surjective-only
Node kernel:
[]
Edge kernel:
[[-0.17089102 0.32672261 -0.32672261 -0.17089102 0.32672261 -0.32672261
-0.17089102 0.32672261 -0.32672261 -0.15583159 0.49761363]
[-0.41327504 -0.13510121 0.13510121 -0.41327504 -0.13510121 0.13510121
-0.41327504 -0.13510121 0.13510121 0.54837625 0.27817383]]
[41]:
double.show_kernel()
Last but not least, the bipartite fan created a large node kernel.
[42]:
bip = sm.Fan(cycle_size=4)
bip.show_graph()
[43]:
bip.kernel
[43]:
Kernels of a graph with 12 nodes and 13 edges.
Node dimension is 2.
Edge dimension is 3
Type: Nonjective
Node kernel:
[[-0.03577392 0.40667787]
[ 0.03577392 -0.40667787]
[-0.03577392 0.40667787]
[ 0.03577392 -0.40667787]
[ 0.37008033 -0.17235781]
[-0.37008033 0.17235781]
[ 0.37008033 -0.17235781]
[-0.37008033 0.17235781]
[-0.33430641 -0.23432006]
[ 0.33430641 0.23432006]
[-0.33430641 -0.23432006]
[ 0.33430641 0.23432006]]
Edge kernel:
[[ 0.0879802 -0.0879802 -0.0879802 0.0879802 -0.46609144 0.46609144
0.46609144 -0.46609144 0.15817159 -0.15817159 -0.15817159 0.15817159
0. ]
[-0.48975298 0.48975298 0.48975298 -0.48975298 -0.06690184 0.06690184
0.06690184 -0.06690184 0.07527389 -0.07527389 -0.07527389 0.07527389
0. ]
[ 0.04900509 -0.04900509 -0.04900509 0.04900509 0.16817524 -0.16817524
-0.16817524 0.16817524 0.46831142 -0.46831142 -0.46831142 0.46831142
0. ]]
The node kernel can be interpreted as follows:
There are three bipartite components, one for each square. Along the square, the nodes value must alternate positively and negatively.
The central edge forces the sum of the weights of its adjacent nodes to be zero. so if we fix two squares, the values on the last square are fully determined.
[44]:
bip.show_kernel()
Remark that in this example, the hyperedge is not part of the edge kernel. Only the three regular squares are.
Just for the experience, let us add another hyperedge.
[45]:
bip = sm.Fan(cycle_size=4, hyperedges=2)
bip.show_graph()
[46]:
bip.kernel
[46]:
Kernels of a graph with 12 nodes and 14 edges.
Node dimension is 2.
Edge dimension is 4
Type: Nonjective
Node kernel:
[[ 0.32250561 -0.25031339]
[-0.32250561 0.25031339]
[ 0.32250561 -0.25031339]
[-0.32250561 0.25031339]
[-0.37803057 -0.15414136]
[ 0.37803057 0.15414136]
[-0.37803057 -0.15414136]
[ 0.37803057 0.15414136]
[ 0.05552495 0.40445475]
[-0.05552495 -0.40445475]
[ 0.05552495 0.40445475]
[-0.05552495 -0.40445475]]
Edge kernel:
[[-0.56906235 0.1744534 0.1744534 -0.1744534 -0.39193558 -0.00267337
-0.00267337 0.00267337 -0.2685181 -0.12609085 -0.12609085 0.12609085
0.39460895 0.39460895]
[ 0.06237319 -0.30242679 -0.30242679 0.30242679 0.12293935 -0.36299295
-0.36299295 0.36299295 -0.37551859 0.13546499 0.13546499 -0.13546499
0.2400536 0.2400536 ]
[-0.02439087 0.08230634 0.08230634 -0.08230634 -0.14626481 0.20418028
0.20418028 -0.20418028 -0.41026921 0.46818468 0.46818468 -0.46818468
-0.05791547 -0.05791547]
[-0.23245569 0.36883003 0.36883003 -0.36883003 0.43844265 -0.30206831
-0.30206831 0.30206831 0.0302644 0.10610994 0.10610994 -0.10610994
-0.13637434 -0.13637434]]
[47]:
bip.show_kernel()