标签传播在社会网络中的运用范文

《计算机工程与应用杂志》2014年第十四期

1研究现状

针对在大规模网络结构中进行聚类时，需要事先知道聚类数目、规模等先验信息，或者聚类算法的计算代价比较大的情况，Raghavan等人提出了基于标签传播[8]的简单快速算法。在算法中，初始化时每个节点被赋予唯一的数字标签，在之后的每步中，将所有节点以随机序列排列，根据邻接节点当前出现频率最高的标签依次确定随机序列中节点的标签。如此迭代，在几乎线性的时间内实现了节点聚类。由于算法的终止条件是事先约定的一个准则，并非函数值的最大化或者最小化，因此满足停止条件的网络划分结果不唯一，但Raghavan等人通过计算发现这些不同的网络划分之间具有极大的相似性。并且提出将各种网络划分结果进行聚合，可以发现重叠的簇结构。该算法仅将已知的网络结构作为启发式搜索条件，在线性时间O(m+n)内实现高效聚类，且适用于含有百万节点的大规模网络。Barber和Clark指出LPA算法在将不同聚类结果进行聚合时，若不同的划分方案中簇结构越小，那么聚合后的簇结构也就越多，是该算法存在的一个比较严重的缺陷。为了解决该问题，他们在过程中引入了一些限制，在目标函数H（对H进行极大化，等价于原始的LPA算法）上增加了一些数据项，提高了LPA算法的性能[9]。Leung等人在对线性时间的LPA算法进行分析总结的基础上，提出了在社会网络结构中进行实时聚类的方法，改善了LPA算法簇结构规模不均匀的缺陷，并且证明了标签传播的启发式方法在大规模网络中进行聚类更准确、更高效[10]。此外，Long等人提出的基于图相似的CLGA算法[11]，Narasimhamurthy等人提出的图模型分解方法[12]，Zarei和Samani提出了基于Newman的反簇结构概念，将网络看成一个图，通过在原图的补图中寻找反簇结构，进而得到原簇的结构的算法[12]等。国内的研究学者也对这一问题进行了相关研究[13-14]。基于局部信息的聚类方法通常是考虑网络中节点的局部近邻信息，在大规模数据集中，可以高效地找到网络最优划分或者近似最优划分，一般具有概念简单，易于实现，算法复杂度相对较低等优点。但纵观每个基于局部信息的启发式聚类算法，又分别有它各自的局限性。

2基于节点属性相似度的标签传播算法

2.1问题描述LPA算法仅以网络拓扑结构作为向导，根据节点之间的连接，可高效地进行网络聚类，这是LPA算法的优点。但现实世界中的绝大多数网络，除了具有拓扑结构特征，网络中的节点自身的属性信息也很容易获取，如科学家合著网络中，每个学者都有其主要的研究方向。因此，LPA算法忽略了节点本身的属性信息，仅考虑连接的局部信息，而且LPA算法具有较大的随机性，这会致使算法对网络划分可能并非最优，甚至出现节点的错误划分。下面通过一个实例来形象、直观地说明该算法存在的问题。一个小型的人际交互网络如图1所示，其中每个节点代表一个人，每个人所属的学校用节点旁的字母表示。根据标签传播算法，显然网络可以被划分为两个簇结构，A大学{v1v2v3v4v5v6}，B大学{v7v8v9v10}。现在仔细分析v6节点，在标签传播过程中，根据连接节点与其邻节点的连接情况来看，它的候选集合有两个：{v4v5}和{v9v10}对应的标签分别为A大学和B大学。随机选择其一，如：A大学，但根据它的实际属性来看，它是属于B大学的，因此节点出现了错误的划分，影响了网络聚类的质量。即使在下一轮的迭代过程中，它被划分到正确的结构中，但这也是需要付出时间代价的。针对上述情况，本文综合考虑节点属性信息，在保证原算法时间复杂度的基础上，引入节点属性相似度的概念，提出基于节点属性相似度的标签传播算法，致力于提高网络划分效果，降低算法的时间开销。

2.2节点属性相似度在给出LPA-SNA算法的具体描述前，先给出计算节点属性相似度所需的一些基本概念及定义。本文要用到的重要的表示符号如表1所示。

