一种基于特征匹配网络的社团划分方法和装置

摘要

本发明实施例涉及数据处理领域，尤其涉及一种基于特征匹配网络的社团划分方法和装置，用于对社团划分。本发明实施例中，根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量；将每个账号信息对应的哈希向量，顺序划分为m＝K/k类子哈希向量；针对每个类，将子哈希向量相同的账号信息划分为同一组；计算同一组内的各账号信息之间的相似度；若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络；根据特征匹配网络，对各账号信息进行社团划分，进而可以根据划分后的社团进行社团分析，发现异常社团。

说明书

技术领域

本发明实施例涉及数据处理领域，尤其涉及一种基于特征匹配网络的社团划分方法和装置。

背景技术

目前，国内信用卡市场面临的风险形势日益严峻，信用卡套现、伪卡欺诈、盗卡欺诈等案件日益增加，具体的，信用卡套现是指持卡人通过虚假消费交易或与商户合谋刷卡后获取现金，之后退款或购买容易变现商品后变卖获取现金等行为、伪卡欺诈是指按照银行卡的磁条信息格式写磁，凸印或平印伪造真实有效的银行卡进行交易的欺诈行为；盗卡欺诈是指欺诈者获得真实持卡人的部分或者全部信息并假冒真实持卡人对账户的信息进行变更以达到欺诈目的的行为。信用卡犯罪手段不断向着高科技、集团化、专业化发展，案件实施过程更为隐蔽，手法不断翻新，这对银行和持卡人的资金安全构成威胁，成为制约信用卡产业长期健康发展的重要因素。

面对各种各样的欺诈手段，现有技术中，通常采用聚类的方法来应对，然而采用这种方法存在多种缺陷，例如，一方面，如果后续对反欺诈模型添加数据，会对反欺诈模型更新数据造成困难，另一方面，经过聚类之后，虽然能将节点划分为若干类，但群体内的结构以及结构之间的关联仍然难以描述。

综上所述，现有技术中存在着如果后续对反欺诈模型添加数据，造成反欺诈模型更新数据困难；经过聚类之后，群体内的结构以及结构之间的关联仍然难以描述的问题，因此，需要采取有效的措施来解决以上问题。

发明内容

本发明实施例提供一种基于特征匹配网络的社团划分方法和装置，用以解决现有技术中存在着如果后续对反欺诈模型添加数据，造成反欺诈模型更新数据困难、经过聚类之后，群体内的结构以及结构之间的关联仍然难以描述的问题。

本发明实施例提供一种基于特征匹配网络的社团划分方法，包括：

根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量；

将每个账号信息对应的哈希向量，顺序划分为m＝K/k类子哈希向量；

针对每个类，将子哈希向量相同的账号信息划分为同一组；

计算同一组内的各账号信息之间的相似度；

若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络；

根据特征匹配网络，对各账号信息进行社团划分。

可选地，计算同一组内的各账号信息之间的相似度，包括：

若第i账号信息与第j账号信息位于n类同组中，则将n/m作为第i帐号信息与第j账号信息之间的相似度；第i账号信息与第j账号信息为各账号信息中的任一个。

可选地，计算同一组内的各账号信息之间的相似度，包括：

若第i账号信息与第j账号信息位于同一组中，统计第i账号信息的哈希向量与第j账号信息的哈希向量中位于同一位且哈希向量值相同的个数h；第i账号信息与第j账号信息为各账号信息中的任一个；

第i账号信息与第j账号信息的相似度s＝h/K。

可选地，根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量，包括：

根据公式(1)确定每个账号信息对应的K位哈希向量

其中，2'b表示是一个二进制数，是预设的K个哈希函数中的一个，

表示账号信息的特征向量，其中，c₁,c₂…,c_d表示账号信息的特征属性，表示随机选取的一个非零向量，

可选地，根据特征匹配网络，对各账号信息进行社团划分，包括：

(1)将各账号信息划分在特征匹配网络中不同的社区中；

(2)根据各账号信息之间的相似度，计算每个账号信息的相似强度，从而生成节点相似强度矩阵；

(3)针对每个账号信息，从节点相似强度矩阵中账号信息所在的行，按相似强度从大到小的的顺序尝试将账号信息划至其他社区中；若账号信息自第p社区划分至第q社区后的模块度差为正数，则将账号信息划分至第q社区后结束；

