edu.stanford.math.plex4.graph.random

Class BinaryHierarchicalGraph

java.lang.Object

edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

edu.stanford.math.plex4.graph.random.BinaryHierarchicalGraph

All Implemented Interfaces:

java.io.Serializable

Direct Known Subclasses:

HierarchicalERGraph

public class BinaryHierarchicalGraph
extends GraphInstanceGenerator

Makes a random hierarchical graph by considering points P = {1,2,...,n} and partitions C_{i,j}, where j is the granularity. C_{i,j+1} refines C_{i,j}. The probability of an edge between p_1 and p_2 is a function of the largest value of j such that there exists C_{i,j} with p_1,p_2 in C_{i,j}. This is a first attempt approximation to see how PLEX characterizes graphs with structure like this.

Author:

Tim Harrington

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

GraphInstanceGenerator.ImplementationType

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	debugFlag
protected int	k
protected double	maxProbability
protected int	numNodes

Fields inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

graphImplementation, implementationType

Constructor Summary

Constructors

Modifier	Constructor and Description
	BinaryHierarchicalGraph(int n)
protected	BinaryHierarchicalGraph(int n, boolean dummy) Creates a HierarchicalGraph without any edges.
	BinaryHierarchicalGraph(int n, double maxProbability)

Method Summary

Methods

Modifier and Type	Method and Description
protected AbstractUndirectedGraph	construct(double maxProbability) Construct the Hierarchical graph.
protected AbstractUndirectedGraph	constructEdges(int n0, int n1, int k, double[] probs) Construct the edges of the graph using probabilities in the array probs.
protected void	debug(java.lang.String msg)
AbstractUndirectedGraph	generate()
double[]	getProbabilities()
protected double[]	getProbabilities(int k, double dampingFactor) We need one probability for each potential common ancestor depth d=1..k-1.
protected int	getTreeDepth(int n) We want to construct the smallest binary tree of size 2^{d+1}-1 (d>0) such that there are at least n leaves.
java.lang.String	toString()

Methods inherited from class edu.stanford.math.plex4.graph.random.GraphInstanceGenerator

initializeGraph, setImplementationType

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

numNodes

protected int numNodes

k

protected int k

maxProbability

protected double maxProbability

debugFlag

protected boolean debugFlag

Constructor Detail

BinaryHierarchicalGraph

public BinaryHierarchicalGraph(int n)

Parameters:

n - the number of nodes

BinaryHierarchicalGraph

public BinaryHierarchicalGraph(int n,
                       double maxProbability)

Parameters:

n - the number of nodes in the graph

maxProbability - the maximum edge probability

BinaryHierarchicalGraph

protected BinaryHierarchicalGraph(int n,
                       boolean dummy)

Creates a HierarchicalGraph without any edges. Convenience method for use by classes that extend HierarchicalGraph

Parameters:

n - the number of nodes

dummy - a dummy variable used to force this constructor to be used

Method Detail

getProbabilities

public double[] getProbabilities()

generate

public AbstractUndirectedGraph generate()

Specified by:

generate in class GraphInstanceGenerator

construct

protected AbstractUndirectedGraph construct(double maxProbability)

Construct the Hierarchical graph. As an approximation, this algorithm considers a binary tree with n nodes, labeled 1,2,..,n in a BFS. For example, 1 / \ 3 2 / \ / \ 7 6 5 4 ... Only the leaves of the tree are associated with nodes. To build a binary tree with n leaves it takes 2^m nodes, where m=floor(ln(n)/ln(2)). The probability of edge (a,b) existing is a function of the depth of the first common ancestor in the tree. For example, if D = maxDepth then i,j-depth probability of (i,j) in E 1 p=[1/D]^q 2 p=[2/D]^q 3 p=[3/D]^q ... D-1 p=[(D-1)/D]^q D p=[D/D]^q

getProbabilities

protected double[] getProbabilities(int k,
                        double dampingFactor)

We need one probability for each potential common ancestor depth d=1..k-1. They are constructed here.

Parameters:

k - a value such that (2^k <= n <= (2^{k+1})-1)

dampingFactor - a scaling factor in the open set (0,1)

Returns:

constructEdges

protected AbstractUndirectedGraph constructEdges(int n0,
                                     int n1,
                                     int k,
                                     double[] probs)

Construct the edges of the graph using probabilities in the array probs.

Parameters:

n0 - the starting index of the binary tree leaves

n1 - the ending index of the binary tree leaves

k - a value such that [2^k <= n < 2^{k+1}]

probs - an array of probabilities for each common ancestor depth

getTreeDepth

protected int getTreeDepth(int n)

We want to construct the smallest binary tree of size 2^{d+1}-1 (d>0) such that there are at least n leaves. That is, we need to find k that satisfies 2^k <= n < 2^{k+1} To do this we solve for k and let d=ceil(k).

Returns:

the value of k that satisfies [2^k <= n < 2^{k+1}].

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

debug

protected void debug(java.lang.String msg)