Matthew Toseland wrote:
Swapping creates this problem. Or does it? Could you perhaps do some
simulations of two networks of different sizes weakly linked and show whether
they get independant location spaces, or whether swapping tries to put one of
them within the global keyspace for the other?
Here's a quick simulation that shows that two weakly-connected subnets
move into separate regions of the key space. Each subnet has an ideal
Kleinberg topology and starts out uniformly distributed across the whole
key space, and there are also a few random links between the subnets -
this is meant to represent what would happen if you created a few links
between two mature networks, or between a real network and a Sybil network.
I couldn't be bothered to do a nice GUI so the output is just a series
of histograms: on each line the key space is divided into 20 regions,
and each column shows the number of nodes from the first subnet in that
region. Initially there are roughly 50 nodes in each region, but
swapping causes the subnets to segregate so that eventually most regions
are almost exclusively occupied by one subnet or the other.
It's kind of interesting to compare this with "white flight" in sociology...
Cheers,
Michael
import java.util.ArrayList;
import java.util.HashSet;
class Simulation
{
// We don't need to steenkin command line arguments, we got constants
static final int REDS = 1000, BLACKS = 1000, NODES = REDS + BLACKS;
static final int DEGREE = 10, JOINS = 5, COLUMNS = 20;
static final int ROUNDS = 100, SWAPS_PER_ROUND = 1000 * 1000;
ArrayList<Node> reds, blacks, nodes;
int[] loc = new int[COLUMNS];
Simulation()
{
// Create two separate networks each covering the whole keyspace
reds = new ArrayList<Node> (REDS);
for (int i = 0; i < REDS; i++) reds.add (new Node());
makeKleinbergNetwork (reds);
blacks = new ArrayList<Node> (BLACKS);
for (int i = 0; i < BLACKS; i++) blacks.add (new Node());
makeKleinbergNetwork (blacks);
// Join the networks at a few randomly chosen points
for (int i = 0; i < JOINS; i++) {
Node a = reds.get ((int) (Math.random() * REDS));
Node b = blacks.get ((int) (Math.random() * BLACKS));
a.neighbours.add (b);
b.neighbours.add (a);
}
// Allow the networks to swap with each other
nodes = new ArrayList<Node> (NODES);
nodes.addAll (reds);
nodes.addAll (blacks);
// See whether the locations become segregated
for (int i = 0; i < ROUNDS; i++) {
printLocations();
swapLocations();
}
}
void printLocations()
{
// Print the location distribution of the reds
for (Node r : reds) loc[(int) (r.location * COLUMNS)]++;
for (int i = 0; i < COLUMNS; i++) {
System.out.print (loc[i] + " ");
loc[i] = 0;
}
System.out.println();
}
void swapLocations()
{
for (int i = 0; i < SWAPS_PER_ROUND; i++) {
Node a = nodes.get ((int) (Math.random() * NODES));
Node b = nodes.get ((int) (Math.random() * NODES));
if (shouldSwap (a, b)) {
double temp = a.location;
a.location = b.location;
b.location = temp;
}
}
}
static double distance (Node a, Node b)
{
double x = a.location, y = b.location;
if (x > y) return Math.min (x - y, y - x + 1.0);
else return Math.min (y - x, x - y + 1.0);
}
static boolean shouldSwap (Node a, Node b)
{
double before = 1.0;
for (Node c : a.neighbours) before *= distance (a, c);
for (Node d : b.neighbours) before *= distance (b, d);
double after = 1.0;
for (Node c : a.neighbours) after *= distance (b, c);
for (Node d : b.neighbours) after *= distance (a, d);
if (after <= before) return true;
else return Math.random() < before / after;
}
static void makeKleinbergNetwork (ArrayList<Node> nodes)
{
for (Node a : nodes) {
// Normalise the probabilities
double norm = 0.0;
for (Node b : nodes) {
if (a.location == b.location) continue;
norm += 1.0 / distance (a, b);
}
// Create DEGREE/2 outgoing connections
for (Node b : nodes) {
if (a.location == b.location) continue;
double p = 1.0 / distance (a, b) / norm;
for (int i = 0; i < DEGREE / 2; i++) {
if (Math.random() < p) {
a.neighbours.add (b);
b.neighbours.add (a);
break;
}
}
}
}
}
public static void main (String[] args)
{
new Simulation();
}
class Node
{
HashSet<Node> neighbours = new HashSet<Node>();
double location = Math.random();
}
}
_______________________________________________
Devl mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