(4)重复执行，直到社区结构不再改变为止。

可选地，根据各账号之间的相似度，计算每个账号信息的相似强度，包括：

根据公式(2)计算第i账号信息与第j账号信息之间的相似强度s_i,j；

其中，w(z)＝w_ai,z公式(2)

其中，Γ(i)表示第i账号信息的邻居集合，Γ(i)∩Γ(j)表示第i账号信息与第j账号信息的共同邻居集合，w_ai,z为任意账号信息ai与第z账号信息之间的边的权重和。

本发明实施例还提供一种基于特征匹配网络的社团划分装置，包括：

确定单元：用于根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量；

第一划分单元：用于将每个账号信息对应的哈希向量，顺序划分为m＝K/k类子哈希向量；

第二划分单元：用于针对每个类，将子哈希向量相同的账号信息划分为同 一组；

计算单元：用于计算同一组内的各账号信息之间的相似度；

形成网络单元，用于若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络；

第三划分单元：用于根据特征匹配网络，对各账号信息进行社团划分。

可选地，计算单元具体用于：

若第i账号信息与第j账号信息位于n类同组中，则将n/m作为第i帐号信息与第j账号信息之间的相似度；第i账号信息与第j账号信息为各账号信息中的任一个。

可选地，计算单元具体还用于：

若第i账号信息与第j账号信息位于同一组中，统计第i账号信息的哈希向量与第j账号信息的哈希向量中位于同一位且哈希向量值相同的个数h；第i账号信息与第j账号信息为各账号信息中的任一个；

第i账号信息与第j账号信息的相似度s＝h/K。

可选地，确定单元用于：

根据公式(3)确定每个账号信息对应的K位哈希向量

其中，2'b表示是一个二进制数，是预设的K个哈希函数中的一个，

表示账号信息的特征向量，其中，c₁,c₂…,c_d表示账号信息的特征属性，表示随机选取的一个非零向量，

可选地，第三划分单元具体用于：

(1)将各账号信息划分在特征匹配网络中不同的社区中；

(2)根据各账号信息之间的相似度，计算每个账号信息的相似强度，从而生成节点相似强度矩阵；

(3)针对每个账号信息，从节点相似强度矩阵中账号信息所在的行，按相似强度从大到小的的顺序尝试将账号信息划至其他社区中；若账号信息自第p社区划分至第q社区后的模块度差为正数，则将账号信息划分至第q社区后结束；

(4)重复执行，直到社区结构不再改变为止。

可选地，计算单元具体还用于：

根据公式(4)计算第i账号信息与第j账号信息之间的相似强度s_i,j；

其中，w(z)＝w_ai,z公式(4)

其中，Γ(i)表示第i账号信息的邻居集合，Γ(i)∩Γ(j)表示第i账号信息与第j账号信息的共同邻居集合，w_ai,z为任意账号信息ai与第z账号信息之间的边的权重和。

本发明实施例中提供了一种基于特征匹配网络的社团划分方法和装置，根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量；将每个账号信息对应的哈希向量，顺序划分为m＝K/k类子哈希向量；针对每个类，将子哈希向量相同的账号信息划分为同一组；计算同一组内的各账号信息之间的相似度；若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络；根据特征匹配网络，对各账号信息进行社团划分。本发明实施例中首先通过根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量，对于网络中数量巨大的账号信息来说，仅仅产生两个哈希值的哈希函数是不够的，因此确定每个账号信息对应的K位哈希向量能够应对复杂的网络账号信息。然后针对每个类，将子哈希向量相同的账号信息划分为一组，计算同一组内任意账号信息之间的相似度，能够避免针对整个网络中任意账号信息之间计算相似度而带来的计算量非常大的缺点；本发明技术方案能够有效减少账号信息之间相似度的计算量，仅仅计算同一组内的账号信息之间的相似度。最后根据确定各账号信息之间的相似度大于阈值，在各账号信息之间建立互连 边，形成特征匹配网络；根据特征匹配网络，对各账号信息进行社团划分，能够更精准的对各账号信息进行社团划分，这样不仅能够使社团之间的关联关系很清楚，而且能够对划分的社团进行分析，找出异常社团，进而对异常社团内的账号进行异常账号排查，更加有针对性地找出欺诈账号，提高应对欺诈账号的效率。此外，如果需要对划分出的社团添加账号信息，只需要对该添加的账号信息重复以上简单的几个步骤，将所添加的账号信息更新到相应的位置即可，并不会产生更新困难的问题。

