一种基于图数据库的虚拟身份关系挖掘算法

尹玉娇 张伟

摘要：基于虚拟身份的关系挖掘是关系挖掘的重要途径，但虚拟身份存在一定的不真实性。鉴于此，将虚拟身份一一映射到真实身份，再针对真实身份进行关系挖掘，并采用图数据库存储强关联的关系数据。该关系挖掘算法包括3部分：首先基于公共场所卡口设备和审计设备采集到的日志数据，抽取手机终端MAC、卡口设备MAC及微信构建虚拟身份库，将虚拟身份微信反向映射到真实身份手机终端MAC：然后找出单节点手机终端MAC在某段时间内的同行人作为一个关系团体，或者直接找出虚拟身份库中微信对应映射到的手机终端MAC最大度数节点作为核心节点;再利用同行人分析算法找出该节点在某段时间内的同行节点作为一个关系团体。研究结果表明，相比单纯基于虚拟身份的关系挖掘，基于图数据库的虚拟身份关系挖掘算法准确率可提高至100%。

关键词：社交网络;图数据库;虚拟身份;关系挖掘

DOI： 10. 11907/rjdk.191322

开放科学（资源服务）标识码（OSID）：

中图分类号：TP312

文献标识码：A

文章编号：1672-7800（ 2020） 001-0117-06

0 引言

自沃尔玛公司“啤酒和尿布”的潜在关联关系被挖掘出来后，关联规则挖掘逐渐进入人们的视野并受到关注。关联规则起源于购物篮的物品搭配问题，最终目的是获得事务集中各属性间的关联关系，获得可信的强关联规则，并应用这些规则服务于人类，如商店中物品的放置位置、电子商务中用户的购物行为。

Agrawal等[1]最先提出关联规则的概念，同时给出了相应的挖掘算法AIS，但其性能较差;随后建立了项目集格空间理论，并依据上述两个定理，提出了著名的Apriori算法，之后大部分学者基于经典Apriori算法进行算法改进研究。2015年邵文爽[2]针对传统Apriori算法执行效率低、1/0负载大、算法冗余等缺陷提出了两种改进算法，第一种优化是基于逻辑位运算，第二种优化是基于哈希表;崔妍等[3]提出了基于散列技术、基于划分、基于采样、FP增长等串行算法以及并行分布式算法，其中并行是基于多处理器进行的。

随着数据量的增长，传统关联规则挖掘算法已经不能满足大数据时代的生产和生活需要，于是出现了分布式、并行的关联规则挖掘算法。MapReduce是一种流行的分布式并行计算模型，因其使用简单、伸缩性好、自动负载均衡和自动容错等优点，得到了广泛应用，由此出现了基于Ma-pReduce的并行关联规则挖掘算法。基于MapReduce的并行关联规则挖掘算法主要基于磁盘访问，降低了计算性能。随着加州大学伯克利分校AMLab实验室研发的用于大型数据快速处理的并行计算框架被提出，基于Spark的关联规则挖掘逐渐受到人们的广泛关注。

不论是传统的关联规则挖掘算法，改进的关联规则挖掘算法，还是分布式的基于MapReduce和Spark的关联规则挖掘算法，都是在传统关联规则挖掘算法Apriori.FP-growth、Eclat基础上提出的，其实质仍然是两个事物之间关联关系的挖掘。

在关联规则分析基础上出现了关系挖掘。关系挖掘算法更加实用，有基于机器学习的方法和统计的方法，关系挖掘的范畴包括两个事物之间的关联关系和多个事物之间的关联关系。姜丽莉[4]对传统关联规则挖掘算法进行了优化，算法借鉴元组ID传播思想，对关系图进行切分，对每一部分建立全局键值映射哈希表，通过哈希表，将表单挖掘出的项集进行连接，从而得到多关系间的频繁项集。

随着社交媒体的不断普及，人们更多地在虚拟网络中进行沟通和交流，出现了大量通过社交软件进行注册的账号信息。基于虚拟身份的关系挖掘为社交关系挖掘提供了新的助力，通过识别多个属于同一个现实用户的所有虚拟身份信息，并将其合并到一起，最终生成一个虚拟身份库。随着网络技术的快速发展，用于隐藏网络用户身份的技术手段和方法越来越多且更新速度较快，造成用户身份识别特别困难[5]。基于数据挖掘的虚拟身份识别方法可以解决在线网站的身份识别问题。

