Message Boards Message Boards

Coloring graphs roughly according to local dimension size

Posted 3 years ago

I wrote a function which counts the neighborhood size of each node in a graph, as the neighborhood size increases. It then weights closer neighbors more than father neighbors, but does take the global neighborhood into account. It then colors the graph according to this weighted global neighborhood, visualizing perhaps a rough estimate of local dimension sizes of the graph. The notebook is attached to this post. Here are some graphs colored according to the function: enter image description here

Attachments:
POSTED BY: Eric Parfitt
2 Replies

Very interesting and beautiful visualization. I will try to read your code. Thank you!

POSTED BY: Ruggero Valli

The functions IGDistanceCounts and IGNeighborhoodSize form my IGraph/M package make it possible to do similar calculations with better performance, and the soon-to-come IGNeighborhoodCloseness will make it even easier.


I wrote a function which counts the neighborhood size of each node in a graph, as the neighborhood size increases. It then weights closer neighbors more than father neighbors, but does take the global neighborhood into account.

This is a bit opaque. Can you explain what you are calculating with more mathematical precision, why it is interesting to calculate it, and what one can learn from the result? (So we don't have to read the code to understand what we see.)


visualizing perhaps a rough estimate of local dimension sizes

The usual concept people mean when talking about "dimension" is the exponent in the power-law function describing the growth of the neighbourhood size with graph distance (i.e. radius). For example, in a $n$-D grid graph, the neighbourhood size grows with power $n$ of the radius. Of course, the growth does not need to be a power-law. In a random graph it is exponential, i.e. faster than any power law. Thus we can consider such graphs "infinite dimensional".

While a weighted average is related to the dimension in this sense, it is not quite the same thing.


What you compute is also closely related to closeness centrality, which is just the inverse of the average distance to all other vertices. Note that the Differences of neighbourhood sizes is the number of vertices at a given distance. A weighted average of these, using distances as the weights, gives the inverse of closeness.

POSTED BY: Szabolcs Horvát
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract