一种新的复杂网络概述算法研究

张洁1，耿向华1，程凤娟2

（1.郑州旅游职业学院信息工程系，郑州450000；2.河南工业大学信息科学与工程学院，郑州450001）

摘要：针对大型复杂网络相关的概述问题展开了深入系统地研究,本文重点对属性与结构的相似度

进行了全面考量，由于用户具有各自的选择属性，主要是将虚拟连接与实连接进行有效的集成，一般而言，对于大型网络数据会同时把具有相同属性的节点共同放置于k个非重叠的分类上。本文主要是以属性相似度为核心，然后将节点全部置于对应的分类中，重点采用了虚拟图概念，主要是围绕属性相似度开展的，旨在较好的划分复杂网络。另外，对子分类进行调整的过程中借助了HB-图，这样可以有助于在分类结构时，对算法进行优化。该论文为了更好地加强算法的执行效率，专门提出了诸多方法对算法加以改进。也就是说，该论文中所采用的算法，能够确保用户较好地对上卷操作（Roll-up）以及下钻操作（Drill-down）加以执行，并且，围绕各粒度层面为中心，对复杂网络的概述过程展开全面的分析。实验结果表明本文提出的基于虚连接和实连接的复杂网络概述算法OCNVR算法是切实可行的，较之于其他算法而言其执行效率更加高校。

关键词：选择属性；非重叠的分类；虚连接；实连接；复杂网络概述算法中图分类号：TP312

文献标识码：A

文章编号：1001-7119（2017）08-0129-04

DOI:10.13774/j.cnki.kjtb.2017.08.027

ResearchonNewAlgorithmforComplexNetworks

ZhangJie1，GengXianghua1，ChengFengjuan2

（1.DepartmentofInformationEngineering，ZhengzhouTourismCollege，Zhengzhou450000，China；2.CollegeofInformationScienceandEngineering，HenanUniversityofTechnology，Zhengzhou450001，China）Abstract：In-depthsystematicresearchoverviewoftheproblemforlargecomplexnetwork,thispaperfocusesonthesimilarityofattributesandstructureofcomprehensiveconsideration,becausetheuserhasthechoiceofattributesrespectively,ismainlyconnectedwiththerealvirtualconnectionforeffectiveintegration,ingeneral,forlargenetworkdataatallnodeswiththesamethecommonattributeplacedonKnonoverlappingclassification.Thisarticleisbasedontheattributesimilarityasthecore,andthenthenodesareplacedinthecorrespondingclassification,focusingontheuseofvirtualmapconcept,mainlyaroundtheattributesimilarityiscarriedout,inordertobetterdivisionofcomplexnetworks.Inaddition,theclassificationstructure,thealgorithmisoptimized.Inordertoimprovetheefficiencyofthealgorithm,theprocessofadjustmenttothesubclassificationwiththeaidoftheHB-map,whichcanbehelpfulinthispaperputsforwardalotofmethodstoimprovethealgorithm.Thatistosay,usingthepaper'salgorithm,toensurethatusersbettertorollupoperations(Roll-up)anddrilldown(Drill-down)tocarryout,andaroundthelevelofgranularityforthecenter,acomprehensiveanalysisofthecomplexnetworkofcomplexnetworkoverviewOCNVRalgorithmisfeasible,comparedwithotheralgorithmsanditsdeploymentoverview.Theexperimentalresultsshowthatbasedonthevirtualconnectionandconnection收稿日期：2016-09-25作者简介：张洁（1983-），女，汉族，工程硕士，讲师，郑州旅游职业学院信息工程系，计算机应用。130implementationefficiencyismorehigher.科技通报第33卷

Keywords：selectionofattributes；nonoverlappingclassification；virtualconnection；realconnection；complexnetwork从2010年开始，复杂网络呈现了大规模化的趋势，并且其增长速度极快，如社交网络、传感器网络等。针对这些复杂网络的研究，研究人员怎么样来科学的发掘其潜在的特性，是当今行业内一个焦点课题[1]。同时，也是一个难度系数高的挑战。在这些复杂网络中，当用户想要理解正在浏览网络所包含的潜在信息，采用可视化网络的模式来分析，效果不是很理想[2]。所以，图概述算法能发挥非常明显的作用，尤其是在大规模复杂网络中，另外，又被称之为节点汇聚方法。

目前许多专家学者提出了大量的图概述算法，这些算法都是采用了统计方法来进行，主要对图中包含的特征信息进行阐述，如度分布[3]、集聚系数[4]等。不过，采用这种处理方式，还是存在不足，所获取的概述信息不够全面，比较狭窄，还有难于控制这个的概述过程。OLAP类型的聚类方法[5]能有效的处理上文提到的图数据遇到各种的问题。Chen等研究人员[6]全面的研究分析该模型后，设计和开发了一种更加优秀的新型图框架。Chen等研究人员根据不同的实际情况，对不同的图，分别采用了相对应的操作和语义信息，同时，他们也对OLAP框架进行了分类，分别是：第一个类别是信息的框架；第二个类别柘扑结构的框架。但是，Chen等研究人员也只是简单的描述了OLAP的概念[7]。Tian等人[8]对OLAP类型的聚类方法也经过长期坚持不懈的研究，SNAP这两种算法，和K-SNAP提出了都是概述大型图结构，两种算法。接下来，采用的原理简单的介绍是用户选择的属性和汇聚节点信息以及用户属性相对应的关系来实现，这两种算法的优点是提高了控制图概述的解析度，其缺点是概述图的信息不能从两个或者两个以上的方向进行。

