Detecting fake accounts (sybils) in online social networks (OSNs) is vital to protect OSN operators and their users from various malicious activities. Typical graph-based sybil detection (a mainstream methodology) assumes that sybils can make friends with only a limited (or small) number of honest users. However, recent evidences showed that this assumption does not hold in real-world OSNs, leading to low detection accuracy. To address this challenge, we explore users’ activities to assist sybil detection. The intuition is that honest users are much more selective in choosing who to interact with than to befriend with. We first develop thesocial and activity network(SAN), a two-layer hyper-graph that unifies users’ friendships and their activities, to fully utilize users’ activities. We also propose a more practical sybil attack model, where sybils can launch both friendship attacks and activity attacks. We then design Sybil_SAN to detect sybils via coupling three random walk-based algorithms on the SAN, and prove the convergence of Sybil_SAN. We develop an efficient iterative algorithm to compute the detection metric for Sybil_SAN, and derive the number of rounds needed to guarantee the convergence. We use“matrix perturbation theory”to bound the detection error when sybils launch many friendship attacks and activity attacks. Extensive experiments on both synthetic and real-world datasets show that Sybil_SAN is highly robust against sybil attacks, and can detect sybils accurately under practical scenarios, where current state-of-art sybil defenses have low accuracy. Lastly, we present two extensions of Sybil_SAN to further improve its accuracy.

Random walk sampling is often used to conduct statistical estimation over graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. Our bias reduction algorithm only utilizes a small number of valid sub-samples, which can reduce more bias of the estimator but may increase the variance of the estimator significantly. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. We provide theoretical guarantees and computational complexity analysis of our proposed bias reduction algorithms. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. Extensive experiments on four public datasets confirm the effectiveness and computational efficiency of our proposed algorithmic framework under the mean square metric and beyond.

Graphs are commonly used in various applications such as online social networks (OSNs), E-commerce systems and social recommender systems. Random walk sampling is often used to conduct statistical estimation over such graphs. This paper develops an algorithmic framework to reduce the mean square error of such statistical estimation. Our algorithmic framework is inspired by that the mean square error can be decomposed into a sum of the bias and variance of the estimator. More specifically, we apply the bootstrapping technique to design a bias reduction algorithm. A new feature of this bias reduction algorithm is that it allows the variance to increase whenever the bias can be further reduced. The increased variance may lead to a large mean square error of the estimator. We use multiple parallel random walks to reduce this variance such that it can be reduced to arbitrarily small by deploying a sufficient number of random walks. Our algorithmic framework enables one to attain different trade-offs between the sample complexity (i.e., number of parallel random walks) and the mean square error of the statistical estimation. Also, the proposed bias reduction algorithm is generic and can be applied to optimize a large class of random walk sampling algorithms. To demonstrate the versatility of the framework, we apply it to optimize the Metropolis random walk and simple random walk sampling. Extensive experiments confirm the effectiveness and efficiency of our proposed algorithmic framework.

The application of Missing Data Technique (MDT) has shown to improve the performance of speech recognition. To apply MDT to cepstral domain, this paper presents a weighted approach to compute the reliability of cepstral feature based on sigmoid function and introduces a weighted distance algorithm. It is deduced that the reliability compensates the Gaussian variance in hidden Markov model (HMM) frame by frame to reduce the mismatch between clean-trained model and corrupted speech. Experimental evaluation using the Aurora2 database demonstrates a distinct digit error rate reduction. The main advantages of the approach are simple system implementation, low computation cost and easy to plug into other robust recognition algorithm.