public class RandomWalk extends org.graphstream.stream.SinkAdapter implements DynamicAlgorithm
This algorithm create a given number of entities first associated with random nodes in the graph. Then by turns, each entity chooses an edge at random and crosses it. This is iterated a given number of turns. Each time an entity crosses an edge, a count is incremented on it and each time it arrives on a node a count is counted on it.
You can override the entity class to provide your own behaviour for entity movement.
If the algorithm was run for an infinite number of turns, each counter would have the same value. However we can choose to stop the algorithm when needed. Furthermore the algorithm can be biased by providing each entity with a memory of the already crossed edges. It can avoid these edges when choosing at random its next edge.
When an entity has no edge to choose (either because of its memory or because it reached a node that is only reachable via a one directed edge), the entity will jump randomly on another node.
When the number of turns awaited is reached, one can observe the counts on each edge and node. Edges and nodes that are very attractive in terms of topology should have a more important count than others.
This algorithm does not cope well with dynamic graphs. You can however improve this by using evaporation. When evaporation is activated, at each turn, the node and edge counts are multiplied by a number between 0 and 1. Therefore each edge or node count must be constantly updated by entities leading to a value that stabilizes in time.
At each step, the default entities move from their current node to another via
an edge randomly chosen. This is done in the Entity.step()
method.
This method makes a list of all leaving edges of the current node. If the node has no leaving edge, the entity jumps to another randomly chosen node. Then an edge is chosen at random in the list of leaving edges. The edge is chosen uniformly if there are no weights on the edges, else, an edge with an higher weight has more chances to be chosen than an edge with a lower weight.
When crossed, if the memory is larger than 0, the edge crossed is remembered so that the entity will not choose it anew until it crosses as many edges as the memory size.
With the default entities, you can make a node entirely tabu by putting the ``tabu`` attribute on it. No entity will traverse an edge that leads to such a node.
You can change the default entity class either by overriding the
createEntity()
method or by changing the entity class name
using setEntityClass(String)
.
If the edges have weights, the entities can use them to favour edges
with higher weights when randomly choosing them. By default the
weights are searched on edges using the ``weight`` attribute. However
you can override this using setWeightAttribute(String)
method.
If you choose to have evaporation on edge counts at each turn, you can
set it using setEvaporation(double)
. The evaporation is a number
between 0 and 1. If set to 1 (the default), the counts are not modified,
else the counts are multiplied by the evaporation at each turn.
To compute a turn, use the compute()
method. This will move each
entity from one node to another.
Once computed each edge and node will have an attribute ``passes`` stored
on it containing the number of passage of an entity. You can change the
name of this attribute using setPassesAttribute(String)
. After
each computation of a turn, you can obtain the edge and nodes counts using
either the passes attribute, or the utility methods getPasses(Node)
and getPasses(Edge)
.
You can count only the passes on the nodes or edges using the two methods
computeEdgesPasses(boolean)
and computeNodePasses(boolean)
.
As some entities may have jumped from their node to another one chosen
randomly, you can obtain the number of entities that jumped using
getJumpCount()
.
Graph graph = new MultiGraph("random walk"); RandomWalk rwalk = new RandomWalk(); // Populate the graph. rwalk.setEntityCount(graph.getNodeCount()/2); rwalk.init(graph); for(int i=0; i<1000; i++) { rwalk.compute(); } rwalk.terminate(); for(Edge edge: graph.getEachEdge()) { System.out.println("Edge %s counts %f%n", edge.getId(), rwalk.getPasses(edge)); }
Modifier and Type | Class and Description |
---|---|
class |
RandomWalk.Context |
Constructor and Description |
---|
RandomWalk()
New random walk with a new random seed (based on time), with an entity
memory set to 10 nodes (tabu list), with an attributes to store passes
named "passes" and no weight attribute.
|
RandomWalk(long randomSeed)
New random walk with a given random seed, with an entity memory set to 10
nodes (tabu list), with an attributes to store passes named "passes" and
no weight attribute.
|
Modifier and Type | Method and Description |
---|---|
void |
compute()
Execute one step of the algorithm.
|
void |
computeEdgesPasses(boolean on)
Activate or not the counts on edges when entities cross thems.
|
void |
computeNodePasses(boolean on)
Activate or not the counts on nodes when entities cross thems.
|
Entity |
createEntity()
Create an entity.
|
java.lang.String |
defaultResult() |
void |
edgeAdded(java.lang.String graphId,
long timeId,
java.lang.String edgeId,
java.lang.String fromNodeId,
java.lang.String toNodeId,
boolean directed) |
java.util.ArrayList<org.graphstream.graph.Edge> |
findTheMostUsedEdges()
Sort all edges by their "passes" attribute and return the array of sorted
edges.
|
java.util.ArrayList<org.graphstream.graph.Node> |
findTheMostUsedNodes()
Sort all nodes by their "passes" attribute and return the array of sorted
nodes.
|
int |
getEntityCount()
Number of entities.
|
double |
getEvaporation()
The evaporation value.
|
int |
getGoCount() |
int |
getJumpCount()
Number of entities that jumped instead of traversing an edge at last
step.
|
double |
getJumpRatio()
Ratio of entities that executed a jump instead of traversing an edge at
last step.
|
double |
getPasses(org.graphstream.graph.Edge edge)
The number of entity passage on the given edge.
|
double |
getPasses(org.graphstream.graph.Node node)
The number of entity passage on the given node.
|
java.lang.String |
getPassesAttribute()
The name of the attribute where the number of entities passes are stored
(for edges and nodes).
|
long |
getRandomSeed()
The random seed used.
|
int |
getWaitCount() |
void |
init(org.graphstream.graph.Graph graph)
Initialize the algorithm for a given graph with a given entity count.
|
void |
nodeAdded(java.lang.String graphId,
long timeId,
java.lang.String nodeId) |
void |
setEntityClass(java.lang.String name)
Set the name of the entity class to use.
|
void |
setEntityCount(int entityCount)
Set the number of entities which will be created at the algorithm
initialization.
|
void |
setEntityMemory(int size)
Set the entity memory in number of nodes remembered.
|
void |
setEvaporation(double evaporation)
Set the evaporation of edge counts.
|
void |
setPassesAttribute(java.lang.String name)
Set the name of the attribute used to store the number of passes of each
entity on each edge or node.
|
void |
setWeightAttribute(java.lang.String name)
The name of the attribute used to fetch edges importance.
|
void |
terminate()
End the algorithm by removing any listener on the graph and releasing
memory.
|
edgeAttributeAdded, edgeAttributeChanged, edgeAttributeRemoved, edgeRemoved, graphAttributeAdded, graphAttributeChanged, graphAttributeRemoved, graphCleared, nodeAttributeAdded, nodeAttributeChanged, nodeAttributeRemoved, nodeRemoved, stepBegins
public RandomWalk()
public RandomWalk(long randomSeed)
randomSeed
- The random seed.public java.lang.String getPassesAttribute()
public void setEntityClass(java.lang.String name)
name
- The name of the entity class to use.public void setEntityMemory(int size)
size
- The memory size, 0 is a valid size to disable the tabu list.public void setEvaporation(double evaporation)
evaporation
- A number between 0 and 1.public double getEvaporation()
public long getRandomSeed()
public int getEntityCount()
public int getJumpCount()
public int getWaitCount()
public int getGoCount()
public double getJumpRatio()
public void setWeightAttribute(java.lang.String name)
name
- A string giving the weight name.public void setPassesAttribute(java.lang.String name)
name
- A string giving the passes name.public double getPasses(org.graphstream.graph.Edge edge)
edge
- The edge to look at.public double getPasses(org.graphstream.graph.Node node)
node
- The node to look at.public void setEntityCount(int entityCount)
entityCount
- number of entitiespublic void computeEdgesPasses(boolean on)
on
- If true (the default) the edges passes are counted.public void computeNodePasses(boolean on)
on
- If true (the default) the nodes passes are counted.public Entity createEntity()
setEntityClass(String)
public void init(org.graphstream.graph.Graph graph)
public void compute()
compute
in interface Algorithm
Algorithm.init(Graph)
public void terminate()
terminate
in interface DynamicAlgorithm
Algorithm.init(org.graphstream.graph.Graph)
public java.util.ArrayList<org.graphstream.graph.Edge> findTheMostUsedEdges()
public java.util.ArrayList<org.graphstream.graph.Node> findTheMostUsedNodes()
public void edgeAdded(java.lang.String graphId, long timeId, java.lang.String edgeId, java.lang.String fromNodeId, java.lang.String toNodeId, boolean directed)
edgeAdded
in interface org.graphstream.stream.ElementSink
edgeAdded
in class org.graphstream.stream.SinkAdapter
public void nodeAdded(java.lang.String graphId, long timeId, java.lang.String nodeId)
nodeAdded
in interface org.graphstream.stream.ElementSink
nodeAdded
in class org.graphstream.stream.SinkAdapter
public java.lang.String defaultResult()