Neighboring nodes in the network Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Test if directed graph is connectedWhy is NeighborhoodGraph so slow?How to add new nodes to an existing graph with fixed (coordinates) nodes?How do I upload a graph as an adjacency list and find the betweenness centrality?Arranging “ranked” nodes of a graph symmetricallyVertexLabels with Graph PropertiesNetwork with Radial Gradient Fill NodesHow to format vertices and control placement in a directed graphHow to label a large number of vertices using a list of namesColor the nodes according to certain valuesHighlight all paths in a graph below some threshold length
What are some likely causes to domain member PC losing contact to domain controller?
How can I prevent/balance waiting and turtling as a response to cooldown mechanics
Random body shuffle every night—can we still function?
First paper to introduce the "principal-agent problem"
Why are current probes so expensive?
Fit odd number of triplets in a measure?
"Destructive power" carried by a B-52?
Getting representations of the Lie group out of representations of its Lie algebra
Are there any irrational/transcendental numbers for which the distribution of decimal digits is not uniform?
Why do C and C++ allow the expression (int) + 4*5;
Is this Kuo-toa homebrew race balanced?
Is the Mordenkainen's Sword spell underpowered?
Why did Bronn offer to be Tyrion Lannister's champion in trial by combat?
Is it OK to use the testing sample to compare algorithms?
Weaponising the Grasp-at-a-Distance spell
Is there a verb for listening stealthily?
Is this Half-dragon Quaggoth boss monster balanced?
Is the time—manner—place ordering of adverbials an oversimplification?
How do Java 8 default methods hеlp with lambdas?
French equivalents of おしゃれは足元から (Every good outfit starts with the shoes)
Can two people see the same photon?
How to achieve cat-like agility?
Did John Wesley plagiarize Matthew Henry...?
Why are two-digit numbers in Jonathan Swift's "Gulliver's Travels" (1726) written in "German style"?
Neighboring nodes in the network
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Test if directed graph is connectedWhy is NeighborhoodGraph so slow?How to add new nodes to an existing graph with fixed (coordinates) nodes?How do I upload a graph as an adjacency list and find the betweenness centrality?Arranging “ranked” nodes of a graph symmetricallyVertexLabels with Graph PropertiesNetwork with Radial Gradient Fill NodesHow to format vertices and control placement in a directed graphHow to label a large number of vertices using a list of namesColor the nodes according to certain valuesHighlight all paths in a graph below some threshold length
$begingroup$
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.
graphs-and-networks
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
asked Apr 4 at 8:25
ralphralph
1907
$endgroup$
add a comment |
$begingroup$
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.
graphs-and-networks
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
asked Apr 4 at 8:25
ralphralph
1907
$endgroup$
add a comment |
$begingroup$
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.
graphs-and-networks
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
asked Apr 4 at 8:25
ralphralph
1907
$endgroup$
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.
graphs-and-networks
graphs-and-networks
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
asked Apr 4 at 8:25
ralphralph
1907
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
asked Apr 4 at 8:25
ralphralph
1907
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311468
98.9k10311468
asked Apr 4 at 8:25
ralphralph
1907
asked Apr 4 at 8:25
ralphralph
1907
asked Apr 4 at 8:25
ralphralph
1907
1907
add a comment |
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
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
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
$endgroup$
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15).
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
@ralph is 0.1 seconds is slow? What timings do you need? No criteria for timings is mentioned in your original post.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 12:41
$begingroup$
Please forgive me. I meant about 200,000 no 20,000 nodes.
$endgroup$
– ralph
Apr 4 at 12:57
$begingroup$
@Szabolcs i was just answering question without performance consideration as it was not asked in the OP, which had a tiny graph. I added benchmark after he made a comment, and then he changed his comment again.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 13:51
$begingroup$
@VitaliyKaurov Sorry about the comments, I was wrong: this was actually fixed in 12.0. That is why I deleted them.
$endgroup$
– Szabolcs
Apr 4 at 16:01
|
show 2 more comments
$begingroup$
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
For weighted graphs:
SeedRandom[123];net2 = Graph[net, EdgeWeight -> RandomInteger[1, 20, EdgeCount[net]]];
edgeWeight[g_, x_, y_] :=
With[weight = PropertyValue[g, UndirectedEdge[x, y],EdgeWeight],
If[NumericQ[weight], weight, 0]]
Clear[dist]; dist[_] := 0;
weights =
Reap[BreadthFirstScan[net2,
9, "DiscoverVertex" -> ((dist[#1] =
dist[#2] + edgeWeight[net2, #1, #2];
Sow[#1 -> dist[#1]]) &)]][[2, 1]];
set = Select[weights, #[[2]] <= 5 &];
set[[;; 10]]
9 -> 0, 66 -> 4, 126 -> 5, 160 -> 5, 190 -> 3, 274 -> 3, 283 -> 4,
312 -> 4, 519 -> 5, 537 -> 4
set // Length
105
Note that BreadthFirstScan approach might not work in general (non tree graphs).
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
$endgroup$
1
$begingroup$
Amazingly fast, halmir! Any idea why this solution is so much faster thanGraphDistance, which I would have thought works byBreadthFirstScaninternally?
$endgroup$
– Roman
Apr 4 at 16:05
1
$begingroup$
@Roman I had the conviction thatGraphDistancecompute the entireGraphDistanceMatrixeven if you gave it only one vertex. I do not remember what led me to this conclusion though. I do remember that I put a lot of effort into this functionality area in IGraph/M as I could not use M's built-ins for large graphs.
$endgroup$
– Szabolcs
Apr 4 at 16:14
$begingroup$
@Roman A qucik test tells me that on a tree (which is being benchmarked here) the complexity ofGraphDistanceis quadratic in the graph size even when given just one vertex. That should not be so.
$endgroup$
– Szabolcs
Apr 4 at 16:17
$begingroup$
@halmir Can you tell us whether this is a bug and if it is fixable? The quadratic complexity looks like a bug.
$endgroup$
– Szabolcs
Apr 4 at 16:20
$begingroup$
@Roman I strongly suspect that I may have reported this issue to Wolfram in the past. See e.g. this post I wrote 3 years ago, where I mention it: mathematica.stackexchange.com/a/109408/12
$endgroup$
– Szabolcs
Apr 4 at 16:30
|
show 7 more comments
$begingroup$
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
answered Apr 4 at 9:04
RomanRoman
5,93611131
$endgroup$
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15)
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Yes if you want only short distances then @szabolcs has better tools available. ThisGraphDistancesolution is only good if you want the distances to all nodes in the graph.
$endgroup$
– Roman
Apr 4 at 13:50
add a comment |
$begingroup$
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.
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
$endgroup$
$begingroup$
Thanks. And how to count the same as the 'IGDistanceCounts[graph, vertex]' formula but for weighted networks?
$endgroup$
– ralph
Apr 4 at 14:15
$begingroup$
@ralph As I said above, useIGDistanceHistogram
$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
Apr 5 at 6:19
$begingroup$
@ralph Did you check the documentation? If you checked the documentation and you found it to be unclear, you are very welcome to suggest improvements.
$endgroup$
– Szabolcs
Apr 5 at 7:16
$begingroup$
@ralph The syntax isIGDistanceHistogram[graph, binSize, vertex]wherebinSizeis the bin size used for constructing the distance histogram. You must put the vertex in a list as the syntax also accepts multiple vertices.
$endgroup$
– Szabolcs
Apr 5 at 7:17
|
show 5 more comments
$begingroup$
For weighted network:
g1 = 4798 <-> 2641, 4798 <-> 2310, 4798 <-> 4721, 2310 <-> 1942,2310 <-> 961, 4721 <-> 4507, 4721 <-> 4779, 4779 <-> 4336, 4779 <-> 3238, 4336 <-> 3277, 4336 <-> 3514, 3277 <-> 2923, 2923 <-> 2772, 2923 <-> 2401, 2772 <-> 2, 2772 <-> 2771, 3514 <-> 3042, 3514 <-> 2739, 3042 <-> 3007, 3042 <-> 1655, 2739 <-> 2277, 2739 <-> 1895, 2 <-> 5, 2 <-> 3, 3277 <-> 100, 5 <-> 6, 5 <-> 7, 5 <-> 8, 5 <-> 9;
w1 = 10, 20, 20, 4, 35, 3, 4, 6, 17, 7, 13, 2, 2, 7, 2, 1, 3, 5, 3, 6,4, 6, 2, 1, 1, 1, 1, 1, 1;
w2=Table[1, 29];
net1 = Graph[g1, EdgeWeight -> w1, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
net2 = Graph[g1, EdgeWeight -> w2, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
s = RandomSample[VertexList[net1], 15];
Mr = Table[IGDistanceCounts[net1, s[[i]]], i, 1, Length[s]] (*for non weighted*)
Mr2 = IGDistanceHistogram[net1, 9] (*for weighted graph ?*)
Mr3 = IGDistanceHistogram[net2, 9] (*for non weighted graph ? Mr3==Mr *)
answered Apr 4 at 17:40
ralphralph
1907
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "387"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f194581%2fneighboring-nodes-in-the-network%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
$endgroup$
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15).
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
@ralph is 0.1 seconds is slow? What timings do you need? No criteria for timings is mentioned in your original post.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 12:41
$begingroup$
Please forgive me. I meant about 200,000 no 20,000 nodes.
$endgroup$
– ralph
Apr 4 at 12:57
$begingroup$
@Szabolcs i was just answering question without performance consideration as it was not asked in the OP, which had a tiny graph. I added benchmark after he made a comment, and then he changed his comment again.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 13:51
$begingroup$
@VitaliyKaurov Sorry about the comments, I was wrong: this was actually fixed in 12.0. That is why I deleted them.
$endgroup$
– Szabolcs
Apr 4 at 16:01
|
show 2 more comments
$begingroup$
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
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
$endgroup$
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15).
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
@ralph is 0.1 seconds is slow? What timings do you need? No criteria for timings is mentioned in your original post.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 12:41
$begingroup$
Please forgive me. I meant about 200,000 no 20,000 nodes.
$endgroup$
– ralph
Apr 4 at 12:57
$begingroup$
@Szabolcs i was just answering question without performance consideration as it was not asked in the OP, which had a tiny graph. I added benchmark after he made a comment, and then he changed his comment again.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 13:51
$begingroup$
@VitaliyKaurov Sorry about the comments, I was wrong: this was actually fixed in 12.0. That is why I deleted them.
$endgroup$
– Szabolcs
Apr 4 at 16:01
|
show 2 more comments
$begingroup$
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
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
$endgroup$
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
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
edited Apr 4 at 12:44
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
58k6163285
58k6163285
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15).
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
@ralph is 0.1 seconds is slow? What timings do you need? No criteria for timings is mentioned in your original post.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 12:41
$begingroup$
Please forgive me. I meant about 200,000 no 20,000 nodes.
$endgroup$
– ralph
Apr 4 at 12:57
$begingroup$
@Szabolcs i was just answering question without performance consideration as it was not asked in the OP, which had a tiny graph. I added benchmark after he made a comment, and then he changed his comment again.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 13:51
$begingroup$
@VitaliyKaurov Sorry about the comments, I was wrong: this was actually fixed in 12.0. That is why I deleted them.
$endgroup$
– Szabolcs
Apr 4 at 16:01
|
show 2 more comments
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15).
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
@ralph is 0.1 seconds is slow? What timings do you need? No criteria for timings is mentioned in your original post.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 12:41
$begingroup$
Please forgive me. I meant about 200,000 no 20,000 nodes.
$endgroup$
– ralph
Apr 4 at 12:57
$begingroup$
@Szabolcs i was just answering question without performance consideration as it was not asked in the OP, which had a tiny graph. I added benchmark after he made a comment, and then he changed his comment again.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 13:51
$begingroup$
@VitaliyKaurov Sorry about the comments, I was wrong: this was actually fixed in 12.0. That is why I deleted them.
$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15).
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15).
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
@ralph is 0.1 seconds is slow? What timings do you need? No criteria for timings is mentioned in your original post.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 12:41
$begingroup$
@ralph is 0.1 seconds is slow? What timings do you need? No criteria for timings is mentioned in your original post.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 12:41
$begingroup$
Please forgive me. I meant about 200,000 no 20,000 nodes.
$endgroup$
– ralph
Apr 4 at 12:57
$begingroup$
Please forgive me. I meant about 200,000 no 20,000 nodes.
$endgroup$
– ralph
Apr 4 at 12:57
$begingroup$
@Szabolcs i was just answering question without performance consideration as it was not asked in the OP, which had a tiny graph. I added benchmark after he made a comment, and then he changed his comment again.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 13:51
$begingroup$
@Szabolcs i was just answering question without performance consideration as it was not asked in the OP, which had a tiny graph. I added benchmark after he made a comment, and then he changed his comment again.
$endgroup$
– Vitaliy Kaurov
Apr 4 at 13:51
$begingroup$
@VitaliyKaurov Sorry about the comments, I was wrong: this was actually fixed in 12.0. That is why I deleted them.
$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
@VitaliyKaurov Sorry about the comments, I was wrong: this was actually fixed in 12.0. That is why I deleted them.
$endgroup$
– Szabolcs
Apr 4 at 16:01
|
show 2 more comments
$begingroup$
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
For weighted graphs:
SeedRandom[123];net2 = Graph[net, EdgeWeight -> RandomInteger[1, 20, EdgeCount[net]]];
edgeWeight[g_, x_, y_] :=
With[weight = PropertyValue[g, UndirectedEdge[x, y],EdgeWeight],
If[NumericQ[weight], weight, 0]]
Clear[dist]; dist[_] := 0;
weights =
Reap[BreadthFirstScan[net2,
9, "DiscoverVertex" -> ((dist[#1] =
dist[#2] + edgeWeight[net2, #1, #2];
Sow[#1 -> dist[#1]]) &)]][[2, 1]];
set = Select[weights, #[[2]] <= 5 &];
set[[;; 10]]
9 -> 0, 66 -> 4, 126 -> 5, 160 -> 5, 190 -> 3, 274 -> 3, 283 -> 4,
312 -> 4, 519 -> 5, 537 -> 4
set // Length
105
Note that BreadthFirstScan approach might not work in general (non tree graphs).
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
$endgroup$
1
$begingroup$
Amazingly fast, halmir! Any idea why this solution is so much faster thanGraphDistance, which I would have thought works byBreadthFirstScaninternally?
$endgroup$
– Roman
Apr 4 at 16:05
1
$begingroup$
@Roman I had the conviction thatGraphDistancecompute the entireGraphDistanceMatrixeven if you gave it only one vertex. I do not remember what led me to this conclusion though. I do remember that I put a lot of effort into this functionality area in IGraph/M as I could not use M's built-ins for large graphs.
$endgroup$
– Szabolcs
Apr 4 at 16:14
$begingroup$
@Roman A qucik test tells me that on a tree (which is being benchmarked here) the complexity ofGraphDistanceis quadratic in the graph size even when given just one vertex. That should not be so.
$endgroup$
– Szabolcs
Apr 4 at 16:17
$begingroup$
@halmir Can you tell us whether this is a bug and if it is fixable? The quadratic complexity looks like a bug.
$endgroup$
– Szabolcs
Apr 4 at 16:20
$begingroup$
@Roman I strongly suspect that I may have reported this issue to Wolfram in the past. See e.g. this post I wrote 3 years ago, where I mention it: mathematica.stackexchange.com/a/109408/12
$endgroup$
– Szabolcs
Apr 4 at 16:30
|
show 7 more comments
$begingroup$
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
For weighted graphs:
SeedRandom[123];net2 = Graph[net, EdgeWeight -> RandomInteger[1, 20, EdgeCount[net]]];
edgeWeight[g_, x_, y_] :=
With[weight = PropertyValue[g, UndirectedEdge[x, y],EdgeWeight],
If[NumericQ[weight], weight, 0]]
Clear[dist]; dist[_] := 0;
weights =
Reap[BreadthFirstScan[net2,
9, "DiscoverVertex" -> ((dist[#1] =
dist[#2] + edgeWeight[net2, #1, #2];
Sow[#1 -> dist[#1]]) &)]][[2, 1]];
set = Select[weights, #[[2]] <= 5 &];
set[[;; 10]]
9 -> 0, 66 -> 4, 126 -> 5, 160 -> 5, 190 -> 3, 274 -> 3, 283 -> 4,
312 -> 4, 519 -> 5, 537 -> 4
set // Length
105
Note that BreadthFirstScan approach might not work in general (non tree graphs).
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
$endgroup$
1
$begingroup$
Amazingly fast, halmir! Any idea why this solution is so much faster thanGraphDistance, which I would have thought works byBreadthFirstScaninternally?
$endgroup$
– Roman
Apr 4 at 16:05
1
$begingroup$
@Roman I had the conviction thatGraphDistancecompute the entireGraphDistanceMatrixeven if you gave it only one vertex. I do not remember what led me to this conclusion though. I do remember that I put a lot of effort into this functionality area in IGraph/M as I could not use M's built-ins for large graphs.
$endgroup$
– Szabolcs
Apr 4 at 16:14
$begingroup$
@Roman A qucik test tells me that on a tree (which is being benchmarked here) the complexity ofGraphDistanceis quadratic in the graph size even when given just one vertex. That should not be so.
$endgroup$
– Szabolcs
Apr 4 at 16:17
$begingroup$
@halmir Can you tell us whether this is a bug and if it is fixable? The quadratic complexity looks like a bug.
$endgroup$
– Szabolcs
Apr 4 at 16:20
$begingroup$
@Roman I strongly suspect that I may have reported this issue to Wolfram in the past. See e.g. this post I wrote 3 years ago, where I mention it: mathematica.stackexchange.com/a/109408/12
$endgroup$
– Szabolcs
Apr 4 at 16:30
|
show 7 more comments
$begingroup$
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
For weighted graphs:
SeedRandom[123];net2 = Graph[net, EdgeWeight -> RandomInteger[1, 20, EdgeCount[net]]];
edgeWeight[g_, x_, y_] :=
With[weight = PropertyValue[g, UndirectedEdge[x, y],EdgeWeight],
If[NumericQ[weight], weight, 0]]
Clear[dist]; dist[_] := 0;
weights =
Reap[BreadthFirstScan[net2,
9, "DiscoverVertex" -> ((dist[#1] =
dist[#2] + edgeWeight[net2, #1, #2];
Sow[#1 -> dist[#1]]) &)]][[2, 1]];
set = Select[weights, #[[2]] <= 5 &];
set[[;; 10]]
9 -> 0, 66 -> 4, 126 -> 5, 160 -> 5, 190 -> 3, 274 -> 3, 283 -> 4,
312 -> 4, 519 -> 5, 537 -> 4
set // Length
105
Note that BreadthFirstScan approach might not work in general (non tree graphs).
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
$endgroup$
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
For weighted graphs:
SeedRandom[123];net2 = Graph[net, EdgeWeight -> RandomInteger[1, 20, EdgeCount[net]]];
edgeWeight[g_, x_, y_] :=
With[weight = PropertyValue[g, UndirectedEdge[x, y],EdgeWeight],
If[NumericQ[weight], weight, 0]]
Clear[dist]; dist[_] := 0;
weights =
Reap[BreadthFirstScan[net2,
9, "DiscoverVertex" -> ((dist[#1] =
dist[#2] + edgeWeight[net2, #1, #2];
Sow[#1 -> dist[#1]]) &)]][[2, 1]];
set = Select[weights, #[[2]] <= 5 &];
set[[;; 10]]
9 -> 0, 66 -> 4, 126 -> 5, 160 -> 5, 190 -> 3, 274 -> 3, 283 -> 4,
312 -> 4, 519 -> 5, 537 -> 4
set // Length
105
Note that BreadthFirstScan approach might not work in general (non tree graphs).
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
edited Apr 5 at 14:07
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
answered Apr 4 at 14:29
halmirhalmir
10.8k2544
10.8k2544
1
$begingroup$
Amazingly fast, halmir! Any idea why this solution is so much faster thanGraphDistance, which I would have thought works byBreadthFirstScaninternally?
$endgroup$
– Roman
Apr 4 at 16:05
1
$begingroup$
@Roman I had the conviction thatGraphDistancecompute the entireGraphDistanceMatrixeven if you gave it only one vertex. I do not remember what led me to this conclusion though. I do remember that I put a lot of effort into this functionality area in IGraph/M as I could not use M's built-ins for large graphs.
$endgroup$
– Szabolcs
Apr 4 at 16:14
$begingroup$
@Roman A qucik test tells me that on a tree (which is being benchmarked here) the complexity ofGraphDistanceis quadratic in the graph size even when given just one vertex. That should not be so.
$endgroup$
– Szabolcs
Apr 4 at 16:17
$begingroup$
@halmir Can you tell us whether this is a bug and if it is fixable? The quadratic complexity looks like a bug.
$endgroup$
– Szabolcs
Apr 4 at 16:20
$begingroup$
@Roman I strongly suspect that I may have reported this issue to Wolfram in the past. See e.g. this post I wrote 3 years ago, where I mention it: mathematica.stackexchange.com/a/109408/12
$endgroup$
– Szabolcs
Apr 4 at 16:30
|
show 7 more comments
1
$begingroup$
Amazingly fast, halmir! Any idea why this solution is so much faster thanGraphDistance, which I would have thought works byBreadthFirstScaninternally?
$endgroup$
– Roman
Apr 4 at 16:05
1
$begingroup$
@Roman I had the conviction thatGraphDistancecompute the entireGraphDistanceMatrixeven if you gave it only one vertex. I do not remember what led me to this conclusion though. I do remember that I put a lot of effort into this functionality area in IGraph/M as I could not use M's built-ins for large graphs.
$endgroup$
– Szabolcs
Apr 4 at 16:14
$begingroup$
@Roman A qucik test tells me that on a tree (which is being benchmarked here) the complexity ofGraphDistanceis quadratic in the graph size even when given just one vertex. That should not be so.
$endgroup$
– Szabolcs
Apr 4 at 16:17
$begingroup$
@halmir Can you tell us whether this is a bug and if it is fixable? The quadratic complexity looks like a bug.
$endgroup$
– Szabolcs
Apr 4 at 16:20
$begingroup$
@Roman I strongly suspect that I may have reported this issue to Wolfram in the past. See e.g. this post I wrote 3 years ago, where I mention it: mathematica.stackexchange.com/a/109408/12
$endgroup$
– Szabolcs
Apr 4 at 16:30
1
1
$begingroup$
Amazingly fast, halmir! Any idea why this solution is so much faster than
GraphDistance, which I would have thought works by BreadthFirstScan internally?$endgroup$
– Roman
Apr 4 at 16:05
$begingroup$
Amazingly fast, halmir! Any idea why this solution is so much faster than
GraphDistance, which I would have thought works by BreadthFirstScan internally?$endgroup$
– Roman
Apr 4 at 16:05
1
1
$begingroup$
@Roman I had the conviction that
GraphDistance compute the entire GraphDistanceMatrix even if you gave it only one vertex. I do not remember what led me to this conclusion though. I do remember that I put a lot of effort into this functionality area in IGraph/M as I could not use M's built-ins for large graphs.$endgroup$
– Szabolcs
Apr 4 at 16:14
$begingroup$
@Roman I had the conviction that
GraphDistance compute the entire GraphDistanceMatrix even if you gave it only one vertex. I do not remember what led me to this conclusion though. I do remember that I put a lot of effort into this functionality area in IGraph/M as I could not use M's built-ins for large graphs.$endgroup$
– Szabolcs
Apr 4 at 16:14
$begingroup$
@Roman A qucik test tells me that on a tree (which is being benchmarked here) the complexity of
GraphDistance is quadratic in the graph size even when given just one vertex. That should not be so.$endgroup$
– Szabolcs
Apr 4 at 16:17
$begingroup$
@Roman A qucik test tells me that on a tree (which is being benchmarked here) the complexity of
GraphDistance is quadratic in the graph size even when given just one vertex. That should not be so.$endgroup$
– Szabolcs
Apr 4 at 16:17
$begingroup$
@halmir Can you tell us whether this is a bug and if it is fixable? The quadratic complexity looks like a bug.
$endgroup$
– Szabolcs
Apr 4 at 16:20
$begingroup$
@halmir Can you tell us whether this is a bug and if it is fixable? The quadratic complexity looks like a bug.
$endgroup$
– Szabolcs
Apr 4 at 16:20
$begingroup$
@Roman I strongly suspect that I may have reported this issue to Wolfram in the past. See e.g. this post I wrote 3 years ago, where I mention it: mathematica.stackexchange.com/a/109408/12
$endgroup$
– Szabolcs
Apr 4 at 16:30
$begingroup$
@Roman I strongly suspect that I may have reported this issue to Wolfram in the past. See e.g. this post I wrote 3 years ago, where I mention it: mathematica.stackexchange.com/a/109408/12
$endgroup$
– Szabolcs
Apr 4 at 16:30
|
show 7 more comments
$begingroup$
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
answered Apr 4 at 9:04
RomanRoman
5,93611131
$endgroup$
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15)
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Yes if you want only short distances then @szabolcs has better tools available. ThisGraphDistancesolution is only good if you want the distances to all nodes in the graph.
$endgroup$
– Roman
Apr 4 at 13:50
add a comment |
$begingroup$
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
answered Apr 4 at 9:04
RomanRoman
5,93611131
$endgroup$
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15)
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Yes if you want only short distances then @szabolcs has better tools available. ThisGraphDistancesolution is only good if you want the distances to all nodes in the graph.
$endgroup$
– Roman
Apr 4 at 13:50
add a comment |
$begingroup$
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
answered Apr 4 at 9:04
RomanRoman
5,93611131
$endgroup$
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
answered Apr 4 at 9:04
RomanRoman
5,93611131
edited Apr 4 at 12:19
answered Apr 4 at 9:04
RomanRoman
5,93611131
answered Apr 4 at 9:04
RomanRoman
5,93611131
answered Apr 4 at 9:04
RomanRoman
5,93611131
5,93611131
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15)
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Yes if you want only short distances then @szabolcs has better tools available. ThisGraphDistancesolution is only good if you want the distances to all nodes in the graph.
$endgroup$
– Roman
Apr 4 at 13:50
add a comment |
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15)
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Yes if you want only short distances then @szabolcs has better tools available. ThisGraphDistancesolution is only good if you want the distances to all nodes in the graph.
$endgroup$
– Roman
Apr 4 at 13:50
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15)
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Thank you. The code gives correct results but is memory-consuming for large networks (around 200,000 nodes: net = RandomGraph [BarabasiAlbertGraphDistribution [20,000, 1] and d = 1,2,3,4, ..., 15)
$endgroup$
– ralph
Apr 4 at 12:24
$begingroup$
Yes if you want only short distances then @szabolcs has better tools available. This
GraphDistance solution is only good if you want the distances to all nodes in the graph.$endgroup$
– Roman
Apr 4 at 13:50
$begingroup$
Yes if you want only short distances then @szabolcs has better tools available. This
GraphDistance solution is only good if you want the distances to all nodes in the graph.$endgroup$
– Roman
Apr 4 at 13:50
add a comment |
$begingroup$
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.
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
$endgroup$
$begingroup$
Thanks. And how to count the same as the 'IGDistanceCounts[graph, vertex]' formula but for weighted networks?
$endgroup$
– ralph
Apr 4 at 14:15
$begingroup$
@ralph As I said above, useIGDistanceHistogram
$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
Apr 5 at 6:19
$begingroup$
@ralph Did you check the documentation? If you checked the documentation and you found it to be unclear, you are very welcome to suggest improvements.
$endgroup$
– Szabolcs
Apr 5 at 7:16
$begingroup$
@ralph The syntax isIGDistanceHistogram[graph, binSize, vertex]wherebinSizeis the bin size used for constructing the distance histogram. You must put the vertex in a list as the syntax also accepts multiple vertices.
$endgroup$
– Szabolcs
Apr 5 at 7:17
|
show 5 more comments
$begingroup$
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.
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
$endgroup$
$begingroup$
Thanks. And how to count the same as the 'IGDistanceCounts[graph, vertex]' formula but for weighted networks?
$endgroup$
– ralph
Apr 4 at 14:15
$begingroup$
@ralph As I said above, useIGDistanceHistogram
$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
Apr 5 at 6:19
$begingroup$
@ralph Did you check the documentation? If you checked the documentation and you found it to be unclear, you are very welcome to suggest improvements.
$endgroup$
– Szabolcs
Apr 5 at 7:16
$begingroup$
@ralph The syntax isIGDistanceHistogram[graph, binSize, vertex]wherebinSizeis the bin size used for constructing the distance histogram. You must put the vertex in a list as the syntax also accepts multiple vertices.
$endgroup$
– Szabolcs
Apr 5 at 7:17
|
show 5 more comments
$begingroup$
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.
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
$endgroup$
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.
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
answered Apr 4 at 13:40
SzabolcsSzabolcs
165k14450954
165k14450954
$begingroup$
Thanks. And how to count the same as the 'IGDistanceCounts[graph, vertex]' formula but for weighted networks?
$endgroup$
– ralph
Apr 4 at 14:15
$begingroup$
@ralph As I said above, useIGDistanceHistogram
$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
Apr 5 at 6:19
$begingroup$
@ralph Did you check the documentation? If you checked the documentation and you found it to be unclear, you are very welcome to suggest improvements.
$endgroup$
– Szabolcs
Apr 5 at 7:16
$begingroup$
@ralph The syntax isIGDistanceHistogram[graph, binSize, vertex]wherebinSizeis the bin size used for constructing the distance histogram. You must put the vertex in a list as the syntax also accepts multiple vertices.
$endgroup$
– Szabolcs
Apr 5 at 7:17
|
show 5 more comments
$begingroup$
Thanks. And how to count the same as the 'IGDistanceCounts[graph, vertex]' formula but for weighted networks?
$endgroup$
– ralph
Apr 4 at 14:15
$begingroup$
@ralph As I said above, useIGDistanceHistogram
$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
Apr 5 at 6:19
$begingroup$
@ralph Did you check the documentation? If you checked the documentation and you found it to be unclear, you are very welcome to suggest improvements.
$endgroup$
– Szabolcs
Apr 5 at 7:16
$begingroup$
@ralph The syntax isIGDistanceHistogram[graph, binSize, vertex]wherebinSizeis the bin size used for constructing the distance histogram. You must put the vertex in a list as the syntax also accepts multiple vertices.
$endgroup$
– Szabolcs
Apr 5 at 7:17
$begingroup$
Thanks. And how to count the same as the 'IGDistanceCounts[graph, vertex]' formula but for weighted networks?
$endgroup$
– ralph
Apr 4 at 14:15
$begingroup$
Thanks. And how to count the same as the 'IGDistanceCounts[graph, vertex]' formula but for weighted networks?
$endgroup$
– ralph
Apr 4 at 14:15
$begingroup$
@ralph As I said above, use
IGDistanceHistogram$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
@ralph As I said above, use
IGDistanceHistogram$endgroup$
– Szabolcs
Apr 4 at 16:01
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
Apr 5 at 6:19
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
Apr 5 at 6:19
$begingroup$
@ralph Did you check the documentation? If you checked the documentation and you found it to be unclear, you are very welcome to suggest improvements.
$endgroup$
– Szabolcs
Apr 5 at 7:16
$begingroup$
@ralph Did you check the documentation? If you checked the documentation and you found it to be unclear, you are very welcome to suggest improvements.
$endgroup$
– Szabolcs
Apr 5 at 7:16
$begingroup$
@ralph The syntax is
IGDistanceHistogram[graph, binSize, vertex] where binSize is the bin size used for constructing the distance histogram. You must put the vertex in a list as the syntax also accepts multiple vertices.$endgroup$
– Szabolcs
Apr 5 at 7:17
$begingroup$
@ralph The syntax is
IGDistanceHistogram[graph, binSize, vertex] where binSize is the bin size used for constructing the distance histogram. You must put the vertex in a list as the syntax also accepts multiple vertices.$endgroup$
– Szabolcs
Apr 5 at 7:17
|
show 5 more comments
$begingroup$
For weighted network:
g1 = 4798 <-> 2641, 4798 <-> 2310, 4798 <-> 4721, 2310 <-> 1942,2310 <-> 961, 4721 <-> 4507, 4721 <-> 4779, 4779 <-> 4336, 4779 <-> 3238, 4336 <-> 3277, 4336 <-> 3514, 3277 <-> 2923, 2923 <-> 2772, 2923 <-> 2401, 2772 <-> 2, 2772 <-> 2771, 3514 <-> 3042, 3514 <-> 2739, 3042 <-> 3007, 3042 <-> 1655, 2739 <-> 2277, 2739 <-> 1895, 2 <-> 5, 2 <-> 3, 3277 <-> 100, 5 <-> 6, 5 <-> 7, 5 <-> 8, 5 <-> 9;
w1 = 10, 20, 20, 4, 35, 3, 4, 6, 17, 7, 13, 2, 2, 7, 2, 1, 3, 5, 3, 6,4, 6, 2, 1, 1, 1, 1, 1, 1;
w2=Table[1, 29];
net1 = Graph[g1, EdgeWeight -> w1, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
net2 = Graph[g1, EdgeWeight -> w2, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
s = RandomSample[VertexList[net1], 15];
Mr = Table[IGDistanceCounts[net1, s[[i]]], i, 1, Length[s]] (*for non weighted*)
Mr2 = IGDistanceHistogram[net1, 9] (*for weighted graph ?*)
Mr3 = IGDistanceHistogram[net2, 9] (*for non weighted graph ? Mr3==Mr *)
answered Apr 4 at 17:40
ralphralph
1907
$endgroup$
add a comment |
$begingroup$
For weighted network:
g1 = 4798 <-> 2641, 4798 <-> 2310, 4798 <-> 4721, 2310 <-> 1942,2310 <-> 961, 4721 <-> 4507, 4721 <-> 4779, 4779 <-> 4336, 4779 <-> 3238, 4336 <-> 3277, 4336 <-> 3514, 3277 <-> 2923, 2923 <-> 2772, 2923 <-> 2401, 2772 <-> 2, 2772 <-> 2771, 3514 <-> 3042, 3514 <-> 2739, 3042 <-> 3007, 3042 <-> 1655, 2739 <-> 2277, 2739 <-> 1895, 2 <-> 5, 2 <-> 3, 3277 <-> 100, 5 <-> 6, 5 <-> 7, 5 <-> 8, 5 <-> 9;
w1 = 10, 20, 20, 4, 35, 3, 4, 6, 17, 7, 13, 2, 2, 7, 2, 1, 3, 5, 3, 6,4, 6, 2, 1, 1, 1, 1, 1, 1;
w2=Table[1, 29];
net1 = Graph[g1, EdgeWeight -> w1, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
net2 = Graph[g1, EdgeWeight -> w2, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
s = RandomSample[VertexList[net1], 15];
Mr = Table[IGDistanceCounts[net1, s[[i]]], i, 1, Length[s]] (*for non weighted*)
Mr2 = IGDistanceHistogram[net1, 9] (*for weighted graph ?*)
Mr3 = IGDistanceHistogram[net2, 9] (*for non weighted graph ? Mr3==Mr *)
answered Apr 4 at 17:40
ralphralph
1907
$endgroup$
add a comment |
$begingroup$
For weighted network:
g1 = 4798 <-> 2641, 4798 <-> 2310, 4798 <-> 4721, 2310 <-> 1942,2310 <-> 961, 4721 <-> 4507, 4721 <-> 4779, 4779 <-> 4336, 4779 <-> 3238, 4336 <-> 3277, 4336 <-> 3514, 3277 <-> 2923, 2923 <-> 2772, 2923 <-> 2401, 2772 <-> 2, 2772 <-> 2771, 3514 <-> 3042, 3514 <-> 2739, 3042 <-> 3007, 3042 <-> 1655, 2739 <-> 2277, 2739 <-> 1895, 2 <-> 5, 2 <-> 3, 3277 <-> 100, 5 <-> 6, 5 <-> 7, 5 <-> 8, 5 <-> 9;
w1 = 10, 20, 20, 4, 35, 3, 4, 6, 17, 7, 13, 2, 2, 7, 2, 1, 3, 5, 3, 6,4, 6, 2, 1, 1, 1, 1, 1, 1;
w2=Table[1, 29];
net1 = Graph[g1, EdgeWeight -> w1, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
net2 = Graph[g1, EdgeWeight -> w2, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
s = RandomSample[VertexList[net1], 15];
Mr = Table[IGDistanceCounts[net1, s[[i]]], i, 1, Length[s]] (*for non weighted*)
Mr2 = IGDistanceHistogram[net1, 9] (*for weighted graph ?*)
Mr3 = IGDistanceHistogram[net2, 9] (*for non weighted graph ? Mr3==Mr *)
answered Apr 4 at 17:40
ralphralph
1907
$endgroup$
For weighted network:
g1 = 4798 <-> 2641, 4798 <-> 2310, 4798 <-> 4721, 2310 <-> 1942,2310 <-> 961, 4721 <-> 4507, 4721 <-> 4779, 4779 <-> 4336, 4779 <-> 3238, 4336 <-> 3277, 4336 <-> 3514, 3277 <-> 2923, 2923 <-> 2772, 2923 <-> 2401, 2772 <-> 2, 2772 <-> 2771, 3514 <-> 3042, 3514 <-> 2739, 3042 <-> 3007, 3042 <-> 1655, 2739 <-> 2277, 2739 <-> 1895, 2 <-> 5, 2 <-> 3, 3277 <-> 100, 5 <-> 6, 5 <-> 7, 5 <-> 8, 5 <-> 9;
w1 = 10, 20, 20, 4, 35, 3, 4, 6, 17, 7, 13, 2, 2, 7, 2, 1, 3, 5, 3, 6,4, 6, 2, 1, 1, 1, 1, 1, 1;
w2=Table[1, 29];
net1 = Graph[g1, EdgeWeight -> w1, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
net2 = Graph[g1, EdgeWeight -> w2, EdgeLabels -> "EdgeWeight", VertexShapeFunction -> "Name"]
s = RandomSample[VertexList[net1], 15];
Mr = Table[IGDistanceCounts[net1, s[[i]]], i, 1, Length[s]] (*for non weighted*)
Mr2 = IGDistanceHistogram[net1, 9] (*for weighted graph ?*)
Mr3 = IGDistanceHistogram[net2, 9] (*for non weighted graph ? Mr3==Mr *)
answered Apr 4 at 17:40
ralphralph
1907
answered Apr 4 at 17:40
ralphralph
1907
answered Apr 4 at 17:40
ralphralph
1907
answered Apr 4 at 17:40
ralphralph
1907
1907
add a comment |
add a comment |
Thanks for contributing an answer to Mathematica Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathematica.stackexchange.com%2fquestions%2f194581%2fneighboring-nodes-in-the-network%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
