Online social network measurements and search privacy protection

This dissertation investigates the following issues within the context of online social networks (OSNs). (1) How to collect data from OSNs; (2) How to estimate OSN properties; (3) How to measure OSN behavior.;First a case study is conducted with real OSN data to analyze the data collection process. The following problems are answered by evaluating various factors including the choice of seeds, node selection algorithms, and sample sizes. (1) Efficiency: How fast different crawlers discover nodes/links; (2) Sensitivity: How different OSN graphs and protected users affect crawlers; (3) Bias: How major graph properties are skewed.;Secondly, to estimate the size of an OSN, this dissertation introduces two estimators using widely available OSN functionalities/services. An O(logn) algorithm is proposed to replace the original O(n) solution for the MLE estimator. The RW estimator is generalized to estimate other graph properties. In-depth evaluations are performed to show the bias and variance of these estimators.;Furthermore, to measure information propagation and social influence, two important but not well defined types of social behavior, we present a measurement study of 58M messages collected from 700K Twitter users. First, we employ three methods to trace message propagation and examine their applicabilities on Twitter. Besides analyzing the propagation patterns of general messages, we show how breaking news (Michael Jackson's death) spread through Twitter. Finally, we evaluate different social influences and their stabilities, assessments, and correlations.;With real OSN data, we address the complications and challenges to crawl, estimate and measure OSNs. We believe that our analysis here provides valuable insights for future OSN research.;The second part of this dissertation proposes a noise injection model for search privacy protection. We model the search privacy threat as an information inference problem and show how to inject noise into user queries to minimize privacy breaches. We give the lower bound for the amount of noise queries required by a perfect privacy protection and provide the optimal protection given the number of noise queries. This work presents the first theoretical analysis on user side noise injection for search privacy protection.