edu.ucla.sspace.graph

Class SamplingSubgraphIterator<T extends Edge>

java.lang.Object

edu.ucla.sspace.graph.SamplingSubgraphIterator<T>

All Implemented Interfaces:

Serializable, Iterator<Graph<T>>

public class SamplingSubgraphIterator<T extends Edge>
extends Object
implements Iterator<Graph<T>>, Serializable

An implementation of the Randomized EnumerateSubgraphs (RAND-ESU) method from Wernicke (2006), which provides a unbiased random sampling of the size-k subgraphs of an input graph. For full details see:

• Sebastian Wernicke. Efficient detection of network motifs. in IEEE/ACM Transactions on Computational Biology and Bioinformatics.

Callers specify how much of the backing graph should be sampled using an array of probabilities. Each probability corresponds to how likely a subgraph with k vertices will be expanded to include k+1 vertices. The product of all the probabilities is the percentage of the subgraphs that are expected to be sampled. For example, to sample 25% of the size-3 subgraphs, the probilities [1, 1, .25] or [1, .5, .5] may be used. In general, it is preferrable to set only the last probability to the percentage of subgraphs desired (as in the first of the previous two examples) as it is less likely to prune away unintentionally larger portions of the possible subgraph space. See the reference for further details on performance.

This class is not thread-safe and does not support the remove() method.

Author:

David Jurgens

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
SamplingSubgraphIterator(Graph<T> g, int subgraphSize, double[] traversalProbabilitiesAtDepth) Constructs an iterator over all the subgraphs of g with the specified subgraph size, where the list of probabilities is used to decide probabilistically whether the next level of expansion should be taken.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	hasNext() Returns true if there are more subgraphs to return
Graph<T>	next() Returns the next subgraph from the backing graph.
void	remove() Throws an UnsupportedOperationException if called.

Methods inherited from class java.lang.Object

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

Constructor Detail

SamplingSubgraphIterator

public SamplingSubgraphIterator(Graph<T> g,
                        int subgraphSize,
                        double[] traversalProbabilitiesAtDepth)

Constructs an iterator over all the subgraphs of g with the specified subgraph size, where the list of probabilities is used to decide probabilistically whether the next level of expansion should be taken.

Parameters:

g - a graph

subgraphSize - the size of the subgraphs to return

traversalProbabilitiesAtDepth - an array of probabilities where each index i corresponds to the probability of expanding the subgraph at depth i. This array must be the same size as the the number of desired vertices in the subgraph.

Throws:

IllegalArgumentException - if

• subgraphSize is less than 1 or is greater than the number of vertices of g,
• the number of traversal probabilities does not equal the size of the subgraph, or
• the any of the probabilities are outsize the range (0, 1].

NullPointerException - if g or traversalProbabilitiesAtDepth is null

Method Detail

hasNext

public boolean hasNext()

Returns true if there are more subgraphs to return

Specified by:

hasNext in interface Iterator<Graph<T extends Edge>>

next

public Graph<T> next()

Returns the next subgraph from the backing graph.

Specified by:

next in interface Iterator<Graph<T extends Edge>>

remove

public void remove()

Throws an UnsupportedOperationException if called.

Specified by:

remove in interface Iterator<Graph<T extends Edge>>