设计 任务书 论文 开题 答辩 说明书 格式 模板 外文 翻译 范文 资料 作品 文献 课程 实习 指导 调研 下载 网络教育 计算机 网站 网页 小程序 商城 购物 订餐 电影 安卓 Android Html Html5 SSM SSH Python 爬虫 大数据 管理系统 图书 校园网 考试 选题 网络安全 推荐系统 机械 模具 夹具 自动化 数控 车床 汽车 故障 诊断 电机 建模 机械手 去壳机 千斤顶 变速器 减速器 图纸 电气 变电站 电子 Stm32 单片机 物联网 监控 密码锁 Plc 组态 控制 智能 Matlab 土木 建筑 结构 框架 教学楼 住宅楼 造价 施工 办公楼 给水 排水 桥梁 刚构桥 水利 重力坝 水库 采矿 环境 化工 固废 工厂 视觉传达 室内设计 产品设计 电子商务 物流 盈利 案例 分析 评估 报告 营销 报销 会计
 首 页 机械毕业设计 电子电气毕业设计 计算机毕业设计 土木工程毕业设计 视觉传达毕业设计 理工毕业论文 文科毕业论文 毕业设计资料 毕业设计论文流程 
垫片
您现在所在的位置:首页 >>理工毕业论文 >> 文章内容
                 
垫片
   我们提供全套毕业设计和毕业论文服务,联系点击这里给我发消息   914298682   
多原型表示的基于相似性社区检测方法
文章来源:www.biyezuopin.cc   发布者:学生毕业作品网站  

多原型表示的基于相似性社区检测方法

摘要

在社交网络中社区对于理解图型结构非常重要。一些现有社区检测算法使用单一原型来代表每一组。在真正的应用程序中,这对于不同类型的社区可能是不适当的建模,因此限制了在社交网络上的聚类性能。为了解决这个问题,我们在这里提出了一个基于相似性多原型(SMP)社区检测的方法。 在SMP中,在每个社区中的顶点携带不同的权重来描述他们的代表程度。这个机制,使每一个社区由不止一个节点来体现。节点的中心用来计算原型权重,而相似性是用来指导我们将图型分区。在生成计算机和现实世界的网络中实验结果清楚地表明,检测社区时SMP表现良好。此外,该方法可以提供更丰富的信息, 是在原型重量与现有的社区检测模型比较的帮助下,来发现社区的内部结构。

1.介绍

为了在现实世界网络系统的组织和功能上有更好的理解,图中的群落结构是一个主要特性,它应该被纳入考虑[1]。因此,社区检测,可以从复杂的网络中提取特殊的结构, 从物理、生物和经济学到社会学,跨越许多领域引起了相当大的关注[2,3],在系统中通常表示为图。一般来说,一个社区在网络中是一个子图,它的节点与它本身是紧密连接的,而与其他网络是稀疏连接的[4-6]。

最近,在这一研究领域提出了一些取得的重大进展和流行的社区检测算法。最受欢迎的经典方法之一是通过优化某些标准来进行网络分区。纽曼和Girvan[7]提出了一个网络模块化测量方法(通常用Q)和几个算法,试图最大化此方法 [8 -10]。但是最近的研究发现,基于模块化的算法不能检测到小于一定规模的社区。这个问题是有名的分辨率限制[11]。单一的优化标准,也就是说,模块化,可能在复杂网络结构中表示的并不恰当,从而Amiri 等人[12]提出了一个新的社区检测过程例如一个多目标优化的问题。另一个组的方法考虑分层聚类技术。显示合并或拆分集群拓扑测量的节点之间的相似性,并试图建立一个分区分层树[13-18]。也有一些方法,如光谱方法[19]和信号处理方法[6 ,20], 将拓扑关系图中的节点映射到n维欧几里得空间向量的几何结构,经典的类聚方法类似于经典的C均值方法(CM)[6], 模糊c均值算法(FCM)[5,20]或证据理论c均值算法(ECM)[21]可能被诱发。然而,在映射过程中必然有一些信息丢失。此外,这些基于原型的分区方法的本身对初始种子是敏感。对于社交网络而言良好的社区结构是基础,一个群体的中心可能是一个人,他们在社区中扮演领导者的角色。也就是说,像种子一样小组的成员之一是更好的选择,而不是所有对象的中心。