附图说明

为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简要介绍。

图1为本发明实施例提供了一种基于特征匹配网络的社团划分方法流程示意图；

图2为本发明实施例提供了本发明的整体思路流程图；

图3为本发明实施例提供的一种基于特征匹配网络的社团划分装置结构示意图。

具体实施方式

为了使本发明的目的、技术方案及有益效果更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

应理解，本发明实施例的技术方案可以应用于各种银行出现的网络欺诈手段的场景，比如可以是信用卡产品的欺诈、银行卡产品的欺诈、盗卡欺诈、伪卡欺诈、套现欺诈等等。本发明实施例的技术方案的应用场景也可以是对异常账号信息社团的发现、发现特定种类欺诈的共性、根据欺诈账号信息样本发现其它欺诈账号信息、帮助发现未知欺诈类型等。

图1示例性示出了本发明实施例提供的一种基于特征匹配网络的社团划分方法流程示意图，如图1所示，包括以下步骤：

步骤S101：根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量；

步骤S102：将每个账号信息对应的哈希向量，顺序划分为m＝K/k类子哈希向量；

步骤S103：针对每个类，将子哈希向量相同的账号信息划分为同一组；

步骤S104：计算同一组内的各账号信息之间的相似度；

步骤S105：若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络；

步骤S106：根据特征匹配网络，对各账号信息进行社团划分。

步骤S101中，根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量，具体来说，经过每个预设的哈希函数的处理都能得到一位哈希向量，那么，根据预设的K个哈希函数，就可以产生K位哈希向量，而每个账号信息对应K位哈希向量，具体实施中，每个账号信息是包含多个特征属性的，如果仅仅使用现有技术中一个账号信息只用一个哈希函数来表示的话，会存在不足以表达一个账号信息的多个特征属性的缺点，所以，本步骤可以有效避免这个缺点。其中，K的取值可以根据具体实施中各账号信息的具体情况来设定，比如，K可以设定为4，那么账号信息就可以表示为一个4位的哈希向量。

步骤S102：将每个账号信息对应的哈希向量，顺序划分为m＝K/k类子哈希向量，具体来说，比如，K＝4，k＝2，那么，就将每个账号信息为4位的哈希向量划分为2类子哈希向量，划分的好处是为后续计算账号间的相似度减少计算量，避免出现像现有技术中并没有对账号信息的哈希向量进行划分而出现直接对所有账号信息中的任意两个账号来进行相似度计算而造成的计算量特别大的缺点。

步骤S103：针对每个类，将子哈希向量相同的账号信息划分为同一组，具 体来说，对每个账号信息划分为各类之后，针对划分的每个类，将子哈希向量相同的账号信息划分为同一组，比如，K＝4，k＝2的话，在第1类中，所有账号信息中4位哈希向量中前两位相同的为一组，同样，在第2类中，所有账号信息中4位哈希向量中后两位相同的账号信息为一组。这样划分的目的也是为了后面减少计算相似度的计算量，只计算各类之间子哈希向量相同的账号信息之间的相似度。

步骤S104：计算同一组内的各账号信息之间的相似度，具体实施中，可以统计同一组内各账号信息的哈希向量的位相同的个数与位的大小的比值，比如，账号信息1的哈希向量为0010，账号信息2的哈希向量为0011，按照K＝4，k＝2，那么两个账号信息在第一类中位于同一组，则确定位于同一组的两个账号信息的相似度；那么，两个账号信息的哈希向量的位相同的个数是3，位的大小是4位的，所以，这两个账号信息之间的相似度为3/4，也可以根据关于相似度的计算公式来计算同一组内的任意两个账号信息之间的相似度，比如相似度的计算公式可以是欧式距离、余弦距离、杰卡德距离公式等。一方面，相比于计算所有账号信息中的任意两个账号信息的相似度，只计算同一组内的任意两个账号信息之间的相似度能够大大减少计算量。比如，取N个账号信息样本，那么N个账号信息样本就被分到了2^k个组内，每个组内的账号信息样本数为N/2^k，每组内进行任意两个账号信息进行相似度计算的次数为2^k个组进行任意两个账号信息进行相似度计算的次数为因此，所有类需要进行相似度计算的次数就为其中，是划分的类的个数，这个值是一个根据实际情况可以进行控制的常数，而传统的方法计算所有账号中任意两个账号信息进行相似度计算需要进行次，综上可以看出，采用本发明的计算同一组内的任意两个账号信息之间的相似度的计算量比传统的方法计算所有账号中任意两个账号信息的相似度的计算量大约缩减2^k级别的>

