4
$\begingroup$

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?
$\endgroup$
6
  • $\begingroup$ Ah, you define a family of probability measures on your graph, and you want to use these measures to quantify how 'layered' the graph is.... $\endgroup$ Nov 10, 2016 at 17:40
  • $\begingroup$ Maybe it's just that? $\endgroup$ Nov 10, 2016 at 17:42
  • $\begingroup$ I'm not sure to see how your layer distribution is useful in the context of neural network. I'd say you could search for better (more natural) random variables on your neural network reflecting the data-flow to one neuron from the others. $\endgroup$
    – reuns
    Nov 11, 2016 at 1:14
  • $\begingroup$ @user1952009: Could you give me some examples of better and more natural random variables and how the reflect the data-flow? $\endgroup$ Nov 11, 2016 at 9:14
  • $\begingroup$ @user1952009: Many neural networks - including the human brain - are described - inter alia - by their layer structure. So at first sight a more general description of the layer structure seems desirable. Or why do you not believe so? If there are different and more useful general descriptions of the layer structure, I am keen to learn about them. $\endgroup$ Nov 11, 2016 at 9:18

1 Answer 1

2
$\begingroup$

There is quite a bit of work on drawing graphs in as layered a manner as possible, e.g.,

Bastert, Oliver, and Christian Matuszewski. "Layered drawings of digraphs." Drawing graphs. Springer Berlin Heidelberg, 2001. 87-120.


LayeredGraph
            (Image from this SE posting.)
Perhaps this work has been generalized to something akin to your statistical situation...

$\endgroup$
2
  • 1
    $\begingroup$ Thanks, Joseph! You gave me the hint I was looking for: the name of the game is "layered graph drawing". It will be interesting to see how the algorithms correspond to the definitions in my approach. (Do optimal layered graph drawings calculated with a given algorithm correspond to an optimal layer scheme?) $\endgroup$ Nov 11, 2016 at 9:36
  • $\begingroup$ @HansStricker optimal for what ? What do you want/hope to do ? (it is not clear to me at all) is what Joseph answered "drawing graphs in as layered a manner as possible" what you want ? $\endgroup$
    – reuns
    Nov 11, 2016 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.