How would you calculate something like a Hausdorff dimension of a graph given there’s no unique embedding in Euclidean space, but we still think of (for eg) bushy vs sparse branching etc? A long skinny DAG with few branches should be lower dim than dense random graph for eg 🤔
Conversation
Replying to
Maybe average or median fan-out per node for a directed graph? Or average number of choices (also fan-out) at each node for a DAG?
Which flavor or quality are trying to capture, transferred over from the original scalar?
1
Replying to
If you squint at a (biological) tree or cauliflower it looks like a sankey diagram of an aggregate flow.
The coarse topology of that flow given a resolution level. Like a recursive approximation of min-cut-max-flow view.
DAGs are the easiest case.
1
Specific application: “thickness” of time history of a software project in github, given graph of forks, merges, PRs etc
1
Replying to
en.m.wikipedia.org/wiki/Fractal_d
This is just weird. All of these methods take abstract graphs and then *embed* them in e.g. a Euclidean space. Gotta be a better way.
1
1
Replying to
You have to embed them to get a meaningful notion of spatial dimension. Pure graph-theoretic metrics lack a notion of dimension. Or even proper norms. You can only get quasi-spatial metrics like “diameter” which yield an O(n) notation type analog to dimension (log, linear etc).
Replying to
Sure; you can get norms if not metrics if you add weights to edges (like edit distance between commits). But I'm just surprised there isn't something that's made it onto wikipedia that has some relevant flavor of fractal dimension, thickness, bushiness, self-similarity for graphs
1
Replying to
The moment you add weights you’re bringing in a whole new information set. I’d like a “natural” embedding that minimizes the amount of extra information added. Also weights are halfway to an embedding so you might as well go all the way.
1

