Package it.unimi.dsi.law.rank

Class Salsa

java.lang.Object
it.unimi.dsi.law.rank.Salsa
public class Salsa
extends Object
Computes the SALSA score using a non-iterative method.

This class implements a direct computation of the SALSA score. The method used is based on the description given by Ron Lempel and Shlomo Moran in Proposition 2 of “The stochastic approach for link-structure analysis (SALSA) and the TKC effect”, Computer Networks, 33(1):387−401, 2000, Elsevier.

First, the connected components of the symmetric graph underlying the matrix GTG are identified. Then, each nodes gets a first score that is proportional to its indegree in G (not in GTG) so that the sum of the scores on each component is one. Finally, the first score of each node is scaled proportionally to the size of the connected component it belongs to.

We remark that this implementation needs a single sequential pass on the graph. The computational cost is entirely concentrated in the computation of the connected components defined above, as it requires to enumerate the neighbourhoods of all nodes of the graph, and, for each pair of vertices in a neighbourhood, to add a virtual arc to a union-find data structure. At the same time, we compute the indegree of each node, which is then scaled as explained above to obtain the final rank.