为了要解决这些问题, Jiang 等人[6]提出了一个名叫 k档位的高效算法,这种算法选择最高的节点中心值作为原型。在我们以前的工作中,一个证据中心性测度用于设置一个“最可能的”对象,即在类中作为原型[22]。我们相信每个社区的原型的特征是非常重要的社区检测。然而,在某些情况下只使用一个节点的方式来描述社区可能是远远不够的。为了说明一个原型的限制社区表示,我们使用两个简单的社区结构如图1所示。第一个社区由四个成员组成而第二个社区有八个成员。可以看出,在左边的社区,用小组中的四个节点中任何一个来描述集群结构都是不合理的,因为这四个节点中没有任何一个可以被看作比其他三个更具有代表性。在图1中正确的社区,两名成员(黄色标记)在八个节点中是具有对等性的,合理的被选择作为社区的代表。这意味着选择他们中的任何一个可能无法完整的检测到所有候选代表节点。从这些例子中,我们可以看到,对于一些网络,为了捕捉社区的各个方面的结构,我们可能需要更多的成员,而不是一个在个人组中被称为原型的事物。

出于这个想法,在本文中提出了一个基于相似性的多原型(SMP)社区检测方法。中心值作为标准选择多个原型来描述每个社区,并且原型重量被推导为自己的社区来描述相关对象的代表性程度。然后每个节点和社区之间的相似性被定义了,根据这些相似之处,节点被划分为若干个小的社区。在这里,我们强调一些,在此工作中与早期研究和贡献不同的关键点。首先,尽管这里有一些,在经典数据集中的多原型集群方法[23,24],但是几乎没有对社区检测问题的探究。在这里提出了一个新的使用多原型的社区表示机制。实验结果在人工和实际网络中显示,多个原型比一个社区代表中心更强大,特别是对于没有清晰的社区结构的图像而言。其次,提出了原型权重的概念,描述了一个成员在自己小组的代表性程度。借助原型权重,SMP为每个社区提供更充分的描述。这使我们能够深刻了解一个社区的内部结构,我们相信这对于网络分析是非常重要并且很有用的。第三, 在该社区检测方法中,也可能采用不同的相似度和中心的措施,这可以使得它在实际的应用程序中更实用并且更灵活。

本文的其余部分组织如下。在第二节,简要的介绍了一些基本概念和方法的基本原理。在第三节,详细的介绍了多原型社区的检测方法。为了显示我们的方法的有效性,第四节我们在不同的人工和现实网络中测试我们的算法,并且与现有的方法进行比较。最后,我们在第五节得出结论并提出一些观点。

2.基础知识

在本节中与社区检测问题和社交网络相关的一些背景知识,包括中心和相似性度量,模块化和一些存在地经典算法,将会提出。

2.1 节点中心和相似

一般来说,一个代表社区的中心的人,在一个社交网络具有以下特点:他与大多数的组和成员有联系,并且关系比平时更强,他可以直接与其他人联系,这些人在自己的社区也发挥着重要作用。因此,社区的中心的设置应该不仅考虑其深度和重量,也应该同时考虑与中心相邻的部分的深度和重量。节点的深度是与其他节点的连接的数量,重量是用来描述这些连接的程度。Gao 等人[25]提出了一个基于证据中心的方法,名为Semi-local证据中心(ESC),是基于信念功能的理论。在ESC的应用中,每个节点首先通过基本信念任务(BBA)来表达它的程深度和重量,然后使用理论信念函数的组合规则来计算融合重要性。ESC值越高,节点越重要。Gao 等人[25]指出,这是比现有的中心措施更有效的方法,例如 学位中心(DC)、介数中心(BC)和亲密中心(CC)。ESC的细节计算过程可以在[25]中找出。

在图片中相似性措施中的任何一对节点之间都有着密切的联系。[26]在这几个节点描述了基于本地信息的相似性度量,以及 ,讨论了不同措施应用在集合检测上的表现。这里我们给出一个简短描述的一些措施。令G(V,E)为一个无向网络,V是N个节点的集合,E是m集的边缘。令表示邻接矩阵,其中表示节点i和j之间有一个边缘。

(1) 共同的邻居。这种方法是基于这个想法,更常见的一对共享邻居,他们更相似。因此,相似性可以简单的与他们共同的邻居的数量成正比:

                           (1)

