Robert Hailey wrote:
I don't know, it just seems like a degree-6 graph should not have
node(s) with 21 connections.
Agreed, it should be very rare (though not impossible). The degree
distribution should be Poisson, approximately normal for large graphs.
The histogram at the end of the test code output looks about right to me
- what kind of degree distribution are you getting in RealNodeTest?
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).
That sounds about right - the actual mean will usually be lower than the
specified mean, especially in small networks, because duplicate
connections are discarded.
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.
Again, it's possible but it should be very rare.
(Slightly updated version of the test code attached - you can now choose
regular or random locations. Still no correlation between index and degree.)
Cheers,
Michael
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, RANDOM_LOCS = true;
ArrayList<Node> nodes;
KleinbergDegreeTest()
{
nodes = new ArrayList<Node> (NODES);
double div = 1.0 / NODES;
double loc = 0.0;
for (int i = 0; i < NODES; i++) {
if (RANDOM_LOCS) nodes.add (new Node (Math.random()));
else nodes.add (new Node (loc));
loc += div;
}
}
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 = 0.0;
Node (double location)
{
this.location = location;
}
}
}
_______________________________________________
Devl mailing list
[email protected]
http://emu.freenetproject.org/cgi-bin/mailman/listinfo/devl
