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 
-
-
Replying to @vgr
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 reply 0 retweets 0 likes -
Replying to @meditationstuff
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 reply 0 retweets 0 likes -
Replying to @vgr @meditationstuff
Specific application: “thickness” of time history of a software project in github, given graph of forks, merges, PRs etc
1 reply 0 retweets 0 likes -
Replying to @vgr
https://en.m.wikipedia.org/wiki/Fractal_dimension_on_networks … 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 reply 0 retweets 1 like -
Replying to @meditationstuff
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).
1 reply 0 retweets 0 likes -
Replying to @vgr
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 reply 0 retweets 0 likes
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.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.