其中表示相邻的顶点集x。

(2)Jaccard指数。Jaccard提出的这个指数在一百多年前,被定义为:

                              (2)

zhou-lv-zhang指数。Zhou 等人[26]还提出了一种新的出于资源分配过程的相似性度量:其中d(z)是节点z的度。

 ,                    (3)

Pan 等人[27]指出,Zhou等人提出的相似性度量[26],在网络社区检测中可能导致不准确的结果,因为度量标准不能区分一对节点之间的紧张关系是直接相连还是间接相连。为了克服这一缺陷,在他提出的新的测量方法中,无关对的相似度仅设置为0:

   (4)

相似度度量考虑了Hu等人[20]提出的整体图结构,在网络中是基于信号传播的。例如在一个网络中有N个节点,每个节点都被看作是一个易兴奋的系统,它可以发送、接收和记录信号。最初,选择一个节点作为源的信号。然后源节点首先向它的邻居和它本身发送一个信号。后来,节点的信号也能对自己和他们的邻居发送信号。在一个特定的T时间步骤内,覆盖节点的分布信号数量可以被视为在整个网络中影响源节点的因素。当然,与其他社区的节点相比,在整个网络中同一社区的节点有更多相似的影响。因此,节点之间相似之处,可以通过计算他们收到的信号数量之间的差异来获取。

2.2 模块化

最近,许多评价标准提出了对网络的分区进行评估。一种广泛使用的测量称为模块化、或由纽曼和Girvan[7]提出的Q函数。令表示一个无向网络,V是N个节点的集合,E是边的集合,W是一个N * N边的权重矩阵的元素给定一个硬盘分区与K组,如果顶点属于集合则是1,否是0。用表示K的顶点子集,然后这种模块化可以被定义为[1]:

            (5)

虽然Fortunato和Barthelemy [11]声称基于模块化划分方法的有局限性,但是Q措施仍在实践中被证明是非常有效的社区评价。此外,还在Newman的模块化中发现一些其他问题[28]。为了解决这些问题,我们还提出了一些新的模块化措施[28.29]。在这里列出了Chen等人[28]提出的最大-最小(MM)模块化功能,是利用索引来确定最优数量的社区。MM模块化试图,最大化组内边总数,同时,在组内最小化来自用户定义的非关联设定的非关联对的数目:

                  (6)

其中是Q模块化的原始图,虽然是图的补充部分,图创建基于用户定义的标准M,它定义了两个断开连接的节点i和j是否相关,当属于M是相关的,当不属于M时是不相关的。也就是说如果不属于E和M时是属于的。这对相关组M,可以由专家给出,或者根据原始结构来定义。

2.3 一些集合发现的经典方法

在第四节我们将对提出的该算法与现有五个方法进行比较,现有的五种算法包括:k档位算法[6],多层次模块化优化算法(MMO)[8],主要特征向量(LE)算法[30], 标签传播(LP)算法[31],和信息地图(InfoMap)算法[32]。因此在这里我们对这五种方法进行一个简短的陈述。

多层次模块化优化算法MMO是基于模块化优化的启发式方法,并且该算法分为两个阶段,并且不停地重复。在第一阶段的开始,网络被认为有N组,每组只有一个节点。然后每个节点i, 可能被放置到一个新的社区(这个社区必须包括一个它的邻居)可以获得最大的模块化。如果实现模块化没有进一步的提升,那么第一阶段是没有完成的,。第二阶段包括建立一个新的网络,网络中的节点是在最后阶段的社区发现,然后第一阶段可以被这个新创建的图重新运用。Blondel等人[8]指出,MMO就计算时间而言超过所有其他已知的社区检测方法。

纽曼[30]表明,模块化可以简洁地表示为,一个函数的特征值和特征向量,以及使用竞争性的LE算法识别集合。此图首先分为两组,根据元素的迹象将模块化矩阵最积极的特征值来对应特征向量,然后可以根据类似的需求将其分割成更多的集合。这个方法显出,当非限制要找到任何特定大小[30]的小组时,主要特征向量算法LE比标准光谱分区方法更好。

Raghavan等人[31]研究了标签传播算法LP,它只利用网络结构,既不需要一个优化的预定义的目标函数,也不需要集合的预先信息。在这个模型中每个节点利用一个独特的标签进行初始化。然后每个节点采用它的大多数邻居的目前的每一步作为标签。在这个迭代过程中小组中的节点紧密相连,在形成集合独特的标签时形成一个共识。

