6.3 Katz Centrality and HITS Algorithm

Network centrality measures like Katz and HITS help us understand node importance in complex networks. Katz centrality considers both direct and indirect connections, assigning scores based on weighted walks. It's useful for social networks and citation analysis.

HITS, developed for web page ranking, assigns hub and authority scores to nodes. It focuses on query-specific subgraphs, making it ideal for topic-based information retrieval. Both methods offer unique insights into network structure and node significance.

Katz Centrality and its Recursiveness

Concept and Calculation

Top images from around the web for Concept and Calculation

• 

  Centrality Measures Based on Matrix Functions View original

  Is this image relevant?

• 

  Frontiers | Gene Set Enrichment Analysis of Interaction Networks Weighted by Node Centrality View original

  Is this image relevant?

• 

  Centrality Measures Based on Matrix Functions View original

  Is this image relevant?

• 

  Frontiers | Gene Set Enrichment Analysis of Interaction Networks Weighted by Node Centrality View original

  Is this image relevant?

1 of 2

Top images from around the web for Concept and Calculation

• 

  Centrality Measures Based on Matrix Functions View original

  Is this image relevant?

• 

  Frontiers | Gene Set Enrichment Analysis of Interaction Networks Weighted by Node Centrality View original

  Is this image relevant?

• 

  Centrality Measures Based on Matrix Functions View original

  Is this image relevant?

• 

  Frontiers | Gene Set Enrichment Analysis of Interaction Networks Weighted by Node Centrality View original

  Is this image relevant?

1 of 2

• Measures node importance in a network considering both direct and indirect connections
• Calculates a weighted sum of walks of all lengths from a node to other nodes
• Represented by the formula $x = αAx + β1$
  • x denotes the centrality vector
  • A represents the adjacency matrix
  • α signifies the attenuation factor
  • β indicates the bias term
• Attenuation factor α controls importance of longer walks vs shorter ones
  • Typically set between 0 and reciprocal of largest eigenvalue of A
• Generalizes eigenvector centrality by incorporating a bias term
• Ensures non-zero scores for all nodes, even those with no outgoing edges (sinks)

Applications and Computation

• Particularly useful for directed networks (social media connections, citation networks)
• Handles networks with sinks effectively
• Computed through two main methods
  • Iterative approach
  • Matrix inversion
• Choice of computation method depends on
  • Network size (number of nodes and edges)
  • Available computational resources (processing power, memory)

HITS Algorithm and its Components

Algorithm Overview

• Developed by Jon Kleinberg for link analysis and web page rating
• Operates on a focused subgraph of the web
  • Typically constructed from text-based search query results
• Assigns two scores to each node (web page)
  • Hub score
  • Authority score
• Employs an iterative process
  • Alternates between updating hub and authority scores
  • Continues until convergence or reaching a specified iteration limit
• Normalizes scores after each iteration
  • Prevents numerical overflow
  • Ensures algorithm convergence

Mathematical Foundation

• Utilizes adjacency matrix A and its transpose A^T in update equations
• Represents an eigenvector problem
  • Final hub vector corresponds to principal eigenvector of A^T A
  • Final authority vector aligns with principal eigenvector of AA^T
• Update equations for scores
  • Hub scores: $h = A a$
  • Authority scores: $a = A^T h$
  • A denotes the adjacency matrix of the network

Hub vs Authority Scores

Score Definitions and Relationships

• Hub scores measure a node's effectiveness in pointing to high-quality authority pages
  • Proportional to sum of authority scores of nodes it points to
• Authority scores indicate a node's value based on quality of hubs pointing to it
  • Proportional to sum of hub scores of nodes pointing to it
• Mutually reinforcing relationship creates circular definition
  • Necessitates iterative computation process
• Good hub links to many good authorities (directories, curated link collections)
• Good authority receives links from many good hubs (high-quality content pages)

Web Search Context

• Hub pages often resemble directory-like structures
  • Contain numerous outlinks to relevant resources
  • Examples include curated lists, resource pages, or link aggregators
• Authority pages typically offer high-quality content on specific topics
  • Frequently cited or linked to by other reputable sources
  • Examples include academic papers, expert blogs, or official documentation

Katz Centrality vs HITS Algorithm

Scope and Application

• Katz centrality analyzes global network structure
• HITS focuses on query-specific subgraph of network
• Katz centrality assigns single score per node
• HITS computes two distinct scores (hub and authority) for each node
• Katz centrality applies to
  • Social networks (influencer identification)
  • Citation networks (impactful papers)
  • General graph analysis (key nodes in complex systems)
• HITS primarily used for
  • Web page ranking
  • Topic-specific information retrieval

Algorithmic Characteristics

• Katz centrality recursion based on walks of all lengths
• HITS recursion relies on mutual reinforcement of hub and authority scores
• Katz centrality handles both directed and undirected networks
• HITS typically applied to directed networks (hyperlink structures)
• Computational complexity often higher for Katz centrality
  • Potential need for matrix inversion in large networks
• Both algorithms susceptible to topic drift
  • HITS particularly vulnerable due to query-dependent nature