基于改进蚁群算法的集体垃圾邮件发送者检测研究

Research on Collective Spammers Detection Based on Improved Ant Colony Algorithm

摘要: 社交媒体评论对购物至关重要，但不良商家组织欺诈性评价者发布恶意评论，误导消费者。本文提出了一种名为IACOA的改进蚁群算法，通过评论投影图检测隐式社区，提高垃圾邮件发送者的识别精度。该算法在审查者投影图中执行，使用组和个人垃圾邮件指标评估意见垃圾邮件发送者组的怀疑度，并输出排名。该方法在预测精度上优于其他四种比较方法。

Abstract: Social media reviews are crucial for shopping, but unscrupulous merchants organize fraudulent reviewers to post malicious reviews and mislead consumers. In this paper, we propose an improved ant colony algorithm called IACOA to improve the spammer identification accuracy by detecting implicit communities through review projection maps. The algorithm executes in the reviewer projection map, evaluates the skepticism of the opinion spammer group using group and individual spam metrics, and outputs the rankings. The method outperforms the other four comparative methods in terms of prediction accuracy.

1. 引言

随着互联网计算[1]、云计算[2]和人工智能(AI) [3] [4]的发展，社交网络的规模以及商业信息、政治观点、社交和情感信息的数量显著增加。大多数消费者在购买产品或服务时会将他人的评论视为对产品或服务的评价。正面评论可以增强消费者的购买意愿，而负面评论则相反。根据哈佛大学的一份研究报告，美国最大的评论网站Yelp的产品评级每提高一颗星，收入就会增加5%~9% [5]。

垃圾邮件发送者制作的欺诈性评论广泛存在，试图提高销售额或攻击竞争对手的声誉。集体垃圾邮件发送者组是为实现相似目标而协同工作的垃圾邮件发送者组。产品在发布初期遭到意见垃圾攻击，攻击者将完全掌控相关消费者情绪，对产品具有很大的影响。因此，集体垃圾邮件发送者检测具有重要应用价值。

2. 相关工作

2.1. 社团检测

复杂网络[6]广泛应用于生态系统、社交网络、互联网等，是多学科研究的焦点。网络由节点和边组成[7]，节点表示系统组成部分，边表示连接关系。社团[8]是网络中具有共享属性的节点组成的结构，类似于社会网络中的角色。最近，重叠社团检测引起学术界关注，通过算法在延迟容忍网络[9]、推荐系统[10]等领域应用广泛。

2.2. 传统蚁群算法

蚁群算法(ACO)模拟蚂蚁觅食行为，是一种群体智能优化算法。最早由Dorigo等人于1991年提出，最初用于解决旅行商问题。蚂蚁在觅食中通过留下信息素选择路径，路径上信息素浓度高则被选择概率大。该正反馈机制使蚂蚁最终选择最优路径。文章提出了基于改进蚁群算法的社团检测模型，将评论数据集建模为评论投影图，用于检测集体垃圾邮件发送者组。

3. 模型与算法

3.1. 构建评价者投影图

定义1 共同评审可能性：评审间隔时间和评分偏差分数用于确定两名评审员之间的共同评审可能性。如果评审员i和评审员j共同评审产品p，则两名评审员之间共同发表评论的可能性取决于评论间隔和得分偏差。定义为：

