共享局部算法的数据分析

崔鹏宇

摘要：本文针对单一关系的数据挖掘方案不能精准的发现网络中隐藏的问题，通过提出异构网络数据挖掘的算法达到网络节点的初步划分目标的实并且能够初步此得到各数据子集。

关键词：异构网络；数据挖掘；共享局部结构

中图分类号：TP311.13 文献标识码：A 文章编号：1007-9416（2018）01-0138-02

随着社会网络分析的进一步发展，人们逐渐发现单一的关系网络并不能很好的刻画出实体间的真实结构[1]。在现实的社会网络中，实体之间往往是多种关系交织在一起的[2]。每种关系对应一个关系图，仅仅利用一种关系图分析网络结构有可能会造成重要信息的缺失，从而不能精准地挖掘其隐含的数据结构[3-4]。将含有多种关系的网络称之为“异质网络”或者多关系网络[5]。以信息共享为代表的各种异构网络应用蓬勃发展，使得人们与互联网间的联系更加紧密与多向，由简单单项的信息检索转变为以用户为主导的信息的创建与传播。随着用户之间的互交越来越密切与深入，异构网络下的数据挖掘研究逐渐成为复杂网络分析的一大热点[6]。

本文提出一种基于共享局部结构的异质网络数据挖掘算法，该模型利用各维关系网络间的共性信息，根据各关系图的初始聚类结果，找出那些在多个关系网中都同属于一个类型的节点簇，即数据子集，并对其中的节点进行标记，然后根据某种划分原则依次将剩余未标记的节点并入相应的数据子集中，从而完成整个网络节点的划分。通过在模拟计算机合成网络数据集上的比较试验，证明了所提出算法的鲁棒性和有效性。

1 异构网络下的数据结构

一个包含种关系的异构网络可以抽象地表示为，，其中表示含有个元素的节点集合，表示第维关系网络的邻接矩阵。将异构网络中的不同关系看作是从不同角度对网络节点的描述。此外，各维关系网并不是独立存在的。本文的任务就综合实体间的多种关系并从中挖掘其隐含的数据结构，引入了共享局部结构和节点簇凝聚度思想，提出了新的异构网络挖掘算法。

2 基于局部共享结构的异构网络数据挖掘

2.1 共享局部信息的提取

异构网络的实体间存在的对应的关系为。由网络进行数据划分可以得到如下集合：，这里—第维网络划分出来的数据结构。如果将被假定的关系网格都划分成为个数据集，并且在聚类时，随机分配（1～k）数据标号。

目标是提取有关异质网络之间的共享信息，有必要找到在划分的方式不尽相同的情况下的数据标号的相互对应关系，其公式如下：

其中表示由关系划分出来的标号为的数据集，为节点被划分到的概率而则表示节点在关系与关系中分别被划分到与中的概率。

2.2 共享局部结构的更新

将划分的结果一并加入到各维网络划分的数据结构的集合之中，这时分集合将扩充为，算法的主要步骤可以归纳如下：

维度改进算法：

输入：维异质关系网络、数据集个数；

输出：各节点所属的数据集标号；

（1）分别对各单维网络进行数据集划分，得到种不同的划分结果；

For ；

（2）将未标记节并入使节点簇的凝聚度增益最大的数据子集中；

（3）对未标记节点进行相应划分，将划分结果也并入集合（）。

3 实验数据集及对比结果

通过对比实验来验证有效性及鲁棒性。选取的方法有如下两种方式：一、各单一的异构网络下的数据集挖掘；二、关系矩阵加权组合的方法WAMM以及PMM算法。

为了比较各算法的数据集划分性能，我们使用了两种经典的指标：归一化互信息（NMI）与准确率（Ac）。两者的取值都在0-1之间，如果它们的值越大的话，说明结果越接近真实。

我们在计算机的合成数据上进行试验分析的目的是为了验证算法是否有效。这种合成网络一共包括350个节点，将其划分成了三个大小各不相同的数据集，并且各个网络节点间存在4种关系，各关系图的可以用对应图1中的来表示。

圖2指出了每种算法在合成网络中数据集划分的性能，从图中我们可以看出异质网络的算法性能明显比单一的关系网的数据集挖掘性能要好，并且基本上能实现了正确的划分。

4 结语

针对异构网络中多元化的节点关系，本文提出一种基于共享局部结构的异质网络数据集挖掘算法。该算法将网络节点通过提取多种关系间共享的局部信息基本实现了网络节点的局部划分，最后在通过在计算机合成的数据集上验证了该算法的有效性。

参考文献

[1]张春英，郭景峰.集对社会网络α关系社区及动态挖掘算法[J].计算机学报，2013，（8）：1682-1692.

[2]孙荣德，邵峰晶，孙仁诚.一种基于复合网的面向微博关注的推荐算法[J].计算机光盘软件与应用，2013，（24）：132-133.

[3]王会梅，鲜明，王国玉.基于扩展网络攻击图的网络攻击策略生成算法[J].电子与信息学报，2011，（12）：3015-3021.

[4]黄光球，李艳.基于粗糙图的网络风险评估模型[J].计算机应用，2010，（1）：190-195.

[5]荣智海，吴枝喜，王文旭.共演博弈下网络合作动力学研究进展[J].电子科技大学学报，2013，（1）：10-22.

[6]刘钰峰，李仁发.异构信息网络上基于图正则化的半监督学习[J].计算机研究与发展，2015，（3）：606-613.