信息地图算法InfoMap在真实的系统中 在网络上使用随机步伐的可能性流作为信息代理,图聚类然后转变成寻找最小化表示无限步伐长度[1]的问题。网络是通过压缩所需的信息来描述扩散在整个图中的信息从而分解成最优模块的[32]。群落结构的规律和他们的关系是通过地图来反映的。

k档位算法是由Jiang等人提出的[6],它与K-means算法相似,使用一个替代的迭代策略。首先, K节点的顶部也就是最高等级中心被选为初始种子。这种初始化机制可以克服随机初始中心带来的问题,在应用程序中基于原型的聚类方法与k-means算法相似。然后种子和集群标签通过使用迭代技术进行更新交替。如之前所示的方法,选择K代表成员,他们彼此可以完全代表一个个人的集合,但可能不足以完全描述一个集合。这反过来表明,多节点被用来捕获网络中组,会更准确。

3.多原型集合检测方法

在这里建议使用我们的方法。之后在3.1节引入代表权重的概念(也称为原型权重),整个算法将在3.2节中详细介绍。确定最优集合的数量和复杂性算法的问题将分别在3.3和3.4节中讨论。

3.1 原型权重

假设是图的一个分区, 是一组节点,是一组边的集合。图中的个节点可以用来表示。矩阵表示个节点对应所有个集合的原型权重。在分析之前,一个节点的中心价值可以用来表达节点在它的集合中扮演中心角色的信仰。因此,节点j在代表性集群的概率重量程度可以推导如下:

  (7)

其中是在子图中相应的社区中的节点的中心。然后,给出一个节点、  和社区之间的相似性可以用来表示,如下得到

                            (8)

其中是节点之间的相似点,来自Eqs。从方程式。在公式(7)、(8)我们可以看到是节点和社区内所有节点之间相似性的权重之和,并且使用的权重总和,依赖于节点对他们自己的社区的贡献。

3.2检测算法

整个SMP算法来检测社交网络集合将在算法1中进行总结。事实上SMP是一个变动的k - means, K-medoids和k档位聚类算法。SMP和其他三个聚类算法的区别在于更新原型的方式不同。k – means算法使用平均值来表示每个类,而K-medoids和k档位聚类算法使用一个“最可能的”对象来表示类。相反,SMP采用一个有效多原型代表,基于小组中的每个成员的原型权重。由于集合结构的类型繁多,表示集群的方式运用了多原型,这使在实际的应用程序中更为合理。此外,SMP往往比k - means需要更少的迭代来使算法趋于一致。

备注:如我们所见,SMP提供给我们一个脆(硬)分析网络的分区。节点和社区 之间的相似性可以通过Eq来获得(8),节点的成员对社区可以如下定义:

           (9)

通过FCM算法获得的这种形式的成员方法是成线性的,其中成员值分配给一个对象,与集群的相对距离是成反比的。同样的,相对相似性取决于属于Eq(9)的成员。已经报导的模糊成员问题之一是,它不能区分“平等的证据”(成员值大、平等的替代品)和“无知”(所有成员的值是相等的,但非常接近于零)[33,34]。如果节点和其它点之间是等距的

算法1:基于相似性多原型(SMP)集合检测算法

输入: ,集合的数量; 邻接矩阵; ,权重矩阵(如果有的话); ,迭代的最大数量。

初始化:

(1)选择节点的最高中心作为初始原型。

(2)计算图中任意两个节点之间的相似性矩阵。

(3)提取节点和原型之间的相似性矩阵。分区的节点放入最近的原型所属的集合,并得到的初始类图: 

重复

(4)更新矩阵来记录节点的原型权重,使之成为使用Eq的基于当前隔离的集。

(5)用Eq.(8)计算节点和集合之间的相似性,然后将集群顶点和每个属于集合的节点最类似的点放入集合。

直到所有探测到的集合值不再改变或迭代的次数成为最大值

输出:每个节点的成员数和每个集合所有成员的原型重量。

和一个集合相比, 无论集合相似性的绝对值怎样,每个集群成员数将是相同的。因此,模糊成员不能应用于检测噪声对象(异常值),这些异常值虽然远,但是与一些集合等距[34]。在SMP中,原型权重可以帮助我们解决这个问题,我们将在4.2节详细展示。

