Say you have a weighted directed graph with (potentially) some cycles in it. You want to have some sort of a measure of how "cyclical" this graph is. The requirements are:
- This measure C=0 on an acyclical graph
- C=1 on a fully connected graph
- C monotonously decreases as you eliminate edges from a fully connected graph
- Should generalize well to unweighted directed graphs
- In my case, graph weights represent connections between nodes, not distances, so high weights make good cycles. It means that a low weight within a cycle should act as "bottleneck", lowering the "impact" of this cycle on C.
Beyond that the measure is really flexible.
How to best build a cyclicity measure like that?
So far the best I could do is some sort of a free-association on spectral techniques, random walks, and stable flows, wherein I inject a flow of 1 into each node, make them propagate through the graph with some decay, and look for a a stable flow solution. Then I sum all flows that originate in each node and cycle back to this node. Here's an attempt to write it down mathematically, in case it's easier to read that way:
I initialize $s_0 = E$, where $E$ is a unitary matrix. I then run a stepwise equation $s_{i+1} = d\cdot A'\cdot\text{max}(s_i,E)$, where $A$ is my adjacency matrix, $d$ is a dampening coefficient of about 0.9 (pagerank-style), and $\text{max}$ operates on both matrices elementwise. I do it until $s$ reaches a stable solution; then I assume $C=\text{Tr}(s_{end})$.
The problem here of course is that A needs to be normalized somehow, so that the solution would converge, yet I should not completely invalidate the values of weights, as I want it to work on weighted graphs. For now I solve it in the following way: I normalize A so that the highest in-degree (sum of in-weights) on the graph is equal to 1. Then I run this analysis on my graph, and also on a full graph of the same dimension. And then I normalize C achieved on my graph to C on a full graph. Essentially the measure I've built tells me the share of self-flow (cyclical flow) in my graph of interest, compared to a full graph.
It sort of works, for my purposes, but I have three concerns. One is that it feels unnecessary complex. I am particularly concerned with the fact that I have to normalize things twice: first $A$, then $C$ itself. Two, it feels suspiciously similar to spectral analysis, so I was wondering whether this problem is already solved long time ago, and I just don't know the solution, or fail to recognize it. Three, the normalization of $A$ I perform, namely $A \rightarrow A/\text{max}(d_i) = A/\text{max}(\sum_i a_{ij})$, feels a bit random, and I'm concerned that it can cause "oscillations" in violation of my criterion 2 (monotonous change in C with graph reduction). I could not catch them by debugging so far, but it feels dangerous.
The only alternative to this normalization I have is to make $A \rightarrow A/[\text{max}(a_{ij})\cdot n]$, where $n$ is the dimension of $A$. It also works, but values of C become astronomically small very quickly, which is uncomfortable as well.
Sorry for a long-winded question, and I'll be extremely grateful for any suggestions or thoughts on this topic! Thanks!
