Thread: Networking

This is my dilemma:
Situation: n number of people are in a network. Each pair has a mutual distance they desire to be from each other. If there are discrepencies, all members compromise equally to adjust for the closest fit possible. E.G., A and B 1 unit; B and C 2 units; A and C 4 units. (Keep in 2D) Therefore, A and B add 1/3 unit, B and C add 1/3 unit, and A and C reduce 1/3 unit. Thus, each is as close to the desired distance as possible and all adjust equally.
Occassionally arbitrary choices must be made, e.g., four members all wanting to be 1 unit from each other. Some will have to adjust away and some toward. Which member goes which direction is arbitrary.
So, Any good way to do this?

Originally Posted by jakemalloy

This is my dilemma:
Situation: n number of people are in a network. Each pair has a mutual distance they desire to be from each other. If there are discrepencies, all members compromise equally to adjust for the closest fit possible. E.G., A and B 1 unit; B and C 2 units; A and C 4 units. (Keep in 2D) Therefore, A and B add 1/3 unit, B and C add 1/3 unit, and A and C reduce 1/3 unit. Thus, each is as close to the desired distance as possible and all adjust equally.
Occassionally arbitrary choices must be made, e.g., four members all wanting to be 1 unit from each other. Some will have to adjust away and some toward. Which member goes which direction is arbitrary.
So, Any good way to do this?

If it weren't for the restriction that all the discrepancies be equal I would
consider using either simulated annealing of a genetic optimisation algorithm
for this.

RonL

If you could give me more info about the algorithm you mentioned, maybe I can do something with it. The restriction is just to make it as "fair" as possible. So that everyone compromises.

Originally Posted by jakemalloy

If you could give me more info about the algorithm you mentioned, maybe I can do something with it. The restriction is just to make it as "fair" as possible. So that everyone compromises.

Wikkipedia-Simulated Annealing

Wikipedia-Genetic Algorithm

RonL

Thank you.

I'm pretty confident that this is above my capacity. But any more ideas regarding this is welcome.

Originally Posted by jakemalloy

I'm pretty confident that this is above my capacity. But any more ideas regarding this is welcome.

If the number of people is small-ish there is a possibility that this could
be done using the Excel solver, but it would be fussy to set up, and
probably max out at a fairly small number of people.

RonL

I need some analysis help.
What I have so far:
Finding and adjusting for a third point is cake.
For example. ab = 1, bc = 1, ac = 5. Find the discrepancy (3). Divide by 3 and adjust each by the result. [A little more involved to get a computer to do it but I can manage]
It works irrespective of which point is plotted first, which is a good thing. And each adjusts equally. I don’t know if this is helping or hurting my ability to generalize.

When I get to 2D it gets a lot harder for me. So, I started looking what I think is the simplest form in which a fourth point would be added. The first three points are equidistant. Let’s say, ab = 2, ac = 2, and bc = 2. And say the desired distance from D is the same, so that ad = 1, bd = 1, and cd = 1. So, the result will look something like the right hand picture. Then I found the ratio of AD:AB to be x: x(sqrt(3)). Then by guess and check I found the number that if each adjusted by it would actually produce the needed picture to be approx. .098076 [for some reason I’m blanking on how to find the real number by a method better than guess and check; feel free to advise me on this point]. Below is some guessing

New AB New AD Orig. - New AB Orig. - New AD closeness to equality
1.90194 1.098086 0.09806 0.098086 -2.6E-05
1.90193 1.09808 0.09807 0.09808 -9.8E-06
1.90192 1.098074 0.09808 0.098074 5.98E-06
1.901925 1.098077 0.098075 0.098077 -1.9E-06
1.901924 1.098076 0.098076 0.098076 -3.3E-07
1.901923 1.098076 0.098077 0.098076 1.24E-06
1.9019237 1.098076 0.098076 0.098076 1.4E-07
1.9019236 1.098076 0.098076 0.098076 2.98E-07


So, first I need the method by which I can find the exact number that would work in the case.
Second, I need to know what the significance of this number is, or how it should generalize.
Third, I need to make sure that if I would have encountered D before C, that the result would be the same.