Skip to main content

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.
  • 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.