gov.llnl.ontology.wordnet
Class SynsetPagerank

java.lang.Object
  gov.llnl.ontology.wordnet.SynsetPagerank

public class SynsetPagerank
extends Object

This class performs PageRank over a graph of Synsets. Synsets are assumed to be connected with an arbitrary set of directional links. Each Synset will be given a single score that rates it's importance in the graph.

This algorithm works as follows:

Each Synset is given a set of transition probabilities. Each outgoing link from a Synset is assumed to have equal weight. These transition probabilities are stored as an Attribute in the Synset. Calling setupTransitionAttributes will create these Attributes for each Synset. If there is a core subgraph that is held constant through multiple Page Rank runs, it is suggested that this core subgraph is stored in a separate list and setupTransitionAttributes be called once on this subgraph.

If there are other nodes beyond the core subgraph, they should be given transition probability Attributes through setTransitionAttribute.

The Page Rank algorithm is ran over the graph for a fixed number of iterations. In each iteration, the page rank score is updated and used in conjunction with a set of random surfer probabilities.

This implementation is designed such that Page Rank can be run over several graphs that have the same core subgraph in parrallel. Each Synset in the graph is only given a set of transition probabilities. As long as the link structure is held constant, there is no need to setup new transition probabilities for the core graph.

Author:

Keith Stevens

Field Summary

static String

TRANSITION_ATTRIBUTE The identifier for an Attribute of transition probabilities.

Constructor Summary

SynsetPagerank()

Method Summary

static edu.ucla.sspace.vector.SparseDoubleVector	computePageRank(List<Synset> synsetList, edu.ucla.sspace.vector.SparseDoubleVector sourceWeights, double weight) Returns a SparseDoubleVector representing the page rank scores of each synset in synsetList.
static void	setTransitionAttribute(Synset synset, Map<Synset,Integer> synsetMap) Create a Attribute for the transition probabilities of the given Synset.
static void	setupTransitionAttributes(List<Synset> synsetList, Map<Synset,Integer> synsetMap) Adds transition probability Attributes for each Synset in synsetList.

Methods inherited from class java.lang.Object

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

Field Detail

TRANSITION_ATTRIBUTE

public static final String TRANSITION_ATTRIBUTE

The identifier for an Attribute of transition probabilities. These Attributes will simply be SparseDoubleVectors.

See Also:

Constant Field Values

Constructor Detail

SynsetPagerank

public SynsetPagerank()

Method Detail

setTransitionAttribute

public static void setTransitionAttribute(Synset synset,
                                          Map<Synset,Integer> synsetMap)

Create a Attribute for the transition probabilities of the given Synset. Each connection is given an even weight. synsetMap provides the desired indices for each possible Synset.

Parameters:

synset - The synset for which transition probability transtions will be added

synsetMap - A mapping from Sysnets to a vector indices

Throws:

NullPointerException - if synsetMap does not contain a mapping for an outward link in synset

setupTransitionAttributes

public static void setupTransitionAttributes(List<Synset> synsetList,
                                             Map<Synset,Integer> synsetMap)

Adds transition probability Attributes for each Synset in synsetList. The indices for outward links are specified by synsetMap.

Parameters:

synset - The list of synsets for which transition probability transtions will be added

synsetMap - A mapping from Sysnets to a vector indices

Throws:

NullPointerException - if synsetMap does not contain a mapping for an outward link in any Synset

computePageRank

public static edu.ucla.sspace.vector.SparseDoubleVector computePageRank(List<Synset> synsetList,
                                                                        edu.ucla.sspace.vector.SparseDoubleVector sourceWeights,
                                                                        double weight)

Returns a SparseDoubleVector representing the page rank scores of each synset in synsetList. Each Synset is assumed to have a SparseDoubleVector Attribute representing the transition probabilities, which can be setup by calling setupTransitionAttributes. Altogether, these transition vectors form the transition matrix needed in the PageRank computation. Note that if one sets the sourceWeights carefully, a customized page rank can be computed. It is recomended that a small number of values in sourceWeights be set to a non zero value if synsetList contains a large number of Synsets from the original word net graph.

Parameters:

synsetList - The set of Sysnets over which to compute page rank scores

sourceWeights - A vector of teleporation probabilities, i.e., the probability that a random surfer lands at a particular synset given that a random jump was made

weight - The probability of making a random jump at any point in time