>> 社区发现算法GN算法
社区发现算法GN算法
所属分类：
下载地址：
GN.rar文件大小：1.31 MB
分享有礼！ 》
请点击右侧的分享按钮，把本代码分享到各社交媒体。
通过您的分享链接访问Codeforge，每来2个新的IP，您将获得0.1 积分的奖励。
通过您的分享链接，每成功注册一个用户，该用户在Codeforge上所获得的每1个积分，您都将获得0.2 积分的分成奖励。
GN算法是一个经典的社区发现算法，它属于分裂的层次聚类算法，最初，由Michelle Girvan和Mark Newman提出。其基本思想是不断的删除网络中具有相对于所有源节点的最大的边介数(ege betweenness)的边，然后，再重新计算网络中剩余的边的相对于所有源节点的边介数，重复这个过程，直到网络中，所有边都被删除。
Sponsored links
源码文件列表
温馨提示： 点击源码文件名可预览文件内容哦 ^_^
38.00 B16-05-11 16:18
GN.bsc417.00 kB12-05-11 19:06
GN.exe596.07 kB12-03-14 11:51
GN.ilk817.72 kB12-03-14 11:51
gn.obj519.63 kB12-03-14 11:51
GN.pch3.21 MB16-07-13 10:46
GN.pdb1.16 MB12-03-14 11:51
&gn.sbr&0.00 B12-05-11 19:06
vc60.idb121.00 kB12-03-14 11:51
vc60.pdb196.00 kB12-03-14 11:51
1.04 kB28-03-13 10:42
483.00 B17-05-11 14:09
54.00 B23-04-11 08:48
215.49 kB01-04-11 13:44
13.03 kB17-05-11 14:16
10.80 kB12-03-14 11:51
GN.dsp4.20 kB04-04-11 21:23
GN.dsw529.00 B04-04-11 21:23
GN.ncb65.00 kB12-03-14 11:52
GN.opt55.50 kB12-03-14 11:52
GN.plg1.25 kB12-03-14 11:51
914.00 B12-03-14 11:47
175.00 B25-05-11 16:37
&Debug&0.00 B12-03-14 11:51
&GN&0.00 B12-03-14 11:52
（提交有效评论获得积分）
评论内容不能少于15个字，不要超出160个字。
评价成功，多谢！
下载GN.rar
CodeForge积分（原CF币）全新升级，功能更强大，使用更便捷，不仅可以用来下载海量源代码马上还可兑换精美小礼品了
您的积分不足，优惠套餐快速获取 30 积分
10积分 / ￥100
30积分 / ￥200原价 ￥300 元
100积分 / ￥500原价 ￥1000 元
订单支付完成后，积分将自动加入到您的账号。以下是优惠期的人民币价格，优惠期过后将恢复美元价格。
支付宝支付宝付款
微信钱包微信付款
更多付款方式：、
您本次下载所消耗的积分将转交上传作者。
同一源码，30天内重复下载，只扣除一次积分。
鲁ICP备号-3 runtime:Elapsed:100.709ms - init:0.1;find:0.7;t:0.5;tags:0.4;related:48.4;comment:0.2; 27.69
登录 CodeForge
还没有CodeForge账号？
Switch to the English version?
^_^"呃 ...
Sorry!这位大神很神秘，未开通博客呢，请浏览一下其他的吧基于密度分布的社区发现算法研究-论文发布
&&&&&|&&|&&&|&&|&&|&&|&&|&&|&&|&
作者：　发布时间：　来源：　
要： 基于密度吸引点和其对相邻节点的影响度，提出了一种密度分布社区发现算法。该算法以节点度数最大的密度吸引点为初始社区，访问社区的相邻节点，把对社区影响度最大的节点加入到社区中，如果有些节点对多个社
摘& 要： 基于密度吸引点和其对相邻节点的影响度，提出了一种密度分布社区发现算法。该算法以节点度数最大的密度吸引点为初始社区，访问社区的相邻节点，把对社区影响度最大的节点加入到社区中，如果有些节点对多个社区都有影响，则把它归属为影响度最大的那个社区中，同时如果两个社区之间的相互影响度很大，可以将这两个社区合并为一个社区。将该算法应用到Zachary空手道俱乐部网络和随机无标度网络中，实验表明该算法能够很好地分出网络中的社区，同时实验还发现社区的收敛速度与幂率分布特性近似成反比。 &关键词： 复杂网络；幂率分布；社区发现；密度分布；影响度 所谓社区，是指具有共同兴趣、爱好的人或者学有专精的专业人士，通过一定的方式聚集在一起，彼此之间可以沟通、交流、分享相关信息。在现实世界中，存在着很多这样的社区，例如社会关系网络[1]、神经网络、食物链网络、城市交通网络等。在这些社区中，有着复杂的内部结构，用节点表示实体，用连线表示实体间的联系，社区内部节点之间的联系非常紧密，社区之间的联系相对稀疏。近几年，随着网络的急速发展，网络社区也成为一个研究热点，同时取得了很重要的进展，并且发现了网络社区的很多特点，其中包括小世界特性(即网络中节点之间的平均距离很短，对数依赖于网络中的节点数)、无标度特性(即网络中节点的度分布右偏斜，具备幂函数或指数函数的形式)、聚集性或网络传递性以及社区结构特性，大量实证研究表明，许多网络是异构的，即复杂网络不是大批性质相同节点的随机连接，而是许多类型节点的组合，其中相同类型的节点存在较多的连接，而不同类型节点的连接则相对较少。把同一类型节点以及这些节点之间的边所构成的子图称为网络中的社区。社区如图1所示，图中的小型网络中包含3个社区，对应图中的3个椭圆，在这些社区内部，节点与节点之间的联系非常紧密，而社区之间的联系则比较稀疏[2-4]。
&&& 网络社区发掘对于了解网络结构和分析网络特征具有重要的意义，目前已经提出了具有基于节点集划分的社区发现算法，例如基于贪婪算法原理的Kernighan-Lin算法、基于谱思想的谱平分算法、基于分裂思想的GN算法和基于凝聚思想的Newman快速算法等[5-7]。网络社区发现的最终目的就是将网络划分为若干个互相独立的社区，这些算法对研究社区发现都产生了重大的影响。 1 算法设计 && &由于网络社区中节点之间的联系相对紧密，社区之间节点的联系相对稀疏，根据这一特性，本文提出了基于密度分布的社区发现算法。在实际网络中，存在一些节点与其他节点的联系非常紧密，即该节点的度最大，称为&密度吸引点&，其他节点以&密度吸引点&为中心，从而形成社区。该算法的基本思想是以密度吸引点为初始社区，然后找出对该吸引点影响最大的节点依次加入到社区，一个网络中存在可能不止一个吸引点，因此在网络中可能存在多个社区，在计算节点影响度时要考虑对多个社区的影响。直到所有的节点都被分到了各自的社区中。同时要考虑不同社区之间的影响度，如果两个社区之间的相互影响度非常大，就认为这两个社区为一个社区，则合并这两个社区。
1.2 算法描述 && &本算法中，假设社区内部度数越大则社区密度越大；密度越大的社区对其周围节点的吸引力越大；对在同一个层次即相对密度吸引点来说密度相同的节点的吸引力相同。 && &(1)初始化网络，将网络中的每个节点看成是独立的社区，计算社区的密度，每个社区的初始密度为节点的度数； && &(2)找出网络中密度最大的社区，该社区为密度吸引点； && &(3)根据影响函数，计算与密度吸引点相邻社区对密度吸引点的影响度，找出影响度最大的社区，此处认为这个社区与密度吸引点为同一个社区（影响度最大的社区可能不止一个）； && &(4)再次计算网络中所有社区的密度，此时应用密度函数进行计算，并找出密度最大的社区作为密度吸引点； && &(5)重复步骤(3)、步骤(4)，直到所有的社区都合并完成，算法结束。 && &算法流程图如图2所示。
2 算法验证 && &为了验证本算法的有效性，将本算法应用到Zachary&s Karate Club Network[9]和随机的无标度网络。实验结果表明，本算法可以将网络划分为大小不同的社区，且具有较好的效果。 2.1 Zachary&s Karate Club Network && &在复杂网络社区结构的研究中，Zachary&s Karate Club Network是经常被使用的经典数据集，它是20世纪70年代初期Zachary用了两年的时间观察得到的美国一所大学中空手道俱乐部成员的相互社会关系网络。在这个网络数据集中包含了34个节点和78条边，其中节点表示俱乐部成员，边表示成员之间的社会关系，网络结构如图3所示。
【】【】【
※ 相关信息
无相关信息
※ 其他信息
访问数：&|&
数据加载中..10379人阅读
Finding and evaluating community structure in networks&
一种新的评价社区结构的模块度研究
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：282148次
积分：3705
积分：3705
排名：第7505名
原创：130篇
转载：24篇
评论：54条
(7)(1)(2)(3)(10)(1)(11)(6)(20)(8)(6)(2)(6)(4)(4)(4)(1)(5)(10)(7)(10)(1)(11)(1)(2)(1)(1)(1)(3)(1)(2)(6)(1)(1)硕博论文网欢迎您
您当前的位置： >
> 复杂网络的社区发现算法研究
本文是工程论文，本文提出了基于聚类算法预处理的社区发现算法，首先利用社区发现算法在构建相似度后可以转换为聚类算法的基本思路，使用局部相似指标构建相似矩阵，使用谱聚类算法，
第 1 章 & 绪论&
1.1 & 研究背景及意义&
自工业革命爆发以来，计算机互联网技术得到高速发展，我们也进入了日新月异的互联网时代。正是因为它的快速发展使得整个各个国家的距离无限缩小，就如同生活在一个村庄里一样，地球村的说法也就不足为奇。当然也渐渐的发现我们衣食住行各个方面的行为活动生活都处于复杂网络之中。 我们所生活的大千世界其实都可以看成一个由若干相互作用的子系统组成的复杂系统,如果我们把子系统抽象为节点，将各个子系统间的相互影响抽象成连接节点的边,复杂系统就会演变为一个复杂网络。例如,流行病传播网和科学家协作网络，社会系统中的人际关系网、生态系统中的神经元网、基因调控网和蛋白、生物新陈代谢网、科技系统中的电话网、因特网和万维网，等等都是典型的复杂网络。复杂网络根据评判标准的不同可以划分为结果也是不一样的，如果参考边的权重值为标杆,复杂网络可以分为无权复杂网和有权复杂网。鉴于前网络中的边的方向性,复杂网络可以分为有向网络和无向网络。此外，假如以社区是否有重叠的标准,复杂网络则可以看成是重叠社区网和非重叠社区网组成的交叉混合的大型复杂网络。当然我们也可以综合网络拓扑机构、节点的归属度、边的全权重值等各个方面信息对复杂网络进行归类处理,从而产生了一类结构和内容更加复杂的异质型网络。例如，很多在线的社交门户网络新浪微博网络、知乎论坛、校内网、Facebook 等都是典型的异质型网络,在这些网络中,节点的定义更抽象、内容也更广泛。与此同时，网络的边代表的内容也千差万别，甚至可能是通过综合分析各种指标后的计算参考值。总之,复杂网络的研究为我们探索生活中各个实体网络提供了新方法、新思路，对复杂网络进行学习与研究，不论在理论创新和项目科研上都有十分重要的意义。 在一般的复杂网络研究中会做出如下定义：用复杂网络中的每一个节点代表一个实体,例如在淘宝网络系统中，每一淘宝玩家都代表一个节点，自然网络中的边则代表制定网络系统中实体之间的相互关系,例如淘宝系统网络的边即代表购买玩家与售出玩家之间是否直接或间接存在交易关系。根据这样类似的复杂网络构建方式，我们可以把许多系统经过建模分析后抽象为网络，然而在构建了真实的网络系统之后,系统内部各元组之间也存在着一定的联系，可以将其进一步抽象为具有一定组织联系的小型划分，这类小型划分共同作用下体现了整个系统的功能，并且这些小型的划分的内部都会按照在一定的切合度组织起来，来维持内部划分内的紧密联系。我们把这样的小型划分称之为为复杂网络的社区。&
...........
1.2 & 国内外研究现状&
随着科学技术的发展，复杂网络的研究价值逐渐凸显，研究者们更多的关注复杂网络社区发现中关键节点的探索与研究，到目前为止，关于复杂网络的社区发现已经提出了大量的科研成果，在这众多的成果之中也有一些较为实用的方法，为更好的研究复杂网络提供了便利条件。自 &Newman &提出了 GN &算法以来，经过这些年的拓展和创新，复杂网络的社区结构发现算法已经有了较快的反战，很多新的想法不断的被提出，根据社区之间是否重合的特点大体上可以把这些被提出的算法划分为两类：非重叠社区发现结构的算法和识别重叠社区发现结构算法。 通过学习我们可以发现社区结构划分与计算机领域解决图分割的问题有许多雷同之处，因为图的划分问题的核心目的是指将一个网络中所有节点大致平均的划分到两个部分，使得划分后的两个部分子图之间的关联度最小。这种定义的方式与复杂网的社区结构的定义有较高的一致性，所以我们自然可以用雷同的方法对复杂网络进行划分处理进而得到相应的社区机构，在实际解决问题时，可以一般也通过迭代法进行迭代处理，把一个复杂网络先分割成两个部分，然后对划分后的两个部分分别使用图分割方法进行计算，一直迭代下去直到得到最优的划分结果为止。Kernighan-Lin &算法最开始是受到一些电路问题的启发，此电路问题旨用最少的链接数量完成电路板的链接。通过使用模块函数Q，对模块内部及模块之间完成边的数量优化处理。初始结点既可以所及选取，又可以通过图的拓扑结构有针对性的选取，然后将候选集平均分为两组，如果函数 Q 的值增加则交换节点，重新计算 Q 函数的值，依次选择最大的 Q 进行下一次计算。Kernighan-Lin &算法执行效率较高算法复杂度并且算法的为 &O(n2logn)，如果该图变为稀疏图则算法复杂度可以优化到 O(n2) &当然这种算法也存在一定的依赖性，如果初始化的节点选取不当就很难达到预期的预期的效率。&
...........
第 2 章 & 复杂网络与社区发现相关理论&
2.1 & 复杂网络的简介&
自然界中普遍存在的一个有机的、完整的整体可以称之为一个系统，系统内各个元素相互结合、相互影响、相互依赖、使这个整体具有一定的功能特性，自然构成系统的各个元素是不能离开整体而孤立的存在。 在复杂网络可以参考计算机数据结构中图论的先关概念，它代表由节点和节点间的边所构成的图。网络中的图同样具有一定的物理意义，与通讯网络、运输网络一样，它是从大量同类型的具有实际意义的问题中提炼出来的。复杂网络与之前提到的系统之间存在紧密的联系，倘若用点来表示系统中的元素，节点之间的边的属性代表个元素之间的关联关系，此时我们就可以把网络看成是一个系统。 复杂网络从定义上来看，所表述的是具有很高复杂性的网络，同时具有网络和系统的双重含义。使用复杂网络这一概念模型的使用可以更好的描述系统之间的关联关系，既可以清晰的表述网络中图的拓扑结构，又能体现系统状态和功能等各方面指标。对于复杂网络概念的我国的著名科学家钱学森先生给出了这样一个定义[13]：具有自组织、自相似、吸引子、小世界、无标度中的部分或是全部性质的网络称为复杂网络。在这里做出几点解释，自组织是指复杂网络在不需要外力的条件下可以自行运转，各个部分乃至各个部分内元素之间能够按照某种特定的形成协调稳定的结构。而自相似则代表一种图形的每个部分在几何形状上与整体间具有一定的相似度。 综上所述,现实世界中的大多数系统都具有很高的复杂度,并可以用网络的相关概念按照一定的规则进行转换，可以把经过网络概念、图论基础抽象化后的复杂系统称之为复杂网络，网络的规模和其在结构与功能上的异构特征是复杂网络复杂度高的主要根源。
.............
2.2 & 复杂网络的特性
2.2.1 & 复杂性
复杂性是复杂网络最直接的属性，我们之所以称复杂网络具有复杂性主要体现在以下几个方面[8]： (1) &网络的规模巨大。对于规模不大的网络，我们能够直接观测其形态特征。而在显示世界的网络一般都具有成千上网个节点，在这样的条件，研究复杂网络结构、功能及特性就变得很复杂。 (2) &拓扑结构的复杂。每个复杂网络包含许多子网，每个子网内部的连接结构在某种程度上具有一定的规律性，并非都是随机的，有这些结构各异的子网相互结合，自然复杂网络的拓扑结构也变得异常复杂，而且网络内的连接可能每时每刻都发生变化，节点与节点之间的连接边也会存在权重、方向性等属性。 (3) &节点的复杂性。复杂网络中的节点具有高度的代表性，在实际网络科研课题研究中，即便是权重、方向属性具有一致性，但代表的具体意义也仍旧千差万别，例如在社交网络中，每个节点代表社区内的每个成员，而在商品交易网络模型中，则节点代表了具体的从属于某一类的商品，在此基础上，同一个复杂网络中的节点也可能代表完全不同的含义，出动力学复杂性，节点的状态也会受到时间、空间、环境等多方面因素所左右。&
...........&
第 3 章 & 局部相似性聚类预处理的社区发现算法 .......... 20&
3.1 & 研究背景 ............. 20&
3.2 & 局部相似性聚类预处理算法相关概念 ..... 21&
3.3 & 局部相似性聚类预处理算法 ........... 27&
3.3.1 & 算法思想 .... 27&
3.3.2 & 算法过程 .... 29&
3.3.3 & 算法总结 .... 30&
3.4 & 本章小结 ............. 30&
第 4 章 & 局部相似聚类预处理算法实验 ...... 31&
4.1 & 模块度与纯净度 ........... 31&
4.2 & 海豚数据集 ......... 32&
4.3 & 空手道俱乐部数据集 ............. 34&
4.4 & 美国大学橄榄球数据集 ......... 35&
4.5 & 本章小结 ............. 38&
第 5 章 & 总结与展望 ........ 39&
5.1 & 本文总结 ............. 39&
5.2 & 研究展望 ............. 39&
第 4 章 & 局部相似聚类预处理算法实验&
4.1 & 模块度与纯净度&
在处理复杂网络社区发现问题的研究中，一般会引入模块度以及纯净度等基本参考指标用来验证算法的准确，与此同时对算法的效率进行评价。Newman 在提出了 GN 算法之后，模块度这一概念就被广泛的运用，渐渐的已经成为参考社区划分质量优劣的重要指标，对衡量社区发现结构稳定性与算法可靠性方面做出了卓越的贡献，然而我们不由得思考的是这样一个问题，此项参考指标既然能够评价社区发现的处理结果的好会坏那么也应该可以参考这个指标完成社区发现算法的改进与优化，正式由于这样的思考，基于模块度优化的社区发现的方法被提出。 模块度方法的主要思路是在复杂网络中针对节点度的分布情况进行分析，规定当前网络标记为 G，G 由 m 条边与 n 个节点共同组成。设定节点 ni与 nj为当前复杂网络中的两个随机的节点，其节点的度数分别用，di与 dj表示,则此时随机节点 ni与 nj之间的边的期望表达式为 &didj/2m，在实际节点对之间连接可能会与预期连接数量有差别，可以使用 Aij-didj/2m 计算。&
...........
本文提出了基于局部相似度聚类算法预处理的社区发现算法，鉴于利用社区发现算法在构建相似度后可以转换为聚类算法的基本思路，使用局部相似指标构建相似矩阵，使用谱聚类算法，参考特征间隙标准对当前网络进行预处理划分(如果先验信息中已经给出聚类中心参数则可以直接跳过特征间隙处理阶段)，再使用考量网络全局拓扑特性 Page Rank 算法作为核心节点的选择的参考指标，在预处理的每个社区结构内选择重要节点，计算每个非中心节点对每个重要节点所形成的社区结构的贡献值即节点适应度，选取适应度更大的节点依次加入相应社区，进而完成网络社区划分，最后融合 K-means 算法优秀思想，对得到的划分结果进行迭代计算直至社区结构达到稳定状态。 需要特别指出的是，一部分复杂网络社区发现算法大多针对网络中重要节点为核心，进而进行社区拓展，当处理核心节点不明晰的网络时，划分的结构很难得到保证，本文提出的方法考首先运用谱聚类算法对当前网络社区结果进行预处理，克服了上述情况，使网络结构初始划分得到保证，同时由于在谱聚类算法过程中使用特征间隙求出初始聚类个数，社区结构有一定的效率做保证，因此，可根据初始划分社区数目作为一个合理的预选择参考值，同样避免 K-means 算法在不知晓社区划分个数参数 K 的情况下带来的效率问题，并在此基础上运用Page Rank、节点适应度等参考指标对重要节点的选择及社区合并算法进一步优化，进而完善社区结构。 在实验阶段，分别使用了空手道俱乐部数据集、海豚数据集、美国大学橄榄球俱乐部数据集，实验结果证明了基于聚类预处理划分的社区发现算法正确性，并且保证了一定的效率。&
参考文献(略)
原文地址：/gclw/15883.html，如有转载请标明出处，谢谢。
您可能在寻找工程论文方面的范文，您可以移步到工程论文频道（/gclw/）查找
上一篇： 下一篇：没有了
COPYRIGHT (C) 2011 – 2012 SBLUNWEN. ALL RIGHTS RESERVED.
硕博论文网免费提供专科论文，大学本科论文，硕士论文，博士论文范文，为毕业生解决写论文烦恼。