FRAUDARCatchSync算法简介
参考:https://blog.51cto.com/u_15127663/2778705
1. 背景
Fraudar 要解决的问题是:找出社交网络中最善于伪装的虚假用户簇。虚假用户会通过增加和正常用户的联系来进行伪装,而这些伪装(边)会形成一个很密集的子网络,可以通过定义一个全局度量,再移除二部图结构中的边,使得剩余网络结构对应的度量值最大,找到最紧密的子网络,即最可疑的作弊团伙。
1. 建立优先树(一种用于快速移除图结构的边的树结构);
2. 对于二部图中的任意节点,贪心的移除优先级最高的节点,直至整个网络结构为空;
3. 比较上述每一步得到的子网络对应的全局度量,取该值为最大的子网络(最密集的子网络),即最可疑的团伙。
2. 可疑程度度量
最关键的地方是定义一个描述可疑程度的度量,要求其有如下性质:
1. 可扩展性;
2. 具备理论上的“界”;
3. 对抗虚假行为的鲁棒性。
特别地,该度量可以理解成子网络中每个节点的平均可疑程度。令 代表用户节点的子集,
代表目标节点的子集,那么
,而
,
那么可疑程度的度量被定义为:。
其中: 表示S 中节点本身的可疑程度之和,
表示 S 中节点之间边的可疑程度之和,整个公式表示点和边的总可疑程度。可以得出4条性质:
1. 如果其他条件不变,包含更高可疑度节点的子网络比包含较低可疑度节点的子网络更可疑;
2. 如果其他条件不变,在子网络中增加可疑的边会使得子网络更可疑;
3. 如果节点和边的可疑程度不变,那么大的子网络比小的子网络更可疑;
4. 如果节点和边的总可疑程度相同,那么包含节点数少的子网络更可疑。
该算法的核心是:贪心地移除图中的点,使得每次变更f 的变化最大。在移除一个节点时,只有与之相邻的节点会发生变化,那么这样最多产生O(|E|)次变更,如果找到合适的数据结构使得访问节点的时间复杂度为O(log|V|),那么算法总的时间复杂度就是O(NlogN)。基于这样的考虑建立优先树(二叉树),图中的每个节点都是树的一个叶子节点,其父节点为子节点中优先级较高的节点。这棵树建完之后就可以按照O(log|V|)的速度获得优先级最高的节点。
3. 如何识别虚假行为?
可通过列权重下降的方法来实现。不能简单的将每条边的嫌疑程度设为相等,因为出度和入度大的节点,可能真的就是很受欢迎的节点。
如大V用户和销量不错的商品,这些节点都是天然存在的,并不是虚假的。如果每条边的嫌疑程度相等的话,那么在最大化可疑程度的度量时,就会聚焦于这些出度和入度较大的点,而不是聚焦于紧密的子网络。所以如果存在节点i 到一个出度和入度较大的节点j 的边,就需要将其边对应的嫌疑程度降低,这就是列权重下降法。
该方法不仅关注出度和入度较大的节点,而且更关注紧密的子网络。eg: 在邻接矩阵中,令行代表用户节点,列代表目标节点,那么虚假用户向正常的目标节点增加边并不会使得子网络的嫌疑程度变低。因为虚假用户向正常的目标增加边只会使正常目标对应的嫌疑程度下降,而嫌疑子网络内的权重却不会发生变化。实验表明,列权重下降函数选择类似TF-IDF形式的函数时,算法表现会比较好。
4. 算法优缺点
1. 优点
1. 采用了“贪心”的计算思想,运行速度很快;
2. 原理清晰明了,且能够给出理论上的“界”;
3. 能够识别虚假行为。
2. 缺点:
1. 因采用贪心算法,所以不能保证得到全局最优解;
2. 原始算法只能找出一个最紧密的子网络,即可以程度最大的子网络;
3. 只考虑了边的权重,没有考虑节点的权重(或节点的权重都设为相等的常数),且节点和边的嫌疑程度需要自定义。
5. 应用
5.1 一个改进:循环Fraudar 算法
在网络结构中找出最可疑的子网络后,移除子网络中所有相关的边,再使用Fraudar 算法对剩余的图结构进行挖掘,找出次可疑的子网络。最终得到可疑程度由高到低排列的多个子网络。
5.2 识别虚假社交关系
在社交平台和电商网络中,用户与用户或用户与商品之间会形成巨大的有向网络。而由于虚假行为的存在,这个有向网络中被注入了异常的行为模式。如:
Twitter、Facebook、微博等社交平台中会有虚假的关注、转发等;
而Amazon、淘宝等电商平台中会有误导性评论、虚假交易等。
在这些静态的有向网络中,可疑的异常行为会形成一个紧密的子网络(可通过Fraudar 算法贪心找到)。
6. CatchSync 算法
利用了两个容易被欺诈者忽视的特点,一个是同步行为特性,另一个是稀有行为特性。大多数情况下,异常的行为模式往往是稀少而集中的,可以设计算法来捕捉它们,CatchSync正是基于同步行为特性和稀有行为特性来找到有向网络中的异常行为模式的。
6.1 原理
是基于图的性质提出的异常识别算法,在有向图结构中,可以利用很多性质,如:
1. 基本的出度和入度;
2. HITS(Hyperlink-InducedTopic Search) 得分;
3. 中介中心性(betweenness centrality);
4. 节点的入权重和出权重;
5. 节点对应的左右奇异值向量的第i 个元素值。
CatchSync 算法利用了HITS得分中的权威度和入度,将其作为基本的特征。并基于此提出了两个新概念来研究源节点的特性:
1. synchronicity(同步性|一致性): 用于描述源节点u 的目标节点在特征空间中的同步性;
2. normality(正常性):用于描述源节点u 的目标节点的正常性。
在CatchSync 算法中用c(V,V*)来表示特征空间InF-plot中源节点的目标节点间的临近性(相似性)。为了快速计算,该算法将特征空间划分成G个网格,并将原有向图中的节点映射到每个网络中。有了这个网络之后,c(V,V*)的计算就非常容易了,如果两个节点在同一个网络中,那么临近性为1,否则为0。
通过synchronicity和normality就可以刻画出特征空间SN-plot,进而基于正态分布找出异常节点(高同步性和低正常性的节点)。为了评估直播业务中是否存在主播删粉丝关注量的情况,对现有直播业务中的关注关系应用CatchSync 算法进行挖掘,得到全站直播业务中关注关系的SN-plot 和 InF-plot,如图:
可以看出:直播业务的关注关系中存在一定的高同步性和低正常性的节点,这些节点很大程度上是可疑的。利用CatchSync提取异常节点后,人工验证,确实有问题。
7. 总结
基于图的挖掘算法上线以来,识别团伙作弊在风控中的作用越来越显著,为打击黑灰产提供了充分的技术支撑,且建立起一套较完备的风险分析技术体系,包含了主流的ML技术:统计ML方法、DL方法和基于图的挖掘算法。同时,还搭建了平台化的风控系统,把ML和人工运营有效结合起来,不仅利用有标签的数据持续提高识别能力,还干预和控制了各种风险。在和黑灰产持续对抗的道路上,需要不断优化和提升风控技术手段,以应对未来充满挑战的业务安全生态环境。
相关文章:

FRAUDARCatchSync算法简介
参考:https://blog.51cto.com/u_15127663/2778705 1. 背景 Fraudar 要解决的问题是:找出社交网络中最善于伪装的虚假用户簇。虚假用户会通过增加和正常用户的联系来进行伪装,而这些伪装(边)会形成一个很密集的子网络,可以通过定义…...

刷题之将有序数组转换成二叉搜索树(leetcode)
将有序数组转换成二叉搜索树 正常递归,中序遍历 递归经常会把自己绕晕,还是得画图分析 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(null…...
K-means聚类模型教程(个人总结版)
K-means聚类是一种广泛应用于数据挖掘和数据分析的无监督学习算法。它通过将数据点分成K个簇(cluster),使得同一簇内的数据点之间的相似度最大,不同簇之间的相似度最小。本文将详细介绍K-means聚类算法的背景、基本原理、具体实现…...
android怎么告诉系统不要回收
在Android中,如果你想告诉系统不要回收你的应用程序,可以通过设置Activity的属性来实现。你可以设置android:configChanges属性,指定在哪些配置更改时不重新创建Activity。 例如,如果你想指示系统在屏幕方向更改时不要重新创建Ac…...
【FAQ】HarmonyOS SDK 闭源开放能力 —IAP Kit(2)
1.问题描述: 应用内支付IAP Kit和Payment Kit的区别以及适用场景? 解决方案: IAP Kit是四方支付,仅支持在线虚拟商品,如会员,游戏钻石等,双框架支持全球,目前单框架暂时只支持国内…...

ubuntu设置root开机登录,允许root用户ssh远程登录
ubuntu与centos系统不同,默认root开机不能登录。 1、输入一下命令创建root密码,根据提示输入新密码 sudo passwd root 2、打开gdm-autologin文件,将auth required pam_succeed_if.so user ! root quiet_success这行注释掉,这行就…...
Web测试面试题(二)
一:简述HTTP协议的状态码包含哪些? 2XX,表示成功 3XX,表示重定向 4XX,表示客户端错误 5XX,表示服务器错误 二:HTTP和HTTPS的区别? 《1》安全性上的区别: HTTPS&#x…...
VBA宏指令写的方法突然不能用了
背景:项目组有个自动化测试项目,实在excel中利用VBA开发的;时间比较久远,我前面的哥们走后,这个软件一直在用,最近系统不知道是不是更新的缘故;有些代码除了问题; 先上源码: Dim Conn As Object, Rst As Object Dim sqlStr$ Dim str_start_SN$, str2$ str_start_SN …...
第13章 Python建模库介绍
以下内容参考自https://github.com/iamseancheney/python_for_data_analysis_2nd_chinese_version/blob/master/%E7%AC%AC05%E7%AB%A0%20pandas%E5%85%A5%E9%97%A8.md 《利用Python进行数据分析第2版》 用以学习和记录。 本书中,我已经介绍了Python数据分析的编程基…...

IP学习——ospf1
OSPF:开放式最短路径优先协议 无类别IGP协议:链路状态型。基于 LSA收敛,故更新量较大,为在中大型网络正常工作,需要进行结构化的部署---区域划分、ip地址规划 支持等开销负载均衡 组播更新 ---224.0.0.5 224.0.0.6 …...

别说废话!说话说到点上,项目高效沟通的底层逻辑揭秘
假设你下周要在领导和同事面前汇报项目进度,你会怎么做?很多人可能会去网上搜一个项目介绍模板,然后按照模板来填充内容。最后,汇报幻灯片做了 80 页,自己觉得非常充实,但是却被领导痛批了一顿。 这样的境…...
前后端编程语言和运行环境的理解
我已重新检查了我的回答,并确保信息的准确性。以下是常用的编程语言,以及它们通常用于前端或后端开发,以及相应的框架和运行环境: 前端开发 JavaScript 框架:React, Angular, Vue.js, Ember.js, Backbone.js运行环境:Web 浏览器HTML (HyperText Markup Language) 不是编…...

一顿五元钱的午餐
在郑州喧嚣的城市一隅,藏着一段鲜为人知的真实的故事。 故事的主角是一位年过半百的父亲,一位平凡而又伟大的劳动者。岁月在他脸上刻下了深深的痕迹,但他眼神中闪烁着不屈与坚韧。 他今年52岁,为了给远在家乡的孩子们一个更好的…...
【前端每日基础】day60——TDK三大标签及SEO引擎优化
TDK 是指 Title(标题)、Description(描述)、Keywords(关键词)这三个网页的重要元信息标签,对于 SEO(搜索引擎优化)至关重要。下面是它们的作用和 SEO 优化建议࿱…...

vscode添加代办相关插件,提高开发效率
这里写目录标题 前言插件添加添加TODO Highlight安装TODO Highlight在项目中自定义需要高亮显示的关键字 TODO Tree安装TODO Tree插件 单行注释快捷键 前言 在前端开发中,我们经常会遇到一些未完成、有问题或需要修复的部分,但又暂时未完成或未确定如何处…...

JS对象超细
目录 一、对象是什么 1.对象声明语法 2.对象有属性和方法组成 二、对象的使用 1.对象的使用 (1)查 (2)改 (3)增 (4)删(了解) (5…...

远程PLC、工控设备异地调试,贝锐蒲公英异地组网方案简单高效
北京宇东宁科技有限公司专门提供非标机电设备,能够用于金属制品的加工制造。设备主要采用西门子的PLC作为控制系统,同时能够连接上位机用于产量、温度、压力、电机运行数据的监控,以及工厂的大屏呈现需求。目前,客户主要是市场上的…...
【算法】梦破碎之地---三数之和
相信大家都有做过两数之和, 题目链接: 15. 三数之和 - 力扣(LeetCode) 在文章的开始让我们回顾一下三数之和吧! 题目描述: 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], …...
c语言如何将一个文本内容复制到另外一个文本里
c语言如果要把一个文本文件的文件复制到另外一个文件里,代码如下 #include<stdio.h>int main() {FILE *fp1,*fp2;char a;fp1fopen("D://cyy//aaa.txt","r");fp2fopen("ccc.cpu","w");while(a!EOF){afgetc(fp1);fput…...

JavaScript基础(九)
冒泡排序 用例子比较好理解: var arry[7,2,6,3,4,1,8]; //拿出第一位数7和后面依次比较,遇到大的8就换位,8再与后面依次比较,没有能和8换位的数,再从下一位2依次与下面的数比较。 console.log(排列之前:arry); for (…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...