analytics

Monday, May 13, 2013

Redistribution network

I was thinking to study a network like so: suppose you have a graph, this one is simple but they don't have to be:




Now consider this matrix, the letters on the left are just labeling the rows: 

Now imagine what each cell in the matrix represents is how much of each different variable each node has in its inventory. Here I've started every node off with 1 unit of it's own variable, but they could start in any way.

Then they go through this cycle, every node divides what it has in it's inventory among the nodes it is connected to. For example A in the graph diagram is connected to B,E, and F. and it has in it's inventory A, so it will give (1/3)A to B, (1/3)A to E, and (1/3)A to F. At the same time every node distributes what is in it's inventory to all the other nodes. So after one iteration you have:
So F has 5 connections to A, D, E, G, and H. It gets a share from each of those nodes that depends on the number of nodes those nodes are connected to. Like row F and column E is 1/4 because E is connected to 4 nodes of which F is one, and E had previously just had one E in it's row.

After another iteration (rounded to maximum of 3 decimal places):
[0.261, 0.083, 0.111, 0.113, 0.133, 0.05 , 0.1     , 0.05  , 0.0   ,  0.0    ],
[0.083, 0.305, 0.0    , 0.145, 0.083, 0.116, 0.0    , 0.0    , 0.083, 0.0    ],
[0.111, 0.0    , 0.277, 0.062, 0.145, 0.05  , 0.0    , 0.062, 0.062, 0.125],
[0.15  , 0.194, 0.083, 0.258, 0.05  , 0.05  , 0.1    , 0.113, 0.083, 0.125],
[0.177, 0.11  , 0.194, 0.05  , 0.279, 0.116, 0.1    , 0.05  , 0.063, 0.0    ],
[0.083, 0.194, 0.083, 0.063, 0.145, 0.316, 0.125, 0.125, 0.125, 0.125],
[0.066, 0.0    , 0.0    , 0.05  , 0.05  , 0.05  , 0.225, 0.05  , 0.063, 0.125],
[0.066, 0.0    , 0.083, 0.113, 0.05  , 0.1    , 0.1    , 0.363, 0.125, 0.125],
[0.0    , 0.111, 0.083, 0.083, 0.063, 0.1    , 0.125, 0.125, 0.333, 0.125],
[0.0    , 0.0    , 0.083, 0.063, 0.0    , 0.05  , 0.125, 0.063, 0.063, 0.25  ]

Here row A and column A is .261 because A gets 1/3 of every part of B's inventory but B had 1/3 A so A gets 1/9 from B. And similarly 1/12 and 1/15 from E and F, added together that is .261.

After 100 iterations:

[[0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088],
 [0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088],
[0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088, 0.088],
[0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118],
[0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118],
[0.147, 0.147, 0.147, 0.147, 0.147, 0.147, 0.147, 0.147, 0.147, 0.147]
[0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058],
[0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118],
[0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118, 0.118],
 [0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058],
[0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058, 0.058],

It ends up all of these numbers are approached as limits! 30 Iterations is correct to about 3 decimal places and they get closer and closer.

**EDIT**
I found a way to find these numbers exactly. Imagine that the process iterated until it reached the limits. That would mean in another iteration, the amount going into each node would match the amount going out. That would mean that the new amount in A for example would be 1/3 B, 1/4 E, 1/5 F. So we can write out the equations:
Here there would be 10 equations one for each node, but you remove one or otherwise the solutions would be 0 for all variables. In the removed equations place you put A+B+C+D+E+F+G+H+J+K=1. That's the other constraint on the system. Then the solutions are:

And it appears that the bottom number of these fractions is twice the number of edges in the graph and the top number is the number of edges coming from the vertex.

No comments:

Post a Comment