I'm working with road networks, in which each edge is a physical street segment with a length attribute. Nodes represent junctions. However, my question should be generalizable to any weighted graph.

I'm interested in a specific measure of 'branchiness' that I have devised to normalise a density estimate. I would like to know if this corresponds to, or is related to, any pre-existing measures. I'm no expert in network science, and as such don't know what search terms to use.

The measure is best described with a diagram:

network branching measure

Start with a point, $a$, somewhere on the graph. Move an increasing distance away from $a$ and measure the number of shortest-distance branches that are possible at this distance. Once a branch terminates (as is the case for cul de sacs/dead ends in the road network), it is no longer counted. Repeat for many points on the network (e.g. point $b$ illustrated in the figure).

If I generate many traces for many points on the network, as shown in the top panel of the figure, the mean trace should appear smooth(?). I'm interested in whether this mean "distance<->branches" relationship has a name. It seems to be related to betweenness, but I don't think it's the same thing.

  • $\begingroup$ what is a branch? $\endgroup$ – Chao Xu May 11 '15 at 18:33
  • $\begingroup$ Sorry if my question wasn't clear. A branch occurs at a node when the degree is >2. If you travel along an edge in the graph, when you reach a branch node you are forced to make a decision about which edge to take next (assuming you cannot cover the same edge more than once). I hope that helps. $\endgroup$ – Gabriel May 12 '15 at 6:29
  • $\begingroup$ from looking at the picture. it seems you are just asking how many points with distance $d$ from a point. $\endgroup$ – Chao Xu May 12 '15 at 6:58
  • $\begingroup$ I suppose it's a related question. Is there any kind of standard terminology for that property, do you know? To be more precise, I want the sum over all nodes within shortest network distance $d$ of that point. Each node contributes $n-1$ to the sum, where $n$ is the degree of that node, if $n>2$, or -1 to the sum if $n=1$ (i.e. if the edge comes to an end). $\endgroup$ – Gabriel May 12 '15 at 11:35
  • $\begingroup$ You can increase the distance from $d$ to $d+\epsilon$, and get the same value for both the node and my version. This become exactly number of points in this metric space that has distance exactly $d$ from some other point, which is just boundary of a ball. $\endgroup$ – Chao Xu May 12 '15 at 17:20

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.