gov.sandia.cognition.graph.community

Class PersonalizedPageRank<NodeNameType>

java.lang.Object

gov.sandia.cognition.graph.community.PersonalizedPageRank<NodeNameType>

Type Parameters:

NodeNameType - The graph's node name type

@PublicationReference(type=WebPage,
                      title="Personalized PageRank code",
                      author="dgleich",
                      year=2016,
                      url="https://gist.github.com/dgleich/6201856")
public class PersonalizedPageRank<NodeNameType>
extends java.lang.Object

This class can compute PersonalizedPageRank for the input graph and a specified node, and also can determine a community for any specified node. The code permits multiple queries against the same graph, storing the necessary speed-up objects as part of the instance.

Author:

jdwendt

Constructor Summary

Constructors

Constructor and Description
PersonalizedPageRank(DirectedNodeEdgeGraph<NodeNameType> graph) Initializes all of the internal data-structures for the input graph.
PersonalizedPageRank(DirectedNodeEdgeGraph<NodeNameType> graph, double tolerance) Initializes all of the internal data-structures for the input graph.

Method Summary

Modifier and Type	Method and Description
java.util.Set<java.lang.Integer>	getCommunityForNode(NodeNameType node, int numRunsPpr, int numRunsCut) Computes the best community for the input node id by personalized page rank scores and conductance of cut.
java.util.Set<java.lang.Integer>	getCommunityForNodeById(int nodeIdx, int numRunsPpr, int numRunsCut) Computes the best community for the input node id by personalized page rank scores and conductance of cut.
java.util.Set<java.lang.Integer>	getCommunityForNodes(java.util.List<NodeNameType> nodes, int numRunsPpr, int numRunsCut) Computes the best community for the input node id by personalized page rank scores and conductance of cut.
java.util.Set<java.lang.Integer>	getCommunityForNodesById(java.util.List<java.lang.Integer> nodeIdxs, int numRunsPpr, int numRunsCut) Computes the best community for the input node id by personalized page rank scores and conductance of cut.
DoubleArrayList	getScoresForAllNodes(java.util.List<NodeNameType> nodes) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seeds
DoubleArrayList	getScoresForAllNodes(java.util.List<NodeNameType> nodes, boolean randomized) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seeds
DoubleArrayList	getScoresForAllNodes(NodeNameType node) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)
DoubleArrayList	getScoresForAllNodes(NodeNameType node, boolean randomized) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)
DoubleArrayList	getScoresForAllNodesById(int nodeIdx) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)
DoubleArrayList	getScoresForAllNodesById(int nodeIdx, boolean randomized) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)
DoubleArrayList	getScoresForAllNodesByIdMultirun(int nodeIdx, int numRuns) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed index.
DoubleArrayList	getScoresForAllNodesByIdMultirun(java.util.List<java.lang.Integer> nodeIdxs, int numRuns) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed index.
DoubleArrayList	getScoresForAllNodesByIds(java.util.List<java.lang.Integer> nodeIdxs) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed indices
DoubleArrayList	getScoresForAllNodesByIds(java.util.List<java.lang.Integer> nodeIdxs, boolean randomized) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed indices
DoubleArrayList	getScoresForAllNodesMultirun(java.util.List<NodeNameType> nodes, int numRuns) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed index.
DoubleArrayList	getScoresForAllNodesMultirun(NodeNameType node, int numRuns) Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed.
void	setRandomSet(long seed) Initialize the random number generator with the input seed.
void	setTolerance(double tolerance) Set the tolerance to a new value.

Methods inherited from class java.lang.Object

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

Constructor Detail

PersonalizedPageRank

public PersonalizedPageRank(DirectedNodeEdgeGraph<NodeNameType> graph)

Initializes all of the internal data-structures for the input graph. Note that if the input graph is altered after passing it to this class, the results for this instance can become unstable.

Parameters:

graph - The graph to compute personalized page rank for

PersonalizedPageRank

public PersonalizedPageRank(DirectedNodeEdgeGraph<NodeNameType> graph,
                            double tolerance)

Initializes all of the internal data-structures for the input graph. Note that if the input graph is altered after passing it to this class, the results for this instance can become unstable.

Parameters:

graph - The graph to compute personalized page rank for

tolerance - The tolerance for further spreading PPR. Should be fairly small 0.01 or smaller. The closer to 0, the further it will spread. Setting to 0 could lead to never quite converging (so probably don't do that).

Method Detail

setTolerance

public void setTolerance(double tolerance)

Set the tolerance to a new value. Should be small (0, 0.01]. The closer to 0, the further it will spread. Setting to 0 could lead to never quite converging (so probably don't do that).

Parameters:

tolerance - The tolerance for further spreading PPR.

setRandomSet

public void setRandomSet(long seed)

Initialize the random number generator with the input seed.

Parameters:

seed - The seed for the random number generator

getScoresForAllNodes

public DoubleArrayList getScoresForAllNodes(NodeNameType node)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)

Parameters:

node - The node to use as seed

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesById

public DoubleArrayList getScoresForAllNodesById(int nodeIdx)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)

Parameters:

nodeIdx - The node index to use as seed

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodes

public DoubleArrayList getScoresForAllNodes(java.util.List<NodeNameType> nodes)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seeds

Parameters:

nodes - The nodes to use as seed

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodes

public DoubleArrayList getScoresForAllNodes(NodeNameType node,
                                            boolean randomized)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)

Parameters:

node - The node to use as seed

randomized - If true, the order nodes are treated within the algorithm will be randomized so that you can get an average result across multiple runs or just realize that any single run is not the completely true answer.

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesById

