[freenet-dev] Bogus network construction function?? was Re: [freenet-cvs] r18322 - trunk/freenet/src/freenet/node/simulator

[Robert Hailey]

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