rwclust {Rwclust}

Sharpen the edge weights of a weighted graph.

Description

Sharpens the weights of a weighted graph for later pruning.

Usage

rwclust(x, iter = 5, k = 3, similarity = "hk")

## S3 method for class 'data.frame'
rwclust(x, iter = 5, k = 3, similarity = "hk")

## S3 method for class 'matrix'
rwclust(x, iter = 5, k = 3, similarity = "hk")

Arguments

x

matrix or dataframe with three columns

1. vertex label (integer)

2. vertex label (integer)

3. edge weights (float)

iter

integer, number of iterations

k

integer, maximum length of random walk

similarity

string, the name of the similarity metric used to update weights

Value

list

weights

A vector of the updated edge weights

adj

Updated adjacency matrix containing updated weights

Details

Internally, the edgelist passed to rwclust is converted into a transition matrix, whose powers are used to compute the probability of reaching a vertex u from vertex v in k steps for all v and u. New edge weights are computed using the similarity between these "walk probabilities" for each pair of vertices. The intuition is that vertices who have similar neighborhoods in terms of random walk reachability are similar to each other.

The returned weights can be used for clustering by deleting edges with weights below a certain threshold. The connected components of the resulting graph form the clusters.

References

Harel, David, and Yehuda Koren. "On clustering using random walks." International Conference on Foundations of Software Technology and Theoretical Computer Science. Springer, Berlin, Heidelberg, 2001.