Package edu.claflin.finder.algo.clustering

# Class Walktrap

java.lang.Object
edu.claflin.finder.algo.Algorithm
edu.claflin.finder.algo.clustering.ClusteringAlgorithm
edu.claflin.finder.algo.clustering.Walktrap

All Implemented Interfaces:
  `Processable<Graph,Graph>`

public class Walktrap extends ClusteringAlgorithm
Walktrap Algorithm for Community Detection. Random walks from a Node in a community tend to stay in the same Node. Based on python's igraph library.

Author:
  Cesar Martin and Adolfo Perera
See Also:
  - Original Paper
  - Original igraph implementation

- ## Nested Class Summary

  Nested Classes
  Modifier and Type
  Class
  Description
  `private class`
  `Walktrap.MutualConnectionsRecord`
  Stores the delta sigmas between a Community C connected to community 1 or community 2.

  ## Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

  `Algorithm.GraphSortOrder`

- ## Field Summary

  Fields
  Modifier and Type
  Field
  Description
  `private HashMap<Integer,HashMap<Node,Double>>`
  `Pv`
  `private int`
  `steps`

  ### Fields inherited from class edu.claflin.finder.algo.Algorithm

  `args, PROP_PROGRESS`

- ## Constructor Summary

  Constructors
  Constructor
  Description
  `Walktrap(ArgumentsBundle args)`

- ## Method Summary

  Modifier and Type
  Method
  Description
  `private HashMap<Node,Double>`
  `cprobs(List<Node> C, Graph graph, List<Node> nList)`
  Get a probability vector for a community.
  `private double`
  `delta_sigma(int C1index, int C2index, List<Node> nList, Communities cms)`
  Calculate delta sigma from communities C1 and C2 according to Section 4.2 Theorem 5 in the paper.
  `private double`
  `distance(int i, int j, List<Node> nList)`
  Compute the distance between community i and community j.
  `private int`
  `getDegree(Node n)`
  Get the Node degree.
  `private double`
  `getWeight(Node n)`
  Get the Node weight.
  `private HashMap<Node,Double>`
  `merge_probs(int i, int j, Communities cms)`
  Calculate the probability vectors of joining 2 communities.
  `ArrayList<Graph>`
  `process(Graph graph)`
  Processes data.
  `private void`
  `remove_node(HeapNodeWT info, PriorityQueue<HeapNodeWT> q)`
  Remove a HeapNode from the Queue.
  `String`
  `toString()`

  ### Methods inherited from class edu.claflin.finder.algo.clustering.ClusteringAlgorithm

  `buildCommunityGraphs, isWeighted`

  ### Methods inherited from class edu.claflin.finder.algo.Algorithm

  `addPropertyChangeListener, cull, getGraphSortOrder, getMinNodeCount, getPartiteNumber, getWeightName, removePropertyChangeListener, setGraphSortOrder, setMinNodeCount, setPartiteNumber, setProgress, setWeightName, zeropad`

  ### Methods inherited from class java.lang.Object

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

- ## Field Details

  - ### steps

    private int steps

  - ### Pv

    private HashMap<Integer,HashMap<Node,Double>> Pv

- ## Constructor Details

  - ### Walktrap

    public Walktrap(ArgumentsBundle args)

- ## Method Details

  - ### toString

    public String toString()
    Overrides:
      `toString` in class `Object`

  - ### process

    public ArrayList<Graph> process(Graph graph)
    Description copied from interface: `Processable`
    Processes data.
    Parameters:
      `graph` - the T type object to process.
    Returns:
      the S type object array produced by the processing.

  - ### remove_node

    private void remove_node(HeapNodeWT info, PriorityQueue<HeapNodeWT> q)
    Remove a HeapNode from the Queue.
    Parameters:
      `info` - the node to remove
      `q` - the priority queue to remove from

  - ### delta_sigma

    private double delta_sigma(int C1index, int C2index, List<Node> nList, Communities cms)
    Calculate delta sigma from communities C1 and C2 according to Section 4.2 Theorem 5 in the paper.
    Parameters:
      `C1index` - the index of community C1 in the list
      `C2index` - the index of community C2 in the list
      `nList` - the sorted Node list
      `cms` - the Communities
    Returns:
      the delta sigma between C1 and C2

  - ### getDegree

    private int getDegree(Node n)
    Get the Node degree. The algorithm counts the node itself as a degree.
    Parameters:
      `n` - the Node to get the degree of
    Returns:
      the degree of the Node counting itself

  - ### getWeight

    private double getWeight(Node n)
    Get the Node weight. The algorithm counts the node itself as having a weight of weight/degree.
    Parameters:
      `n` - the Node to get the weight of
    Returns:
      the weight of the Node counting its own

  - ### cprobs

    private HashMap<Node,Double> cprobs(List<Node> C, Graph graph, List<Node> nList)
    Get a probability vector for a community. The probabilities are of going from the community to all Nodes in a random walk of length steps instance variable. This is an adaptation of the int constructor of the Probabilities class in igraph master's walktrap_communities.cpp
    Parameters:
      `C` - the community
      `graph` - the original graph
      `nList` - the sorted list of Nodes
    Returns:
      the probability vector

  - ### merge_probs

    private HashMap<Node,Double> merge_probs(int i, int j, Communities cms)
    Calculate the probability vectors of joining 2 communities. Equation in section 4.4 of the paper (first bullet point). This is an adaptation of the 2 ints constructor of the Probabilities class in igraph master's walktrap_communities.cpp
    Parameters:
      `i` - index of community 1
      `j` - index of community 2
      `cms` - the Communities
    Returns:
      the new probability vector

  - ### distance

    private double distance(int i, int j, List<Node> nList)
    Compute the distance between community i and community j. This is an adaptation of the 2 ints constructor of the compute_distance of the Probabilities class in igraph master's walktrap_communities.cpp
    Parameters:
      `i` - index of community 1
      `j` - index of community 2
      `nList` - the sorted list of nodes
    Returns:
      the distance between the communities