Cover image for Numerical Algorithms for Personalized Search in Self-organizing Information Networks

Numerical Algorithms for Personalized Search in Self-organizing Information Networks

Author Sep Kamvar
Release Date: 2010/09/01
ISBN: 9781400837069
Topic:
0%
21
Chapters
0-1
Hours read
0k
Total Words
    Start Reading Now    
       Add to Wishlist       
View table of contents

Book Description

This book lays out the theoretical groundwork for personalized search and reputation management, both on the Web and in peer-to-peer and social networks. Representing much of the foundational research in this field, the book develops scalable algorithms that exploit the graphlike properties underlying personalized search and reputation management, and delves into realistic scenarios regarding Web-scale data.


Sep Kamvar focuses on eigenvector-based techniques in Web search, introducing a personalized variant of Google's PageRank algorithm, and he outlines algorithms--such as the now-famous quadratic extrapolation technique--that speed up computation, making personalized PageRank feasible. Kamvar suggests that Power Method-related techniques ultimately should be the basis for improving the PageRank algorithm, and he presents algorithms that exploit the convergence behavior of individual components of the PageRank vector. Kamvar then extends the ideas of reputation management and personalized search to distributed networks like peer-to-peer and social networks. He highlights locality and computational considerations related to the structure of the network, and considers such unique issues as malicious peers. He describes the EigenTrust algorithm and applies various PageRank concepts to P2P settings. Discussion chapters summarizing results conclude the book's two main sections.


Clear and thorough, this book provides an authoritative look at central innovations in search for all of those interested in the subject.