本文设计出一个性能更加强大的复杂网络描述框架，将包含两个方面的内容，分别是：第一个是属性相似度的内容；第二个是结构相似度的内容。本文提出的OCNVR算法，k个非重叠Non-overlapping）通过三个方面的途径接收复杂网络的相似节点，采用了用户选择的属性和实连接（结构）以及虚连接（属性）。OCNVR算法既可

以运用上卷操作（Roll-up），还可以运用下卷操作

（Drill=down），能很好的帮助用户实现动态化的管理复杂网络概述过程，有利于从多个维度的粒度来可视化复杂网络。

1基于虚连接和实连接的复杂网络概述算法OCNVR算法

1.1

算法概述

算法OCNVR的4个分类主要是根据用户选择的单值属性来生成，其中单值属性主要是指城市和用户的性别，并且4个分类中全部的用户性别和城市都是一样的。不过，在实际的运用中，往往会出现一些大的节点分类结果，这是由于节点分类增加了相对应的单值属性。因此，要科学的划分初始分类结果。

节点汇聚算法的流程将会在算法1中进行描述，1其获得的信息是非重叠的图的划分。在算法的数值来完成，中，第一个步骤是节点的分类是按照单值属性同时，EL同构的分类将接收到图中全部的节点，最初的概述结果就是前文提到的分类结果。一般情况下，EL同构的分类数较多，超过了用户的分类数k，因此，需要将数量较多的分类进行科学的处理，分成小的的子分类。根据全部的分类信息，概述图Gsum将构建虚拟图，并且将及时的得出虚拟图的密度（第3~5行）。不紧密的分类是可以被多次的选择，并且分为L个子分类，如果总分类数超过了k时，所获得的结果也就是最终的分类划分结果。算法选择的分类通常情况下在最后一个环节中被划分（k-∣Gsum∣）个子分类，能实现k个分类数的最终需求。稀疏的分类结果φ在重复划分的过程中，是网络的分类的群，接下来将介绍其操作步骤：第一个步骤是对分类结果φ的L个图心进行快速的计算，其次，在多值属性的基础上，合理的划分分类结果φ，将其分为L个子分类（第11行），不过，有可能不能获得一个理想ФSL分类结果，产生这种问题的原因是没实连接的信息在汇聚节点的过程中并没有得到充分的运用，为了处理该问题，需要

（第8期

张洁等.一种新的复杂网络概述算法研究131

优化执行节点的操作，这方面的内容将在第12行中进行详细的说明。然后，完成该操作后，计算已经划分好的分类群的密度，最后，在复杂网络概述过程中，把这次获得的结果看作是最终结果。

算法OCNVR支持全部的用户自由的选择参数k，参数k主要是指该概述过程中的分类数。参数k的数值有着规定的范围，一般情况下，其取值范围在∣ФeL∣到∣V(G)∣之中，根据这种计算的方法，能将该网络划分为很多个∣ФeL∣个分类，并且它们的单值属性也是一样的。另外，(况下，G)∣个分类，也可以计算出∣V都能单独划分为一个分类。该网络中的全部节点在条件特殊的情1.2基于相似连接同构的分类方法

本小节将全面的介绍该方法在评估分类的汇聚结果中的运用，接下来将简单的描述该算法，其构成部分分别是：（1）构建图心集合；（2）分析基于图心集合的汇聚过程。

在该算法中，图心集合的构成主要是由最大距离的节点来完成，但是，如何获得这个节点是一个NP-完全问题。为了有效地获得该节点，将通过贪心算法来实现，从而能选择最大距离的图心，更可以最大程度化该网络的最大距离，接下来将介绍其操作步骤：第一个步骤是对虚拟图的图心进行合理的选择；第二个步骤是在进行连续选择时，一定要最先考虑比初始图心距离更大的点。

算法首先对虚拟图的图心C进行计算。以图心C为基础，对其初始图心集合C加以有效构建，同时，图心C应当被融于分类集合Фst中。图心C与之分类中的节点距离可以借助Dijkstra算法进行计算。其次，以计算得到的记录为基础，图心集合需要通过Gvir虚拟图挑选（l-1）个节点。当执行算法进行重复运行时，选择的节点应当确保与之前的图心集合距离最远，进而促成了新图心。借助该方法可以得到一个初始图心的集合，同时，该图心结果的相关节点具有特定性，还可以扩散这些图心节点，并非全部融合起来。

means然后，复杂网络中的节点主分类ϕ聚类算法进行汇聚。的计算需要借助图心集合SL同构分类集合要是通过K-C来完成。同ФsL时，将虚拟图的全部节点逐一指派至距离这一节点最短的图心上。这样就构成了SL同构的分类，

