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
if f is close enough to 0.0:
let in_conn = in_deg(n)
for each child c of n:
in_conn += f * find_in_conn(c, f * f)
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.
- 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.
- 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.