com.phoenixst.plexus.examples
public class RandomGraphFactory extends Object
Since: 1.0
Version: $Revision: 1.9 $
Method Summary | |
---|---|
static Graph | createBarabasiAlbert(int numInitialNodes, int numFinalNodes, int numEdges)
Creates a random graph according to the Barabasi-Albert model.
|
static Graph | createStandardGraph(int n, double prob)
Creates a random graph with n nodes where each
pair of nodes has probability prob of having an
edge between them. |
static Graph | createWattsStrogatz(int n, int d, double prob)
Creates a random graph according to the Watts-Strogatz model.
|
Start with numInitialNodes
nodes. At each
step, add a new node which is connected to
numEdges
existing nodes, with preference given to
nodes that are more highly connected.
n
nodes where each
pair of nodes has probability prob
of having an
edge between them.d
here is half of K
in
the standard literature.
Start with a circulant graph. Arrange the nodes in a
circle, starting at 0 and increasing, in order, clockwise.
Begin with node 0 and the edge which connects it to its
nearest clockwise neighbor, which is node 1. With probability
prob
, reconnect this edge from node 0 to a
uniformly randomly selected node, with duplicate and self edges
forbidden. Repeat this process for each node, moving
clockwise around the circle. Now, repeat the entire cycle,
but instead choose edges which connect nodes to their
second-nearest clockwise neighbor. And so on, until every one
of the original edges has been considered.