I wonder if the following statistical description of the layer architecture of finite graphs has been considered before and where I can find some references (especially under which name).
Consider a huge (but finite) directed graph with a big set of roots $\{\rho_j\}$ having in-degree 0.
Let $d(\nu_1,\nu_2)$ be the length of the shortest path from node $\nu_1$ to node $\nu_2$ and $\infty$ when there is no path from $\nu_1$ to $\nu_2$.
A graph has a strictly layered architecture when for each node $\nu$ there is a unique number $\mathcal{l}$ (the level of the node) such that $d(\rho,\nu)=\mathcal{l}$ or $=\infty$ for all root nodes $\rho$. Call the set of all nodes having level $\mathcal{l}$ the layer $\mathcal{l}$.
Strictly layered graphs prohibit "short cuts" from the root layer (layer 0) to a given node $\nu$, but permit different paths from a root node $\rho$ to $\nu$. Furthermore they permit inner layer connections and arbitrary cycles (because these can be ignored when considering shortest paths).
Note that inner layer connections or cycles may possibly occur only inside or between a few layers, i.e. only inside layer 3 or by nodes from layer 4 being linked back to nodes from layer 2. You may notice that I have neural networks in mind.
For a given node $\nu$ let $p(x)$ be the number of root nodes $\rho$ such that $d(\rho,\nu)=x$. Normalize such that $\sum_x p(x)=1$, making $p(x)$ a probability distribution. Call $p(x)$ the layer distribution of $\nu$. Note that $0 \leq x \leq L$, the maximal distance in the graph.
Consider a set $\mathcal{L} = \{f_{\sigma_i}^{l_i}(x)\}_{0\leq i < n}$ of normal distributions with mean $l_i$, $0 \leq l_i \leq L$, and standard deviation $\sigma_i$. Call $\mathcal{L}$ a layer scheme.
When for each node $\nu$ of a given graph $G$ the layer distribution $p(x)$ overlaps strongly enough with one of the elements/distributions of the layer scheme $\mathcal{L}$, one could say that the layer scheme $\mathcal{L}$ reflects the (fuzzy) layer structure of the graph $G$.
This last part is intentionally left vague because I don't know yet how to specify "overlaps strongly enough" and "reflects the fuzzy layer structure". But I am confident, that both can be made precise and quantified.
What seems clear to me (but maybe I'm wrong) is:
being "strictly layered" means "having a layer scheme" $\mathcal{L}$ with all standard deviations $\sigma_i = 0$
there is an ordering of possible layer schemes $\mathcal{L}$, making some better than others
there are optimal layer schemes describing a given graph
Questions
- Has this approach been taken before?
- Under which name?
- References?