步骤S105：若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络，具体来说，如果任意两个账号信息之间的相似度大于阈值，就在任意两个账号信息之间建立一条互连边，边的权重就是两个账号信息之间的相似度值，最终形成特征匹配网络。具体实施中，阈值的选取可以选择较高的值没这样最终可以生成较为稀疏的特征匹配网络，便于后续的计算，另外，阈值的取值可以根据实际情况进行调整。

步骤S106：根据特征匹配网络，对各账号信息进行社团划分，具体来说，根据计算出来的各账号信息之间的相似度值，相似度值越接近的越容易被划分到同一个社团中。划分社团之后，对于网络中的欺诈账号更容易去排查，可以计算欺诈账号样本在每个社团中的比例，比例较大的，则该社团为异常社团的可能性就越大，可以根据业务需要进行相关调查，再对异常社团内的账号根据一些指标来进行计算，找出具有代表性的账号，对这些具有代表性的账号再进行相关案件排查，其中，一些指标可以是社团内账号信息的度中心性、紧密中心性、特征向量中心性等；或者也可以对社团内的账号信息进行特征再分析，以期发现该社团的一些共同行为的特征，进行有针对性地欺诈预防。此外，如果新加入的账号信息形成新的社团，则可以根据前面查出来的异常社团进行比对，这对于未知欺诈的侦测与预防是大有裨益的。

计算同一组内的各账号信息之间的相似度，可以以下面两种方法来计算：

方式1：可选地，计算同一组内的各账号信息之间的相似度，包括：若第i账号信息与第j账号信息位于n类同组中，则将n/m作为第i帐号信息与第j账号信息之间的相似度；第i账号信息与第j账号信息为各账号信息中的任一个，具体来说，在所有账号信息中任意取两个账号信息，比如称为账号信息1与账号信息2，m取3，也就是账号信息1与账号信息2分在了3类中，这3类分别称为第1类、第2类、第3类，假设这两个账号信息在第1类与第3类中同组， 那么，这两个账号信息在这3类中的相似度为2/3。

方式2：可选地，计算同一组内的各账号信息之间的相似度，包括：若第i账号信息与第j账号信息位于同一组中，统计第i账号信息的哈希向量与第j账号信息的哈希向量中位于同一位且哈希向量值相同的个数h；第i账号信息与第j账号信息为各账号信息中的任一个；第i账号信息与第j账号信息的相似度s＝h/K，具体来说，如果所有账号信息中任意的两个账号信息，账号信息1与账号信息2位于同一组，并且账号信息1与账号信息2都是4位的，也就是K为4，账号信息1与账号信息2的4位哈希向量中，前3位是完全相同的，第4位不同，那么，账号信息1与账号信息2的相似度s为3/4。

以上两种计算同一组内各个账号信息之间的相似度的计算方法，可以得出，第1中方法是计算的两个账号信息在各个类中的相似度，而第2种方法是计算的被分到了各类中同一组中的两个账号信息之间的相似度，可以看出，这两种方法中，相比于第2种方法，第1种方法是比较粗略的计算两个账号信息所属的类与类之间的相似度，而第2种计算的两个账号信息在同一组之间的相似度则更精准。不过，这两种方法都相比于现有技术中利用欧式距离公式等来计算网络中所有账号信息中任意两个账号信息之间的相似度的计算量上得到了明显的改善，进一步加速了网络的建立。

可选地，根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量，包括：根据公式(1)确定每个账号信息对应的K位哈希向量

其中，2'b表示是一个二进制数，是预设的K个哈希函数中的一个，