目前，大部分虚拟身份关系挖掘是将虚拟身份对应转换成现实世界中的真实身份。根据涉及领域不同，对应转换成的对象也不同，而且大部分虚拟身份关系挖掘算法仍停留在理论阶段。本文从公安部门构建虚拟身份库的实际需求出发，提出了一种基于图数据库的虚拟身份关系挖掘算法G VIRM（A Virtual Identity Relation Mining AlgorithmBased on Craph Database）。该关系挖掘算法利用具有强实用性的同行人分析算法挖掘虚拟身份之间的关联关系，并针对虚拟身份的不真实性，将虚拟身份一一映射到真实身份，然后针对真实身份进行关系挖掘。

1 相关工作

在关系挖掘之前最早出现的是关联规则挖掘，关联规则挖掘最初研究的是单纯两个事物之间的关联关系，由于单纯的关联规则算法存在缺陷，便出现了关联规则算法的优化算法。随着大数据时代的到来，传统关联规则计算模式已经不能满足大规模数据处理需求，于是出现了分布式大数据平台，如Hadoop和Spark。目前，基于MapReduce计算模型的并行关联规则挖掘算法大多是将Apriori、FP-Crowth和Eclat 3种经典算法向MapReduce计算模型迁移，实现并行计算。基本思路是：利用hadoop作为运行平台，利用Hadoop的分布式文件系统HDFS进行大数据集的分布式存储，将算法的输入和输出改造成MapReduce计算模型要求的<键，值>，将算法运行改造成map和re-duce两个阶段[6]。MapReduce是一种基于磁盘的分布式并行计算模型，但存在抽象层次低、仅支持Map和Reduce两种操作、处理效率低、不适合迭代运算等缺点，而Spark是基于内存进行计算，克服了MapReduce的诸多缺点，具有抽象层次更高、效率更高、有迭代处理和内存计算的特性。OIU H[7]等在2014年提出了一种经典的基于SparkRDD计算模型的并行Apriori算法;FANC X[8]等在2016年提出了一种基于Spark的改进FP-growth并行算法IP-FP-growth，实现了将改进的PFP-growth算法移植到Spark計算模型上进行分布式计算。Apriori算法和FP-growth算法处理的事务数据格式是水平格式，而Eclat算法不一样，是垂直格式。冯兴杰等[9]提出一种基于Spark的并行Eclat算法即SPEclat，通过改变数据存储格式，将数据按前缀进行分组划分到不同的计算节点，压缩数据的搜索空间，实现并行化计算。

本文虚拟身份库是面向公安应用而构建，如图1所示。基于公共场所的卡口设备和审计设备采集日志数据，抽取卡口设备MAC、手机终端MAC、虚拟账号微信等实体，以及卡口设备MAC和手机终端MAC、手机终端MAC和微信的关联关系，利用图数据库进行实体和关系的存储。

2.2 虚拟身份到真实身份的映射

要想准确识别虚拟身份或者定位虚拟身份团体，需要将虚拟身份定位到真实身份，其难度随着虚拟身份种类的复杂性而增加。本文虚拟身份微信与手机终端MAC直接绑定，因此直接将微信账号定位到手机终端MAC，这种情况下的转换是一对一的，如图2所示。

2.3 虚拟身份关系挖掘算法设计

将微信虚拟身份映射到手机终端MAC这一真实身份后，再基于手机终端MAC进行关系挖掘。一种情况是基于特定的某个手机终端MAC进行同行人分析，得到关系团体1;另一种情况是首先挖掘出虚拟身份库中微信虚拟身份对应映射的手机终端MAC度数最大的节点作为核心节点，然后基于已经挖掘出来的核心节点，利用同行人分析算法找出其在某段时间内的同行人作为一个关系团体，得到关系团体2。虚拟身份关系挖掘算法设计如图3所示。

同行人分析算法如图4所示。其中，圆圈节点是核心节点，图中总共出现了5个轨迹点，然后在每个轨迹点找出某段时间同出现的其它节点，如图4中的菱形和长方形，其中长方形节点是在5个轨迹点都出现过的节点，即核心节点的关系团体。

2.4 算法描述及伪代码实现

2.4.1 虚拟身份库构建

