peersim.graph
Class GraphFactory

java.lang.Object
  extended by peersim.graph.GraphFactory

public class GraphFactory
extends java.lang.Object

Contains static methods for wiring certain kinds of graphs. The general contract of all methods is that they accept any graph and add edges as specified in the documentation.


Method Summary
static Graph wireHypercube(Graph g)
          A hypercube.
static Graph wireKOut(Graph g, int k, java.util.Random r)
          Random graph.
static Graph wireRegRootedTree(Graph g, int k)
          A regular rooted tree.
static Graph wireRingLattice(Graph g, int k)
          Wires a ring lattice.
static Graph wireScaleFreeBA(Graph g, int k, java.util.Random r)
          This contains the implementation of the Barabasi-Albert model of growing scale free networks.
static Graph wireStar(Graph g)
          A sink star.
static Graph wireWS(Graph g, int k, double p, java.util.Random r)
          Watts-Strogatz model.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

wireRingLattice

public static Graph wireRingLattice(Graph g,
                                    int k)
Wires a ring lattice. The added connections are defined as follows. If k is even, links to i-k/2, i-k/2+1, ..., i+k/2 are added (but not to i), thus adding an equal number of predecessors and successors. If k is odd, then we add one more successors than predecessors. For example, for k=4: 2 predecessors, 2 successors. For k=5: 2 predecessors, 3 successors. For k=1: each node is linked only to its successor. All values are understood mod n to make the lattice circular, where n is the number of nodes in g.

Parameters:
g - the graph to be wired
k - lattice parameter
Returns:
returns g for convenience

wireWS

public static Graph wireWS(Graph g,
                           int k,
                           double p,
                           java.util.Random r)
Watts-Strogatz model. A bit modified though: by default assumes a directed graph. This means that directed links are re-wired, and the undirected edges in the original (undirected) lattice are modeled by double directed links pointing in opposite directions. Rewiring is done with replacement, so the possibility of wiring two links to the same target is positive (though very small).

Note that it is possible to pass an undirected graph as a parameter. In that case the output is the directed graph produced by the method, converted to an undirected graph by dropping directionality of the edges. This graph is still not from the original undirected WS model though.

Parameters:
g - the graph to be wired
k - lattice parameter: this is the out-degree of a node in the ring lattice before rewiring
p - the probability of rewiring each
r - source of randomness
Returns:
returns g for convenience

wireKOut

public static Graph wireKOut(Graph g,
                             int k,
                             java.util.Random r)
Random graph. Generates randomly k directed edges out of each node. The neighbors (edge targets) are chosen randomly without replacement from the nodes of the graph other than the source node (i.e. no loop edge is added). If k is larger than N-1 (where N is the number of nodes) then k is set to be N-1 and a complete graph is returned.

Parameters:
g - the graph to be wired
k - samples to be drawn for each node
r - source of randomness
Returns:
returns g for convenience

wireStar

public static Graph wireStar(Graph g)
A sink star. Wires a sink star topology adding a link to 0 from all other nodes.

Parameters:
g - the graph to be wired
Returns:
returns g for convenience

wireRegRootedTree

public static Graph wireRegRootedTree(Graph g,
                                      int k)
A regular rooted tree. Wires a regular rooted tree. The root is 0, it has links to 1,...,k. In general, node i has links to i*k+1,...,i*k+k.

Parameters:
g - the graph to be wired
k - the number of outgoing links of nodes in the tree (except leaves that have zero out-links, and exactly one node that might have less than k).
Returns:
returns g for convenience

wireHypercube

public static Graph wireHypercube(Graph g)
A hypercube. Wires a hypercube. For a node i the following links are added: i xor 2^0, i xor 2^1, etc. this define a log(graphsize) dimensional hypercube (if the log is an integer).

Parameters:
g - the graph to be wired
Returns:
returns g for convenience

wireScaleFreeBA

public static Graph wireScaleFreeBA(Graph g,
                                    int k,
                                    java.util.Random r)
This contains the implementation of the Barabasi-Albert model of growing scale free networks. The original model is described in http://arxiv.org/abs/cond-mat/0106096. It also works if the graph is directed, in which case the model is a variation of the BA model described in http://arxiv.org/pdf/cond-mat/0408391. In both cases, the number of the initial set of nodes is the same as the degree parameter, and no links are added. The first added node is connected to all of the initial nodes, and after that the BA model is used normally.

Parameters:
k - the number of edges that are generated for each new node, also the number of initial nodes (that have no edges).
r - the randomness to be used
Returns:
returns g for convenience