《标签传播在社会网络中的运用.docx》由会员分享，可在线阅读，更多相关《标签传播在社会网络中的运用.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、标签传播在社会网络中的运用（计算机工程与应用杂志）2014年第十四期1研究现状针对在大规模网络构造中进行聚类时，需要事先知道聚类数目、规模等先验信息，或者聚类算法的计算代价比拟大的情况，Raghavan等人提出了基于标签传播8的简单快速算法。在算法中，初始化时每个节点被赋予唯一的数字标签，在之后的每步中，将所有节点以随机序列排列，根据邻接节点当前出现频率最高的标签依次确定随机序列中节点的标签。如此迭代，在几乎线性的时间内实现了节点聚类。由于算法的终止条件是事先约定的一个准则，并非函数值的最大化或者最小化，因而知足停止条件的网络划分结果不唯一，但Raghavan等人通过计算发现这些不同的网络划分
2、之间具有极大的类似性。并且提出将各种网络划分结果进行聚合，能够发现重叠的簇构造。该算法仅将已知的网络构造作为启发式搜索条件，在线性时间O(m+n)内实现高效聚类，且适用于含有百万节点的大规模网络。Barber和Clark指出LPA算法在将不同聚类结果进行聚合时，若不同的划分方案中簇构造越小，那么聚合后的簇构造也就越多，是该算法存在的一个比拟严重的缺陷。为了解决该问题，他们在经过中引入了一些限制，在目的函数H对H进行极大化，等价于原始的LPA算法上增加了一些数据项，提高了LPA算法的性能9。Leung等人在对线性时间的LPA算法进行分析总结的基础上，提出了在社会网络构造中进行实时聚类的方法，改善
3、了LPA算法簇构造规模不均匀的缺陷，并且证实了标签传播的启发式方法在大规模网络中进行聚类更准确、更高效10。此外，Long等人提出的基于图类似的CLGA算法11，Narasimhamurthy等人提出的图模型分解方法12，Zarei和Samani提出了基于Newman的反簇构造概念，将网络看成一个图，通过在原图的补图中寻找反簇构造，进而得到原簇的构造的算法12等。国内的研究学者也对这一问题进行了相关研究13-14。基于局部信息的聚类方法通常是考虑网络中节点的局部近邻信息，在大规模数据集中，能够高效地找到网络最优划分或者近似最优划分，一般具有概念简单，易于实现，算法复杂度相对较低等优点。但纵观每
4、个基于局部信息的启发式聚类算法，又分别有它各自的局限性。2基于节点属性类似度的标签传播算法2.1问题描绘LPA算法仅以网络拓扑构造作为向导，根据节点之间的连接，可高效地进行网络聚类，这是LPA算法的优点。但现实世界中的绝大多数网络，除了具有拓扑构造特征，网络中的节点本身的属性信息也很容易获取，如科学家合著网络中，每个学者都有其主要的研究方向。因而，LPA算法忽略了节点本身的属性信息，仅考虑连接的局部信息，而且LPA算法具有较大的随机性，这会致使算法对网络划分可能并非最优，甚至出现节点的错误划分。下面通过一个实例来形象、直观地讲明该算法存在的问题。一个小型的人际交互网络如图1所示，其中每个节点代
5、表一个人，每个人所属的学校用节点旁的字母表示。根据标签传播算法，显然网络能够被划分为两个簇构造，A大学v1v2v3v4v5v6，B大学v7v8v9v10。如今仔细分析v6节点，在标签传播经过中，根据连接节点与其邻节点的连接情况来看，它的候选集合有两个：v4v5和v9v10对应的标签分别为A大学和B大学。随机选择其一，如：A大学，但根据它的实际属性来看，它是属于B大学的，因而节点出现了错误的划分，影响了网络聚类的质量。即便在下一轮的迭代经过中，它被划分到正确的构造中，但这也是需要付出时间代价的。针对上述情况，本文综合考虑节点属性信息，在保证原算法时间复杂度的基础上，引入节点属性类似度的概念，提出
6、基于节点属性类似度的标签传播算法，致力于提高网络划分效果，降低算法的时间开销。2.2节点属性类似度在给出LPA-SNA算法的详细描绘前，先给出计算节点属性类似度所需的一些基本概念及定义。本文要用到的重要的表示符号如表1所示。2.3LPA-SNA算法描绘及实如今原始的LPA算法的基础上，当待更新节点的大部分邻节点所属的簇构造不止一个，即该节点的邻接子系统不唯一时，基于节点属性类似度的标签传播算法LPA-SNA计算每个邻接子系统中节点属性的平均值，进而计算待更新节点与各邻接子系统的属性类似度，并选取令类似度maxSimi(SiSNir)最高的子系统的标签作为当前节点的标签。由于一般的原始网络包含节
7、点及边的信息，算法每次迭代时，要根据邻居节点标签信息来决定当前节点的标签，假如每次都统计该节点有哪些邻节点，算法运行时需要消耗大量的时间。因而，对LPA-SNA算法进行实现时，要先进行预处理，首先读入包含网络G节点及边信息的文件，并根据读入的G的拓扑构造，构造对应的邻接表构造体ALGraph，ALGraph包含顶点表节点构造体VNode和边表节点构造体ArcNode，而VNode存储了每个节点的邻节点数量及其属性信息，ArcNode存储了邻居节点位置信息及边信息。LPA-SNA算法包括下面5个步骤：1初始化网络中的节点标签，依次为每个节点分配唯一的数字标签，即对于节点v，令Cv(0)=v。2令
8、迭代计数器t=1。3以随机顺序排列网络中的节点，并将排序结果存放在向量X中。其中，Max_Vertex_Number为宏定义，表示网络包含的节点数量。在迭代经过中，为了根据随机顺序对节点标签进行更新，算法定义的随机数组RandArrayMax_Vertex_Number，存储0Max_Vertex_Number-1的随机排列的数据，并设计函数RandInPlace(RandArray)来实现对数组中数据元素的随机排序。3实验分析本文LPA-SNA算法的实验环境是InterCoreTM2.66GHz，2GB内存，MicrosoftWindowsXP操作系统的PC机；选用VisualC+6.0开发
9、环境。为了对改良的LPA-SNA算法的可行性及有效性进行实验论证，选择美国大学足球赛程网络15、科学家合著网络两个数据集进行实验。3.1美国大学足球赛程网络数据集实验首先，将LPA和LPA-SNA算法应用美国大学足球赛程网络。Newman提供的美国大学足球赛程网络，是分析社会网络聚类的经典的数据集，根据2000年秋季常规赛的比赛计划构建的，包含115个代表大学足球队的节点，616条表示两个大学球队之间进行了比赛的边。这些球队构成了一个具有簇构造特性的网络，通常8到12个足球队组成一个小组，不同小组间的球队比赛的可能性要少于同一小组内的球队间比赛的可能性。将LPA算法与LPA-SNA算法分别应用
10、在该包含12个簇构造的数据集上。为了不使算法陷入固定化、形式化的情况，在每次迭代经过中，LPA与LPA-SNA算法中节点更新顺序都是随机的。但由于存在该随机策略，屡次运行两种算法时会产生不同的聚类效果。为了愈加真实地分析算法的性能，在美国大学足球网络上分别将这两种算法运行30次，并且得到相关数据如表2所示。另外，为了愈加直观地比拟LPA与LPA-SNA算法在运行速度、网络划分质量方面的性能，本文对两种算法在足球赛程网络上屡次运行时的时间、网络模块度两个参数值情况绘制了比照折线图，如图2、3所示。根据表2所提供的实验数据结果能够看出，引入节点属性类似度的LPA-SNA算法的平均迭代次数少于LPA
11、算法，当节点候选集合标签不唯一时，通过计算节点属性与候选邻接子系统的属性类似度选择最佳的标签，使得节点很快被划分到正确的网络中，因而平均运行时间更低，效率更高。同时，观察网络聚类模块度的平均值，能够看出LPA-SNA算法的平均Q值更大，讲明LPA-SNA算法中所划分出的簇构造内部节点联络得愈加严密，对网络划分质量更高。另外，从迭代次数范围、运行时范围两个参数来分析，LPA算法的数据范围更大。通过图2、3能够看出，LPA算法的运行时间、模块度值的变化幅度要大，而LPA-SNA算法参数范围区间相对较小，运行时间及模块度变化幅度相对较小。上述数据讲明，LPA算法在每次迭代经过中，由于节点顺序排列具有
12、随机性，当最高标签频率不一致时，标签选择也具有随机性，导致算法对网络划分的随机性比拟大。而LPA-SNA算法通过引入节点属性类似度，降低了原始LPA算法的随机性，提高原始算法运行时间、聚类质量的同时，也具有更好的稳定性。原始的足球赛程网络数据集具有12个簇构造，为了进一步分析LPA算法及LPA-SNA算法网络聚类性能的差异，本文从上述的运行30次的聚类结果中将美国足球赛程网络均划分为12个簇构造时的情况进行简单统计，综合考虑运行时间和模块度两个参数，选取性能比拟平衡情况下的两种算法对应的网络划分，如图4所示。该情况下，两种算法的迭代次数、模块度Q值、运行时间3种情况如表3所示。将LPA-SNA
13、算法与LPA算法与足球赛程网络的真实划分情况进行比照分析，发现LPA算法在模块度为0.5807时得出的簇构造个数为12，运行0.047s，有16个节点划分错误，其中五边形表示的MidAmerican小组被划分到两个簇构造中，正确率为86.08%，而LPA-SNA算法在网络中挖掘12个簇构造时的模块度为0.5974，运行时间为0.035s，有10个节点划分错误，正确率为91.30%。3.2科学家合著网络数据集实验DBLPDigitalBibliographyLibraryProject是由德国的Trier大学建立的，收录计算机科学领域内的出版物，包括书籍、期刊和会议论文，作者及合著者的姓名等相关
14、内容，提供非常全面的信息。目前为止，它至少已收录13000000条书目记录，由于文献的质量比拟高且具有实时性，能够快速反映领域内最新研究动态，因而它极具权威性，遭到计算机领域学者们的广泛认可。此外，DBLP数据集可免费获取，因而本文从DBLP网站中搜集部分数据作为实验研究对象。首先，搜集来自DBLP的6个领域20个会议上发表文章的学者，其中涉及的会议领域及名称如下所示。选择在会议中发表文章较多的1590个学者作为科学家合著网络的节点，假如两个学者共同合作了文章，那么在网络中他们之间就对应存在一条边，以此构建一个科学家合著网络，并将学者的研究领域、发表文章的期刊名称作为节点属性信息。在该节点具有
15、文本属性的科学家合著网络数据集上，分别实现LPA及LPA-SNA算法。本文通过引用这些属性信息，计算节点属性类似度，为节点选择最佳的标签。通过对该数据集进行聚类，比拟PLA及PLA-SNA算法的性能。根据数据的搜集经过可知，在科学家合著网络真实数据集原则上应该划分为6个簇构造。将LPA算法和改良的LPA-SNA算法运行在网络上，得到的簇构造数量分别4个、6个，如表4所示。ComputerVisionUtilize领域的CVPR会议中发表文章的作者经常参加IJCAI、AAAI、ICML和ECML会议，由于LPA算法仅使用网络的拓扑构造，根据网络中节点的连接关系，很容易将CVPR中的学者划分到Ar
16、tificialIntelligence领域中。但ComputerVisionUtilize领域的学者固然经常使用人工智能的方法，但它仍存在着一些独特的方法，如分割、对象跟踪和图像建模等，因而，ComputerVisionUtilize领域的学者应该从属单独的一个簇构造。另外，InformationandKnowledgeMan-agement领域的CIKM中的文章涉及的研究领域非常广泛，吸引了很多信息分析、数据挖掘、数据库等领域的研究学者。但是很显然，与这些领域的任何一个会议相比拟，CIKM有着本人独特的研究主题，因而它也应该构成独立的簇构造。原始的LPA算法仅根据节点间的连接来聚类，因而很
17、容易将ComputerVisionUtilize与InformationandKnowledgeManagement中的节点划分到其他簇构造中，造成网络划分为4个簇构造，而LPA-SNA算法在引入节点属性类似度以后，将DBLP的20个会议中的作者正确地划分为6个簇构造。另外，在该合著网络上屡次运行LPA与LPA-SNA算法，实验得到的其他性能方面的数据如表5所示。如图5、6为对算法运行30次的时间、模块度参数。结合表5的统计数据与图5、6两种算法的运行时间、网络模块度参数折线图能够看出，在科学家合著网络上，LPA-SNA算法的聚类速度、网络划分质量也明显优于LPA算法。引入节点属性类似度以后，
18、使具有多个邻接子系统的节点根据其属性特征很快地找到和本身接近的簇构造，降低了LPA算法的迭代次数，减少了时间开销，提高了网络聚类的质量。4总结在对基于局部信息的LPA算法进行深化研究的基础上，引入节点属性类似度的概念，提出了LPA-SNA算法。它以网络构造为主要根据的同时，考虑节点属性信息，对大规模数据集网络进行聚类，一定程度上克制了原始的LPA算法的随机策略，提高了算法的聚类速度与网络划分质量。通过在美国大学生足球赛程网络、科学家合著网络数据集上运行LPA与LPA-SNA算法，验证了LPA-SNA算法的可行性与有效性。目前基于局部信息的聚类算法研究已获得了很大的进展，能够有效地探测社会网络的簇构造，但随着应用领域的不断拓展，网络聚类问题的多样化，簇构造挖掘仍不能完全发现网络的全部功与特性。因而，怎样针对各种不同类型的网络，设计出愈加高效，无需先验知识指导，利用局部信息即可挖掘簇构造的算法，还是今后需努力的一个方向。