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
I'm pretty sure a graph simply has a hausdorff dimension of zero since the nodes are points and there's only one link between any two points. I suppose you could think of a graph with an uncountable number of nodes by constructing some set but that sounds a bit iffy
1
Replying to
You're technically correct, but that's why I said something *like* a hausdorff dimension that captures the sense of spatial density of an embedded graph
2
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
Show replies
Replying to
can take e.g. the average degree / 2, although i don't know how useful this is. you can think of the average degree / 2 localized in a region of a graph as being a "local dimension" which can then vary across regions of the graph
1
1
Replying to
Start at a vertex, look at the number of first neighbors, second, ... . Repeat and average for all vertices. Try fitting r^{d-1},where r is the order of the neighbor. This should be *a* valid dimension, though not sure if it matches the Hausdorff dimension.






