0

I have a bunch of nodes arranged in a hierarchy structure as follows:

Node hierarchy

I would like to determine if one node is connected to another node, even if the connection between the two is separated by different levels in the hierarchy.

For example, node A is connected to node K through nodes B and D. Node A is also connected to node L either through nodes B and D or nodes C and G.

Nodes E, F, H, J and M are not connected to node L.

Without transversing the hierarchy from a parent node to some child node in order to determine whether two nodes are connected, I believe that it is possible to assign some numeric value to each node and through a formula that takes the numeric value of two nodes can determine that they are connected.

Is this possible?

AndroidDev
  • 125
  • 6

1 Answers1

1

One can associate to this network a matrix $\bf{A},$ where $1$ represents a direct path from a vertex $X$ to $Y,$ and $0$ says there is no path.
Then the entry $a_{ij,2}$ in the matrix ${\bf{A}}^2$ says whether $i$-th and $j$-th nodes are connected (directly or not) in the second generation.
In general, denote $a_{ij,k}$ the entry $ij$ in the matrix ${\bf{A}}^k.$
Then $a_{ij,k}=0 \iff$ there is no connection in $k$-th generation between $i$-th and $j$-th nodes.

Finally, the matrix $${\bf{B}}={\bf{A}}+p{\bf{A}}^2+p^2{\bf{A}}^3+...$$ or shortly ${\bf{B}}=\sum_{n=1}^\infty p^{n-1} {\bf{A}}^n$ does the work, here $p$ is a parameter. (In any concrete case, $p$ can take a convenient numerical value, e.g. $p$ is a prime or $0.1$ or ... The only thing we have to care, is the unicity, if you want to keep the information about the generation, in which is a connection.)

Example
The matrix of your network is bellow, $0$s are replaced by dots.
${\bf{A}}^2$ has the first three rows

$$\begin{matrix} &A&B&C&D&E&F&G&H&J&K&L&M\\ A&.&.&.&1&1&1&1&1&1&.&.&.\\ B&.&.&.&.&.&.&.&.&.&1&1&.\\ C&.&.&.&.&.&.&.&.&.&.&1&.\\ \end{matrix}$$

all other entries are zeros. From this we read that in the second level are $D,E,F,G,H,J$ the followers of $A,$ further $K,L$ are the followers of $B,$ and $L$ is the follower of $C.$
${\bf{A}}^3$ has non-zero elements only in the first row, which is $$(\begin{matrix}.&.&.&.&.&.&.&.&.&1&2&.\\ \end{matrix})$$

This means that in the third level has $A$ two followers $K,L,$ where $L$ can be reached through two connections.
There are no other second- or third-order followers in this network.
Any higher power of $\bf{A}$ is the zero matrix, therefore there is no connection in higher generations.

The matrix $\bf{B}$ has the first three rows $$\begin{matrix} &A&B&C&D&E&F&G&H&J&K&L&M\\ A&.&1&1&p&p&p&p&p&p&p^2&2p^2&.\\ B&.&.&.&1&1&1&.&.&.&p&p&.\\ C&.&.&.&.&.&.&1&1&1&.&p&.\\ \end{matrix}$$ the rest is identical to the matrix $\bf{A}.$

$${\bf{A}}=\begin{matrix} &A&B&C&D&E&F&G&H&J&K&L&M\\ A&.&1&1&.&.&.&.&.&.&.&.&.\\ B&.&.&.&1&1&1&.&.&.&.&.&.\\ C&.&.&.&.&.&.&1&1&1&.&.&.\\ D&.&.&.&.&.&.&.&.&.&1&1&.\\ E&.&.&.&.&.&.&.&.&.&.&.&.\\ F&.&.&.&.&.&.&.&.&.&.&.&.\\ G&.&.&.&.&.&.&.&.&.&.&1&.\\ H&.&.&.&.&.&.&.&.&.&.&.&.\\ J&.&.&.&.&.&.&.&.&.&.&.&.\\ K&.&.&.&.&.&.&.&.&.&.&.&.\\ L&.&.&.&.&.&.&.&.&.&.&.&.\\ M&.&.&.&.&.&.&.&.&1&.&.&.\\ \end{matrix} $$

user376343
  • 8,311
  • Unfortunately I'm not a mathematician, so I'm having a difficult time deciphering your formula. So this is your formula: B=∑∞n=1pnAn ? I don't know how to use it. So how do I use it to plug in say nodes A and L and it returns a result that says they are connected? Or A and M and it says they are not connected? If I understand, are you saying I need to create a matrix of my nodes and then run the formula on the matrix? – AndroidDev Oct 30 '18 at 15:41
  • Yes, my method suggests to create the matrix. The software should know to compute $A^2,A^3,...$ Those are powers of $A.$ In other words, $A^3=AAA$ matrix product. Similarly for other powers. Multiplying by $p^{n-1}$ will multiply each entry of the matrix $A^n$ by the number $p^{n-1}.$ I hope the computation in my answer is correct now. – user376343 Oct 30 '18 at 15:53
  • So a lot of those matrix indexes are left blank. I assume that with a good library that can deal with matrixes, it will not create a bunch of empty indexes that would result in wasted space. – AndroidDev Oct 30 '18 at 16:16
  • If this helps: matrices with many zero entries are called sparse matrices – user376343 Oct 30 '18 at 16:19