On Mar 4, 2008, at 7:52 AM, Michael Rogers wrote: > I don't see any correlation between index and degree with the > attached test code (which rejects duplicate connections because it > uses HashSet). > > Cheers, > Michael
I don't know, it just seems like a degree-6 graph should not have node(s) with 21 connections. Something's afowl here, the array-scanning was just my best guess when I ran out of time to track it down. Running your sim at the stats of the present network coloring test (50 nodes, degree=6), I get a graph with an average degree of about 4 and a peak connection count of 8 (not 21). Without Michael's forceNeighborConnections mod, it would also make quite a number of leaf nodes. I don't recall if it makes zero- connection nodes. -- Robert Hailey > Matthew Toseland wrote: >> Hmmm, we really need to fix this, if our simulations are skewed... >> Any hints, Oskar? The network construction function is right at the >> top of this file.. could you have a look at it? Thanks. >> http://emu.freenetproject.org/cgi-bin/viewcvs.cgi/trunk/freenet/src/freenet/node/simulator/RealNodeTest.java?rev=18322&view=markup >> On Monday 03 March 2008 21:40, robert at freenetproject.org wrote: >>> Author: robert >>> Date: 2008-03-03 21:40:44 +0000 (Mon, 03 Mar 2008) >>> New Revision: 18322 >>> >>> Modified: >>> trunk/freenet/src/freenet/node/simulator/RealNodeTest.java >>> Log: >>> comments >>> >>> >>> Modified: trunk/freenet/src/freenet/node/simulator/RealNodeTest.java >>> =================================================================== >>> --- trunk/freenet/src/freenet/node/simulator/RealNodeTest.java >>> 2008-03-03 >> 13:38:58 UTC (rev 18321) >>> +++ trunk/freenet/src/freenet/node/simulator/RealNodeTest.java >>> 2008-03-03 >> 21:40:44 UTC (rev 18322) >>> @@ -29,6 +29,10 @@ >>> >>> /* >>> Borrowed from mrogers simulation code (February 6, 2008) >>> + -- >>> + FIXME: May not generate good networks. Presumably this is >>> because the >> arrays are always scanned >>> + [0..n], some nodes tend to have *much* higher >>> connections than the >> degree (the first few), >>> + starving the latter ones. >>> */ >>> static void makeKleinbergNetwork (Node[] nodes, boolean >>> idealLocations, >> int degree, boolean forceNeighbourConnections) >>> { >>> >>> ------------------------------------------------------------------------ >>> >>> _______________________________________________ >>> Devl mailing list >>> Devl at freenetproject.org >>> http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl > > import java.util.ArrayList; > import java.util.HashSet; > > class KleinbergDegreeTest > { > static final int NODES = 1000, DEGREE = 10, MAX_DEGREE = 20; > static final boolean LIMIT = false; > > ArrayList<Node> nodes; > > KleinbergDegreeTest() > { > nodes = new ArrayList<Node> (NODES); > for (int i = 0; i < NODES; i++) nodes.add (new Node()); > } > > void makeKleinbergNetwork() > { > 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) { > connect (a, b); > break; > } > } > } > } > } > > 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); > } > > void connect (Node a, Node b) > { > if (LIMIT && > (a.neighbours.size() == MAX_DEGREE > || b.neighbours.size() == MAX_DEGREE)) return; > a.neighbours.add (b); > b.neighbours.add (a); > } > > // Print a scatterplot of index vs degree and a histogram of degree > void printDegreeDistribution() > { > int[] histogram = new int[DEGREE]; > for (int i = 0; i < NODES; i++) { > Node n = nodes.get (i); > System.out.println (i + " " + n.neighbours.size()); > int degree = n.neighbours.size(); > if (degree >= histogram.length) { > int[] newHistogram = new int[degree + 1]; > for (int j = 0; j < histogram.length; j++) > newHistogram[j] = histogram[j]; > histogram = newHistogram; > } > histogram[degree]++; > } > System.out.print ("#"); > for (int i = 0; i < histogram.length; i++) > System.out.print (" " + histogram[i]); > System.out.println(); > } > > public static void main (String[] args) > { > KleinbergDegreeTest kdt = new KleinbergDegreeTest(); > kdt.makeKleinbergNetwork(); > kdt.printDegreeDistribution(); > } > > class Node > { > HashSet<Node> neighbours = new HashSet<Node>(); > double location = Math.random(); > } > } > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