表示账号信息的特征向量，其中，c₁,c₂…,c_d表示账号信息的特征属性，表示随机选取的一个非零向量，具体来说，预设的哈希函数是是预设的K个哈希函数中的任一个，哈希函数的 值用0或1来表示，也就是说这样的一个哈希函数只能产生两个哈希值，对于数量巨大的账号信息来说明显是不够的，所以根据这样的哈希函数，来确定每个账号的K位哈希向量是一个K位的二进制数，比如，可以是6位的二进制数，具体可以为010110，那么，其中，表示账号信息的特征向量，c₁,c₂…,c_d表示账号信息的特征属性，具体的账号信息特征属性可以是交易金额、交易时间、交易地点、交易地点数、转账地点、转账金额、转账次数等。其中，各账号信息的特征向量在具体实施中可以经过筛选来得到一批理论上效果最好的特征向量，具体地，在一定时间段内抽取欺诈账号信息样本以及正常账号信息样本，将抽取的欺诈账号信息样本以及正常账号信息样本组合为一个整体账号信息样本，根据业务经验进行整体账号信息的数据预处理、特征筛选及属性相关性分析等步骤之后，筛选出一批理论上效果最好的特征向量。根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量，能够充分提取每个账号信息的特征属性并用特征向量表示出来，能够应对复杂的网络中账号信息数量巨大的情况。此外，需要说明的是，第一，每个账号信息对应的K位哈希向量的确定实际上是经过一个哈希随机映射的过程得来的，是由经过哈希映射得到这里使用哈希随机映射的主要目的是使得使得账号信息的特征向量能映射为0或1的统一表示，以便后续处理，而并非简单的降维；第二，原来的特征向量映射到新的哈希空间中，会使得在原来的特征向量相似的数据在新的哈希空间中数据也相似的概率很大，这个概率为：符合相似度s到概率p的单调递增映射关系。

以上实施方式中，对于每个账号信息对应的K位哈希向量以及将每个账号信息对应的哈希向量顺序划分为m＝K/k类子哈希向量的关系，下面以一个表格的方式将其展示出来，表1示例性地示出了账号信息样本与类之间的关系，如表1所示：

表1：账号信息样本与类之间的关系

表1中，账号信息样本与类之间的关系可以表示成一个K行N列的矩阵，N表示取的账号信息样本数，c₁到c_N代表N个账号信息样本，将N个账号信息样本分到m＝K/k个类，其中，表格中除第一行之外下面的每一行代表一个类，N个账号信息样本被分到了2^k个组内。

可选地，根据特征匹配网络，对各账号信息进行社团划分，包括：

(1)将各账号信息划分在特征匹配网络中不同的社区中；

(2)根据各账号信息之间的相似度，计算每个账号信息的相似强度，从而生成节点相似强度矩阵；

(3)针对每个账号信息，从节点相似强度矩阵中账号信息所在的行，按相似强度从大到小的的顺序尝试将账号信息划至其他社区中；若账号信息自第p 社区划分至第q社区后的模块度差为正数，则将账号信息划分至第q社区后结束；

(4)重复执行，直到社区结构不再改变为止。

可选地，根据各账号之间的相似度，计算每个账号信息的相似强度，包括：

根据公式(2)计算第i账号信息与第j账号信息之间的相似强度s_i,j；

其中，w(z)＝w_ai,z公式(2)

其中，Γ(i)表示第i账号信息的邻居集合，Γ(i)∩Γ(j)表示第i账号信息与第j账号信息的共同邻居集合，w_ai,z为任意账号信息ai与第z账号信息之间的边的权重和。