3.3 确定社区的数量

在SMP算法的第一步,关于集合()数量的额外信息应详细说明。这也是古典CM和FCM聚类中的一个基本问题。事实上, 为基于原型的聚类方法确定最优数量的集群是一个开放的问题。大部分的方法来解决这个问题在于计算有效性指数,计算是从几个集合结构发现不同的值和寻找一个给定标准的最小值或最大值[5,20,35]。在这里MM模块化 (Eq.(6))是用来估计一个适当的值。模块化值表示检测到集合的质量。当模块化达到最大时,我们可以得到最好的

3.4 SMP算法的复杂性

SMP的复杂性由计算相似性和中心节点的迭代的过程组成。如果我们使用信号相似性和证据semi-local中心措施,正如我们在第四节将看到的,相应的时间复杂度[20]和[25],其中c是传播的数量, 是网络中顶点的平均程度,N是节点的数量。迭代技术类似于k – means中方法。唯一的区别是更新原型的策略。k - means计算集群中的所有成员的平均值,而SMP试图找到所有成员的原型重量。随着集合子图远小于原始网络,SMP的原型权重的更新过程并不会耗费很多。如果集合K中的元素数量是固定的,K - means聚类算法的时间复杂度是,其中t是迭代的数量。因此,SMP的总复杂性是。值得注意的是,SMP通常需要更少的迭代。

4.实验结果

在本节中的一些实验是在计算机生成的图形和真实的网络条件下执行的,社区的结构是预先已知的。除了k档位[6],我们也比较SMP和其他四个经典方法:多级模块化优化算法(MMO)[8],主要特征向量(LE)算法[30],标签传播(LP)算法[31],信息映射算法(InfoMap)[32],在2.3节中已给出。已经获得的社区结构通过已知的绩效措施来评估,也就是说,准确性和NMI(相互规范化信息)。当在社区中得到了基准和用在文章中的真实数据设定,准确性和NMI测量了,计划隔离(地面实况)和算法的结果之间的相似性。图中A和B两个分区的NMI,I(A,B),可以通过以下公式计算

    (10)

其中分别表示社区分区A和B的数量。符号表示矩阵的元素,代表i社区的A分区出现在j社区的节点数量,矩阵N的的行i总和表示为,列j的总和表示为。准确性和NMI测量节点正确分组的比例,并代表发现社区结构和假设之间的一致性,[20,36]。对不同的相似性和中心性测度在SMP应用中的影响,将在第一个实验中讨论。之后,我们将基于实验结果,使用证据semi-local中心性和信号相似性在接下来进行测试。

4.1 计算机生成的图形

算法首先通过两类生成的人工基准网络对比,也就是Girvan和Newman[3](GN)和Lancichinetti等[37]基准(LFR)网络。对于前者,每个网络总共有N = 128个节点, 四个划分的集合中每个有32个节点。每个顶点的平均度设置为16。对于一个给定的节点, 在集合内部链接到它的同伴的平均数量,用来表示,在8 – 16之间变化。社区之间边的平均数量,用来表示,在8 – 0之间变化。的值更大,表示网络的集合结构更加明显。

但值得一提的是,在应用程序中SMP算法,本文建议,不同的相似性和中心性测度可以被采用来代替信号相似性和证据semi-local的中心。当使用ESC来计算中心值,有四种不同相似性度量的结果,即信号相似性,简单Jaccard指数以及Pan等人[27](图中用Pan来表示)和Zhou等人[26](图中用Zhou来表示)提出的测量结果,如图2-a所示。从图我们可以看到,信号相似性的结果比其他就NMI值而言的指数结果更好。在这里我们可以得出这样的结论:全局相似性措施比如信号的相似性,比局部的相似性更适用于SMP。图2-b描述了当中心性测度不同,但相似性指数(信号)相同时SMP的行为。可以看出,ESC和PR在四个措施之间是更好的,即,ESC, PageRank(PR)[38],学位中心(DC),亲密中心(CC)。虽然在ESC和PR之间没有显著的差异,但是ESC的性能比PR更稳定。本文并没有集中比较相似性和中心性测度的不同,因此在接下来的实验中我们只考虑信号相似性和证据semi-local中心。