Table of Contents

  1. Cover
  2. Title Page
  3. Copyright
  4. Contents
  5. Tables
  6. Figures
  7. Acknowledgments
  8. Chapter One - Introduction
    1. 1.1 World Wide Web
    2. 1.2 P2P Networks
    3. 1.3 Contributions
  9. Part I - World Wide Web
    1. Chapter Two - PageRank
      1. 2.1 Pagerank Basics
      2. 2.2 Notation And Mathematical Preliminaries
      3. 2.3 Power Method
        1. 2.3.1 Formulation
        2. 2.3.2 Operation Count
        3. 2.3.3 Convergence
      4. 2.4 Experimental Setup
      5. 2.5 Related Work
        1. 2.5.1 Fast Eigenvector Computation
        2. 2.5.2 PageRank
    2. Chapter Three - The Second Eigenvalue of the Google Matrix
      1. 3.1 Introduction
      2. 3.2 Theorems
      3. 3.3 Proof Of Theorem 1
      4. 3.4 Proof Of Theorem 2
      5. 3.5 Implications
      6. 3.6 Theorems Used
    3. Chapter Four - The Condition Number of the PageRank Problem
      1. 4.1 Theorem 6
      2. 4.2 Proof Of Theorem 6
      3. 4.3 Implications
    4. Chapter Five - Extrapolation Algorithms
      1. 5.1 Introduction
      2. 5.2 Aitken Extrapolation
        1. 5.2.1 Formulation
        2. 5.2.2 Operation Count
        3. 5.2.3 Experimental Results
        4. 5.2.4 Discussion
      3. 5.3 Quadratic Extrapolation
        1. 5.3.1 Formulation
        2. 5.3.2 Operation Count
        3. 5.3.3 Experimental Results
        4. 5.3.4 Discussion
      4. 5.4 Power Extrapolation
        1. 5.4.1 Simple Power Extrapolation
        2. 5.4.2 A2 Extrapolation
        3. 5.4.3 Ad Extrapolation
      5. 5.5 Measures Of Convergence
    5. Chapter Six - Adaptive PageRank
      1. 6.1 Introduction
      2. 6.2 Distribution Of Convergence Rates
      3. 6.3 Adaptive Pagerank Algorithm
        1. 6.3.1 Algorithm Intuition
        2. 6.3.2 Filter-based Adaptive PageRank
      4. 6.4 Experimental Results
      5. 6.5 Extensions
        1. 6.5.1 Further Reducing Redundant Computation
        2. 6.5.2 Using the Matrix Ordering from the Previous Computation
      6. 6.6 Discussion
    6. Chapter Seven - BlockRank
      1. 7.1 Block Structure Of The Web
        1. 7.1.1 Block Sizes
        2. 7.1.2 The GeoCities Effect
      2. 7.2 Blockrank Algorithm
        1. 7.2.1 Overview of BlockRank Algorithm
        2. 7.2.2 Computing Local PageRanks
        3. 7.2.3 Estimating the Relative Importance of Each Block
        4. 7.2.4 Approximating Global PageRank Using Local PageRank and BlockRank
        5. 7.2.5 Using This Estimate as a Start Vector
      3. 7.3 Advantages Of Blockrank
      4. 7.4 Experimental Results
      5. 7.5 Discussion
      6. 7.6 Personalized Pagerank
        1. 7.6.1 Inducing Random Jump Probabilities over Pages
        2. 7.6.2 Using “Better” Local PageRanks
        3. 7.6.3 Experiments
        4. 7.6.4 Topic-Sensitive PageRank
        5. 7.6.5 Pure BlockRank
  10. Part II - P2P Networks
    1. Chapter Eight - Query-Cycle Simulator
      1. 8.1 Challenges In Empirical Evaluation Of P2P Algorithms
      2. 8.2 The Query-Cycle Model
      3. 8.3 Basic Properties
        1. 8.3.1 Network Topology
        2. 8.3.2 Joining the Network
        3. 8.3.3 Query Propagation
      4. 8.4 Peer-Level Properties
      5. 8.5 Content Distribution Model
        1. 8.5.1 Data Volume
        2. 8.5.2 Content Type
      6. 8.6 Peer Behavior Model
        1. 8.6.1 Uptime and Session Duration
        2. 8.6.2 Query Activity
        3. 8.6.3 Queries
        4. 8.6.4 Query Responses
        5. 8.6.5 Downloads
      7. 8.7 Network Parameters
        1. 8.7.1 Topology
        2. 8.7.2 Bandwidth
      8. 8.8 Discussion
    2. Chapter Nine - EigenTrust
      1. 9.1 Design Considerations
      2. 9.2 Reputation Systems
      3. 9.3 Eigentrust
        1. 9.3.1 Normalizing Local Trust Values
        2. 9.3.2 Aggregating Local Trust Values
        3. 9.3.3 Probabilistic Interpretation
        4. 9.3.4 Basic EigenTrust
        5. 9.3.5 Practical Issues
        6. 9.3.6 Distributed EigenTrust
        7. 9.3.7 Algorithm Complexity
      4. 9.4 Secure Eigentrust
        1. 9.4.1 Algorithm Description
        2. 9.4.2 Discussion
      5. 9.5 Using Global Trust Values
      6. 9.6 Experiments
        1. 9.6.1 Load Distribution in a Trust-based Network
        2. 9.6.2 Threat Models
      7. 9.7 Related Work
      8. 9.8 Discussion
    3. Chapter Ten - Adaptive P2P Topologies
      1. 10.1 Introduction
      2. 10.2 Interaction Topologies
      3. 10.3 Adaptive P2P Topologies
        1. 10.3.1 Local Trust Scores
        2. 10.3.2 Protocol
        3. 10.3.3 Practical Issues
      4. 10.4 Empirical Results
        1. 10.4.1 Malicious Peers Move to Fringe
        2. 10.4.2 Freeriders Move to Fringe
        3. 10.4.3 Active Peers Are Rewarded
        4. 10.4.4 Efficient Topology
      5. 10.5 Threat Scenarios
        1. 10.5.1 Threat Model A
        2. 10.5.2 Threat Model B
        3. 10.5.3 Threat Model C
      6. 10.6 Related Work
      7. 10.7 Discussion
    4. Chapter Eleven - Conclusion
  11. Bibliography
3.145.167.176