基于用户的关注关系的垃圾用户发现方法

摘要

一种基于用户的关注关系的垃圾用户发现方法，其包括：获取用户以及用户之间的关注关系；对于任一第一用户，基于所述关注关系来统计所述第一用户的局部三角形的数量，其中，所述局部三角形中的任意一个由所述第一用户与另外两个用户构成，并且其中，所述第一用户关注所述另外两个用户中的每一个，且在所述另外两个用户之间也存在关注关系；根据所述第一用户的局部三角形的数量来计算所述第一用户的局部三角形比例；以及至少部分地基于所述第一用户的局部三角形比例来判断所述第一用户是否是垃圾用户。

说明书

技术领域

本发明涉及web挖掘领域，尤其涉及基于用户的关注关系的垃圾用户 或垃圾账户发现方法。

背景技术

类Twitter的微博服务最近作为一个新的通信媒介得到迅速发展，据 第29次中国互联网报告统计：截至2011年12月底，我国微博实际用户 数达到2.5亿，较上一年底增长了296.0%，网民使用率为48.7%。区别于 其他类Facebook的社交网络服务，微博服务的社会网络关系为单向的， 用户不需要其他用户对其赋予权限就可以“关注”他们。例如，Twitter中 社会网络由关注关系形成，用户关注的人称为该用户的好友或关注好友； 关注某用户的人称为该用户的粉丝，用户发布的所有博文将出现在公共时 间线上，该用户所有粉丝的时间线上将显示该用户的所有消息。

随着微博服务的普及，存在大量以刺探隐私情报、商业推销、推高用 户人气等为目的的人工垃圾用户。这些大量的垃圾用户使得微博服务提供 商的账户资源受到了冲击，加大了管理账户的难度，提高了账户资源开发 和管理成本。例如，大量的垃圾用户使得微博服务提供商不得不花费更多 的硬件资源或人力成本来进行账户管理。同时，这些垃圾用户的大量存在 也对正常用户的使用带来了干扰。因此，一直以来，人们期望能够发现微 博中的垃圾用户以便对其进行合适的处理。

传统的微博中垃圾用户发现方法主要基于用户的显式统计特征来进 行判断，比如发帖规律、关注的好友数量与其粉丝数量比例、博文中提及 （userScreenName）其他用户比例等。这些方法例如：

在参考文献1“Chu Z,Gianvecchio S,Wang H,et al.Who is tweeting on  Twitter:human,bot,or cyborg?[C].Proc of the26th Annual Computer  Security Applications Conference.ACM,2010:21-30.”中依靠Twitter中用户 发布博文的显式统计特性区分垃圾机器人、类人机器人和正常用户，利用 发帖规律、关注的好友数量与其粉丝数量比例、博文中提及（ userScreenName）其他用户比例等识别垃圾用户。

在参考文献2“McCord M,Chuah M.Spam Detection on Twitter Using  Traditional Classifiers[C].Proc of the8th International Conference on  Autonomic and Trusted Computing.NJ:IEEE,2011:175-186.”中，利用用户 特征与博文特征设计分类器区分正常用户与垃圾用户，分类器采用贝叶斯 分类方法。

在参考文献3“Stringhini G,Kruegel C,Vigna G.Detecting spammers on  social networks[C].Proc of the26th Annual Computer Security Applications  Conference.ACM,2010:1-9.”中分析了垃圾用户的发帖行为，依靠显式统 计特性识别垃圾用户和大规模垃圾用户整体活动。

在参考文献4“Thomas,K,Grier,C,Paxson,V,et al.Suspended Accounts  in Retrospect:An Analysis of Twitter Spam[C].Proc of the2011ACM  SIGCOMM conference on Internet measurement conference.New York:ACM, 2011:243-258.”中利用Twitter中暂停的账号分析垃圾用户特性。

本文将使用上述传统方法基于用户的显式统计特征所发现的垃圾用 户称为显式垃圾用户。上述传统方法确实能够在一定程度上发现垃圾用 户，但是由于其算法较为粗糙（例如，仅考虑一些显式统计特征），因此 并不能提供概率上的高可靠性，例如，其可能遗漏大量垃圾用户，或者， 其可能将大量正常用户误判为垃圾用户。特别是，随着上述这些传统垃圾 用户发现方法的使用，一些恶意制造垃圾用户的人也相应地采取了对策， 使得垃圾用户在显式统计特征方面更加类似于正常用户，例如，使得垃圾 用户同样具有大量好友和粉丝，这导致了垃圾用户特征的更加复杂化，也 更加难于准确地区分垃圾用户和正常用户。在本文中可以将此类在显式统 计特征方面比较类似于正常用户的垃圾用户称为隐式垃圾用户。

因此，为了弥补传统的垃圾用户发现方法的不足，需要提供一种可以 更准确地发现微博中的垃圾用户（特别是隐式垃圾用户）的方法，以便使 得微博服务提供商能够对这些垃圾用户进行相应的处理，从而节省微博服 务提供商用于账户管理的硬件资源或人力成本，同时，也避免这些垃圾用 户对正常用户的干扰。

发明内容

本发明的一个方面涉及一种基于用户的关注关系的垃圾用户发现方 法，其包括：获取用户以及用户之间的关注关系；对于任一第一用户，基 于所述关注关系来统计所述第一用户的局部三角形的数量，其中，所述局 部三角形中的任意一个由所述第一用户与另外两个用户构成，并且其中， 所述第一用户关注所述另外两个用户中的每一个，且在所述另外两个用户 之间也存在关注关系；根据所述第一用户的局部三角形的数量来计算所述 第一用户的局部三角形比例；以及至少部分地基于所述第一用户的局部三 角形比例来判断所述第一用户是否是垃圾用户。

优选地，所述根据所述第一用户的局部三角形的数量来计算所述第一 用户的局部三角形比例包括：根据所述第一用户的局部三角形的数量以及 在所述第一用户与其所关注的其他用户之间能够形成的所述第一用户的 局部三角形的最大数量来计算所述第一用户的局部三角形比例；或者，根 据所述第一用户的局部三角形的数量以及所述第一用户关注的其他用户 的数量来计算所述第一用户的局部三角形比例。

优选地，所述至少部分地基于所述第一用户的局部三角形比例来判断 所述第一用户是否是垃圾用户包括：如果所述第一用户的局部三角形比例 低于预定阈值，则判断所述第一用户是垃圾用户。

优选地，判断所述第一用户是否是垃圾用户进一步基于用户之间的信 任正向传播过程和/或信任逆向传播过程。

优选地，所述信任正向传播过程包括：确定正常用户种子节点；确定 所述正常用户种子节点所直接关注或间接关注的所有节点，其中，所述正 常用户种子节点所直接关注或间接关注的节点具有更高的概率是正常用 户；所述信任逆向传播过程包括：确定垃圾用户种子节点；确定直接关注 或间接关注所述垃圾用户种子节点的所有节点，其中，直接关注或间接关 注所述垃圾用户种子节点的节点具有更高的概率是垃圾用户。

本发明的另一个方面涉及一种基于用户的关注关系的垃圾用户发现 设备，其包括：用于获取用户以及用户之间的关注关系的装置；用于对于 任一第一用户，基于所述关注关系来统计所述第一用户的局部三角形的数 量的装置，其中，所述局部三角形中的任意一个由所述第一用户与另外两 个用户构成，并且其中，所述第一用户关注所述另外两个用户中的每一个， 且在所述另外两个用户之间也存在关注关系；用于根据所述第一用户的局 部三角形的数量来计算所述第一用户的局部三角形比例的装置；以及用于 至少部分地基于所述第一用户的局部三角形比例来判断所述第一用户是 否是垃圾用户的装置。

优选地，所述用于根据所述第一用户的局部三角形的数量来计算所述 第一用户的局部三角形比例的装置包括：用于根据所述第一用户的局部三 角形的数量以及在所述第一用户与其所关注的其他用户之间能够形成的 所述第一用户的局部三角形的最大数量来计算所述第一用户的局部三角 形比例的装置；或者，用于根据所述第一用户的局部三角形的数量以及所 述第一用户关注的其他用户的数量来计算所述第一用户的局部三角形比 例的装置。

优选地，所述用于至少部分地基于所述第一用户的局部三角形比例来 判断所述第一用户是否是垃圾用户的装置包括：用于如果所述第一用户的 局部三角形比例低于预定阈值，则判断所述第一用户是垃圾用户的装置。

优选地，判断所述第一用户是否是垃圾用户进一步基于用户之间的信 任正向传播过程和/或信任逆向传播过程。

优选地，所述信任正向传播过程包括：确定正常用户种子节点；确定 所述正常用户种子节点所直接关注或间接关注的所有节点，其中，所述正 常用户种子节点所直接关注或间接关注的节点具有更高的概率是正常用 户；所述信任逆向传播过程包括：确定垃圾用户种子节点；确定直接关注 或间接关注所述垃圾用户种子节点的所有节点，其中，直接关注或间接关 注所述垃圾用户种子节点的节点具有更高的概率是垃圾用户。

附图说明

参考附图详细描述了本发明，应当理解，附图以及相应的描述应当被 理解为是说明性的而非限制性的，其中：

图1示出了微博用户的关注网络的链接结构的两种不同表现形式，其 中，图1（a）示出了一个正常用户A的关注网络的链接结构，图1（b） 示出了一个典型的垃圾用户B的关注网络的链接结构；

图2示出了正常用户与垃圾用户的局部三角形比例的示例分布；

图3示出了根据本发明的一个示例性垃圾用户发现方法；

图4示出了微博用户有向网络图中两个节点的3种关系；

图5示出了微博用户形成局部三角形的3种方式；

图6示出了在一次实验中局部三角形比例为0的用户的时间间隔Δt分 布。

具体实施方式

下面结合附图以微博应用作为示例来对本发明的优选实施方式进行 详细说明，但可以理解，本发明同样适用于在用户之间存在关注关系的其 他网络应用。

如人们所了解的，微博服务不仅表现为社交网络功能，更倾向于表现 为新闻媒体功能，用户不仅可以通过微博服务来交友，而且每个用户都可 以成为新闻媒体角色来发布信息。由此推断，正常用户在使用微博服务时 通常会表现出两种行为：1）发布信息；2）通过微博服务交友，以寻找更 有价值的信息。

统计数据表明，微博中的大部分正常用户（约90%）会根据其目前的 好友来寻找新的好友，从而导致用户与其好友形成局部三角形。例如，在 图1（a）中示出了一个正常用户A的关注网络的链接结构，其中，在用 户A、c、d之间、在用户A、e、f之间、以及在用户A、g、h之间都形成 了局部三角形。以在用户A、e、f之间形成的局部三角形为例，其形成过 程可能如下：用户A首先关注了用户e（即，e是A的好友，A是e的粉 丝），然后用户A发现用户e关注了用户f，从而用户A可能相应地关注 用户f使得用户f也成为其好友；或者，用户A首先关注了用户f，然后 用户A发现用户f的粉丝中包括用户e，从而用户A可能相应地关注用户 e使得用户e也成为其好友。从上可以看出，正常用户会依靠2跳（2-hops） 关系寻找更有价值的好友，最终形成在三个用户之间的局部三角形。

但微博中的垃圾用户通常不具有较多的好友或粉丝，或者虽然具有一 些好友或粉丝，也只是没有目的、随意地关注其他好友，而很少会主动地 根据2跳（2-hops）关系寻找更有价值的好友。在图1（b）中示出了一个 典型的垃圾用户B的关注网络的链接结构，其可能只是在创建时随意地关 注了一些好友，但并未进而根据好友来寻找新的好友。

为了进一步对上述推论进行验证，可以针对微博中的显式垃圾用户 （或者已确认的垃圾用户）样本与正常用户样本分别统计局部三角形比例 分布。图2示出了所进行的一次统计的结果，其表明70%以上的垃圾用户 的局部三角形比例分布在[0,0.1]之间，说明垃圾用户通常以很低的概率根 据2跳（2-hops）关系交友，而约80%的正常用户的局部三角形比例分布 在[0.1,0.5]之间，说明正常用户经常会根据2跳（2-hops）关系交友。因此， 在垃圾用户与正常用户的局部三角形比例之间存在明显的差异性，垃圾用 户相对于正常用户以更低的概率通过2跳（2-hops）关系交友。对于上文 提到的局部三角形比例，其通常正比于用户的局部三角形的数量。在下文 的实施例中会给出局部三角形比例的一个示例性的定义或计算公式，但该 局部三角形比例的定义或计算公式可以根据实际情况进行选取或调整，并 不局限于本文实施例中示出的情形。

上文的统计数据和实验结果表明基于或部分地基于用户的局部三角 形比例能够更为准确地区分正常用户与垃圾用户。下文参考图3描述了本 发明的一个示例性垃圾用户发现方法。

在步骤301，获取用户以及用户之间的关注关系。

为了获取用户的局部三角形比例，需要首先获得用户的局部三角形数 量。可以通过提取微博用户以及用户之间的关注关系来计算用户的局部三 角形数量，优选地，可以将用户以及用户之间的关注关系抽象为有向网络 图来进行上述计算。例如，对于微博用户所构成的网络，可以构造有向网 络图G_d=(V_d,E_d)，其中V_d表示该有向网络图G_d中的节点集合（也即用户 或账户集合），E_d表示该有向网络图G_d中的各节点之间的有向边集合，其 代表用户之间的关注关系。对于该有向网络图中的两个示例节点u和v， 存在图4所示的3种关系（未考虑u和v之间不存在边的关系），具体地， 图4（a）表示v为u的关注好友；图4（b）表示v为u的粉丝；图4（c） 表示u和v为互粉朋友。

在步骤302，对于任一第一用户，基于所述关注关系来统计该第一用 户的局部三角形的数量，其中，所述局部三角形中的任意一个由该第一用 户与另外两个用户构成，并且其中，该第一用户关注所述另外两个用户中 的每一个，且在所述另外两个用户之间也存在关注关系。

具体地，对用户的局部三角形数量进行统计主要是判断该用户通过2 跳关系进行交友的情况。令用户v为用户u的关注好友，则用户u可以根 据用户v的关注好友来交友，也可以根据用户v的粉丝来交友，同时也可 以根据用户v的互粉朋友来交友。参见图5所示，在图5的（a）中，用 户u将用户v的一个关注好友w作为其关注好友，在图5的（b）中，用 户u将用户v的一个粉丝w作为其关注好友，在图5的（c）中，用户u 将用户v的一个互粉朋友w作为其关注好友。图5中所示的三种类型即为 关于用户u的局部三角形的各种可能类型。因此，可以看出，用户u的局 部三角形由用户u以及其所关注的另外两个用户v和w（也即，该用户u 的两个好友v和w）构成，且在所述两个用户v和w之间也存在关注关系， 例如，用户v关注用户w，或者用户w关注用户v，或者用户v和w互相 关注。

对于由用户u、v和w构成的有向网络图，通过考虑图5所示的三种 类型的局部三角形，可以将关于用户u的局部三角形数量定义为如下： T(u)=|{e_vw∈E_d,e_uv∈E_d,e_uw∈E_d}|+|{e_wv∈E_d,e_uv∈E_d,e_uw∈E_d}|-|{e_vwwv∈E_d,e_uv∈E_d,e_uw∈E_d}| 其中，e_uv表示用户u关注用户v，e_uw表示用户u关注用户w，e_vw表示用户 v关注用户w，e_wv表示用户w关注用户v，e_vwwv表示用户v与w之间互相 关注从而形成互粉关系（等同于“e_vw且e_wv”），E_d表示该有向网络图中的 各节点之间的有向边集合。可以看出，|{e_vw∈E_d,e_uv∈E_d,e_uw∈E_d}|考虑的 是图5（a）或图5（c）所示类型的局部三角形，|{e_wv∈E_d,e_uv∈E_d,e_uw∈E_d}| 考虑的是图5（b）或图5（c）所示类型的局部三角形，而 |{e_vwwv∈E_d,e_uv∈E_d,e_uw∈E_d}|考虑的是图5（c）所示类型的局部三角形， 因为其在前面已经被重复计算，因此需要被减去。

上文示出了对于三个用户如何来计算其中的用户u的局部三角形数量 的方法。下面将该方法扩展到由所有微博用户构成的有向网络图G_d的情 况，其将有向网络图的局部三角形数量统计转换为了集合运算。具体地， 对于有向网络图G_d=(V_d,E_d)中的某一用户u，可以使用Fr(u)来表示该用户 u所有的关注好友的集合，即Fr(u)={w∈V_d:e_uw∈E_d}。对于用户u的任一关 注好友v，相应地，可以使用Fr(v)来表示该用户v所有的关注好友的集合， 即Fr(v)={w∈V_d:e_vw∈E_d}。另外，可以进一步使用Fo(v)={w∈V_d:e_wv∈E_d} 来表示用户v的所有粉丝的集合，使用F(v)={w∈V_d:e_wv∈E_dande_vw∈E_d} 来表示用户v的所有互粉好友的集合。

这样的话，可以将有向网络图G_d=(V_d,E_d)中的节点u的所有局部三角 形的数量计算为：

$N_{\mathrm{Tri}}=\frac{1}{2}\left({\Sigma }_{v\in \mathrm{Fr}\left(u\right)}\right|\mathrm{Fr}\left(u\right)\cap \mathrm{Fr}\left(v\right)|+{\Sigma }_{v\in \mathrm{Fr}\left(u\right)}|\mathrm{Fr}\left(u\right)\cap \mathrm{Fo}\left(v\right)|-{\Sigma }_{v\in \mathrm{Fr}\left(u\right)}|\mathrm{Fr}\left(u\right)\cap F\left(v\right)\left|\right)$

上述公式中的|Fr(u)∩Fr(v)|考虑的是图5（a）或图5（c）所示类型 的局部三角形，|Fr(u)∩Fo(v)|考虑的是图5（b）或图5（c）所示类型的 局部三角形，|Fr(u)∩F(v)|考虑的是图5（c）所示类型的局部三角形。

通过上述公式，将有向网络图中的用户的局部三角形数量统计转换为 了3个集合的交运算。实现上述公式的一个示例性的具体算法如下所示， 其中，两集合的交集运算需要迭代m次，同时针对每对关系的两组节点， 计算其中一个节点的好友集合与另外一个节点的好友、粉丝、互粉朋友集 合的交集数量，即每对关系都需要3次交集运算，所以整个算法时间开销 为O(m|E|)。

在通过步骤302获得了任一第一用户的局部三角形的数量之后，可以 在步骤303，根据该第一用户的局部三角形的数量来计算该第一用户的局 部三角形比例。

例如，对于给定的用户u，如果已经计算出了该用户u的局部三角形 数量为N_Tri，并且知道该用户u的所有的关注好友的数量为N_fr，则该用户 u的局部三角形比例TRatio可以被定义为如下：

$\mathrm{TRatio}=\left(\begin{array}{cc}\frac{N_{\mathrm{Tri}}}{C_{N_{\mathrm{fr}}}^2}& N_{\mathrm{fr}}\ge 2\\ 0& N_{\mathrm{fr}}=1\end{array}\right)$

其中表示用户u与其关注的所有好友能够形成的用户u的局部三 角形的最大数量，即：

$C_{N_{\mathrm{fr}}}^2=\frac{N_{\mathrm{fr}}\times (N_{\mathrm{fr}}-1)}{2},N_{\mathrm{fr}}\ge 2$

然后，在步骤304，可以至少部分地基于该第一用户的局部三角形比 例来判断其是否是垃圾用户。例如，通过使用所获得的用户u的局部三角 形比例TRatio，可以对用户u是否是垃圾用户做出判断。

需要了解的是，上文对局部三角形比例TRatio的定义仅仅是个示例， 可以使用任何其他合理的定义。例如，可以基于某一用户的局部三角形数 量和该用户的好友数量的比例来计算该局部三角形比例TRatio。另外，在 一些实施例中，可以进一步结合其他因素（例如用户发表的博文数量、用 户的好友数量、用户的粉丝数量等）来对用户是否属于垃圾用户进行综合 判断。

上文描述了通过计算用户的局部三角形比例来对用户是否属于垃圾 用户进行判断的方法。为了进一步提高判断的准确性和可靠性，在下文的 实施例中，进一步考虑了信任正向传播模型和/或信任逆向传播模型来判断 用户是否属于垃圾用户。信任正向传播模型和信任逆向传播模型分别基于 微博用户中的如下两个统计规律：1）正常用户通常关注正常用户；2）关 注垃圾用户的用户通常为垃圾用户。

信任正向传播

首先根据用户统计特征确认部分正常用户作为种子节点（例如，某些 影响力较大的微博用户可以被非常肯定地确认为是正常用户，从而可以作 为种子节点），然后确定这些种子节点所关注的其他节点，这些其他节点 是种子节点直接传播可达的节点集合，继而确定这些其他节点所关注的另 外的节点，依此类推，直到不再会获得新的传播可达的节点。最终，便会 获得所有可以由种子节点传播可达的节点，也即，种子节点所直接或间接 关注的节点。这些由种子节点所直接或间接关注的节点被认为具有更高的 概率是正常用户。

可以通过各种模型或算法来获得由种子节点传播可达的节点，在更为 优选的实施例中，还可以进一步计算各个节点的正向得分值。例如，在一 个实施例中，在确认种子节点之后，可以根据随机游走模型计算其他每个 节点的正向得分值。为了保证转移矩阵M的随机性，剪枝掉所有不能由种 子节点传播可达的其他节点，即保证每个节点都能够由种子节点传播可 达，从而剪枝算法转换为种子节点扩散算法。具体地，定义初始种子节点 集合为Set₀，种子节点传播可达的节点集合为Set_done，迭代过程中正在处理的 种子节点集合为Set_seed，新增加的种子节点集合为Set_temp，一种示例性的种子 节点扩散算法Seed_Diffusion如下所示。

上述种子节点扩散算法Seed_Diffusion为一个迭代算法，当不再会获 得新的传播可达的节点时，迭代终止，最后算法得到所有由初始种子节点 传播可达的其他节点集合Set_done，则有向网络图G_d=(V_d,E_d)中包含节点集合 Set_done的子图中每个节点的正向得分可以被计算为：

$\overrightarrow{r}=\alpha ·T^s·\overrightarrow{r}+(1-\alpha )·\overrightarrow{d}$

其中Ts为子图的转移矩阵，α为随机跳 转因子，为种子节点向量，上述公式转换为综合矩阵形式为：

$\overrightarrow{r_k}=\overrightarrow{r_{k-1}}·M^s$

其中M^s为子图中考虑跳转因子的综合矩阵，即：

$M^s=\alpha ·T^s+(1-\alpha )·\overrightarrow{d}·e$

其中，e为单位向量。因为T^s中除种子节点外，其他节点都可由种子 节点传播可达，即肯定存在其他节点随机指向该节点；同时表示算 法以概率(1-α)跳转到种子节点，即肯定存在其他节点随机跳转到种子节 点，所以剪枝掉所有不能由种子节点传播可达的其他节点得到的综合矩阵 M^s为随机性矩阵。

在计算过程中，可以将具有不同统计特征的用户的投票贡献设定为不 同，例如，根据用户的统计特征，可将用户分为5类：1）逼近正常用户； 2）疑似正常用户；3）不确定用户；4）疑似垃圾用户；5）逼近垃圾用户， 上述5类用户投票贡献由大到小。令z(i)为每个用户统计特征的投票贡献 值，且令节点集合Set_done中所有节点投票贡献值z(i)为对角矩阵Z=diag(z)，定义 节点的正向得分AttriGoodRank如下：

$\overrightarrow{r}=\alpha ·Z·T^s·\overrightarrow{r}+(1-\alpha )·\overrightarrow{d}$

AttriGoodRank得分转换为综合矩阵形式为：

$\overrightarrow{r_k}=\overrightarrow{r_{k-1}}·H$

其中H为考虑用户统计特征投票贡献值的综合矩阵，即：

$H=\alpha ·{Z·T}^s+(1-\alpha )·\overrightarrow{d}·e$

因对角矩阵Z与子图的转移矩阵T^s的乘积仅仅以一定比例改变随机 投票的值，不会减少网络中的链接关系，所以综合矩阵H仍为随机性矩阵， 所以AttriGoodRank得分计算为一个各态遍历的马尔科夫过程。因此，给 定一个初始的向量通过n次迭代，计算结果将会逐渐收敛。

信任逆向传播

信任逆向传播与信任正向传播在原理上类似，只是其根据用户统计特 征确认部分垃圾用户作为种子节点，另外，因为其所基于的统计规律是“关 注垃圾用户的用户通常为垃圾用户”，因此其从节点向其粉丝方向进行传 播，由所述垃圾用户种子节点传播可达的节点是直接关注或间接关注这些 垃圾用户种子节点的节点。

同样，在更为优选的一个实施例中，可以根据随机游走模型计算每个 节点的逆向得分值。为了保证转移矩阵的随机性，同样剪枝掉所有不能由 垃圾用户种子节点传播可达的其他节点，从而保证每个节点都能够由垃圾 用户种子节点传播可达。剪枝算法转换为种子节点扩散算法 Seed_Diffusion，其与上文提到的信任正向传播中使用的种子节点扩散算法 的不同之处在于：对迭代过程中正在处理的种子节点集合Set_seed中的每个元 素i，需要获取元素i的所有粉丝节点follower_i。

算法最后得到由种子节点传播可达的其他节点集合Set_bad，则社会网络 图G_d=(V_d,E_d)中包含节点集合Set_bad的子图中每个节点的逆向排名得 分值可以被计算为：

$\overrightarrow{b_k}=\overrightarrow{b_{k-1}}·M^b$

其中M^b为子图中考虑跳转因子的综合矩阵，即：

$M^b=\alpha ·T^b+(1-\alpha )·\overrightarrow{d}·e$

其中T^b为子图的转移矩阵，为种子节点向量，e为单位向量，同样 M^b为随机性矩阵。

在计算过程中，可以将具有不同统计特征的用户的逆向投票贡献设定 为不同，例如，垃圾用户投票贡献最大，其次为不确定用户，正常用户投 票贡献最小。令x(i)为每个用户统计特征的逆向传播投票贡献值，且令节点 集合Set_bad中所有节点逆向传播的投票贡献值x(i)为对角矩阵X=diag(x)，本文定 义节点的逆向得分AttriBadRank如下：

$\overrightarrow{b}=\alpha ·X·T^b·\overrightarrow{b}+(1-\alpha )·\overrightarrow{d}$

AttriBadRank转换为综合矩阵形式为：

$\overrightarrow{b_k}=\overrightarrow{b_{k-1}}·B$

其中B为考虑用户统计特征逆向投票贡献值的综合矩阵，即：

$B=\alpha ·X·T^b+(1-\alpha )·\overrightarrow{d}·e$

同样可以证明综合矩阵B为随机性矩阵，所以AttriBadRank得分计算 为一个各态遍历的马尔科夫过程。因此，给定一个初始的向量通过n 次迭代，计算结果将会逐渐收敛。

实验结果

在基于本发明的垃圾用户发现方法的一次实验中，首先从20万个用 户中提取出了局部三角形比例为0的3901个用户，然后分析这些用户的 账号创建时间（createTime）与发布最后一条博文时间（lastPostTime）的 关系。具体地，令时间间隔（time interval）为：Δt=lastPostTime-createTime，则 3901个用户的时间间隔Δt分布如图6所示。图6的结果表明这些用户大部 份在账号创建时发布少量博文后就从未发布博文，约59.4%的用户在账号 创建1小时内发布博文后从未发布博文，同时约83.7%的用户在账号创建 24小时内发布博文后从未发布博文。也就是说，这些用户中的大部分在账 号创建时发布少量博文后就从未发布博文，同时也没有依靠2跳（2-hops） 关系寻找更有价值的好友，处于“完全非活跃”状态。上述实验结果表明 本申请的基于用户关注关系的垃圾用户发现方法是有效的。

上文已经对本发明的优选实施方式进行了详细说明，需要注意的是， 在优选实施方式中针对微博应用进行了说明，但本领域技术人员可以理 解，本文所述的方法可以应用到微博之外的其他网络应用中。另外，本申 请的具体实施方式部分提到的具体算法、公式、参数设置等等仅仅用于示 例说明，并不用于限制本发明。本领域技术人员在知悉本发明的设计构思 和实质精神的情况下，可以对上述算法、公式、参数等进行合适的变形和 替换，其仍属于本申请的保护范围。