{"id":192,"date":"2025-11-24T00:57:20","date_gmt":"2025-11-24T00:57:20","guid":{"rendered":"http:\/\/ijeesoo.com\/?page_id=192"},"modified":"2025-11-24T02:27:48","modified_gmt":"2025-11-24T02:27:48","slug":"link-analysis","status":"publish","type":"page","link":"http:\/\/ijeesoo.com\/?page_id=192","title":{"rendered":"Link Analysis"},"content":{"rendered":"\n
\n
\n

Why Links Matter<\/h1>\n\n\n\n
<\/div>\n\n\n\n
    \n
  • Core Principle:<\/strong>Links are not just navigation paths; they are implicit endorsements<\/strong> and votes of confidence<\/strong>.<\/li>\n\n\n\n
  • Structural Signals:<\/strong>They provide a rich structural layer that complements content (keyword) analysis.<\/li>\n\n\n\n
  • Authority & Quality:<\/strong>Link analysis allows search engines to quantify the importance<\/em> and quality<\/em>of a page.\n
      \n
    • A link from an authoritative source transfers trust and relevance.<\/li>\n\n\n\n
    • Crucial for solving the Quality\/Authority<\/strong>problem in search ranking.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
      <\/div>\n\n\n\n

      <\/p>\n<\/div>\n\n\n\n

      \n

      Historical Context: A Breakthrough<\/h1>\n\n\n\n
      <\/div>\n\n\n\n
        \n
      • Pre-Link Analysis (The Past):<\/strong>Ranking was based almost entirely on term frequency, density, and content matching. This was highly vulnerable to keyword stuffing and manipulation.<\/li>\n<\/ul>\n\n\n\n
          \n
        • The Breakthrough (Late 1990s):<\/strong>The introduction of link analysis (specifically PageRank and HITS) revolutionized ranking.<\/li>\n<\/ul>\n\n\n\n
            \n
          • The Change:<\/strong>It introduced an intrinsic, query-independent measure of importance<\/strong> that was difficult to artificially inflate, leading to significantly better search quality.<\/li>\n<\/ul>\n\n\n\n
            <\/div>\n\n\n\n

            <\/p>\n<\/div>\n\n\n\n

            \n

            The Web as a Graph<\/h1>\n\n\n\n
            <\/div>\n\n\n\n
              \n
            • Definition:<\/strong>The entire World Wide Web can be modeled as a massive, directed graph.<\/li>\n\n\n\n
            • Nodes (Vertices):<\/strong>Represent individual web pages, documents, or resources (e.g., a specific URL).<\/li>\n\n\n\n
            • Edges (Directed Links):<\/strong>Represent the hyperlinks connecting the pages.\n
                \n
              • The connection is directed<\/strong>: A link from A to B is not the same as a link from B to A.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
              • Structure:<\/strong>The web graph is characterized by its enormous scale<\/strong>, high sparsity<\/strong>(few links per page), and complex connectivity<\/strong>.\n
                  \n
                • <\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                  \n
                  \n

                  Introduction to Link Analysis<\/h2>\n\n\n\n
                  <\/div>\n<\/div>\n\n\n\n
                  <\/div>\n\n\n\n
                  \n
                  \n

                  The Web as a Graph<\/h3>\n\n\n\n

                  7<\/p>\n<\/div>\n\n\n\n

                  \n

                  PageRank<\/h3>\n\n\n\n

                  18<\/p>\n<\/div>\n\n\n\n

                  \n

                  Hubs and Authorities (HITS Algorithm)<\/h3>\n\n\n\n

                  6<\/p>\n<\/div>\n<\/div>\n\n\n\n

                  <\/div>\n\n\n\n
                  \n
                  \n

                  Hubs and Authorities (HITS Algorithm)\u2014Choosing the Subset of the Web<\/h3>\n\n\n\n

                  3<\/p>\n<\/div>\n\n\n\n

                  \n

                  Advanced Link-Based Models<\/h3>\n\n\n\n

                  6<\/p>\n<\/div>\n\n\n\n

                  \n

                  Link Analysis Beyond Web Search<\/h3>\n\n\n\n

                  3<\/p>\n<\/div>\n<\/div>\n\n\n\n

                  \n
                  \n

                  Modern Trends in Link Analysis<\/h3>\n\n\n\n

                  3<\/p>\n<\/div>\n\n\n\n

                  \n

                  Evaluation and Critiques<\/h3>\n\n\n\n

                  3<\/p>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

                  \n
                  \n
                  \n

                  The Web as a Graph<\/h2>\n<\/div>\n\n\n\n
                  <\/div>\n\n\n\n
                  \n
                  \n

                  Structural Properties: Scale and Sparsity<\/h3>\n\n\n\n
                    \n
                  • Scale (Massive Size):<\/strong>The graph contains billions of nodes (pages) and trillions of edges (links). Processing this scale requires distributed computing (e.g., MapReduce).<\/li>\n\n\n\n
                  • Sparsity:<\/strong>The transition matrix representing the graph is extremely sparse.\n
                      \n
                    • Sparsity means the number of actual links is tiny compared to the total possible number of links between all pages.<\/li>\n\n\n\n
                    • This property is key for efficient storage and computation.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                      \n

                      Structural Properties: Connectivity<\/h3>\n\n\n\n
                        \n
                      • The Bow-Tie Structure (Connectivity):<\/strong>Research shows the Web is not uniformly connected but resembles a “bow tie.”\n
                          \n
                        • SCC (Strongly Connected Component):<\/strong>A large core where every page is reachable from every other page.<\/li>\n\n\n\n
                        • IN Component:<\/strong>Pages that link into<\/strong>the SCC.<\/li>\n\n\n\n
                        • OUT Component:<\/strong>Pages that are linked out of<\/strong>the SCC.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                        • Power-Law Distribution:<\/strong>The distribution of incoming links (in-degree) follows a power law.\n
                            \n
                          • A very few pages (hubs like Wikipedia, major news sites) have a disproportionately large number of incoming links.<\/li>\n\n\n\n
                          • Most pages have very few incoming links.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                            <\/div>\n\n\n\n
                            \n
                            \n

                            Directed vs. Undirected Graphs<\/h3>\n\n\n\n
                              \n
                            • Directed Graph (The Reality):<\/strong>The Web is inherently directed.\n
                                \n
                              • A link from Page A to Page B ($A \\to B$) does not imply a reciprocal link ($B \\to A$).<\/li>\n\n\n\n
                              • Link analysis algorithms like PageRank rely entirely on this directionality to model the flow of authority.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                              • Undirected View (For Modeling):<\/strong>Occasionally, the graph can be treated as undirected to analyze relationships like co-citation or similarity, but never for authoritative ranking.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                \n

                                Components and Problems<\/h3>\n\n\n\n
                                  \n
                                • Strongly Connected Components (SCCs):<\/strong>Sets of pages where you can start at any page and reach any other page within the set by following links. Pages within an SCC share and circulate authority effectively.<\/li>\n\n\n\n
                                • Dangling Nodes (Sink Nodes):<\/strong>These are pages that have incoming links but no outgoing links<\/strong>.\n
                                    \n
                                  • Problem:<\/strong>In the random surfer model (used by PageRank), the surfer gets “stuck” here, leading to non-convergence or rank leakage.<\/li>\n\n\n\n
                                  • Solution:<\/strong>Algorithms handle these nodes by assuming a jump (teleportation) to a random page.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                    \n
                                    \n

                                    Anchor Text: Definition and Role<\/h3>\n\n\n\n
                                      \n
                                    • Definition:<\/strong>Anchor text is the clickable, visible text within a hyperlink tag.\n
                                        \n
                                      • Example: <a href=”www.target.com”>**This is the Anchor Text**<\/a><\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                      • Role:<\/strong>Anchor text acts as a label or description<\/strong>provided by the linking page<\/em>to describe the content of the target page<\/em>.<\/li>\n\n\n\n
                                      • Why it’s powerful:<\/strong>It is often a concise, human-generated summary of the target page’s content, which can be more accurate than the target page’s own title or metadata.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                        \n

                                        Anchor Text as a Relevance Signal<\/h3>\n\n\n\n
                                          \n
                                        • Aggregation:<\/strong>Search engines aggregate all anchor text pointing to a single page.\n
                                            \n
                                          • This aggregated text is treated as a highly trusted set of keywords associated with the target page.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                          • Relevance:<\/strong>It is a powerful signal for query relevance. If hundreds of external sites use the phrase “best travel guides” in their anchor text when linking to a specific blog, that blog is highly relevant for that query.<\/li>\n\n\n\n
                                          • Combining Signals:<\/strong>Anchor text is one of the most effective ways to combine the content of one page (the anchor) with the authority of the target page.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                            \n
                                            \n

                                            Retrieval and Ranking Examples<\/h3>\n\n\n\n
                                              \n
                                            • Example 1: Wikipedia:<\/strong>Wikipedia pages are highly authoritative (high PageRank) and receive links with descriptive anchor text (e.g., “Battle of Hastings”). This combination makes them rank highly for relevant, specific queries.<\/li>\n\n\n\n
                                            • Example 2: Corporate Pages:<\/strong>A company’s homepage might not contain the phrase “Investor Relations,” but if all financial news sites link to it using that phrase as anchor text, the page will rank for that query.<\/li>\n\n\n\n
                                            • Ranking Mechanism:<\/strong>The anchor text terms are treated as if they were part of the target page’s document index, allowing content-based search engines to leverage link structure indirectly.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n
                                              \n
                                              \n

                                              PageRank<\/h2>\n<\/div>\n\n\n\n
                                              <\/div>\n\n\n\n
                                              \n
                                              \n

                                              PageRank: The Core Intuition<\/h3>\n\n\n\n
                                                \n
                                              • Definition:<\/strong>PageRank (PR) is an algorithm that measures the intrinsic importance<\/strong> or authority<\/strong> of a web page based on its link structure.<\/li>\n\n\n\n
                                              • Intuition: “Votes” are Weighted:<\/strong>A page is important if it is linked to by many pages, and especially if it is linked to by many important<\/strong> pages.\n
                                                  \n
                                                • A link from CNN is worth far more than a link from a new personal blog.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                • Recursive Definition:<\/strong>The rank of a page depends on the ranks of the pages linking to it. This recursive dependency forms the basis of the calculation.<\/li>\n\n\n\n
                                                • Core Principle:<\/strong>A page gains a high rank if it is linked to by many pages that already<\/em>have high rank. Links act as endorsements, and the value of that endorsement is proportional to the source page’s own rank.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                  \n

                                                  Simple PageRank<\/h3>\n\n\n\n
                                                  \"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                  <\/div>\n\n\n\n
                                                  \n
                                                  \n

                                                  PageRank (Suffers “Rank Sink” Problem)<\/h3>\n\n\n\n
                                                    \n
                                                  • The Flaw: Rank Sink Problem:<\/strong>The Simple PageRank algorithm suffers from a critical flaw when dealing with pages that have no outgoing links (Dangling Nodes).\n
                                                      \n
                                                    • Mechanism:<\/strong>If a page only points to itself (or simply has no out-links), the rank it accumulates is trapped<\/strong>at that node and cannot be redistributed to the rest of the web.<\/li>\n\n\n\n
                                                    • Consequence:<\/strong>This “rank sink” causes the total rank across the entire web graph to gradually drain away, leading to a system where the total rank is no longer conserved, and the ranks of other pages are unfairly reduced.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                      \n

                                                      Teleportation<\/h3>\n\n\n\n
                                                      \"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                      \n
                                                      \n

                                                      The Random Surfer Model<\/h3>\n\n\n\n
                                                      \"\"<\/figure>\n<\/div>\n\n\n\n
                                                      \n

                                                      Importance of Link-Based Ranking<\/h3>\n\n\n\n
                                                        \n
                                                      • Query-Independent Authority:<\/strong>PageRank calculates a score for every page before<\/strong>a user enters a query. This score measures the page’s general, global authority.<\/li>\n\n\n\n
                                                      • Separation of Concerns:<\/strong>It cleanly separates the concepts of:\n
                                                          \n
                                                        • \u2022Authority (Quality):<\/strong>Measured by PageRank (link structure).<\/li>\n\n\n\n
                                                        • \u2022Relevance (Topic):<\/strong>Measured by keyword matching (content).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                        • Breakthrough:<\/strong>This pre-computed authority score provides a robust mechanism to combat content spam, as spammers cannot easily manipulate external links.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                                          \n
                                                          \n

                                                          Markov Chains: The Basics<\/h3>\n\n\n\n
                                                            \n
                                                          • Formal Model:<\/strong>The random surfer model is mathematically equivalent to a Markov Chain<\/strong>.<\/li>\n\n\n\n
                                                          • States:<\/strong>The states in the chain are the individual web pages.<\/li>\n\n\n\n
                                                          • Memoryless Property:<\/strong>The probability of moving to the next page depends only<\/em>on the current page, not on the sequence of pages visited previously.<\/li>\n\n\n\n
                                                          • Transition Matrix (<\/strong>M<\/em><\/strong>):<\/strong>This matrix represents all links in the web graph.\n
                                                              \n
                                                            • An entryM<\/em>ij<\/em>is the probability of moving from page j<\/em>to page i<\/em>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                              \n

                                                              Transition Probabilities<\/h3>\n\n\n\n
                                                              \"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                              \n
                                                              \n

                                                              Steady-State and Connection to PageRank<\/h3>\n\n\n\n
                                                              \"\"<\/figure>\n\n\n\n
                                                                \n
                                                              • <\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                \n

                                                                Iterative Computation (Power Iteration)<\/h3>\n\n\n\n
                                                                \"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                                \n
                                                                \n

                                                                Handling Dangling Nodes<\/h3>\n\n\n\n
                                                                \"\"<\/figure>\n<\/div>\n\n\n\n
                                                                \n

                                                                The Damping Factor (d<\/em>)<\/h3>\n\n\n\n
                                                                \"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                                \n
                                                                \n

                                                                Convergence and Stability<\/h3>\n\n\n\n
                                                                  \n
                                                                • Convergence Speed:<\/strong>The PageRank algorithm typically converges relatively quickly\u2014usually within 50 to 100 iterations\u2014to an acceptable tolerance level, even for the massive web graph.<\/li>\n\n\n\n
                                                                • Stability:<\/strong>The d<\/em>factor ensures numerical stability. The PageRank scores change slowly over time because the underlying link structure of the web is relatively stable.<\/li>\n\n\n\n
                                                                • Update Frequency:<\/strong>Because the computation is massive, PageRank is not calculated in real-time. It’s recomputed periodically (e.g., weekly or monthly) on the latest snapshot of the web graph, and these pre-computed scores are used in the live ranking system.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                  \n

                                                                  Scalability and Large-Scale Computation<\/h3>\n\n\n\n
                                                                    \n
                                                                  • The Bottleneck:<\/strong>The primary challenge is not the complexity of the algorithm but the sheer size<\/strong>of the transition matrix (billions of edges).<\/li>\n\n\n\n
                                                                  • Distributed Computing:<\/strong>PageRank calculation is performed using distributed processing frameworks<\/strong>like MapReduce(or similar modern big data platforms).<\/li>\n\n\n\n
                                                                  • MapReduceImplementation:<\/strong>\n
                                                                      \n
                                                                    • Map Phase:<\/strong>Each page is processed by a mapper which “maps” its current PageRank score and distributes it to all pages it links to, along with the transition probability.<\/li>\n\n\n\n
                                                                    • Reduce Phase:<\/strong>The reducer gathers all incoming rank contributions for a specific page i<\/em>and sums them up to calculate the new PR<\/strong>(i<\/em>) for the next iteration.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                    • This approach effectively parallelizes the large matrix-vector multiplication, making the computation feasible across thousands of servers.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                                                      \n
                                                                      \n

                                                                      Motivation: Why Context Matters<\/h3>\n\n\n\n
                                                                        \n
                                                                      • The Limitation of Global PageRank:<\/strong>Standard PageRank assigns a single “authority score” to every page. It assumes that if a page is important, it is universally important.<\/li>\n\n\n\n
                                                                      • The Context Problem:<\/strong>Authority is inherently topic-dependent<\/strong>.\n
                                                                          \n
                                                                        • Example:<\/em>A highly authoritative page about “Jaguar cars” might receive a high global PageRank, but it is irrelevant to a user researching “Jaguar” the animal.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                        • The Goal:<\/strong>To move from “Global Importance” to “Contextual Importance,”<\/strong>ensuring that ranking reflects authority within a specific domain<\/em> of interest rather than just general popularity across the entire web.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                          \n

                                                                          Topic-Sensitive PageRank (TSPR)<\/h3>\n\n\n\n
                                                                            \n
                                                                          • The Mechanism: Biased Teleportation:<\/strong>\n
                                                                              \n
                                                                            • In standard PageRank, the random surfer teleports to any<\/em>page with equal probability (1\/N<\/em>) when they get bored.<\/li>\n\n\n\n
                                                                            • In TSPR, we restrict the teleportation set to a specific Topic<\/strong>(e.g., “Sports” or “Cooking”).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                            • The Seed Set (<\/strong>S<\/em><\/strong>):<\/strong>A set of pages pre-classified as highly relevant to a given topic (e.g., based on directory listings).<\/li>\n\n\n\n
                                                                            • The Calculation:<\/strong>When the random surfer “teleports,” they jump exclusively to one of these seed pages in set S. This biases the entire rank distribution towards pages that are topologically close to the topic seeds.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                                                              \n
                                                                              \n

                                                                              Personalized PageRank (PPR)<\/h3>\n\n\n\n
                                                                                \n
                                                                              • User-Specific Bias:<\/strong>PPR extends the TSPR idea from a topic to an individual user’s interests<\/strong>.<\/li>\n\n\n\n
                                                                              • The Personalized Seed Set (<\/strong>P<\/em><\/strong>):<\/strong>The teleport set P<\/em>is determined by the user’s history, profile, bookmarks, or recent searches.<\/li>\n\n\n\n
                                                                              • The Mechanism:<\/strong>The random surfer is biased to jump back to pages the specific user<\/em>has previously deemed important or relevant.<\/li>\n\n\n\n
                                                                              • Result:<\/strong>This results in a unique PageRank vector calculated for each user or group, providing rankings tailored to their personal preferences and interests.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                                \n

                                                                                Applications in Search and Recommendation<\/h3>\n\n\n\n
                                                                                  \n
                                                                                • \uf0b7Focused Search:<\/strong>TSPR is used to pre-calculate multiple PageRank vectors (e.g., TSPR-Science, TSPR-Arts). When a user submits a query, the system classifies the intent<\/em>and uses the corresponding TSPR vector to weight results, boosting relevant domain authorities.<\/li>\n\n\n\n
                                                                                • \uf0b7Recommendation Systems:<\/strong>PPR can be used to recommend new content. Pages that have high PPR scores relative to a user’s interest profile but low global PageRank are excellent candidates for discovery.<\/li>\n\n\n\n
                                                                                • \uf0b7Example:<\/strong>TSPR helps a search for “Mars” by prioritizing pages authoritative in “Astronomy” over those authoritative in “Candy Bars,” ensuring topical relevance is reinforced by link structure.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n
                                                                                  \n
                                                                                  \n

                                                                                  Hubs and Authorities (HITS Algorithm)<\/h2>\n<\/div>\n\n\n\n
                                                                                  <\/div>\n\n\n\n
                                                                                  \n
                                                                                  \n

                                                                                  Concept of Hubs and Authorities<\/h3>\n\n\n\n
                                                                                  \"\"<\/figure>\n<\/div>\n\n\n\n
                                                                                  \n

                                                                                  The Intuition: Mutually Recursive Relationship<\/h3>\n\n\n\n
                                                                                    \n
                                                                                  • The Core Philosophy:<\/strong>The definitions of Hubs and Authorities are circular and mutually reinforcing:\n
                                                                                      \n
                                                                                    • A Good Hub<\/strong>is a page that points to many Good Authorities<\/strong>.<\/li>\n\n\n\n
                                                                                    • A Good Authority<\/strong>is a page that is pointed to by many Good Hubs<\/strong>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                    • Recursive Quality:<\/strong>You cannot calculate one without the other. The algorithm exploits this relationship to identify high-quality communities of pages relevant to a specific query.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                                                                      <\/div>\n\n\n\n
                                                                                      \n
                                                                                      \n

                                                                                      HITS Algorithm Step 1: Constructing the Graph<\/h3>\n\n\n\n
                                                                                        \n
                                                                                      • Root Set:<\/strong>The algorithm starts by retrieving a small set of relevant pages (e.g., the top 200 results) from a standard text-based search engine for the user’s query.<\/li>\n\n\n\n
                                                                                      • Expansion to Base Set:<\/strong>To capture the link structure, the Root Set is expanded to form the Base Set<\/strong>:\n
                                                                                          \n
                                                                                        • Add any page that links to<\/em>a page in the Root Set.<\/li>\n\n\n\n
                                                                                        • Add any page that is linked to by<\/em>a page in the Root Set.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                        • Goal:<\/strong>This creates a focused subgraph of the web that contains the most relevant communities for that specific query.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                                          \n

                                                                                          HITS Algorithm Step 2: Iterative Updates<\/h3>\n\n\n\n
                                                                                          \"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n
                                                                                          \n
                                                                                          \n

                                                                                          Normalization step HITS algorithm (Part step 2 Previous slide): Controlling Score Growth<\/h3>\n\n\n\n
                                                                                            \n
                                                                                          • The Problem:<\/strong>The iterative update process (where Hub scores sum Authorities, and Authority scores sum Hubs) causes the scores to increase rapidly with every step. If left unchecked, all scores would quickly approach infinity, losing their comparative meaning.<\/li>\n\n\n\n
                                                                                          • The Solution:<\/strong>After every Authority Update step and every Hub Update step, the scores must be normalized<\/strong>. This ensures the resulting scores are scaled back into a comparable range, usually between 0 and 1.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                                            \n

                                                                                            Normalization step HITS algorithm: Controlling Score Growth<\/h3>\n\n\n\n
                                                                                            \"\"<\/figure>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n
                                                                                            \n
                                                                                            \n

                                                                                            Hubs and Authorities (HITS Algorithm)\u2014Choosing the Subset of the Web<\/h2>\n<\/div>\n\n\n\n
                                                                                            <\/div>\n\n\n\n
                                                                                            \n
                                                                                            \n

                                                                                            Query-Dependent Subgraph Selection<\/h3>\n\n\n\n
                                                                                            \"\"<\/figure>\n<\/div>\n\n\n\n
                                                                                            \n

                                                                                            Practical Considerations and Limitations<\/h3>\n\n\n\n
                                                                                              \n
                                                                                            • Computational Cost:<\/strong>Because the graph is query-specific, the HITS algorithm must be run in real-time<\/strong>after the user submits a query. This makes it significantly slower and more computationally expensive than pre-computed algorithms like PageRank.<\/li>\n\n\n\n
                                                                                            • Topic Drift:<\/strong>A major limitation is “Topic Drift.” If the Root Set contains a few pages from a very tightly-knit but irrelevant community (e.g., a general query about “Jaguars” drifting entirely into “Jaguar Cars” due to strong linking among car sites), the algorithm can converge on the wrong topic, ignoring the user’s broader intent.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                                                                              <\/div>\n\n\n\n
                                                                                              \n
                                                                                              \n

                                                                                              Vulnerabilities: Link Spam and SEO<\/h3>\n\n\n\n
                                                                                              \"\"<\/figure>\n\n\n\n
                                                                                                \n
                                                                                              • <\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n
                                                                                                \n
                                                                                                \n

                                                                                                Advanced Link-Based Models<\/h2>\n<\/div>\n\n\n\n
                                                                                                <\/div>\n\n\n\n
                                                                                                \n
                                                                                                \n

                                                                                                TrustRank: Combatting Web Spam<\/h3>\n\n\n\n
                                                                                                \"\"<\/figure>\n\n\n\n
                                                                                                  \n
                                                                                                • <\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                                                  \n

                                                                                                  TrustRank: Combatting Web Spam<\/h3>\n\n\n\n
                                                                                                    \n
                                                                                                  • The Challenge:<\/strong>“Link Farms” and spam pages artificially inflate PageRank, making standard link analysis unreliable for quality control.<\/li>\n\n\n\n
                                                                                                  • The Semi-Supervised Approach:<\/strong>TrustRankassumes that good pages rarely link to bad pages.\n
                                                                                                      \n
                                                                                                    • Oracle Set:<\/strong>Start with a small, manually verified set of trustworthy “seed” pages (e.g., universities, government sites).<\/li>\n\n\n\n
                                                                                                    • Trust Propagation:<\/strong>Propagate trust scores outward from these seeds using a biased PageRank calculation.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                    • Trust Attenuation:<\/strong>Trust dampens as it moves further from the seed set. A page 1 click away from a seed is highly trusted; a page 5 clicks away is less so.<\/li>\n\n\n\n
                                                                                                    • Spam Mass:<\/strong>By comparing a page’s standard PageRank with its TrustRank, we can estimate its “Spam Mass”\u2014the portion of its rank likely derived from manipulation.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                                                                                      <\/div>\n\n\n\n
                                                                                                      \n
                                                                                                      \n

                                                                                                      TrustRank\u2014The Algorithm<\/h3>\n\n\n\n
                                                                                                        \n
                                                                                                      • The Algorithm:<\/strong>\n
                                                                                                          \n
                                                                                                        • Seed Selection:<\/strong>Identify a small, high-quality set of trusted “Seed Pages” (e.g., .gov, .edusites) that are manually verified as non-spam.<\/li>\n\n\n\n
                                                                                                        • Biased PageRank:<\/strong>Run a modified PageRank calculation where the random surfer teleports only<\/em>to these trusted seed pages (similar to Topic-Sensitive PageRank).<\/li>\n\n\n\n
                                                                                                        • Trust Attenuation:<\/strong>Trust scores decrease as you move further away from the seed set. Pages with high TrustRankscores are legitimate; those with low scores are potential spam.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                        • Application:<\/strong>Used primarily to filter out spam from search results and demote pages involved in manipulative linking schemes.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                                                          \n

                                                                                                          SALSA (Stochastic Approach for Link-Structure Analysis)<\/h3>\n\n\n\n
                                                                                                            \n
                                                                                                          • The Problem with HITS:<\/strong>The original HITS algorithm is vulnerable to the “Tightly Knit Community” (TKC) effect, where a small group of mutually linking pages (even if irrelevant) can dominate the results.<\/li>\n\n\n\n
                                                                                                          • The SALSA Solution:<\/strong>SALSA modifies HITS by casting the problem as a Random Walk<\/strong>on a bipartite graph of hubs and authorities.<\/li>\n\n\n\n
                                                                                                          • Mechanism:<\/strong>Instead of summing all scores (which causes explosion), SALSA normalizes the link weights based on the number of links.\n
                                                                                                              \n
                                                                                                            • It divides the authority weight by the number of in-links and hub weight by the number of out-links.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                            • Result:<\/strong>This stochastic approach is significantly more stable and less prone to manipulation or topic drift than the original HITS algorithm.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n\n\n\n
                                                                                                              \n
                                                                                                              \n

                                                                                                              Integration with Content-Based Signals<\/h3>\n\n\n\n
                                                                                                                \n
                                                                                                              • Authority vs. Relevance:<\/strong>Link analysis measures static<\/em>global authority, but it doesn’t inherently measure relevance<\/em>to a specific user query.<\/li>\n\n\n\n
                                                                                                              • The Hybrid Signal:<\/strong>Modern search engines do not rank by PageRank alone.\n
                                                                                                                  \n
                                                                                                                • Relevance Score:<\/strong>Computed using content models (TF-IDF, BM25, BERT) based on query term matching.<\/li>\n\n\n\n
                                                                                                                • Quality Score:<\/strong>Computed using link models (PageRank, TrustRank).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                                • Ranking Fusion:<\/strong>The final rank is a function (often determined by Machine Learning \/ Learning-to-Rank models) that combines these signals. A page needs both<\/strong>high relevance and high authority to rank well.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                                                                  \n

                                                                                                                  Anchor Text Weighting and Hybrid Approaches<\/h3>\n\n\n\n
                                                                                                                    \n
                                                                                                                  • Weighted Links:<\/strong>Not all links are created equal. Advanced models assign different weights to edges based on the Anchor Text<\/strong>.\n
                                                                                                                      \n
                                                                                                                    • A link with anchor text “click here” carries less topical weight than a link with anchor text “neuroscience research paper.”<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                                    • Structural Weighting:<\/strong>Links are also weighted by their position:\n
                                                                                                                        \n
                                                                                                                      • Editorial Links:<\/strong>Links inside the main body text are trusted more (higher weight).<\/li>\n\n\n\n
                                                                                                                      • Navigational Links:<\/strong>Links in footers or sidebars are trusted less (lower weight).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                                      • Hybrid Graph Models:<\/strong>Newer approaches construct heterogeneous graphs that include not just pages, but users, queries, and clicks as nodes, allowing link analysis to propagate through user behavior data as well as web structure.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n
                                                                                                                        \n
                                                                                                                        \n

                                                                                                                        Link Analysis Beyond Web Search<\/h2>\n<\/div>\n\n\n\n
                                                                                                                        <\/div>\n\n\n\n
                                                                                                                        \n
                                                                                                                        \n

                                                                                                                        Citation Analysis in Academic Publishing<\/h3>\n\n\n\n
                                                                                                                          \n
                                                                                                                        • The Origin of Link Analysis:<\/strong>Web link analysis was heavily inspired by bibliometrics\u2014the statistical analysis of academic citations.<\/li>\n\n\n\n
                                                                                                                        • Direct Parallels:<\/strong>\n
                                                                                                                            \n
                                                                                                                          • Paper = Node:<\/strong>Each academic paper is a node in the citation graph.<\/li>\n\n\n\n
                                                                                                                          • Citation = Link:<\/strong>A citation from Paper A to Paper B is a directed edge, signaling “credit” or “prior art.”<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                                          • Metrics:<\/strong>\n
                                                                                                                              \n
                                                                                                                            • Impact Factor:<\/strong>Similar to in-degree centrality, measuring the average number of citations received by articles in a journal.<\/li>\n\n\n\n
                                                                                                                            • h-index:<\/strong>A metric for author-level authority, balancing productivity (number of papers) and citation impact (number of links).<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                                            • Bibliographic Coupling & Co-citation:<\/strong>These concepts (papers citing the same work, or being cited together) are the direct ancestors of the HITS hub\/authority model.<\/li>\n<\/ul>\n<\/div>\n\n\n\n
                                                                                                                              \n

                                                                                                                              Social Network Analysis (SNA) Parallels<\/h3>\n\n\n\n
                                                                                                                                \n
                                                                                                                              • Mapping the Social Graph:<\/strong>Link analysis algorithms are directly applicable to social networks (Twitter, Facebook, LinkedIn).\n
                                                                                                                                  \n
                                                                                                                                • Follows\/Friending = Links:<\/strong>These edges define the structure of the community.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                                                                                                                                • Centrality Measures:<\/strong>\n