3
$\begingroup$

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:

  1. This measure C=0 on an acyclical graph
  2. C=1 on a fully connected graph
  3. C monotonously decreases as you eliminate edges from a fully connected graph
  4. Should generalize well to unweighted directed graphs
  5. 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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.