Compute SALSA hub and authority scores

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"`.

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.

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.

References

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

Examples