具体实施中，第(1)步骤，初始化特征匹配网络，将每个账号信息划分到不同的社区中，这一步骤中的划分可以是随机划分的；第(2)步骤，根据公式(2)来计算各账号信息的相似强度，具体地，假如账号信息1与账号信息2的共同邻居是账号信息3，账号信息1与账号信息2合起来与账号信息3的边的权重是5，那么，任意账号信息ai与账号信息3相连边的权重为5，因而，账号信息1与账号信息2的相似强度是1/5，类似的，其它账号信息之间也是用此方法来计算。假如，取4个账号信息样本，经过计算之后，形成一个4*4的矩阵，假如，这个矩阵为从这个矩阵可以看出，账号信息1与账号信息2的相似度为0.25，账号信息1与账号信息3的相似度为0.7，账号信息2与账号信息3的相似度为0.4；第(3)步骤，从这个相似强度矩阵中账号信息所在的行，按相似强度从大到小的的顺序尝试将账号信息划至其他社区中，例如从这个相似矩阵第一行可以看出，想要把账号信息1划分到其它某一社团中时，优先选择相似度较大的账号信息3(第一行中0.6最大)所在的社区中去。如果△Q<0，再将账号信息1尝试划分到账号信息4(第一行中0.4次大)所在 的社团中去。如果△Q<0，则再将账号信息1尝试划分到账号信息2所在的社团中去。如果仍然△Q<0，则账号信息1作为一个独立的社团进行保留，矩阵不做更新，再进行第2行的计算。如果上述尝试过程中只要发现△Q>0,比如优先尝试的将账号1划分到相似度较大的账号信息3(第一行中0.6最大)所在的社区中去以后，发现△Q>0，那么表示尝试成功，第一行计算结束。由于此时账号1的状态已经发生改变，因此将矩阵中第一行第一列所有数据删除，表示后续账号信息不再与账号信息1进行比较，也就是，变成 然后以同样的过程开始新一轮的尝试计算，即对账号信息2进行社团划分。其中，模块度差△Q的计算公式： 来验证上面对账号信息的尝试划分社区是否正确，其中，n表示网络中所有的权重，k_i表示与顶点i连接的边的权重，k_i,in表示账号信息i在社区内部的权重之和，Σ_in表示社区内部的边权重和，Σ_tot表示与社区内部账号信息连接的边的权重和，包括社区内部的边以及社区外部的边，若△Q为正数，则接受本次的划分，若不为正数，则放弃本次的划分。通过账号信息的相似强度矩阵的计算，优先将账号信息划分到与其最相似的邻居账号信息的社团中去，大大节省了社团划分的尝试次数，进一步提高了算法的速度，另外，对账号信息尝试的划分是否合理通过模块度差公式来验证，更加有效保证了尝试划分的合理性与准确性。

为了更好的理解本发明技术方案，图2示例性地示出了本发明的整体思路流程图，如图2所示：

步骤S201：将各账号信息的特征属性通过哈希映射的方法映射为一个多位的哈希映射向量；

步骤S202：将各账号信息的哈希映射向量进行分类；

步骤S203：对于每个类，将哈希映射向量相同的账号信息划分为一组；

步骤S204：对每组中的任意两个账号信息进行相似度计算；

步骤S205：若每组中的任意两个账号信息的相似度大于阈值，则建立这两个账号信息之间的互连边，边的权重为相似度，从而形成特征匹配网络，其中，形成的特征匹配网络是稀疏的特征匹配网络；

步骤S206：根据特征匹配网络中各账号信息的相似强度矩阵对特征匹配网络进行社团划分。

与现有技术相比，本发明实施例中，第一，通过随机哈希映射的方法将各账号信息的特征属性映射到一个新的哈希空间中，形成各账号信息的哈希映射向量，对各账号信息的哈希映射向量进行分类，能够在高相似度的账号信息之间建立边，有效避免了大量的任意两个账号信息之间的相似度计算，且高效地为每条边建立了可信的权重值，能够提高后续社团划分的精度与速度；第二，根据各账号信息的相似度建立了特征匹配网络，然后根据网络中各账号信息的相似强度矩阵对特征匹配网络进行社团划分，不仅可以有效发现异常社团并进行有针对性地措施，同时可以侦测未知的欺诈类型，而且通过相似强度矩阵对对特征匹配网络进行社团划分，即优先将账号信息划分到与其最相似的邻居账号信息的社团中去，大大节省了社团划分尝试的次数，进一步提高了算法的速度；第三，通过形成特征匹配网络，相关账号信息间的相似度作为边的权重被永久存储，即使有较多的新的账号信息进来，也不会对网络中原来的互连边产生影响，仅仅需要将新的账号信息插入到原特征匹配网络中。在向原特征匹配网络图添加新数账号信息的时候，仍然先采用随机哈希映射方法及对各账号信息进行分类，然后与类内的账号信息进行相似度计算，如果该相似度大于阈值，则添加新的边。后续只需要进行计算量较小但是更加精准的社团划分算法即可实现功能。同时，特征匹配网络的结构能更加清晰地展示社团内部及社团间的关联结构，这是传统聚类方法所不能实现的。

基于相同构思，本发明实施例提供的一种基于特征匹配网络的社团划分装置，如图3所示，该装置包括确定单元301、第一划分单元302、第二划分单元303、计算单元304、形成网络单元305和第三划分单元306。其中：

