[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Unbiased sampling of graphs
From: |
Jason Alexander |
Subject: |
Unbiased sampling of graphs |
Date: |
Tue, 10 Apr 2001 17:37:16 -0700 |
Hello,
I need to generate a unbiased random sample from the set of connected graphs
having N nodes and no more than K edges per node. One no-brainer way of
sampling would be:
while (true) {
generate a graph w/ N nodes and <= K edges per node.
if it's connected, break; otherwise, scrap graph and try again.
}
I would think there should be a better way. I'm not convinced that any of
the methods I've thought of, though, sample the space without bias. For
example, one might try:
while (true) {
generate a graph w/ N nodes and <= K edges per node.
if connected, break
else {
while (unconnected nodes remain) {
let X be a randomly chosen unconnected node.
choose another node at random; if that node has < K edges, link it to
node X; otherwise,
choose another node at random (keep doing this until you get one with
<K edges, then link to X).
}
}
This seems plausible, but I'm skeptical.
Any thoughts or references would be appreciated.
Cheers,
Jason
--
Jason Alexander
Department of Philosophy
University of California, San Diego
La Jolla, CA 92093-0119
858-822-4910 (office)
858-534-8566 (fax)
==================================
Swarm-Modelling is for discussion of Simulation and Modelling techniques
esp. using Swarm. For list administration needs (esp. [un]subscribing),
please send a message to <address@hidden> with "help" in the
body of the message.
==================================
- Unbiased sampling of graphs,
Jason Alexander <=