输入：从卡口设备和审计设备采集到的日志数据中抽取出卡口设备MAC、手机终端MAC、微信账号实体，卡口设备MAC和手机终端MAC的关联次数，手机终端MAC和微信账号的关联次数。

输出：基于卡口设备MAC、手机终端MAC、微信账号及其之间的关联次数形成的虚拟身份库。

算法：

Stepl：首先从数据库中抽取出实体节点;

Step2：导入实体节点到图数据库;

Step3：导入实体节点之间的边到图数据库;

Step4：判断实体节点之间的边是否出现过，如果出现过累积边的权值加1。

其中创建节点和边的伪代码如下：

Node（“label"， name， real_name， stype）

Relationship（ nodel，“label”.node2， name， stype）

2.4.2 核心节点挖掘

输入：由卡口设备MAC、手机终端MAC、微信及其之间的关联次数形成的虚拟身份库。

输出：虚拟身份库中微信对应映射的手机终端MAC度数最大的节点。

算法：

Stepl：设置初始微信对应映射的手机终端MAC度数最大节点的度为0;

Step2：搜索出虚拟身份库中的所有节点;

Step3：判断节点是否是手机终端MAC节点，如果是则记录下该节点的度数，并搜索出该节点的所有孩子节点。判断孩子节点是否是微信账号，如果是则节点的度数减1，并与初始微信对应映射的度数最大的手机终端MAC节点相比较，取两者中最大的作为当前手机终端MAC度数最大的节点;

Step4：不断循环判断其余所有手机终端MAC节点，保留最终手机终端MAC节点度数最大的作为核心节点。

核心节点挖掘伪代码如下：

max_degree=0

real_name=null

flag=0

for nodel in nodes：

if nodel.label==mac：

flag=0

degree=graph.degree（ nodel）

for node2 in nodel.child：

if node2.label==wechat：

degree=degree-l

flag=l

if（ flag==l°ree>max_degree）：

max_degree=degree

real_name=nodel

2.4.3 關系团体挖掘

输入：虚拟身份库中的核心节点或者特定的虚拟身份映射后的手机终端MAC节点，统称为节点A，以及特定的某段时间内卡口设备采集到的日志数据。

输出：特定某段时间内节点A的关系团体。

算法：

Step1：搜索出特定某段时间内卡口设备采集到的日志数据;

Step2：按时间顺序将日志数据进行排序;

Step3：找出节点A在该段时间内的轨迹，也即出现过的场所;

Step4：在每个轨迹点找出与节点A同出现的其它节点;

Step5：所有轨迹点做交集得出核心节点的关系团体。

按照时间先后顺序搜索出节点A的轨迹，其中status是场所状态，为1表示该场所在线，伪代码如下：

track={}

for line in lines：

if（ status==l）：

track[ netbar]={}

track[netbar][‘equipment_longitude] =longitude

track[ netbar][‘equipment_latitude] =latitude

搜索每个轨迹点同出现的其它节点伪代码如下：

for netbar in netbars：

select distinct （mobile_mac） from table where net-bar_wacode=netbar

所有轨迹点做交集得出核心节点的关系团体伪代码如下所示，其中count是轨迹点的总数：

for i in range（ count）：

if（i_=0）：

continue

listl=colle[i]

list2=colle[i-l]

ans=list（ set（ listl） .intersection（ list2））

3 实验与分析

3.1 实验平台及数据

本实验平台CPU 4核，内存8G，操作系统采用CentosMinial版，数据库采用单机版Greenplum和图数据库Ne04j。实验数据采用某市150 000条卡口设备日志数据和5 000条审计日志数据。

3.2 实验结果

基于卡口设备MAC、手机终端MAC、微信及其关联次数构建的虚拟身份库如图5所示。

虚拟身份到真实身份映射后，虚拟身份库中核心节点和特定某个微信映射的手机终端MAC节点MAC值、度数、某段时间内的轨迹、关系团体总数如表1所示。

3.3 结果分析

实验结果表明，由卡口设备MAC、手机终端MAC，微信等形成的网络具有群聚现象，大部分节点会聚集在一个地方，不松散，这种现象由人类居住特点和人口密度决定。通过将虚拟身份映射到真实身份，增加了虚拟身份关系挖掘的准确性。随着数据量的累积，核心节点的度数维持在66左右。在数据量达不到一定规模时，核心节点出现的场所过少，同行人节点过多。微信等虚拟身份对应映射到真实身份手机终端MAC节点后，特定的某个手机终端MAC节点或者核心节点轨迹非空，同行节点非空。本文同行人分析算法充分利用了时间和空间属性，具有较强实用性。

