Numerical Algorithms for Personalized Search in Self-organizing Information Networks

Tables ix
Figures xi
Acknowledgments xv
Chapter 1: Introduction 1
1.1 World Wide Web 1
1.2 P2P Networks 2
1.3 Contributions 2

PART I: WORLD WIDE WEB 5
Chapter 2: PageRank 7
2.1 PageRank Basics 7
2.2 Notation and Mathematical Preliminaries 9
2.3 Power Method 10
2.3.1 Formulation 10
2.3.2 Operation Count 12
2.3.3 Convergence 12
2.4 Experimental Setup 13
2.5 Related Work 13
2.5.1 Fast Eigenvector Computation 13
2.5.2 PageRank 14

Chapter 3: The Second Eigenvalue of the Google Matrix 15
3.1 Introduction 15
3.2 Theorems 15
3.3 Proof of Theorem 1 15
3.4 Proof of Theorem 2 17
3.5 Implications 18
3.6 Theorems Used 19

Chapter 4: The Condition Number of the PageRank Problem 20
4.1 Theorem 6 20
4.2 Proof of Theorem 6 20
4.3 Implications 21

Chapter 5: Extrapolation Algorithms 23
5.1 Introduction 23
5.2 Aitken Extrapolation 23
5.2.1 Formulation 23
5.2.2 Operation Count 25
5.2.3 Experimental Results 26
5.2.4 Discussion 26
5.3 Quadratic Extrapolation 27
5.3.1 Formulation 27
5.3.2 Operation Count 30
5.3.3 Experimental Results 30
5.3.4 Discussion 34
5.4 Power Extrapolation 35
5.4.1 Simple Power Extrapolation 35
5.4.2 A2 Extrapolation 35
5.4.3 Ad Extrapolation 37
5.5 Measures of Convergence 40

Chapter 6: Adaptive PageRank 42
6.1 Introduction 42
6.2 Distribution of Convergence Rates 42
6.3 Adaptive PageRank Algorithm 44
6.3.1 Algorithm Intuition 45
6.3.2 Filter-based Adaptive PageRank 46
6.4 Experimental Results 48
6.5 Extensions 48
6.5.1 Further Reducing Redundant Computation 48
6.5.2 Using the Matrix Ordering from the Previous Computation 50
6.6 Discussion 50

Chapter 7: BlockRank 51
7.1 Block Structure of the Web 51
7.1.1 Block Sizes 54
7.1.2 The GeoCities Effect 55
7.2 BlockRank Algorithm 55
7.2.1 Overview of BlockRank Algorithm 56
7.2.2 Computing Local PageRanks 57
7.2.3 Estimating the Relative Importance of Each Block 60
7.2.4 Approximating Global PageRank Using Local PageRank and BlockRank 61
7.2.5 Using This Estimate as a Start Vector 62
7.3 Advantages of BlockRank 63
7.4 Experimental Results 64
7.5 Discussion 67
7.6 Personalized PageRank 67
7.6.1 Inducing Random Jump Probabilities over Pages 68
7.6.2 Using "Better" Local PageRanks 68
7.6.3 Experiments 69
7.6.4 Topic-Sensitive PageRank 70
7.6.5 Pure BlockRank 71

PART II: P2P NETWORKS 73
Chapter 8: Query-Cycle Simulator 75
8.1 Challenges in Empirical Evaluation of P2P Algorithms 75
8.2 The Query-Cycle Model 75
8.3 Basic Properties 76
8.3.1 Network Topology 76
8.3.2 Joining the Network 76
8.3.3 Query Propagation 76
8.4 Peer-Level Properties 77
8.5 Content Distribution Model 78
8.5.1 Data Volume 78
8.5.2 Content Type 78
8.6 Peer Behavior Model 80
8.6.1 Uptime and Session Duration 80
8.6.2 Query Activity 81
8.6.3 Queries 81
8.6.4 Query Responses 81
8.6.5 Downloads 82
8.7 Network Parameters 82
8.7.1 Topology 82
8.7.2 Bandwidth 82
8.8 Discussion 83

Chapter 9: EigenTrust 84
9.1 Design Considerations 84
9.2 Reputation Systems 85
9.3 EigenTrust 86
9.3.1 Normalizing Local Trust Values 86
9.3.2 Aggregating Local Trust Values 87
9.3.3 Probabilistic Interpretation 87
9.3.4 Basic EigenTrust 87
9.3.5 Practical Issues 88
9.3.6 Distributed EigenTrust 89
9.3.7 Algorithm Complexity 90
9.4 Secure EigenTrust 91
9.4.1 Algorithm Description 92
9.4.2 Discussion 93
9.5 Using Global Trust Values 94
9.6 Experiments 95
9.6.1 Load Distribution in a Trust-based Network 95
9.6.2 Threat Models 98
9.7 Related Work 106
9.8 Discussion 106

Chapter 10: Adaptive P2P Topologies 108
10.1 Introduction 108
10.2 Interaction Topologies 109
10.3 Adaptive P2P Topologies 109
10.3.1 Local Trust Scores 109
10.3.2 Protocol 110
10.3.3 Practical Issues 112
10.4 Empirical Results 115
10.4.1 Malicious Peers Move to Fringe 115
10.4.2 Freeriders Move to Fringe 118
10.4.3 Active Peers Are Rewarded 119
10.4.4 Efficient Topology 120
10.5 Threat Scenarios 126
10.5.1 Threat Model A 126
10.5.2 Threat Model B 128
10.5.3 Threat Model C 130
10.6 Related Work 131
10.7 Discussion 132
Chapter 11: Conclusion 133
Bibliography 135