How to optimally adjust the probabilities for the random graph-directed IFS algorithm?

In this related question it is shown that the optimal probabilities for an iterated function system of similarities (that satisfy the open set condition) with contraction ratios $r_k$ and fixed point attractor fractal similarity dimension $s$ are $p = r_k^s$.

How does this change when you have a graph-directed iterated function system, where some transitions are disallowed (a non-graph-directed IFS can be seen as a GDIFS with a complete graph)? There will be a matrix $p_{k_{\operatorname{from}}k_{\operatorname{to}}}$ with some items exactly $0$ (determined by the graph structure) and $\sum_{k_{\operatorname{to}}} p_{k_{\operatorname{from}}k_{\operatorname{to}}} = 1$ for each $k_{\operatorname{from}}$. The dimension of the whole fractal can be calculated from the graph structure and contraction ratios, via spectral radius of a matrix:

Hausdorff Dimension in Graph Directed Constructions; R Daniel Mauldin, S C Williams; Transactions of AMS, vol309 no2, October 1988, 811-829; http://cas.unt.edu/~mauldin/papers/no67.pdf

I implemented a numerical algorithm to try to calculate optimal probabilities by adjusting weights during image generation, and it sort of worked sometimes, but I'm not even sure if there is a unique optimal set of probabilities...


Let's denote the digraph by $G$, the set of vertices of the digraph by $V$, and the set of edges by $E$. Thus, any $e \in E$ is a directed edge from $u\in V$ to some $v\in V$; conversely, we could denote all the edges from $u$ to $v$ as $E_{uv}$.

Now, to transform this into a digraph IFS, we associate a similarity transformation $f_e$ with each edge $e\in E$. Then, under suitable hypotheses, there is a unique collection of compact sets $K_v$, one for each $v\in V$, such that for every $u\in V$,

$$K_u = \bigcup_{v\in V,e\in E_{uv}} f_e(K_v).$$

A major result of the paper of Mauldin and Williams is the computation of the common Hausdorff dimension of these sets, under the assumption that the digraph is strongly connected. Specifically, we define a matrix $A(s)$ whose rows and columns are indexed by $V$; the entry in row $u$ and column $v$ is $$A_{uv}(s) = \sum_{e\in E_{uv}} r_e^s.$$ The paper shows that there is a unique value of $s$ such that $A(s)$ has spectral radius 1 and that this value is the common Hausdorff dimension of the sets.

The transition ratios that you seek are proportional to those numbers $r_e^s$. To obtain them, simply normalize them so that the sum of all the numbers coming into any edge is 1.


Here's an example that's worked out in code in this Observable notebook. Our example consists of the following digraph fractal pair:

enter image description here

Each blue piece is a scaled copy of the spiral on the left and each orange piece is a scaled copy of the spiral on the right. Thus, the left image consists of one copy of itself together with one copy of the other. The image on the right consists of one copy of itself together with two copies of the other. This implies the following directed graph:

enter image description here

Note that the edges are labeled with the corresponding contraction ratios. From here, we can read off the matrix $A(s)$:

$$ A(s) = \begin{pmatrix} 0.96^s & 0.1^s \\ 2\times0.1^s & 0.96^s \end{pmatrix}. $$

As it turns out, the largest eigenvalue of $A(s)$ is quite close to 1 when $s\approx1.40449$; thus, the dimension is approximately $1.40449$.

That suggests that each $0.96$ in the transition digraph should be replaced by $0.96^{1.40449} \approx 0.94445$ and that each $0.1$ should be replaced by $0.1^{1.40449} \approx 0.0398$. We still need to normalize, though, so that the sum probability of all edges coming into each node is $1$. For example, the self loop on the left should have probability $$\frac{0.96^{1.40449}}{0.96^{1.40449} +2\times0.1^{1.40449}} \approx0.922975.$$ The self-loop on the right should have probability $$\frac{0.96^{1.40449}}{0.96^{1.40449} + 0.1^{1.40449}} \approx 0.959945.$$ Similar computations can be performed for the other two edges to yield the following transition probabilities:

enter image description here

Finally, I might mention that these spirals fit together quite nicely:

enter image description here

But the image looks not nearly so nice, if we use equal probabilities:

enter image description here