2.3LPA-SNA算法描述及实现在原始的LPA算法的基础上，当待更新节点的大部分邻节点所属的簇结构不止一个，即该节点的邻接子系统不唯一时，基于节点属性相似度的标签传播算法（LPA-SNA）计算每个邻接子系统中节点属性的平均值，进而计算待更新节点与各邻接子系统的属性相似度，并选取令相似度maxSimi(SiSNir)最高的子系统的标签作为当前节点的标签。由于一般的原始网络包含节点及边的信息，算法每次迭代时，要根据邻居节点标签信息来决定当前节点的标签，如果每次都统计该节点有哪些邻节点，算法运行时需要耗费大量的时间。因此，对LPA-SNA算法进行实现时，要先进行预处理，首先读入包含网络G节点及边信息的文件，并根据读入的G的拓扑结构，构造对应的邻接表结构体ALGraph，ALGraph包含顶点表节点结构体VNode和边表节点结构体ArcNode，而VNode存储了每个节点的邻节点数量及其属性信息，ArcNode存储了邻居节点位置信息及边信息。LPA-SNA算法包括以下5个步骤：（1）初始化网络中的节点标签，依次为每个节点分配唯一的数字标签，即对于节点v，令Cv(0)=v。（2）令迭代计数器t=1。（3）以随机顺序排列网络中的节点，并将排序结果存放在向量X中。其中，Max_Vertex_Number为宏定义，表示网络包含的节点数量。在迭代过程中，为了按照随机顺序对节点标签进行更新，算法定义的随机数组RandArray[Max_Vertex_Number]，存储0~Max_Vertex_Number-1的随机排列的数据，并设计函数RandInPlace(RandArray)来实现对数组中数据元素的随机排序。

3实验分析

本文LPA-SNA算法的实验环境是Inter®CoreTM2.66GHz，2GB内存，MicrosoftWindowsXP操作系统的PC机；选用VisualC++6.0开发环境。为了对改进的LPA-SNA算法的可行性及有效性进行实验论证，选择美国大学足球赛程网络[15]、科学家合著网络两个数据集进行实验。

3.1美国大学足球赛程网络数据集实验首先，将LPA和LPA-SNA算法应用美国大学足球赛程网络。Newman提供的美国大学足球赛程网络，是分析社会网络聚类的经典的数据集，根据2000年秋季常规赛的比赛计划构建的，包含115个代表大学足球队的节点，616条表示两个大学球队之间进行了比赛的边。这些球队构成了一个具有簇结构特性的网络，通常8到12个足球队组成一个小组，不同小组间的球队比赛的可能性要少于同一小组内的球队间比赛的可能性。将LPA算法与LPA-SNA算法分别应用在该包含12个簇结构的数据集上。为了不使算法陷入固定化、模式化的情况，在每次迭代过程中，LPA与LPA-SNA算法中节点更新顺序都是随机的。但由于存在该随机策略，多次运行两种算法时会产生不同的聚类效果。为了更加真实地分析算法的性能，在美国大学足球网络上分别将这两种算法运行30次，并且得到相关数据如表2所示。另外，为了更加直观地比较LPA与LPA-SNA算法在运行速度、网络划分质量方面的性能，本文对两种算法在足球赛程网络上多次运行时的时间、网络模块度两个参数值情况绘制了对比折线图，如图2、3所示。根据表2所提供的实验数据结果可以看出，引入节点属性相似度的LPA-SNA算法的平均迭代次数少于LPA算法，当节点候选集合标签不唯一时，通过计算节点属性与候选邻接子系统的属性相似度选择最佳的标签，使得节点很快被划分到正确的网络中，因此平均运行时间更低，效率更高。同时，观察网络聚类模块度的平均值，可以看出LPA-SNA算法的平均Q值更大，说明LPA-SNA算法中所划分出的簇结构内部节点联系得更加紧密，对网络划分质量更高。另外，从迭代次数范围、运行时范围两个参数来分析，LPA算法的数据范围更大。通过图2、3可以看出，LPA算法的运行时间、模块度值的变化幅度要大，而LPA-SNA算法参数范围区间相对较小，运行时间及模块度变化幅度相对较小。上述数据说明，LPA算法在每次迭代过程中，由于节点顺序排列具有随机性，当最高标签频率不一致时，标签选择也具有随机性，导致算法对网络划分的随机性比较大。而LPA-SNA算法通过引入节点属性相似度，降低了原始LPA算法的随机性，提高原始算法运行时间、聚类质量的同时，也具有更好的稳定性。原始的足球赛程网络数据集具有12个簇结构，为了进一步分析LPA算法及LPA-SNA算法网络聚类性能的差异，本文从上述的运行30次的聚类结果中将美国足球赛程网络均划分为12个簇结构时的情况进行简单统计，综合考虑运行时间和模块度两个参数，选取性能比较均衡情况下的两种算法对应的网络划分，如图4所示。该情况下，两种算法的迭代次数、模块度Q值、运行时间3种情况如表3所示。将LPA-SNA算法与LPA算法与足球赛程网络的真实划分情况进行对比分析，发现LPA算法在模块度为0.5807时得出的簇结构个数为12，运行0.047s，有16个节点划分错误，其中五边形表示的MidAmerican小组被划分到两个簇结构中，正确率为86.08%，而LPA-SNA算法在网络中挖掘12个簇结构时的模块度为0.5974，运行时间为0.035s，有10个节点划分错误，正确率为91.30%。