确定单元301：用于根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量；

第一划分单元302：用于将每个账号信息对应的哈希向量，顺序划分为m＝K/k类子哈希向量；

第二划分单元303：用于针对每个类，将子哈希向量相同的账号信息划分为同一组；

计算单元304：用于计算同一组内的各账号信息之间的相似度；

形成网络单元305：用于若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络；

第三划分单元306：用于根据特征匹配网络，对各账号信息进行社团划分。

可选地，计算单元304具体用于：

若第i账号信息与第j账号信息位于n类同组中，则将n/m作为第i帐号信息与第j账号信息之间的相似度；第i账号信息与第j账号信息为各账号信息中的任一个。

可选地，计算单元304具体还用于：

若第i账号信息与第j账号信息位于同一组中，统计第i账号信息的哈希向量与第j账号信息的哈希向量中位于同一位且哈希向量值相同的个数h；第i账号信息与第j账号信息为各账号信息中的任一个；

第i账号信息与第j账号信息的相似度s＝h/K。

可选地，确定单元301用于：

根据公式(3)确定每个账号信息对应的K位哈希向量

其中，2'b表示是一个二进制数，是预设的K个哈希函数中的一个，

表示账号信息的特征向量，其中，c₁,c₂…,c_d表示账号信息的特征属性，表示随机选取的一个非零向量，

可选地，第三划分单元306具体用于：

(1)将各账号信息划分在特征匹配网络中不同的社区中；

(2)根据各账号信息之间的相似度，计算每个账号信息的相似强度，从而生成节点相似强度矩阵；

(3)针对每个账号信息，从节点相似强度矩阵中账号信息所在的行，按相似强度从大到小的的顺序尝试将账号信息划至其他社区中；若账号信息自第p社区划分至第q社区后的模块度差为正数，则将账号信息划分至第q社区后结束；

(4)重复执行，直到社区结构不再改变为止。

可选地，计算单元304具体还用于：

根据公式(4)计算第i账号信息与第j账号信息之间的相似强度s_i,j；

其中，w(z)＝w_ai,z公式(4)

其中，Γ(i)表示第i账号信息的邻居集合，Γ(i)∩Γ(j)表示第i账号信息与第j账号信息的共同邻居集合，w_ai,z为任意账号信息ai与第z账号信息之间的边的权重和。

从上述内容可看出：本发明实施例中提供一种基于特征匹配网络的社团划分装置，根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量；将每个账号信息对应的哈希向量，顺序划分为类子哈希向量；针对每个类，将子哈希向量相同的账号信息划分为同一组；计算同一组内的各账号信息之间的相似度；若各账号信息之间的相似度大于阈值，则在各账号信息之间建立互连边，形成特征匹配网络；根据特征匹配网络，对各账号信息进行社团划分根据 各账号信息之间的相似度，对各账号信息进行社团划分。本发明实施例中首先通过根据预设的K个哈希函数，确定每个账号信息对应的K位哈希向量，对于网络中数量巨大的账号信息来说，仅仅产生两个哈希值的哈希函数是不够的，因此确定每个账号信息对应的K位哈希向量能够应对复杂的网络账号信息。然后针对每个类，将子哈希向量相同的账号信息划分为一组，计算同一组内任意账号信息之间的相似度，能够避免针对整个网络中任意账号信息之间计算相似度而带来的计算量非常大的缺点；本发明技术方案能够有效减少账号信息之间相似度的计算量，仅仅计算同一组内的账号信息之间的相似度。最后根据确定各账号信息之间的相似度大于阈值，在各账号信息之间建立互连边，形成特征匹配网络；根据特征匹配网络，对各账号信息进行社团划分，能够更精准的对各账号信息进行社团划分，这样不仅能够使社团之间的关联关系很清楚，而且能够对划分的社团进行分析，找出异常社团，进而对异常社团内的账号进行异常账号排查，更加有针对性地找出欺诈账号，提高应对欺诈账号的效率。此外，如果需要对划分出的社团添加账号信息，只需要对该添加的账号信息重复以上简单的几个步骤，将所添加的账号信息更新到相应的位置即可，并不会产生更新困难的问题。

本领域内的技术人员应明白，本发明的实施例可提供为方法、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机 或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。