RoleSim

RoleSim (Jin et al. 2014) is a generalization of SimRank that computes similarity using maximum matching between neighbor sets, making it sensitive to automorphic similarity.

Reference

• Jin, R., Lee, V. E., & Li, L. (2014). Scalable and axiomatic ranking of network role similarity. ACM Transactions on Knowledge Discovery from Data (TKDD), 8(1), 1-37.

Optimized Source Code

This optimized version pre-calculates neighbor lists and uses a more robust approach to matching neighbor similarities, significantly improving performance and reliability.

RoleSim <- function(w, beta = 0.5) {
  n <- nrow(w)
  do <- rowSums(w)
  di <- colSums(w)
  
  # Pre-calculate neighbor indices
  out_neigh <- lapply(1:n, function(i) which(w[i, ] == 1))
  in_neigh  <- lapply(1:n, function(i) which(w[, i] == 1))
  
  z <- matrix(1, n, n)
  delta <- 1
  
  while (delta > 1e-10) {
    z_o <- z
    z_new <- matrix(0, n, n)
    
    for (i in 1:n) {
      for (j in i:n) {
        if (i == j) {
          z_new[i, j] <- 1
          next
        }
        
        # Calculate similarity contribution from neighbors
        mu_o <- 0
        if (length(out_neigh[[i]]) > 0 && length(out_neigh[[j]]) > 0) {
          sub_o <- z_o[out_neigh[[i]], out_neigh[[j]], drop = FALSE]
          # Match neighbors
          mu_o <- sum(apply(sub_o, 1, max)) + sum(apply(sub_o, 2, max))
          mu_o <- mu_o / 2 
        }
        
        mu_i <- 0
        if (length(in_neigh[[i]]) > 0 && length(in_neigh[[j]]) > 0) {
          sub_i <- z_o[in_neigh[[i]], in_neigh[[j]], drop = FALSE]
          mu_i <- sum(apply(sub_i, 1, max)) + sum(apply(sub_i, 2, max))
          mu_i <- mu_i / 2
        }
        
        denom <- max(do[i], do[j]) + max(di[i], di[j])
        z_new[i, j] <- if(denom > 0) (beta * (mu_o + mu_i) / denom) + (1 - beta) else (1 - beta)
      }
    }
    # Reflect and update
    z_new[lower.tri(z_new)] <- t(z_new)[lower.tri(z_new)]
    delta <- sum(abs(z_new - z_o))
    z <- z_new
  }
  return(z)
}