对于每个,实验重复20次,评估测度的平均值被记录。通过精确性和利用SMP的NMI还有其它五种算法的计算出的指数的平均值,显示出不同的值,分别在图3-a和图3- b中列出。结果表明,当的值大时,就准确性和NMI而言所有方法表现的都很好。然而,当小于10,他们有不同的表现。LP和InfoMap的结果最糟糕,因为他们在< 10时不能工作。SMP和MMO在所有方法中是最好的。尽管当= 11 和= 12时MMO优于SMP,但优势并不明显。当小的时候(特别是= 8时),SMP比MMO有明显的优势。此外,随着的减小,SMP的性能并不会像在其他方法中那样急剧下降。这演示了,不论网络是否有清晰的集合结构,使用多成员和各种原型权重能够更精确地描述群的结构,进而有助于产生一个高质量的图分区。

LFR基准网络[37]是一个为社区检测提供的虚拟网络,它声称在真实的网络中处理一些基本的统计特征,如异构程度和社区大小的分布。在三种不同的LFR网络(1000,2000和5000节点)方法的结果,分别在图4–6中展示。图中在x轴中说明的参数,在 图形识别中网络是否有明确的社区。当很小,图表有很好的社区结构。在这种情况下,几乎所有的方法都表现很好。但我们可以看到,当很大,SMP的结果比NMI的值相对较大,SMP的性能和k档位不会像在其他方法中那样大幅下降。SMP方法略优于k档位,特别是当 很大时,这可能归因于社区的多原型代表。总的来说,从两种类型的基准来看,无论他们是否有清晰地社区结构,SMP更适合于网络。

4.2 现实世界的网络

A. Zachary的空手道俱乐部。对应用于现实生活网络被提议的方法的有效性进行评估,我们第一次测试在一个广泛使用集合检测为基准的结构,“空手道俱乐部”[39],是由韦恩·扎卡里研究的。这个网络由34个节点和78条边组成,代表了俱乐部的成员之间的友谊。在开发期间,俱乐部的管理员和指导员之间出现争执,导致最终俱乐部分裂成两个较小的俱乐部,分别集中围绕管理员和指导员(参见图7-a)。

模块化的值和不同数量的集合,在图7-b中显示。当K = 2时是模块化函数的峰值。这是与网络有两个组的事实一致的。已经发现的集合在表1中说明。表1也显示了在每个发现组中的原型权重。正如我们看到的,节点1对集合1做出了大部分贡献,而集合2中最重要的是节点34。这证实了两个人在自己的集合中的中心角色。相反,节点17 和节点25在他们的组内看起来并不是很重要,就他们的原型权重而言。我们可以看到,在图7-a中,这两个节点定位在边缘部分。因此,被提议的SMP检测方法在原型权重的帮助下,可以使我们更好地理解图的结构。

B.空手道俱乐部网络添加了一些嘈点。在该测试中,两个嘈点被添加到空手道俱乐部原始的网络中(见图8-a)。第一个是节点35,与节点18,节点27直接相连。另一个是节点36,与节点1和节点33相连。可以看出,节点36和两个集合的连接关系比节点35更强。这是由于一个事实,即这些节点连接到节点36时,在他们自己的群组中扮演了领导角色。但节点35与两个边际节点连接,这两个边际节点在他们的组中只扮演者“小”或无关紧要的角色。模块化的数值随着不同的集合数变化,这一过程在图8-b中描述,检测结果在表2中显示。

从表2可以看出,节点35和36的模糊成员值对于两个集合几乎是相同的 (近似等于0.5)。这些结果不能反映未知性和不确定性的区别。作为节点35在每个集合中只与一个向外的节点相连,因此我们对集合的真的归属是未知的,或者我们可以说节点35是个例外。相反,节点36与两个集合中的关键成员(社区中扮演了重要角色)相连。因此存在不确定性,而不是节点36属于哪个集合的未知性。在这个网络中,节点36是这两个集合的 “好”成员,而节点35是“差”成员。正如之前所提到的,无法区分来自不确定节点的离群值,和相等成员归因于用于模糊成员中的相对相似性。在SMP中,原型权重可以用来解决这个问题和检测离群值。如表2所示,节点35的原型权重是在集合中最小的,但节点36的贡献远远超过节点35。因此,节点35对这两个集合没有贡献(节点35对集合1的原型权重是0.0052,对集合2的原型权重是0),它可以被认为是一个异类。这个例子进一步说明了这一事实,原型权重确实能够使我们更好地理解图型结构,特别是在网络中检测异常值。

