edu.ucla.sspace.graph

Class Fanmod

java.lang.Object

edu.ucla.sspace.graph.Fanmod

public class Fanmod
extends Object

A complete re-implementation of the FANMOD tool for finding motifs in graphs. This implementation does not use the motif subgraph counting described in the original paper due to supporting multigraph-based motifs. Furthermore, this implementation uses an equivalent but non-recursive implementation of the ESU method described in the paper for enumerate all the possible subgraphs of a fixed size in a graph.

The FANMOD method works by counting the number of subgraphs of the specified size in the input graph. Then it generates a number of random graphs that preserve the properties of the original graph (its degree and type sequence). These random graphs create null model of the expected graph distribution, which can then be compared with the actual distribution to identify which subgraphs count as motifs. Typically, a subgraph is a motif if its frequency its greater than one standard deviation away from the expected value (i.e., a Z-score greater than 1).

This implementation provides some flexibility in letting the user identify which subgraphs should count as motifs based on their distribution in the graph and null model. A Fanmod.MotifFilter exposes the three main parameters, a subgraph's actual frequency, its expected frequency, and its standard deviation in the null model, which are then used to decide wither a subgraph is a motif. Typically a Fanmod.ZScoreFilter is used with a value of 1. However, callers may also filter with minimum frequency or based on other attributes.

See Also:

SubgraphIterator

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	Fanmod.FrequencyAndZScoreFilter
static class	Fanmod.FrequencyFilter
static interface	Fanmod.MotifFilter An interface for performing some computation on a subgraph's frequency information to deicide whether its occurrences constitute it being a motif.
static class	Fanmod.Result The result of computing a motif's distribution in the graph and null model
static class	Fanmod.ZScoreFilter

Constructor Summary

Constructors

Constructor and Description
Fanmod() Creates a new Fanmod instance

Method Summary

Methods

Modifier and Type	Method and Description
<E extends Edge> Map<Graph<E>,Fanmod.Result>	findMotifs(Graph<E> g, int motifSize, int numRandomGraphs, Fanmod.MotifFilter filter) Finds motifs in the input graph according to the specified parameters.
<T,E extends TypedEdge<T>> Map<Multigraph<T,E>,Fanmod.Result>	findMotifs(Multigraph<T,E> g, boolean findSimpleMotifs, int motifSize, int numRandomGraphs, Fanmod.MotifFilter filter) Finds motifs in the input graph according to the specified parameters.

Methods inherited from class java.lang.Object

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

Constructor Detail

Fanmod

public Fanmod()

Creates a new Fanmod instance

Method Detail

findMotifs

public <T,E extends TypedEdge<T>> Map<Multigraph<T,E>,Fanmod.Result> findMotifs(Multigraph<T,E> g,
                                                                       boolean findSimpleMotifs,
                                                                       int motifSize,
                                                                       int numRandomGraphs,
                                                                       Fanmod.MotifFilter filter)

Finds motifs in the input graph according to the specified parameters.

Parameters:

g - the graph that contains motifs to be found

findSimpleMotifs - true if the subgraphs must be simple graphs, i.e., graphs that contain no parallel edges. These motifs are created by sampling all possible simple graphs from the multigraph. For example, a three node subgraph with four edges would generate four potential simple graph motifs.

motifSize - the number of vertices in the motif

numRandomGraphs - the number of random graphs to generate from , which have the same graph properties, and which will be used to create the null model.

filter - a Fanmod.MotifFilter used to specify which subgraphs are significant and constitute motifs

Returns:

a mapping from each motif to a Fanmod.Result which describes that motifs distribution and stastics in the null mode.

findMotifs

public <E extends Edge> Map<Graph<E>,Fanmod.Result> findMotifs(Graph<E> g,
                                                      int motifSize,
                                                      int numRandomGraphs,
                                                      Fanmod.MotifFilter filter)

Finds motifs in the input graph according to the specified parameters.

Parameters:

g - the graph that contains motifs to be found

motifSize - the number of vertices in the motif

numRandomGraphs - the number of random graphs to generate from , which have the same graph properties, and which will be used to create the null model.

filter - a Fanmod.MotifFilter used to specify which subgraphs are significant and constitute motifs

Returns:

a mapping from each motif to a Fanmod.Result which describes that motifs distribution and stastics in the null mode.