# Calculating Node Connectivity

In the most trivial sense, node connectivity can be approached by investigating the numbers of in-connections and out-connections at each node. Existing metrics in graph theory include the in-degree and out-degree in directed graphs, as well as the degree in undirected graphs.

However, those existing metrics only provide limited capacity for graph analysis, as they only take 1 layer of graph traversal into account, ignoring the recursive nature of graphs. Hence, we've devised the weight-decaying connectivity metrics which support more in-depth graph analysis.

If we define the weight-decay factor `f`

to be a scalar in [0, 1], we can obtain the connectivity of a node by recursively sampling the degrees of its ancestor/descendant nodes, as follows:

Without loss of generality, assume that we want to find the *in-connectivity* of node `n`

.

`find_in_conn(n, f):`

if f is close enough to 0.0:

return in_deg(n)

let in_conn = in_deg(n)

for each child c of n:

in_conn += f * find_in_conn(c, f * f)

return in_conn

*Note: This algorithm can be implemented with a stack/queue instead of using recursion for performance improvement. Also, graphs with cycles are ignored in this trivial algorithm, but it's simple to deal with in practice.*

Different weight-decay factors lead to different interesting connectivity metrics, most noticeably:

- When it is
`0`

(*Simple connectivity*), the connectivity is simply the trivial degrees.- As the weight essentially decays to 0 immediately in this case, the
*Decay Mode*is*Immediate*.

- As the weight essentially decays to 0 immediately in this case, the
- When it is
`1`

(*Compound connectivity*), the connectivity takes into account**all**the ancestor/descendant nodes in the connected component of the node of interest.- As the weight essentially never decays in this case, the
*Decay Mode*is*None*.

- As the weight essentially never decays in this case, the
- When it is anything in between (
*Complex connectivity*), the connectivity*decays*throughout traversal, which is a nice property for some use cases.- In this case, the
*Decay Mode*is associated with a speed:*the smaller the factor, the faster the decay speed*.

- In this case, the