Neighboring nodes in the networkTest 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 lengthSandbox algorithm for multifractal analysis of complex networks
Concept of linear mappings are confusing me
Why is this code 6.5x slower with optimizations enabled?
A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?
How is it possible for user's password to be changed after storage was encrypted? (on OS X, Android)
How to type dʒ symbol (IPA) on Mac?
Is there really no realistic way for a skeleton monster to move around without magic?
What defenses are there against being summoned by the Gate spell?
Can Medicine checks be used, with decent rolls, to completely mitigate the risk of death from ongoing damage?
Copycat chess is back
Why is an old chain unsafe?
Circuitry of TV splitters
Set-theoretical foundations of Mathematics with only bounded quantifiers
Is there a minimum number of transactions in a block?
How to make payment on the internet without leaving a money trail?
How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?
Copenhagen passport control - US citizen
Why is the design of haulage companies so “special”?
How does one intimidate enemies without having the capacity for violence?
What typically incentivizes a professor to change jobs to a lower ranking university?
How can bays and straits be determined in a procedurally generated map?
Why are only specific transaction types accepted into the mempool?
Could a US political party gain complete control over the government by removing checks & balances?
How to calculate implied correlation via observed market price (Margrabe option)
Infinite past with a beginning?
Neighboring nodes in the network
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 lengthSandbox algorithm for multifractal analysis of complex networks
$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.9k10311467
asked Apr 4 at 8:25
ralphralph
1687
$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.9k10311467
asked Apr 4 at 8:25
ralphralph
1687
$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.9k10311467
asked Apr 4 at 8:25
ralphralph
1687
$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.9k10311467
asked Apr 4 at 8:25
ralphralph
1687
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311467
asked Apr 4 at 8:25
ralphralph
1687
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311467
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311467
edited Apr 4 at 8:26
J. M. is away♦
98.9k10311467
98.9k10311467
asked Apr 4 at 8:25
ralphralph
1687
asked Apr 4 at 8:25
ralphralph
1687
asked Apr 4 at 8:25
ralphralph
1687
1687
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
57.6k6162282
$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.6k2544
$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
4,53011127
$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
163k14448945
$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
2 days ago
$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
2 days ago
$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
2 days ago
|
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
1687
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
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
57.6k6162282
$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
57.6k6162282
$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
57.6k6162282
$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
57.6k6162282
edited Apr 4 at 12:44
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
57.6k6162282
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
57.6k6162282
answered Apr 4 at 9:11
Vitaliy KaurovVitaliy Kaurov
57.6k6162282
57.6k6162282
$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.6k2544
$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.6k2544
$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.6k2544
$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.6k2544
edited 2 days ago
answered Apr 4 at 14:29
halmirhalmir
10.6k2544
answered Apr 4 at 14:29
halmirhalmir
10.6k2544
answered Apr 4 at 14:29
halmirhalmir
10.6k2544
10.6k2544
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
4,53011127
$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
4,53011127
$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
4,53011127
$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
4,53011127
edited Apr 4 at 12:19
answered Apr 4 at 9:04
RomanRoman
4,53011127
answered Apr 4 at 9:04
RomanRoman
4,53011127
answered Apr 4 at 9:04
RomanRoman
4,53011127
4,53011127
$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
163k14448945
$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
2 days ago
$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
2 days ago
$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
2 days ago
|
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
163k14448945
$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
2 days ago
$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
2 days ago
$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
2 days ago
|
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
163k14448945
$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
163k14448945
answered Apr 4 at 13:40
SzabolcsSzabolcs
163k14448945
answered Apr 4 at 13:40
SzabolcsSzabolcs
163k14448945
answered Apr 4 at 13:40
SzabolcsSzabolcs
163k14448945
163k14448945
$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
2 days ago
$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
2 days ago
$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
2 days ago
|
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
2 days ago
$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
2 days ago
$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
2 days ago
$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
2 days ago
$begingroup$
Mr=IGDistanceHistogram[net1, ??] (*for weighted graph *) ???
$endgroup$
– ralph
2 days ago
$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
2 days ago
$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
2 days ago
$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
2 days ago
$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
2 days ago
|
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
1687
$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
1687
$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
1687
$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
1687
answered Apr 4 at 17:40
ralphralph
1687
answered Apr 4 at 17:40
ralphralph
1687
answered Apr 4 at 17:40
ralphralph
1687
1687
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