public DoubleArrayList getScoresForAllNodesById(int nodeIdx,
                                                boolean randomized)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph)

Parameters:

nodeIdx - The node index to use as seed

randomized - If true, the order nodes are treated within the algorithm will be randomized so that you can get an average result across multiple runs or just realize that any single run is not the completely true answer.

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodes

public DoubleArrayList getScoresForAllNodes(java.util.List<NodeNameType> nodes,
                                            boolean randomized)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seeds

Parameters:

nodes - The nodes to use as seed

randomized - If true, the order nodes are treated within the algorithm will be randomized so that you can get an average result across multiple runs or just realize that any single run is not the completely true answer.

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesByIds

public DoubleArrayList getScoresForAllNodesByIds(java.util.List<java.lang.Integer> nodeIdxs)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed indices

Parameters:

nodeIdxs - The node indices to use as seed

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesByIds

public DoubleArrayList getScoresForAllNodesByIds(java.util.List<java.lang.Integer> nodeIdxs,
                                                 boolean randomized)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed indices

Parameters:

nodeIdxs - The node indices to use as seed

randomized - If true, the order nodes are treated within the algorithm will be randomized so that you can get an average result across multiple runs or just realize that any single run is not the completely true answer.

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesMultirun

public DoubleArrayList getScoresForAllNodesMultirun(NodeNameType node,
                                                    int numRuns)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed. This implementation uses the random version and averages over numRuns random runs.

Parameters:

node - The seed node to consider

numRuns - The number of runs to perform

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesMultirun

public DoubleArrayList getScoresForAllNodesMultirun(java.util.List<NodeNameType> nodes,
                                                    int numRuns)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed index. This implementation uses the random version and averages over numRuns random runs.

Parameters:

nodes - The seed nodes

numRuns - The number of runs to perform

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesByIdMultirun

public DoubleArrayList getScoresForAllNodesByIdMultirun(int nodeIdx,
                                                        int numRuns)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed index. This implementation uses the random version and averages over numRuns random runs.

Parameters:

nodeIdx - The seed node's id

numRuns - The number of runs to perform

Returns:

the vector of all scores for all nodes in the graph

getScoresForAllNodesByIdMultirun

public DoubleArrayList getScoresForAllNodesByIdMultirun(java.util.List<java.lang.Integer> nodeIdxs,
                                                        int numRuns)

Returns the vector of all scores for all nodes in the graph (order determined by node order as stored in the graph) as specified for the input seed index. This implementation uses the random version and averages over numRuns random runs.

Parameters:

nodeIdxs - The seed nodes' id

numRuns - The number of runs to perform

Returns:

the vector of all scores for all nodes in the graph

getCommunityForNode

public java.util.Set<java.lang.Integer> getCommunityForNode(NodeNameType node,
                                                            int numRunsPpr,
                                                            int numRunsCut)

Computes the best community for the input node id by personalized page rank scores and conductance of cut. Note both the PPR computation and the community-via-conducntance computation contain order-dependence. Therefore, this code always uses a random ordering. For PPR, it returns the average PPR across all of the runs. For the community determination, it returns the community with the best conductance based as found by following edges in different orders.

Parameters:

node - The node whose community is desired

numRunsPpr - The number of randomized runs to perform for the PPR computation

numRunsCut - The number of randomized runs to perform for community determination

Returns:

getCommunityForNodeById

public java.util.Set<java.lang.Integer> getCommunityForNodeById(int nodeIdx,
                                                                int numRunsPpr,
                                                                int numRunsCut)

Computes the best community for the input node id by personalized page rank scores and conductance of cut. Note both the PPR computation and the community-via-conducntance computation contain order-dependence. Therefore, this code always uses a random ordering. For PPR, it returns the average PPR across all of the runs. For the community determination, it returns the community with the best conductance based as found by following edges in different orders.

Parameters:

nodeIdx - The node id whose community is desired

numRunsPpr - The number of randomized runs to perform for the PPR computation

numRunsCut - The number of randomized runs to perform for community determination

Returns:

getCommunityForNodes

public java.util.Set<java.lang.Integer> getCommunityForNodes(java.util.List<NodeNameType> nodes,
                                                             int numRunsPpr,
                                                             int numRunsCut)

Computes the best community for the input node id by personalized page rank scores and conductance of cut. Note both the PPR computation and the community-via-conducntance computation contain order-dependence. Therefore, this code always uses a random ordering. For PPR, it returns the average PPR across all of the runs. For the community determination, it returns the community with the best conductance based as found by following edges in different orders.

Parameters:

nodes - The node(s) whose community is desired

numRunsPpr - The number of randomized runs to perform for the PPR computation

numRunsCut - The number of randomized runs to perform for community determination

Returns:

getCommunityForNodesById

public java.util.Set<java.lang.Integer> getCommunityForNodesById(java.util.List<java.lang.Integer> nodeIdxs,
                                                                 int numRunsPpr,
                                                                 int numRunsCut)

Computes the best community for the input node id by personalized page rank scores and conductance of cut. Note both the PPR computation and the community-via-conducntance computation contain order-dependence. Therefore, this code always uses a random ordering. For PPR, it returns the average PPR across all of the runs. For the community determination, it returns the community with the best conductance based as found by following edges in different orders.

Parameters:

nodeIdxs - The node id(s) whose community is desired

numRunsPpr - The number of randomized runs to perform for the PPR computation

numRunsCut - The number of randomized runs to perform for community determination

Returns: