社区检测算法在评论中的应用

        介绍一种社群检测算法在恶意评论发掘中的应用

        前言

        在社交网络或者电商网站中,存在着用户关注其他用户或者用户浏览商品的二部图,而这些关系网络之中经常蕴藏大量的刷单,虚假,伪造行为,社区检测算法正是针对这些场景,进行深度行为挖掘,本文主要讲述一种社区检测算法在评论场景下的应用。

        业务场景描述

        应用商店下载评论业务人员发现有大量刷单行为,通过分析发现他们评论的内容和时间点都有明显的聚合效应,业务风控需要协助业务方挖掘出此场景下的恶意,需要评论人员,再依据发掘的信息进行跟踪二次处理。

        算法选型

        FRAUDAR算法来源于2016年KDD会议,该论文获得了当年的最佳论文奖。该算法要解决的问题是找出站内最善于伪装的虚假账户簇。其原理是虚假账户会通过增加和正常用户的联系来进行伪装,而这些伪装(边)会形成一个很紧密的子网络,这样就可以通过定义一个全局的度量,再移除二部图结构中的边,使得剩余网络结构对应的度量的值最大,这样就?#19994;?#20102;最紧密的子网络,而这个网络就是最可疑的。

        算法过程

        算法的核心计算过程可以简要描述如下,具体可以参考原论文中Algorithm1的伪代码:

        a、建立优先树(一种用于快速移除图结构边的树结构);

        b、对于二部图中的任意节点,贪心地移除优先级最高(由优先树得到)的节点,直至整个网络结构为空;

        c、比较上述每一步得到的子网络结构对应的全局的度量,取该值最大的子网络结构,那么该子网络结构就是最紧密的子网络,也就是最可疑的团伙。

        其中最关键的地方是定义了一个全局度量,该Metric的定义是(目标度量),可以理解成子网络结构中每个点的平均可疑程度

        g(s)=f(s)/|s|

        其中,

        f(s)=fv(s)+fe(s)

        通过这样的定义,很容易可以得出4条性?#21097;?/p>

        1、固定其他条件,包含更高可疑度节点的子网络比包含?#31995;?#21487;疑度节点的子网络更可疑;

        2、固定其他条件,增加可疑的边使得子网络更可疑;

        3、如果节点和边的可疑程度固定,那么大的子网络比小的子网络更可疑;

        4、总的可疑程度相同,那么包含节点数少的子网络更可疑。

        核心过程

        该算法的核心计算过程就是贪心地移除图中的点,使得每?#20266;?#26356;f的变化最大,在移除一个节点的同时,只有与之相邻的节点会发生变化,那么这样最多产生O(|E|)?#20266;?#26356;,如果?#19994;?#21512;适的数据结构使得访?#24335;?#28857;的时间复杂度为O(log|V|),那么总的时间复杂度就是O(NlogN)。

        基于这样的考虑建立了优先树,这是一个二叉树,图中的每个节点都是树的一个叶子节点,其父节点为子节点中优先级较高的,树建完之后就可以按照O(log|V|)的速度获得优先级最高的节点。

        抗虚假行为

        该算法的核心计算过程就是贪心地移除图中的点,使得每?#20266;?#26356;f的变化最大,在移除一个节点的同时,只有与之相邻的节点会发生变化,那么这样最多产生O(|E|)?#20266;?#26356;,如果?#19994;?#21512;适的数据结构使得访?#24335;?#28857;的时间复杂度为O(log|V|),那么总的时间复杂度就是O(NlogN)。

        基于这样的考虑建立了优先树,这是一个二叉树,图中的每个节点都是树的一个叶子节点,其父节点为子节点中优先级较高的,树建完之后就可以按照O(log|V|)的速度获得优先级最高的节点。

        线上特征工程

        1、定时获取线上评论数据,包括但不限于:

        用户id、应用id、设备id、创建时间等等

        2、数据进行编码处理(由于设备id及应用id数字过大,需要去重后重新编码处理)

        fd1.png

        3、设备及应用关注?#25104;?#26500;造

        4、设置最大社群10个

        5、保存分类簇结果(以设备id为分群数据提取)

        fd2.png6、设定最小阈值,选择最可疑社区群簇里面的设备

        fd3.png

        线上效果

        我们选择线上抽取连续一个月的数据进行分析,数据集合79927个,原始数据如下:

        fd4.png

        经过FRAUDAR检测出8个问题群簇,效果图如下:

        fd5.png

        总结

        上述社群8类?#26377;?#21040;大可疑度?#26469;?#36882;增,系统中可以依据运营经验设置一个可疑阈值,选择?#31639;?#20540;下的所有社群。检测之后可以针对发掘的用户做行为跟踪或者限制行为处理,同时还可以结合监督学习进行分析,实现系统自动挖掘及模型线上防御,尽可能的来减少人工运营流程。

        取消
        Loading...

        填写个人信息

        姓名
        电话
        邮箱
        公司
        行业
        职位
        css.php 永利彩票是骗局吗

                    澳洲幸运5官方开奖结果 中国体育彩票官方网 88彩票app老版本 北京快3 排列五最易中奖方法 湖北11选56号 天津市体彩11选5天津开奖结果 安徽快3综合走势图 笨人特码诗 天津快乐十分基本走试图近100期 单关混合过关怎么算赢 安徽安徽福彩快三开结果 江苏快三50期走势 新时时彩360官方网站 win007篮球比分直播