Hubs & Authorities

An alternative reputation algorithm for bipartite graphs

The OpenRank SDK—specifically, its EigenTrust algorithm—uses the notion of local trust, as a graph where one peer expresses its explicit or implied trust to another peer. This assumes that each node in the graph is an actor whose trust can be naturally defined.

In real-life scenarios, trusted entities are not necessarily actors. Other non-actor entities are also trusted, so they can appear in the local trust graph, where they can accept inbound local trust.

Hubs and Authorities (H&A) is a reputation algorithm for bipartite graphs, where edges connect two types of nodes, such as people and books. It defines a good book as one liked by good readers, and a good reader as one who likes good books.

The underlying math is very similar to using eugentrust and hubs and authority so we can reuse the same eigentrust function to also run Hubs and Authorities.

Key Participants:

1. Hubs: Nodes that point to other nodes (e.g., readers who like books).

2. Authorities: Nodes that contain useful information (e.g., books liked by readers).

Scores for hubs are based on their links to authorities, and scores for authorities are based on incoming links from hubs. Initially, all nodes have equal importance, with scores set to 1.

Scoring Process:

1. Hubs' Scores: Derived from outgoing links to authorities.

2. Authorities' Scores: Derived from incoming links from hubs.

3. Normalization: Scores are normalized after each iteration to prevent them from becoming excessively large.

Adjacency Matrix: Represents connections between nodes, used to update scores iteratively until convergence.

Outcome: Determines good readers and good books, based on the principle that good books are read by many readers, and good readers read good books.

Limitations: H&A is susceptible to manipulation by sybil actors who can falsely inflate their scores by claiming to like good books. This requires further optimizations for scalable use.

For more information, refer here.

There are 3 main flavors for Hubs and Authorities

1. Simplified Hubs & Authorities - explained in the next section.
2. Fully Convergent Hubs & Authorities (HITS)

3. Interest and Credit (Inspired by H&A and sybil resistant)

Simplified and Fully Convergent Hubs & Authorities algorithms are both prone to sybil.