compute_salsa: Compute SALSA hub and authority scores

In pagerankr: Modular Toolkit for PageRank Calculation

Compute SALSA hub and authority scores

Description

Computes the Stochastic Approach for Link-Structure Analysis (SALSA; Lempel & Moran 2001) hub and authority scores from a processed edge list. SALSA combines HITS-style mutual reinforcement with PageRank-style stochastic random walks on the bipartite hub/authority graph. This is the low-level computational core; the high-level [salsa()] wrapper runs the URL-cleaning, redirect/canonical folding, domain filtering, deduplication, and isolate-handling identity pipeline first.

Usage

compute_salsa(
  edge_list_df,
  vertices_df = NULL,
  from_col = "from",
  to_col = "to",
  vertex_col_name = "node_name",
  pr_node_col = "node_name",
  hub_col = "hub",
  authority_col = "authority"
)

Arguments

edge_list_df	A data frame representing the processed edge list, with source/target columns (see 'from_col', 'to_col'). NAs in those columns are omitted before graph construction.
vertices_df	An optional single-column data frame of node names defining the vertex set (e.g. to retain isolates). If 'NULL' (default), the vertices are inferred from 'edge_list_df'. The column name is given by 'vertex_col_name'.
from_col, to_col	Names of the source/target columns in 'edge_list_df'. Defaults '"from"' / '"to"'.
vertex_col_name	Name of the node column in 'vertices_df'. Default '"node_name"'.
pr_node_col	Name for the node column in the output. Default '"node_name"' (kept consistent with [compute_pagerank()]).
hub_col, authority_col	Names for the hub and authority score columns in the output. Defaults '"hub"' / '"authority"'.

Details

## The two SALSA Markov chains

SALSA builds an undirected bipartite graph \hat{G}: each crawl-graph edge u \rightarrow v contributes a hub-node u_h and an authority-node v_a joined by an edge. Two coupled random walks run on it. The **authority** chain alternates authority \rightarrow hub \rightarrow authority (one step = two traversals); the **hub** chain alternates the other way. Unlike HITS — whose scores are the dominant eigenvectors of A^\top A and A A^\top — each SALSA chain is *stochastic*, so its stationary distribution is the score vector.

## Closed form (no iteration)

Lempel & Moran (2001, Proposition 6) show the stationary distributions have a degree-based closed form, so **no eigenvector iteration is needed**. On a single connected component the authority score of a node is d_{in}(i) / W and the hub score is d_{out}(i) / W, where W is the edge count. When the support graph splits into several weakly connected components, each component's scores are renormalized within the component and then reweighted by the component's share of the relevant side (Proposition 6):

\tilde{\pi}_j = \frac{|A_{c(j)}|}{|A|} \times \frac{d_{in}(j)}{W_{c(j)}}

for authorities (and symmetrically for hubs with d_{out} and |H_c|), where A is the set of all authorities (in-degree > 0), A_{c(j)} the authorities in j's component, and W_{c(j)} the edges in that component. **This component reweighting is required for correctness:** without it, cross-component score comparisons are invalid — a common failure mode on site crawls with orphan page clusters. Each side's scores sum to '1'.

## Coverage and one-sided vertices

The hub side contains only nodes with out-degree > 0; the authority side only nodes with in-degree > 0. A node's 'hub' is 'NA' when its out-degree is '0', and its 'authority' is 'NA' when its in-degree is '0' (a pure sink has 'NA' hub; a pure source has 'NA' authority; an isolate has both 'NA'). SALSA coverage therefore differs from PageRank coverage on the same graph — this is expected, not a bug.

## Weighting

v1 is **unweighted**: the closed form assumes uniform edge weights, so scores are driven by in-/out-degree on the deduplicated simple graph. A weighted extension is deferred.

Value

A data frame with three columns: the node name (named by 'pr_node_col') and the hub and authority scores (named by 'hub_col' / 'authority_col'). Hub and authority each sum to '1' over their non-'NA' entries. Returns an empty (zero-row) data frame with those columns when the graph has no vertices.

References

Lempel, R. & Moran, S. (2001). SALSA: The Stochastic Approach for Link-Structure Analysis. *ACM Transactions on Information Systems*, 19(2), 131-160.

See Also

[salsa()] for the full identity pipeline; [compute_hits()] for the HITS analog; [compute_pagerank()] for the PageRank analog.

Examples

edges <- data.frame(
  from = c("A", "A", "B"), to = c("B", "C", "C")
)
compute_salsa(edges)

# Retain an isolate via vertices_df (NA hub and NA authority)
verts <- data.frame(node_name = c("A", "B", "C", "D"))
compute_salsa(edges, vertices_df = verts)

pagerankr documentation built on Oct. 1, 2026, 5:09 p.m.