Mrthfx

Consider the graph:

graph = {1 <-> 2, 1 <-> 4, 1 <-> 5, 1 <-> 8, 1 <-> 10, 1 <-> 26, 1 <-> 37, 1 <-> 42, 1 <-> 62, 1 <-> 86, 1 <-> 93, 1 <-> 100, 2 <-> 3, 2 <-> 7, 2 <-> 9, 2 <-> 12, 2 <-> 14, 2 <-> 17, 2 <-> 18, 2 <-> 25, 2 <-> 36, 2 <-> 41, 2 <-> 46, 2 <-> 50, 2 <-> 55, 2 <-> 72, 2 <-> 75, 3 <-> 6, 3 <-> 28, 3 <-> 34, 3 <-> 63, 4 <-> 13, 4 <-> 21, 5 <-> 20, 5 <-> 35, 5 <-> 40, 5 <-> 45, 5 <-> 48, 5 <-> 74, 6 <-> 31, 6 <-> 70, 9 <-> 11, 9 <-> 54, 9 <-> 67, 11 <-> 16, 11 <-> 24, 11 <-> 58, 11 <-> 60, 11 <-> 61, 11 <-> 65, 11 <-> 69, 12 <-> 27, 13 <-> 15, 13 <-> 33, 13 <-> 76, 14 <-> 30, 15 <-> 19, 15 <-> 96, 15 <-> 98, 16 <-> 57, 16 <-> 90, 19 <-> 22, 19 <-> 23, 19 <-> 39, 19 <-> 80, 19 <-> 83, 21 <-> 38, 22 <-> 59, 22 <-> 82, 25 <-> 29, 25 <-> 56, 25 <-> 94, 26 <-> 32, 26 <-> 43, 26 <-> 71, 27 <-> 47, 30 <-> 77, 30 <-> 78, 33 <-> 79, 33 <-> 97, 39 <-> 49, 39 <-> 51, 40 <-> 44, 40 <-> 73, 42 <-> 68, 48 <-> 52, 48 <-> 81, 50 <-> 53, 50 <-> 64, 50 <-> 89, 56 <-> 66, 56 <-> 92, 59 <-> 91, 62 <-> 88, 67 <-> 87, 74 <-> 95, 82 <-> 84, 82 <-> 85, 82 <-> 99};



net = Graph[graph, VertexShapeFunction -> "Name"]

Let's choose any node 'g' in the graph:

g=19;

Let 'r' denote the distance (counted in the number of nodes) from the node 'g':

d = GraphDiameter[net]

r = Range[1, d]

How to count all neighboring nodes within radius 'r' from the node 'g' ?

For example for node g=19 we have 6 nodes for r=1 (nodes: 80,83,22,39,23,15). For r=2 we have 7 nodes: 59,82,49,51,98,96,13.

I will choose a bit better GraphLayout for a tree:

net = Graph[graph, VertexLabels -> "Name", GraphLayout -> "RadialEmbedding"];

I suggest don't just count directly - get an object - a subgraph - of your query, so you can then run various computations on it and don't need count all over again based on different criteria w/ a different code.

nei[v_, d_] := NeighborhoodGraph[net, v, d]

Take distance 1:

nei[19, 1]

and see it is right:

HighlightGraph[net, nei[19, 1]]

Now you can compute whatever you need:

VertexList[nei[19, 1]]

Length[%] - 1

{19, 15, 22, 23, 39, 80, 83}

6

For the distance 2:

VertexList[nei[19, 1]]

VertexList[nei[19, 2]]

Complement[%, %%]

Length[%]

{19, 15, 22, 23, 39, 80, 83}

{19, 13, 15, 22, 23, 39, 49, 51, 59, 80, 82, 83, 96, 98}

{13, 49, 51, 59, 82, 96, 98}

7

Timings for large graphs

net = RandomGraph[BarabasiAlbertGraphDistribution[20000, 1]];



nei[v_, d_] := NeighborhoodGraph[net, v, d]



dist15:=Length[Complement[VertexList[nei[#,15]],VertexList[nei[#,14]]]&@RandomInteger[1000]]



Table[AbsoluteTiming[dist15;][[1]], 5]

{0.097359, 0.094737, 0.092589, 0.08872, 0.087478}

You could build it using BreadthFirstScan:

net = RandomGraph[BarabasiAlbertGraphDistribution[200000, 1]];



distance = 

  GroupBy[Reap[

     BreadthFirstScan[net, 

      19, {"DiscoverVertex" -> (Sow[#3 -> #1] &)}]][[2, 1]], 

   First -> Last, Association[{"length" -> Length[#], "set" -> #}] &];

Get length:

distance[3, "length"]

1194

distance[[All, "length"]]

<|0 -> 1, 1 -> 214, 2 -> 1194, 3 -> 3058, 4 -> 5826, 5 -> 10069, 6
-> 15110, 7 -> 19992, 8 -> 23821, 9 -> 24910, 10 -> 24767, 11 -> 21459, 12 -> 17869, 13 -> 13525, 14 -> 9119, 15 -> 5146, 16 -> 2406,
17 -> 1025, 18 -> 337, 19 -> 106, 20 -> 34, 21 -> 11, 22 -> 1|>

and set
distance[21, "set"]

{182224, 145742, 171910, 124658, 125540, 128520, 196392, 166986,
159530, 196846, 144772}

To count how many nodes there are at every distance (unsorted Association): use this if you want to Lookup a particular distance:

Counts@GraphDistance[net, g]

<|4 -> 4, 5 -> 12, 3 -> 7, 6 -> 26, 7 -> 20, 2 -> 7, 8 -> 15, 1 -> 6, 0 -> 1, 9 -> 2|>

Look them all up in order:

BinCounts[GraphDistance[net, g], {0, d, 1}]

{1, 6, 7, 7, 4, 12, 26, 20, 15, 2, 0, 0}

How to count all neighboring nodes within radius 'r' from the node 'g' ?

Use IGraph/M.

IGNeighborhoodSize does precisely this and is probably your fastest bet, but I do not have time to benchmark it against other solutions right now.

If you want to do it for multiple distances in one go, use IGDistanceCounts,

IGDistanceCounts[graph, {vertex}]

This gives you the counts of other vertices found at all (unweighted) distances. You can then simply Accumulate that list to get the result for all r at the same time.

For weighted distances, use IGDistanceHistogram.