3.2科学家合著网络数据集实验DBLP（DigitalBibliography&LibraryProject）是由德国的Trier大学建立的，收录计算机科学领域内的出版物，包括书籍、期刊和会议论文，作者及合著者的姓名等相关内容，提供非常全面的信息。目前为止，它至少已收录13000000条书目记录，由于文献的质量比较高且具有实时性，可以快速反映领域内最新研究动态，因此它极具权威性，受到计算机领域学者们的广泛认可。此外，DBLP数据集可免费获取，因此本文从DBLP网站中搜集部分数据作为实验研究对象。首先，搜集来自DBLP的6个领域20个会议上发表文章的学者，其中涉及的会议领域及名称如下所示。选择在会议中发表文章较多的1590个学者作为科学家合著网络的节点，如果两个学者共同合作了文章，那么在网络中他们之间就对应存在一条边，以此构建一个科学家合著网络，并将学者的研究领域、发表文章的期刊名称作为节点属性信息。在该节点具有文本属性的科学家合著网络数据集上，分别实现LPA及LPA-SNA算法。本文通过引用这些属性信息，计算节点属性相似度，为节点选择最佳的标签。通过对该数据集进行聚类，比较PLA及PLA-SNA算法的性能。按照数据的搜集过程可知，在科学家合著网络真实数据集原则上应该划分为6个簇结构。将LPA算法和改进的LPA-SNA算法运行在网络上，得到的簇结构数量分别4个、6个，如表4所示。ComputerVisionUtilize领域的CVPR会议中发表文章的作者经常参加IJCAI、AAAI、ICML和ECML会议，由于LPA算法仅使用网络的拓扑结构，根据网络中节点的连接关系，很容易将CVPR中的学者划分到ArtificialIntelligence领域中。但ComputerVisionUtilize领域的学者虽然经常使用人工智能的方法，但它仍存在着一些独特的方法，如分割、对象跟踪和图像建模等，因此，ComputerVisionUtilize领域的学者应该隶属单独的一个簇结构。另外，InformationandKnowledgeMan-agement领域的CIKM中的文章涉及的研究领域非常广泛，吸引了许多信息分析、数据挖掘、数据库等领域的研究学者。但是很显然，与这些领域的任何一个会议相比较，CIKM有着自己独特的研究主题，因此它也应该形成独立的簇结构。原始的LPA算法仅根据节点间的连接来聚类，因此很容易将ComputerVisionUtilize与InformationandKnowledgeManagement中的节点划分到其他簇结构中，造成网络划分为4个簇结构，而LPA-SNA算法在引入节点属性相似度以后，将DBLP的20个会议中的作者正确地划分为6个簇结构。另外，在该合著网络上多次运行LPA与LPA-SNA算法，实验得到的其他性能方面的数据如表5所示。如图5、6为对算法运行30次的时间、模块度参数。结合表5的统计数据与图5、6两种算法的运行时间、网络模块度参数折线图可以看出，在科学家合著网络上，LPA-SNA算法的聚类速度、网络划分质量也明显优于LPA算法。引入节点属性相似度以后，使具有多个邻接子系统的节点根据其属性特征很快地找到和本身接近的簇结构，降低了LPA算法的迭代次数，减少了时间开销，提高了网络聚类的质量。

4总结

在对基于局部信息的LPA算法进行深入研究的基础上，引入节点属性相似度的概念，提出了LPA-SNA算法。它以网络结构为主要依据的同时，考虑节点属性信息，对大规模数据集网络进行聚类，一定程度上克服了原始的LPA算法的随机策略，提高了算法的聚类速度与网络划分质量。通过在美国大学生足球赛程网络、科学家合著网络数据集上运行LPA与LPA-SNA算法，验证了LPA-SNA算法的可行性与有效性。目前基于局部信息的聚类算法研究已取得了很大的进展，能够有效地探测社会网络的簇结构，但随着应用领域的不断拓展，网络聚类问题的多样化，簇结构挖掘仍不能完全发现网络的全部功与特性。因此，如何针对各种不同类型的网络，设计出更加高效，无需先验知识指导，利用局部信息即可挖掘簇结构的算法，仍是今后需努力的一个方向。

作者：夏磊张乐君国林张勇实张健沛杨静单位：哈尔滨工程大学计算机科学与技术学院大连飞创信息技术有限公司