Social Spammer Detection in Microblogging

1 Introduction

Microblogging, like Twitter and Sina Weibo, has become a widely popular platform for information dissemination and sharing in various scenarios such as marketing, journalism or public relations. With the growing availability of microblogging, social spamming has become rampant. Many fake accounts, known as social spammers [Webb et al., 2008], are employed to unfairly overpower normal users. Social spammers can be coordinated to launch various attacks such as befriending victims and then grabbing their personal information [Bilge et al., 2009], conducting spam campaigns which lead to phishing, malware, and scams [Grier et al., 2010], and conducting political astroturf [Ratkiewicz et al., 2011a;

2011b]. Successful social spammer detection in microblogging presents its significance to improve the quality of user experience, and to positively impact the overall value of the social systems going forward [Lee et al., 2010].

Spammer detection has been studied in various online social networking (OSN) platforms, e.g., Youtube [O'Callaghan et al., 2012] and Facebook [Brown et al., 2008]. One effective way to perform spammer detection is to utilize the social network information [Boykin and Roychowdhury, 2005; Danezis and Mittal, 2009]. This scheme is built upon the assumption that spammers cannot establish an arbitrarily large number of social trust relations with normal users. However, different from other OSNs, microblogging systems feature unidirectional user binding, meaning anyone can follow anyone else without prior consent from the followee. 1 Many users simply follow back when they are followed by someone for the sake of courtesy [Weng et al., 2010]. Due to the reflexive reciprocity, it is easier for spammers to imitate normal users in microblogging by quickly accumulating a large number of social relations. A recent study [Ghosh et al., 2012] on microblogging shows that spammers can successfully acquire a number of normal followers, especially those referred to as social capitalists who tend to increase their social capital by following back anyone who follows them.

Meanwhile, microblogging provides additional content information, i.e., microblogging messages, other than the social networks. Different from email spam detection, content analysis in microblogging for social spammer detection has been little studied due to the distinct characteristics of microblogging messages. First, microblogging messages are very short. For example, Twitter allows users to post messages up to 140 characters. Short messages bring new challenges to traditional text analytics. They cannot provide sufficient context information for effective similarity measure, the basis of many text processing methods [Hu et al., 2009]. Second, microblogging messages are very unstructured and noisy. In particular, when composing a message, users often prefer to use newly created abbreviations or acronyms that seldom appear in conventional text documents. For example, messages like "How r u?" and "Good 9t" are popular in microblogging systems, but they are not even formal words. Although they provide a better user experience, unstructured expressions make it very difficult to accurately identify the semantic meanings of these messages. Last, microblogging messages are networked [Zhu et al., 2012] in the sense that they are generated by users following some others in microblogging systems. The traditional assumption in many applications that data instances are independent and identically distributed (i.i.d.) is thus no longer valid for networked microblogging messages. The distinct features make traditional text analytics less applicable in microblogging platforms.

1 Although there is often an option for a user to manually (dis)approve a following request, it is rarely used by normal users for convenience.

To address the new challenges posed by microblogging services, we propose to take advantage of both network and content information for social spammer detection in microblogging. In this paper, we study the problem of social spammer detection in microblogging with network and content information. In essence, we investigate: (1) how to model the network information and content information properly in microblogging; and (2) how to seamlessly utilize both sources of information for the problemwe are studying. Our solutions to these two challenges result in a new framework for Social Spammer Detection in Microblogging (SSDM). In particular, we employ a directed Laplacian formulation to model the refined social networks, and then integrate the network information into a sparse supervised formulation for the modeling of content information. The main contributions of the paper are outlined as follows:

• We formally define the problem of social spammer detection in microblogging with both network and content information;
• We propose a unified model to effectively integrate both social network information and content information for the problem we are studying; and
• We empirically evaluate the proposed framework on a real-world Twitter dataset and elaborate the effects of each type of information for social spammer detection.

The remainder of this paper is organized as follows. In Section 2, we formally define the problem of social spammer detection in microblogging. In Section 3, we propose a supervised model to integrate both network and content information for spammer detection. In Section 4, we report empirical results on a real-world dataset. In Section 5, we conclude and present the future work.

2 ProblemFormulation

In this section, we first introduce the notations used in the paper and then formally define the problem we study.

Notation: The following notations are used. Matrices are denoted by boldface uppercase letters, vectors by boldface lowercase letters, and scalars by lower case letters. Let ‖A‖ denote the Euclidean norm, and ‖A‖F the Frobenius norm of the matrix A. Specifically, ‖A‖F = √∑mi=1 ∑nj=1 A2ij . Let

AT denote the transpose of A.

Let U = [G,X,Y] be a target microblogging user set with social network information G, content information of microblogging messages X, and identity label matrix Y.

We use G = (V,E) to denote the social network, where nodes u and v in V represent microblogging users, and each directed edge [u, v] in E represents a following relation from u to v. We do not have self links in the graph, i.e., u ̸= v. We use X ∈ Rm×n to denote content information, i.e., messages posted by the users, where m is the number of textual features, and n is the number of users. We use Y ∈ Rn×c to denote the identity label matrix, where c is the number of identity labels. Following previous work on spammer detection [Benevenuto et al., 2010; Lee et al., 2010], we focus on classifying users as either spammers or normal users, i.e., c = 2. It is straightforward to extend this setting to a multi-class classification task.

With the given notations, we formally define the problem of social spammer detection in microblogging as follows:

Given a set of microblogging users U with social network information G, content information X, and identity label information Y of part of the users in the set (i.e., training data), we aim to learn a classifier W to automatically assign identity labels for unknown users (i.e., test data) as spammers or normal users.

3 Social Spammer Detection

In this section, we first introduce how we model social network information for spammer detection and then discuss the modeling of microblogging messages for each user. Finally, we present a framework SSDM that considers both network and content information with its optimization algorithm.

3.1 Modeling Social Network Information

To make use of network information, many methods assume that two nodes share a similar label when they are mutually connected in the network [Chung, 1997; Gu and Han, 2011; Zhu et al., 2012]. It has distinct features in microblogging. First, users have a directed following relation in microblogging. Second, spammers can easily follow a large number of normal microblogging users within a short time. Thus the existing methods are not suitable to this problem.

We first refine the social relations in the social network. Given the social network information G and the identity label matrix Y, we have four kinds of following relations: [spammer, spammer], [normal, normal], [normal, spammer], and [spammer, normal]. Since the fourth relation can be easily faked by spammers, we make use of the first three relations in the proposed framework. Now we introduce how to represent and model the social network information in detail.

The adjacency matrix G ∈ Rn×n is used to represent the refined social network G, and it is defined as

(1)

where u and v are nodes, and [u, v] is a directed edge in the graph G. The in-degree of the node u is defined as din u = ∑[v,u] G(v, u), and the out-degree of the node u is defined as dout u = ∑[u,v] G(u, v). Let P be the transition probability matrix of random walk in a given graph with P(u, v) = G(u, v)/dout u [Zhou et al., 2005]. The random walk has a stationary distribution π, which satisfy ∑u∈V π(u) = 1, π(v) = ∑[u,v] π(u)P(u, v) [Chung, 2005; Zhou et al., 2005], and π(u) > 0 for all u ∈ V .

The key idea here is that we employ network information to smooth the learned model. It can be mathematically formulated as minimizing

where ˆYu denotes the predicted label of user u, and ˆYv the predicted label of user v. The loss function will incur a penalty if two users have different predicted labels when they are close to each other in the graph.

Let Π denote a diagonal matrix with Π(u, u) = π(u).

Theorem 1 The formulation in Eq. (2) is equivalent to the following objective function:

where the Laplacian matrix [Chung, 2005] L is defined as

2

Proof. The proof is straightforward and can be also found in previous work [Chung, 2005; Zhou et al., 2005]. ✷

3.2 Modeling Content Information

One widely used method for text analytics is Least Squares [Lawson and Hanson, 1995], which learns a linear model to fit the training data. The classification task can be performed by solving

where X is the content matrix of training data, and Y is the label matrix. This formulation is to minimize the learning error between the predicted value ˆY = XT W and the true value Y in the training data.

As we discussed, microblogging messages are noisy and unstructured. The traditional text representation methods, like the "Bag of Words" or the N-gram model, often lead to the "curse of dimensionality." It is also observed that when people speed-read a text, they may not fully parse every word but instead seek a sparse representation with a few key phrases or words [Marinis, 2003]. In addition, by providing some meaningful words rather than non-intuitive ones, it may help sociologists, security engineers, and even the public understand the motivation and behavior of social spammers. So we are motivated to exploit sparse learning [Ghanoui et al., 2011], which allows better interpretability of the learning results for social spammer detection.

Sparse learning methods have been used in various applications to obtain a more efficient and interpretable model. One of the most widely used methods is the lasso [Friedman et al., 2008], which introduces an ℓ1-norm penalization on Least Squares. The classifier can be learned by solving the following optimization problem:

where ‖W‖1 = ∑mi=1 ∑cj=1 |Wij|, and λ1 is the sparse regularization parameter. The second term leads to a sparse representation of the learned model.

As pointed out by Zou and Hastie [2005], if there is a group of variables among which the pairwise correlations are very high, then the lasso tends to randomly select variables from this group. To make the sparse learning more stable, we further employ elastic net [Zou and Hastie, 2005], which does automatic variable selection and continuous shrinkage, and can select groups of correlated variables. It is formulated by further adding a Frobenius norm regularization on the learned model as follows:

where λ1 and λ2 are positive regularization parameters to control the sparsity and robustness of the learned model.

3.3 Social Spammer Detection inMicroblogging

Many existing text classification methods assume that instances are independent and identically distributed (i.i.d.). They focus on either building a sophisticated feature space or employing effective classifiers to achieve better classification performance, without taking advantage of the fact that the instances are networked with each other. In the problem of social spammer detection, microblogging users are connected via social networks. We propose to consider both network and content information in a unified model.

Since ˆY = XT W, Eq. (3) can be easily rewritten as

By considering both network and content information, the social spammer detection can be formulated as the following optimization problem:

By solving Eq. (9), the identity label of each unknown target user x can be predicted by

We next introduce an efficient algorithm to solve the optimization problem in Eq. (9).

3.4 An Optimization Algorithm

The optimization problem in Eq. (9) is convex and nonsmooth. Following [Liu et al., 2009; Nesterov and Nesterov, 2004], the basic idea of the proposed algorithm is to reformulate the non-smooth optimization problem as an equivalent smooth convex optimization problem.

Lemma 1 ‖W‖1 is a valid norm.

Proof. It is easy to verify that ‖W‖1 satisfies the three conditions of a valid norm, including the triangle inequality ‖A‖1 + ‖B‖1 ≤ ‖A + B‖1, which completes the proof. ✷

Theorem 2 Eq. (9) can be reformulated as a constrained smooth convex optimization problem:

where

and z ≥ 0 is the radius of the ℓ1-ball. Note that λ1 and z have a one-to-one correspondence between each other.

Proof. Since ‖W‖1 is a valid norm, it defines a closed and convex set Z. The Hessian matrix of the reformulated objective function O(W) is positive semi-definite. Thus the optimization problem in Eq. (11) is convex and differentiable. Our problem defines a convex and differentiable function O(W) in a closed and convex set Z. Thus the reformulated function is a constrained smooth convex optimization problem, which completes the proof. ✷

A widely used method, proximal gradient descent [Ji and Ye, 2009], is employed to optimize the above constrained smooth convex problem. The method solves the problem by updating the following,

where Mγ,Wt (W) is the Euclidean projection [Boyd and Vandenberghe, 2004, Chapter 8.1], which is defined as

where γ is the step size, and

Let Ut = Wt - 1 γ ∇O(Wt). The Euclidean projection has a closed-form solution [Liu et al., 2009] as follows:

where ujt , wj and wj t are the j-th rows ofUt,WandWt, respectively. We now introduce the detailed algorithm of SSDM in Algorithm 1.

In the algorithm, we use Nesterov's method [Nesterov and Nesterov, 2004] to solve the optimization problem in Eq. (9) from line 2 to 13. To accelerate the proximal gradient descent in Eq. (13), we construct a linear combination [Ji and Ye, 2009] of Wt and Wt-1 to update Ht in line 3. Lines 4 to 11 correspond to the line search algorithm for γ according to the Armijo-Goldstein rule. Based on this algorithm, we can have an efficient and optimal solution to the convex optimization problem. Similar to the proof in [Liu et al., 2009], it is easy to verify that the convergence rate of the proposed algorithm is O( 1 √ϵ ) for achieving an accuracy of ϵ.

Algorithm 1: SSDM - Social Spammer Detection in Microblogging

Input: {X, Y, L,W0, λ1, λ2, λs } Output: W 1: Initialize η0 = 0, η1 = 1,W1 = W0, t = 1 2: repeat 3: Set Ht = Wt + ηt-1-1 ηt (Wt -Wt-1) 4: loop 5: Set Ut = Ht - 1 γ ∇O(Wt) 6: ComputeWt+1 according to Eq. (16) 7: if O(Wt+1) ≤ Mγ,Ht (Wt+1) then 8: λt+1 = γ, break 9: end if 10: γ = 2 × γ 11: end loop 12: W = Wt+1, ηt+1 = 1+√1+4ηt 2 13: until convergence

4 Experiments

In this section, we conduct experiments to assess the effectiveness of the proposed framework SSDM. Through the experiments, we aim to answer the following two questions:

1. How effective is the proposed framework compared with other methods of social spammer detection?
2. What are the effects of the social network and content information on the social spammer detection?

We begin by introducing the dataset and experimental setup and then compare the performance of different spammer detection methods. Finally, we study the effects of important parameters on the proposed method.

4.1 Dataset

We now introduce the real-world Twitter dataset used in our experiment. A data crawling process, which is similar to [Thomas et al., 2011; Yang et al., 2011; Zhu et al., 2012], is employed to construct the dataset. We first crawled a Twitter dataset from July 2012 to September 2012 via the Twitter Search API. 2 The users that were suspended by Twitter during this period are considered as the gold standard [Thomas et al., 2011] of spammers in the experiment. We then randomly sampled the normal users which have social relations with the spammers. According to the literature of spammer detection, the two classes are imbalanced, i.e., the number of normal users we sampled is much greater than that of spammers in the dataset. We finally remove stop-words and perform stemming for all the tweets. The statistics of the dataset is presented in Table 2.

4.2 Experimental Setup

We follow standard experiment settings used in [Benevenuto et al., 2010; Zhu et al., 2012] to evaluate the performance of spammer detection methods. In particular, we apply different methods on the Twitter dataset. Precision, recall, and F1-measure are used as the performance metrics.

2 https://dev.twitter.com/docs/api/1/get/search/

There are three positive parameters involved in the experiments, including λ1, λ2, and λs in Eq. (9). λ1 is to control the sparsity of the learned model, λ2 is the parameter to make the learned model more robust, and λs is to control the contribution of network information. As a common practice, all the parameters can be tuned via cross-validation with validation data. In the experiments, we empirically set λ1 = 0.1, λ2 = 0.1, and λs = 0.1 for general experiment purposes. The effects of the parameters on the learning model will be further discussed in Section 4.5.

4.3 Performance Evaluation

To answer the first question asked in the beginning of Section 4, we compare our proposed method SSDM with the following baseline methods. All the methods utilize both content and network information in different ways.

• LS Content SN: the Least Squares [Lawson andHanson, 1995] is a widely used classifier for i.i.d. data. We combine the content matrix X and adjacency matrix G of the social network together for user representation.
• EN Content SN: the elastic net is one of the most effective sparse learning methods [Zou and Hastie, 2005], and it is applied on the same data matrix as the first baseline.
• SMF UniSN: a multi-label informed latent semantic indexing [Yu et al., 2005; Zhu et al., 2012] is used to model the content information, and undirected graph Laplacian [Chung, 1997] is used to incorporate the network information. This is the state-of-the-art method for spammer detection in an undirected social network. In the experiment, we convert the directed graph to an undirected one with G = max(G, GT ).
• SSDM: our proposed method for spammer detection.

The experimental results of the methods are presented in Table 1. In the experiment, we use five-fold cross validation for all the methods. To avoid effects brought by the size of the training data, we conduct two sets of experiments with different numbers of training samples. In each round of the experiment, 80% of the whole dataset is held for training. In the table, "50% of Training Data" means that we randomly chose 50% of the 80%, thus using 40% of the whole dataset for training. Also, "gain" represents the percentage improvement of the methods in comparison with our first baseline method LS Content SN. In the experiment, each result denotes an average of 10 test runs. By comparing the results of different methods, we draw the following observations:

(1) From the results in Table 1, we can observe that our proposed framework SSDM consistently outperforms other baseline methods using all metrics with different sizes of training data. Our method achieves better performance than the stateof-the-art method SMF UniSN. We apply two-sample one-tail t-tests to compare SSDM with the three baseline methods. The experiment results demonstrate that SSDM performs significantly better (with the significance level α = 0.01) than the three methods. This indicates that, compared with other methods, our proposed model successfully utilizes both content and network information for social spammer detection.

(2) Among the three baseline methods, LS Content SN achieves the worst performance. With the introduction of sparsity regularization, EN Content SN has performance improvement. This demonstrates that sparse learning is effective to handle the noisy and high-dimensional data in microblogging. SMF UniSN achieves the best performance, which indicates that simply combining content and network features together does not work well in the first two methods.

In summary, the methods perform differently in social spammer detection. In most cases, the simple combination of content and network information does not work well. It suggests that the way of using the two kinds of information is important. The superior performance of our proposed method answers the first question that, compared with other methods, SSDM is effective in social spammer detection.

4.4 Effects of Network and Content Information

In this subsection, we study the importance of each kind of information and accordingly answer the second question asked in the beginning of this section. We compare our proposed method with the following two groups of four methods:

• Content-based methods: support vector machine (SVM) and elastic net (EN) are employed for spammer detection based on content information only.
• Network-based methods: SVM and EN are employed based on network information, which is represented as the adjacency matrix of the social network.

We compare the performance of our proposed framework SSDM and the methods with only one type of information on the Twitter dataset. The results are plotted in Figure 1. The first four bars represent the performance of the two representative methods SVM and EN with one type of information, respectively. The last is our proposed method SSDM.

From the figure, we observe that, with the integration of content and network information in a unified model, the proposed framework SSDM achieves better performance than those with only one kind of information. Among the four baseline methods, SVM Content and EN Content have comparable performance. They significantly outperform the other two methods SVM SN and EN SN. This demonstrates that, in this experiment, content information is more effective than social network information. We need a more sophisticated way to represent social network information for social spammer detection. Simply employing neighbors of a user for representation does not work well.

In summary, the methods based on network information do not have good performance in social spammer detection. It suggests that the way of integrating social network information is important. The superior performance of our proposed method SSDM further validates its excellent use of both network and content information in a unified way.

4.5 Parameter Analysis

As discussed in Section 4.2, the effects of two important parameters, i.e., λ1 and λs, need to be further explored. λ1 is to control the sparseness of the learned model, and λs is to control the contribution of social network information to the model. We now conduct experiments to compare the social spammer detection performance of the proposed SSDM on the Twitter dataset with different parameter settings.

The social spammer detection results (F1-measure) of SSDM with different parameter settings on the dataset are plotted in Figure 2. In the figure, performance of SSDM improves as the parameters λ1 and λs increase, and reaches a peak at λ1 = 0.1 and λs = 1. When λ1 > 0.1 or λs > 1, the performance of SSDM declines. Generally, the performance is not very sensitive to λ1 when it is in a reasonable range [0.01, 10]. The performance changes significantly when λs > 1. The results suggest that the proposed framework can achieve relatively good performance when the parameters are in the range [0.01, 1].

5 Conclusion and FutureWork

New features of microblogging services present great challenges to the problem of social spammer detection. In this paper, we investigate how to seamlessly integrate the network and content information of microblogging users to perform effective social spammer detection. In particular, the proposed framework models both types of information in a unified way. Also, we present an efficient algorithm to solve the proposed non-smooth convex optimization problem. Experiments on a real Twitter dataset show that our SSDM framework can effectively integrate both kinds of information to outperform the state-of-the-art methods.

There are many potential future extensions of this work. It would be interesting to investigate other social activities, like retweet behavior and emotion status, for social spammer detection. Also, sparse learning can generate a number of important textual features with the model. Conducting behavior and linguistic analysis across social media sites [Hu et al., 2013] to better understand motivations of the social spammers with the textual features is also a promising direction.

Acknowledgments

We truly thank the anonymous reviewers for their pertinent comments. This work is, in part, supported by ONR (N000141110527) and (N000141010091), and NSF (IIS1217466).