也代表了分类结果的完成。该方法较之于meansK-面，一方面是不要重复指派节点，算法有着一定的区别，大致体现在两个方另一方面是不要对图心集合进行反复计算。

本论文在图中节点展开汇聚操作的过程中，借助了节点相似度概念来处理节点的实连接问题。由于用户个体与个体所具有的相同兴趣或相似行为都可以通过节点相似度体现出来。另外，单纯地采用计算机相似连接同构进行分类，会致使分类结果过多。为了聚类操作更具有实用性与有效性，该论文主要采用实连接的方式进一步对分类结果进行优化。这也意味着，如果小分类存在结构关系的节点，那么，最终可以构成统一的大分类。该论文主要对同构的分类进行计算主要是借助节点属性来完成，对于节点的调整主要是借助图的拓扑结构加以实现。

2实验结果与性能评估

OCNVR本实验部分中采用的一系列对比算法，如据集之间进行比较。本部分将重点对相关的实算法等，主要是对真实数据集与人工数验评估结果进行全面系统地分析与阐述。2.1算法的有效性和性能评估

以真实音乐数据集为对象，通过图1（a）、图1b）展现了OCNVR和K-SNAP及SA-Cluster三类算法，主要是虚连接的分类密度与实连接的分开密度之间进行比较的结果。在这个实验中，选取K125为聚类数目，将其数值设为25，接或者是虚拟连接状态时，。根据上述两个图标可以得知，50，75，100，OCNVR当处于实连算法的密度值明显大于另外两类算法。同时，K-SNAP算法的密度值会因模型参数k的增大而呈现不断下降的趋势。

较之于SA-Cluster算法而言，OCNVR算法具有更强的稳定性，根源是OCNVR算法更加倾向于用户的相同兴趣，同时，该算法可以更好地把用户的相同兴趣节点全部归纳到分类中。另外，K-SNAP用户的个人信息，算法更加倾向于单值属性信息，如性别、年龄，以及其所处的洲特别是信息等。OCNVR算法在对自连接的子分类的具体调整过程中，充分结合了实连接的相关信息，可以有利于处于实连接状态下，不断提高密度

（132科技（a）实连接的分类密度

（b）虚连接的分类密度图1真实数据集中的分类密度Fig.1Classificationdensityofrealdatasets

图2真实数据集中的程序运行时间Fig.2Programrunningtimeforrealdataset

值。根据示例图不难得知，

如果对实连接与虚连接两者的密度值加以考虑，可以发现，其数值十分接近。从实验结果可以发现，一些用户存在好友关系时，对某一事物有着相同的爱好。

SA-Cluster图2主要列举了OCNVR和K-SNAP以运用于真实数据集中所需的程序运行时间进行三种算法，并且逐一对上述算法具体及了详细说明。在真实数据集上，如果分类数目K

通报第33卷

已确定的情况下，OCNVR算法明显要比其他两

种算法的程序运行效率要大。该论文所采用的算法首先需要进行EL同构分类，然后是对虚拟图的计算，通过内存将算法经常使用的节点相似度进行保存，这样有助于缩短节点相似度所耗费的计算时间。值得注意的是，如果虚拟图的密度进行计算的过程中，该论文再次对已经保存的密度结果进行利用，也意味着OCNVR算法的运行性能需要重新加以改进。该文中采用的ClusterSA-这一算法具有的迭代优化计算法对聚类的质量算法是对比算法的一种，从图1不难发现，起到了优化作用，可是，较之于另外两种算法，需要付出更大的代价。参考文献：

[1]侯阿临，缩方法[J].吴亮，吉林大学学报理学版，廖庆，等.计算全息图的小波神经网络压2015，53(4):725-729.[2]计算机工程与应用，曾旭斌，原玲.基于多维标度的动态网络选择算法2014，50(1):83-86.

[J].[3]李栋，计算机学报，徐志明，2014李生，，37(1):189-206.

等.在线社会网络中信息扩散[J].[4]

GharibpoorTransactionsM，AllamehonKnowledgeSM.Online&DataSocialEngineeringNetwork[J].[5]2012IEEECheng，25(3):662-676.

，

Graphs:H，ZhouY，YuJX.ClusteringLargeAttributed

larities[J].ABalanceJournalofbetweenInformationStructuralProcessingandAttribute，2011，Simi⁃5(2):[6]Chen806-813.

sionalC，frameworkYanX，ZhuforF，graphetal.Graphdataanalysis[J].OLAP:amulti-dimen⁃[7]andChenInformationlineC，YanX，SystemsZhuF，，et2009al.，Graph21(1):41-63.

KnowledgeOLAP:TowardsOn⁃[8]

TianAnalyticalgraphY，HankinsProcessingRA，PatelonGraphs[J].J2008:103-112.

Conferencesummarization.[C]//onManagementACMM.EfficientSIGMODaggregationInternationalforcouver，Bc，Canada，June，2008:567-580.

ofData，SIGMOD2008，Van⁃