4 结语

本文基于图数据库的虚拟身份关系挖掘算法通过将微信等虚拟身份映射为手机终端MAC等真实身份，进而将虚拟身份的关系挖掘问题转换为真实身份的关系挖掘问题，提高了虚拟身份关系挖掘的準确性。并且，本文关系挖掘算法充分利用了时间和空间属性，具有较强的实用性，能够解决基于微信等虚拟身份的关系团体挖掘问题。后续研究可针对更为复杂的虚拟身份关系网络进行身份识别和关系挖掘。

参考文献：

[1] 周英，卓金武，卞月青.大数据挖掘系统方法与实例分析[M].北京：机械工业出版社，2016.

[2] 邵文爽.基于关联规则挖掘Apriori算法的改进[D].沈阳：东北大学，2015.

[3] 崔妍，包志强.关联规则挖掘综述[J].计算机应用研究，2016，33 （2）.330-334.

[4]姜丽莉，黄承宁.多关系关联规则挖掘在考勤数据分析中的应用[J].电脑知识与技术，2018，14（ 36）：3-4.

[5] 陈莎.基于大数据的互联网虚拟身份关键技术研究与实现[D].北京：北京邮电大学，2015.

[6] 肖文，胡娟，周晓峰.基于MapReduce计算模型的并行关联规则挖掘算法研究综述[J].计算机应用研究，2018，35（1）：13-23.

[7]QIU H，CU R， YUAN C， et aI.YAFIM：a parallel frequent itemset min-ing algorithmWith Spark[C].Parallel&Distributed Processing Sym-posium Workshops.IEEE， 2014.

[8]FANG X. ZHANG G X. Optimization of parallel FP-growth algorithmhased on Spark [Jl. Modern Electronics Technique， 2016， 39 （8）： 9-13.

[9] 冯兴杰，潘轩.基于Spark的并行Eclat算法[J].计算机应用研究，2019（1）：18-21.

[10] 邵健.基于数据挖掘的及物性和单宾语句典型性关系挖掘[J].汉语学习，2019（1），31-41.

[11]王敏，李万春，扶彩霞，等.基于Apriori算法的战术数据链层次关系挖掘[J].航天电子对抗，2018（6）：29-33.

[12] 江庆华，王亚民，汤在祥.基于生存分析模型挖掘HSPB1基因表达与放疗敏感性关系研究[J].安徽医科大学学报，2019，54（2）：261-266.

[13] 李娇，曹晖，李倩.基于共现和关联挖掘的人物关系图构建过程[J].无线互联科技，2019，16（1）：110-112.

[14]李有增，周全，蒋鸿玲.基于时空关联的高校社会网络关系挖掘方法研究[J].微电子学与计算机，2018，35（ 12）：137-140.

[15]唐佳丽.面向科技评审中专家回避的人物社会关系分析方法研究[D].南昌：华东交通大学，2016.

[16]邱文龙.网络虚拟身份分析系统的研究与实现[D].北京：北京邮电大学，2015.

[17] 蓝邵武.网络虚拟身份关系的提取和分析[D]北京：北京邮电大学，2017.

[18] 闫洲.基于深度学习的多社交网络中虚拟身份关联技术研究[D].长沙：国防科技大学，2017.

[19] 韩浩明.图数据库系统研究综述[J].计算机光盘软件与应用，2014.

[20] 字凤芹，牛进，毕柱兰，等.基于图数据库的电影推荐系统设计[J].软件导刊，2016，15（1）：1-3.

[21] 吕冰清.大规模图数据库中的模式查询算法研究[D].上海：华东师范大学，2018.

（责任编辑：孙娟）

基金项目：北京市教育委员会科技计划项目（ KM201811232017）

作者简介：尹玉娇（1992-），女，北京信息科技大学计算机学院硕士研究生，研究方向为图算法、关系挖掘;张伟（1980-），男，博士，北京信息科技大学计算机学院副教授，研究方向为软硬件协同设计、存储安全、网络安全。本文通讯作者：张伟。