$CoRePos\left(i,j,p\right)=\{\begin{array}{cc}0,& \left(\left|t_i^p-t_j^p\right|>\alpha \right)\text{and}\left(\left|r_i^p-r_j^p\right|\ge 2\right)\\ 1,& \text{otherwise}\end{array}$ (1)

其中$\alpha$ 时间的单位为天，$t_i^p$ 表示评价者i对评论产品p的时间，$t_j^p$ 表示评价者j对评论产品p的时间。$\left|r_i^p-r_j^p\right|$ 表示评价者i和评价者j对产品p评分的评级偏差。$\alpha$ 是根据经验设置的时间阈值。当$CoRePos=1$ 时，表示高度可疑的共同评审可能性。当$CoRePos=0$ 时，表示没有可疑的共同评审可能性。只有当两名评价者达到相似的时间和相似的评分时，他们才会被判定为可疑的共同评审对。$\alpha$ 的值将影响垃圾邮件发送者组检测过程中结果的准确性。如果$\alpha$ 值太大，则将包含大量真实的共同评审。相反，这将导致真正的联合评审对漏检。

定义2 意见垃圾邮件发送者组：将意见垃圾邮件发送者组定义为g，边表示由于相似评论而导致的共审者之间的关系。对于评价者$i,j\in R_g$ ，评价者之间的关系用边权重$w\left(i,j\right)$ 表示，定义为：

$w\left(i,j\right)=\{\begin{array}{l}0,\forall p\in P_i\cap P_j,CoRePos\left(i,j,p\right)=0\\ 1,\text{otherwise}\end{array}$ (2)

其中$P_{i\left(j\right)}$ 表示评价者$i\left(j\right)$ 评价的产品集合。

3.2. 改进的蚁群算法

网络抽象可看作是一个无向图，包括节点和边集合。每个节点都有唯一标签，并有对应的邻域。重叠社团检测的目标是通过某种方法将抽象的无向图G分割成一系列小集群，确保每个集群内节点相同。这可以用数学方式描述为：

${\displaystyle {\cup }_{1\le i\le m}{C}_i}=G\text{and}\exists i,j\in m,C_i\cap C_j\ne \varnothing$ (3)

3.2.1. 算法框架

算法1 IACOA算法框架

Input: $G=\left(V,E\right)$ Output: $C=\left(C_1,C_2,\cdots ,C_m\right)$ 参数初始化:迭代次数最大值T；蚂蚁数量n；初始信息素值$\tau$ ；信息素挥发率$\rho$ ；阈值$\theta$ ；信息素增加量x；信息素阈值b. 1: 根据式(6) ~(8)计算转移概率矩阵 2: 蚂蚁位置初始化 3: 蚂蚁移动 4: for t=1 to T do 5: for i=1 to n do 6: each ant i moves according to the transition probability matrix 7: pheromone diffusion and renewal 8: end for 9: end for 10: 后处理 11: return C

3.2.2. 改进的IACOA算法

ACO中，信息素相对大小直接影响蚁群位置之间的转移概率，进而影响可行解的质量。我们提出了一种方法：直接交换部分边上的信息素，改变其分布。具体而言，我们设定了交换概率，然后在节点间随机选择边进行信息素值的交换，以此来增加搜索区域的多样性。

本文采用变参挥发率来避免最优路径上的某些边由于信息素强度过低而失去选择机会，其计算公式为

${\rho }_{ij}\left(t\right)=1t\le t_{early}$ (4)

${\rho }_{ij}\left(t\right)=\{\begin{array}{l}{k}_1{\tau }_{ij}\left(t\right)\le C,t>t_{early}\\ k_2\text{otherwise}\end{array}$ (5)

其中：${\rho }_{ij}\left(t\right)$ 表示t时刻边ij上的信息素挥发率；$t_{early}$ 是早期搜索时间；$k_1,k_2\in \left(0,1\right)$ 且$k_1>k_2$ ，且，$k_1,k_2$ 两者数值不宜差别过大，以防交换后信息素挥发过快或过慢，从而影响交换边的效果；C为介于${\tau }_{ij}\left(t\right)$ 均值与最大值之间的常数。

3.2.3. 转移概率矩阵计算方法

采用任意节点i与j间相似性度值来更新启发信息，如式(6) (7)所示。

$comm\left(i,j\right)=neibour\left(i\right)\cap neibour\left(j\right)$ (6)

${\delta }_{ij}=\gamma \times \frac{\left|comm\left(i,j\right)\right|}{\left|neibour\left(i\right)\cup neibour\left(j\right)\right|}+1-\gamma \times \frac{2\times \left|Ecomm\left(i,j\right)\right|}{\left|comm\left(i,j\right)\right|\times \left|comm\left(i,j\right)-1\right|}$ (7)

其中：$comm\left(i,j\right)$ 表示节点i和j共同邻居的数量；$neibour\left(i\right)$ 表示节点i的邻居；$neibour\left(j\right)$ 表示节点j的邻居；$\left|E\left(comm\left(i,j\right)\right)\right|$ 表示连接每个共同邻居节点的边的数量。从式(7)可知，启发式信息更新策略由两项组成，并通过权重系数$\gamma$ 控制两者在启发信息中的重要程度。物理上解释为，如果两个邻居节点有许多共同的邻居且它们之间的连接距离较近，那么它们属于同一社团的概率更高。计算信息素与启发信息更新策略的状态转移概率矩阵如下：

$p_{ij}=\{\begin{array}{l}\frac{\tau {\left(i,j\right)}^{\alpha }\delta {\left(i,j\right)}^{\beta }}{{\displaystyle {\sum }_{neibour\left(i\right)}\tau {\left(q,i\right)}^{\alpha }\delta {\left(q,i\right)}^{\beta }}}j\in neibour\left(i\right)\\ 0\text{otherwise}\end{array}$ (8)

其中：$\alpha$ 和$\beta$ 表征信息素与启发信息在迭代过程中的强化程度。

4. IACOA算法步骤

4.1. 蚂蚁位置初始化

首先，进行蚂蚁位置与标签列表的初始化。按节点度降序排列网络，计算公共邻居并形成初始社团。根据初始社团，生成相应的标签列表，并将蚂蚁放置在对应的初始集群节点中。

算法2 蚂蚁位置初始化

Input: $G=\left(V,E\right)$ Output: 蚂蚁的位置$C_{node}$ 以及存储在每个节点v的标签列表$l\left(v.1\right)$ 。 1: $C_{node},CN,v.1\leftarrow \varnothing$ ； 2: $\forall v\in V:v.available=true$ ； # 每个节点v具有一个ID 3: # 根据节点的度对所有节点进行降序排序得到列表L； 4: for each $v_i\in L$ do 5: $sg\leftarrow \varnothing$ 6: if v.available and $d\left(v_i\right)\ge 3$ then 7: 找到$v_i$ 的邻居中度最大对的节点$v_j$ 并令$v_j.available\leftarrow true$ 8: $sg\leftarrow sg\cup \left\{v_i,v_j\right\}$ 9: 计算$v_i$ 和$v_j$ 的共同邻居$comNei$ 10: while $comNei\ne \varnothing$ do 11: for each $v_m$ in $comNei$ do 12: $sg\leftarrow sg\cup \left\{v_m\right\}$

13: $Z=neibour\left(v_m\right)\cap comNei$ 并用Z代替$comNei$ 14: end for 15: end while 16: end if 17: $CN\leftarrow CN\cup sg$ 18: for each $v_x$ in $sg$ do 19: $v_x.l\leftarrow v_j.ID$ 20: end for 21: end for 22: return $C_{node}$ , l $C_{node}$ 是CN中的节点，不在$C_{node}$ 中的节点使用其本身ID初始化

4.2. 蚂蚁的移动

每个蚂蚁都会根据转移概率将ID在两节点间转移。为提高蚂蚁遍历整个网络抽象图G的几率，将蚂蚁移动规则设为：如果随机数$r<0.1$ ，则蚂蚁将选择具有最大概率的邻居作为下一个要访问的节点；否则蚂蚁随机选择除具有最大转移概率的邻居节点作为访问节点。而蚂蚁需访问多个具有相同转移概率的ID时，将随机选择其一。迭代结束时，蚂蚁从当前节点移动至下一节点。此外，每个蚂蚁在当前节点的标签列表中选择一个标签，然后将其存放到下一节点的标签列表中，同时信息素被存放在蚂蚁在不同节点转移路径上。信息素的挥发过程发生在每次迭代结束时。

算法3 蚂蚁的移动策略

1: while 不满足终止条件 do 2: for each ant do 3: 蚂蚁基于转移概率矩阵从节点i移动到节点j 4: 蚂蚁从一个节点移动到下一节点，并从当前节点到下一个节点获得一个标签，将这一标签保留在下一节点标签列表中 5: 该边的信息素量增加x 6: if 信息素值超过阈值b then 7: 将信息素的值设置为b 8: end if 9: 所有蚂蚁移动后，所有边的信息素按$\rho$ 挥发，${\tau }_{new}=\left(1-\rho \right)\times \tau$ 10: end for 11: 重新计算转移概率矩阵 12: end while

为防止算法过早收敛到非全局最优解，规定：当信息素超过预定值时，限制边缘信息素到最大值。这有效地避免了一条路径上的信息量远超其他路径，也消除了所有蚂蚁集中在同一路径的情况。

4.3. 后处理

迭代结束后，统计各节点中标签列表中各值的出现频率。若某一值在整个标签列表中的出现频率较高，那么该节点属于该标签的概率也较高。为了提高重叠社团检测准确率，可以采用后处理算法对待检测网络进行多次扫描，最终确定社团的划分。

算法4 后处理

Input: 节点及其标签列表 Output: 重叠社团的集合C 1: 首先根据标签列表中频率从最大的标签获得每个节点的标签 2: for v in V do 3: 找到节点v邻居节点$N\left(v\right)$ 并记录其邻居的标签集合L 4: for l in L do 5: if $\left|N^l\left(v\right)\right|/sum>\theta$ then 6: l是节点v所从属的一个社团 7: end if 8: end for 9: end for 10: 删除所有包含在大社团中的小社团 11: return C

其中：$\left|N^l\left(v\right)\right|$ 为具有标签l的节点v的邻居节点数量；sum为节点v的邻居节点中所有可能的标签数量。

4.4. 排名候选组

如果一个意见垃圾邮件发送者组包含多个评价者，例如检测到三个评价者作为潜在垃圾邮件发送者组，存在可能错误的检测。真实的垃圾邮件发送者群体通常规模庞大，以最大程度扩大其影响力。为了减少评论人数较少的意见垃圾邮件发送者群体的影响，在本文的方法中，本文将损失函数$L\left(g\right)$ 表示为：

$L\left(g\right)=\frac{1}{1+{\text{e}}^{-\left(\left|R_g\right|+\left|P_g\right|-3\right)}}$ (9)

$\left|R_g\right|$ 表示群组g中的评价者的数量；$\left|P_g\right|$ 是群组g中的评价产品的数量。为了便于计算和比较，本文将垃圾邮件指标标准化为$\left[0,1\right]$ 的范围。

4.4.1. 个人垃圾邮件指标

本文研究的个人垃圾邮件指标包括突发性(BST)、最大评论数(MNR)和平均评级偏差(avgRD)。个人垃圾邮件指标可以称为行为指标。

突发性(BST)：垃圾邮件发送者通常会在短时间内评价目标产品，以产生最大影响。评价者r的时间突发性表示为：

$BST\left(r\right)=\{\begin{array}{ll}0,\hfill & L\left(r\right)-F\left(r\right)>\alpha \hfill \\ 1-\frac{L\left(r\right)-F\left(r\right)}{\alpha },\hfill & \text{otherwise}\hfill \end{array}$ (10)

其中，$L\left(r\right)-F\left(r\right)$ 是评价者r的最后一次评价和第一次评价之间的时间间隔，用户给出一个特殊的$\alpha$ 作为时间阈值，通常为10天。

最大评论数(MNR)：每天提供大量评论是一种不正常的现象。假设评价者r在一天内发布评价，MNR表示为：

$MNR\left(r\right)=\frac{\max V_r}{{\max }_{r\in R}\left(\max V_r\right)}$ (11)

$MNR\left(r\right)$ 计算了一个评价者r在一天内评论的最大数量，本文将MNR的范围设置为$\left[0,1\right]$ 。

平均评分偏差(avgRD)：普通评价者对一种产品的评分与其他评价者对相同产品的评分大致相似。由于垃圾邮件发送者试图诽谤或推广目标产品，垃圾邮件发送者的评分可能与其他评价者的评分有显著差异。因此，评分偏差可以反映评价者的广度。对于评价者r的平均评分偏差表示为：

$avgRD\left(r\right)=av{g}_{p\in B_r}\frac{r_p-{\overline{r}}_p}{4}$ (12)

评价产品p的评价者r的评分表示为$r_p$ 。所有评价者评价产品p的平均分数表示为${\overline{r}}_p$ 。对最大分数偏差进行规范化，以避免维度的影响，产品的最高分数为5，因此产品的最大评级偏差为4。

4.4.2. 组垃圾邮件指标

组垃圾邮件指标有四种：评价紧密度(RT)、产品紧密度(PT)、组内评级偏差(GRD)和群组规模(GS)。通常前三种是结构特征，第四种是行为特征。

评价紧密度(RT)：如果群组g存在意见垃圾邮件发送者，则其RT可表示为：

$RT\left(g\right)=\frac{\left|V_g\right|}{\left|R_g\right|\left|P_g\right|}L\left(g\right)$ (13)

其中，$\left|V_g\right|$ 表示g组内评论数量；$\left|R_g\right|$ 表示g组内评价者数量；$\left|P_g\right|$ 表示g组内评价过的产品数量。本文使用惩罚函数$L\left(g\right)$ 来降低群组大小较小的意见垃圾邮件发送者组的影响。

产品紧密度(PT)：如果有一个意见垃圾邮件发送者组只评价几个特定的产品，那么这个群组可以被视为一个真正的意见垃圾邮件发送者组。对于意见垃圾邮件发送者组g的PT可以表示为：

$PT\left(g\right)=\frac{\left|{\displaystyle {\cap }_{r\in R_g}{P}_r}\right|}{\left|{\displaystyle {\cup }_{r\in R_g}{P}_r}\right|}$ (14)

组内评级偏差(GRD)：出于同样的目的，意见垃圾邮件发送者组中的成员对特定产品的评级是相同或相似的。因此，可以使用组内评级偏差来计算可疑意见垃圾邮件发送者组。

$GRD\left(g\right)=2\left(1-\frac{1}{1+{\text{e}}^{-\alpha v{g}_p\partial S^2\left(g,p\right)}}\right)L\left(g\right)$ (15)

其中，$S^2\left(g,p\right)$ 表示g组内对产品p的评级方差。使用sigmoid函数对其进行归一化，并将整个方程乘以常数2，从而将指标的范围扩展到$\left(0,1\right)$ 。最后，本文使用惩罚函数$L\left(g\right)$ 来降低小群体的影响。

群组规模(GS)：群组大小还可以反映意见垃圾邮件发送者组的垃圾邮件性。一方面，一个小规模的小组，包括两到三名评价者，更可能是巧合。另一方面，垃圾邮件发送者群体越大，损害就越大。因此，此指标旨在捕获更大的意见垃圾邮件发送者群体。给定意见垃圾邮件发送者组g，其GS表示为：

$GS\left(g\right)=\frac{1}{1+{\text{e}}^{-\left(\left|R_g\right|-3\right)}}$ (16)

其中，$\left|R_g\right|$ 表示g组内评价者数量，本文使用sigmoid函数对其进行规范化。

4.4.3. 垃圾邮件分数

垃圾邮件评分可以衡量垃圾邮件发送者组的可疑程度，垃圾邮件评分由组垃圾邮件评分和个人垃圾邮件评分确定。给定一个意见垃圾邮件发送者组g，它可以表示为：

$SS\left(g\right)=\frac{1}{2}\left(GroupSI\left(g\right)+IndividualSl\left(g\right)\right)$ (17)

其中，$GroupSI\left(g\right)$ 表示为所有组垃圾邮件指标的平均值，$IndividualSI\left(g\right)$ 表示为所有个人垃圾邮件指标的平均值。

5. 实验

5.1. 数据集

本文使用表1所示的三个真实世界评论数据集来评估本文中提出的方法。YelpChi是三个数据集中最小的数据集，由[11]收集，主要包括关于芝加哥葡萄酒屋和餐厅的评论，YelpNYC评论数据集和YelpZip评论数据集[12]。YelpNYC包括许多商业评论，主要是关于纽约市餐馆的情况。YelpZip是三个数据集中最大的数据集，其中包括许多餐厅评论，主要来自纽约市附近zipcode连续的地区。

Table 1. Yelp three datasets

表1. Yelp三大数据集

Name	Reviews (filtered %)	Reviewers (spammer %)	Products	Time span
YelpChi	67,395 (13.23%)	38,063 (20.33%)	201	2004.10~2012.10
YelpNYC	359,052 (10.27%)	160,225 (17.79%)	923	2004.10~2015.01
YelpZip	608,598 (13.22%)	260,277 (23.91%)	5044	2004.10~2015.01

5.2. 基线方法

Wang、GSBP、SPEagle和FraudEagle分别提出了基于图的方法。本文以这四种方法为基线进行比较。SPEagle、Wang和FraudEagle没有对意见垃圾邮件发送者群体进行研究，他们只是简单地对评论数量和评论人数进行排名。GSBP作为一种基于排名的垃圾邮件发送者群检测方法，通过相关图来描述意见垃圾邮件发送者群。

5.3. 评价指标

本文提出的方法和其他基线方法进行了比较和排名。因此，本文采用以下指标作为绩效评估指标。(一) precision@n：表示垃圾邮件(发送者)前n位的比率；(二) NDCG@n：它表示垃圾邮件(发送者)排名更接近榜首位置。特别是$\text{NDCG}@\text{n}=\frac{\text{DCG}@\text{n}}{\text{IDCG}@\text{n}}$ ，对于$\text{DCG}@\text{n}={\displaystyle {\sum }_{i=1}^n\frac{2^{l_i}-1}{{\log }_2\left(i+1\right)}}$ ，其中$l_i$ 是排名i的项目的真实标签(1：垃圾邮件，0：非垃圾邮件)，并且IDCG@n指理想排名的DCG，即所有$l_i$ 均为1。

5.4. 实验结果

本文使用三个真实世界的Yelp数据集，用四种比较的方法评估IACOA。为了实现准确性和一致性，使用IACOA中的指标与四种比较方法中的指标相同。本文假设IACOA中的$k=3$ ，$\alpha =10$ ，并且取Topn的评价(者) ($n\le 1000$ )，如图1所示的三个真实世界Yelp数据集上的四种比较方法。比较图1、图2和图3可以发现，随着评价(者)数量的急剧增加，IACOA和SPEagle精度降低，而GSBP、Wang和FraudEagle的精度增加。综上所述，除了YelpChi数据集上的SPEagle外，IACOA在预测精度方面优于其他四种比较方法。随着数据集的扩展，IACOA具有更好的预测精度。

Figure 1. Precision@n of evaluation and evaluator ranking comparison methods in YelpChi datasets

图1. 在YelpChi数据集上的评论排名比较方法的Precision@n

Figure 2. Precision@n of evaluation and evaluator ranking comparison methods in YelpNYC datasets

图2. 在YelpNYC数据集上的评论排名比较方法的Precision@n

Figure 3. Precision@n of evaluation and evaluator ranking comparison methods in YelpZip datasets

图3. 在YelpZip数据集上的评论排名比较方法的Precision@n

Figure 4. NDCG@n of evaluation and evaluator ranking comparison methods in YelpChi datasets

图4. 在YelpChi数据集上的评论排名比较方法的NDCG@n

Figure 5. NDCG@n of evaluation and evaluator ranking comparison methods in YelpNYC datasets

图5. 在YelpNYC数据集上的评论排名比较方法的NDCG@n

Figure 6. NDCG@n of evaluation and evaluator ranking comparison methods in YelpZip datasets

图6. 在YelpZip数据集上的评论排名比较方法的NDCG@n

图4、图5和图6提供了NDCG@n在三个Yelp数据集的比较方法。IACOA在以下方面优于四种比较方法NDCG@n，除了SPEagle。IACOA NDCG@n随着数据集的扩展，变得越来越好。综上所述，IACOA在四种方法中表现最好。

6. 结论

本文试图找到一种创新的基于图的模型来更好地描述意见垃圾制造者群体，并提高预测精度。首先构建Review数据集作为reviewer投影图。其次，通过基于改进蚁群算法的社团检测找到候选群组。第三，使用基于组或个人的垃圾邮件指标，根据其垃圾邮件度对意见垃圾邮件发送者组进行排名，最有可能的意见垃圾邮件发送者组是排名靠前的组。在三个真实数据集上进行对比实验。结果表明，本文提出的方法在预测精度方面优于四种基线，并且在四种方法中获得了最好的性能。