在其他四个实际图型中,也对我们的方法进行了测试:美式足球网络,海豚网络,Lesmis网络和政治书籍网络[1]。两个指标值,准确性和NMI,用于评价不同方法的性能,分别在表3和表4中列出[2]。从表中可以看到,在大多数情况下,SMP应用结果在集合结构中精准度最高。就NMI性能测量而言,SMP也优于其他算法。应该注意的是,一些方法为分区提供的是高精确度,低NMI。这可能是由于这样的事实:他们聚集节点到太多小的集合。k档位和SMP的分区规则是基于节点相似性。一般来说,这两种方法比其他更好,有效性可以归因于顶点相似性的高性能。但原因是,SMP比k档位在真实网络中工作的更好,主要是因为多原型表示集合的应用。从上面的大量实验结果,我们可以总结SMP引人注目的属性如下:

1)在分区过程中,SMP使用多个原型代表集合。这是一个有用的扩展现有的集合检测方法,其中只能允许一个原型,尤其是分析的图型有一些复杂的群结构。

2)原型权重,作为副产品的检测结果,从另一个角度,为我们提供一些关于群落结构的有价值的信息,并且能够使我们能够更好地理解图型分析。

3)SMP甚至在没有明确的集合结构的情况下,可以很好的工作。它可以避免这样的问题,即无法为模糊成员从不确定数据中区分离群值。

4)最后,实验在合成和真实图像数据进行论证,为其拟定的方法是,为集合检测任务竞争的候选者与现有的五种方法作比较。

[1]这些数据集可以在网址http://networkdata.ics.uci.edu/index.php中找到

[2]这些真实的图形都是已知的集合结构,因此,准确性和NMI基于地面真理计算,分区根据不同的算法得到。

5. 结论

在本文中,提出了一种新型的基于相似性集合检测的算法称为SMP。SMP能找到不仅每个节点的社区,而且加权代表每个小组的成员。在现实世界的集合检测问题中,集合标签的信息和每个检测到的 集合的内部结构信息都是重要的。该方法的一个独特的特征是,每个集合通过多原型提出,而不是由一个单一的对象提出。合成网络的实验显示了,该方法的有效性和对实际的网络测试,进一步指出我们的方法比现有的方法完成的更好。使用原型权重的结果表明,集群可以支持SMP更准确和更完全的捕捉各种类型的集合结构,因此提高了集合检测的质量。此外,发现集群更详细的信息可以在原型权重的帮助下获得。

在实际应用中,信号相似性测量和ESC中心性在工作中的运用,可以换成其他的指数。例如,如果我们想将此方法应用于指导网络,相似性和中心措施在指导网络中可以采用。因此,我们打算研究,对不同措施和指导网络在我们未来研究的工作中的应用进行比较。与此同时,不仅中心性还有更多其他的因素应该考虑,来决定原型权重。因此优化原型权重的方式尽可能地利用可用的信息,也将包含在我们的进一步研究中。

鸣谢

作者感谢匿名审稿人,是他们的评论,帮助我们澄清和提高文章的质量。这项工作得到了国家自然科学基金(Nos.61135001,61403310)的支持。这项研究的第一作者在法国得到了中国奖学金委员会的支持。

  全套毕业设计论文现成成品资料请咨询点击这里给我发消息914298682      返回首页 如转载请注明来源于www.biyezuopin.cc  

                 

打印本页 | 关闭窗口
本类最新文章
asp.net+SQL Serv 一种新型高效的重复文件删除系统H 房屋中介企业管理系统的设计与实现
浅谈屋面卷材防水施工 能源和建筑概述 建筑物的地震减灾
| 关于我们 | 友情链接 | 毕业设计招聘 |

Email:biyeshejiba@163.com 在线QQ: 点击这里给我发消息  914298682 学生毕业作品网站  
本站毕业设计毕业论文资料均属原创者所有,仅供学习交流之用,请勿转载并做其他非法用途.如有侵犯您的版权有损您的利益,请联系我们会立即改正或删除有关内容!
蜀ICP备10201305号-4