精华内容
下载资源
问答
  • 复杂网络算法

    2015-06-29 06:53:31
    简单复杂网络算法,运行效果好,效率高。 N=input('请输入最近邻耦合网络中节点的总数N:'); %%参数输入 K=input('请输入最近邻耦合网络中每个节点的邻居数K:'); if K > floor (N-1) | mod (K,2) ~=0 disp ('参数...
  • 复杂网络算法研究

    2015-03-11 10:40:33
    复杂网络算法研究
  • 多种复杂网络算法

    2018-09-05 09:24:33
    本资源包含多种复杂网络MATLAB经典算法,包含GN;ER;BA;WS;NW等算法,对于学者可以当做一个很好地参考范例。
  • //文章编号:1007—1423(2014)17—0007—05 DOI:10.3969~.issn.1007—1423.2014.17.002复杂网络算法中K—shel与介数中心性算法的实现邵浩 一,陈东方 一,刘欣 1,Z(1.武汉科技大学计算机科学与技术学院,...

    ! //

    文章编号:1007—1423(2014)17—0007—05 DOI:10.3969~.issn.1007—1423.2014.17.002

    复杂网络算法中K—shel与介数中心性算法的实现

    邵浩 一,陈东方 一,刘欣 1,Z

    (1.武汉科技大学计算机科学与技术学院,武汉 430065;

    2.智能信息处理与实时工业系统湖北省重点实验室,武汉 430065)

    摘要:

    复杂网络中实现节点的中心性有许多算法 ,这些算法可以让人们快速识别出各种社交环境中的核心人物与话题。常

    用的中心性指标有度中心性.介数中心性、紧密中心性、特征向量中心性和 K—shel1分解方法。但是现有的理论中,仅

    仅提及算法的概念.并且实现的复杂性过高,算法的提及更多是用于分析阶段。为了解决这个问题,主要提出介数中

    心性指标和K—she1分解方法的程序实现.以便更好地应用于各种场合。

    关键词:

    介数中心性;K—shel1分解方法;算法实现;复杂网络

    基金项 目:

    国家级省级大学生创新创业训练计划项目(No.201310488003)、湖北省教育厅科研基金资助项目(No.B20101104)、湖

    北省重点实验室开放基金资助项目(No.znss2013BO12)、武汉科技大学科研基金资助项目(No.2009xzl,2012xz015)、武

    汉科技大学大学生科技创新基金研究项 目(No.12ZRA053)

    0 引言

    现实生活中的很多网络都是以复杂网络(Complex

    Network)的形式存在 。例如生命科学领域的各种网络、

    社会网络等 特别是在 1998年 Wats和 Strogatz在

    Nature杂志上发表文章引入了小世界 (smal—world)网

    络模 型【 1以及 1999年 BarabOsi和 Albe~在 Science上

    发表文章指出.许多实际的复杂网络的连接度分布具

    有幂律形式[21之后 .复杂网络 的研究掀起一股新的热

    潮。我们现在的生活就处在各种各样的社交环境中。每

    个人、每个商品之间都有关系。针对这些关系的分析 ,

    并挖掘出数据背后的价值对于精准的信息营销与广告

    推荐都有重大的意义。不仅在现实世界中.这些相关的

    研究与分析具有重要的价值 ,在我们的虚拟世界中.也

    存在巨大的价值 。虚拟环境是现实环境的仿真 .在我们

    的虚拟网络购物平台里面.也可以通过对于虚拟网络

    相关节点信息的分析,实现虚拟世界的相关应用。

    学术界在复杂网络进行了深入的研究 复杂网络

    的分析中.常以各种中心性指标或者 K—shel1分解算法

    来衡量节点影响力的大小 1977年 Freeman提出基于

    介数中心性(Betweenlies Centrality)的方法来衡量节点

    中心性f3J.他认为中间成员对路径两端的成员具有“更

    大的人际关系影响”.但是该衡量方法有很高的时间复

    杂度与空间复杂度的限制 2001年 Brandes提出了一

    种快速计算介数中心性的算法嗍.对于一个无 向图 G=

    ( ,E),其中 代表图中所有节点的集合。E代表图中

    所有边的集合,其算法的时间复杂度降到0(VE)。2010

    年.Maksim Kitsak等人在 Nature Physics杂志上发表一

    篇影响学术界的论文 .该篇文献中首次提及 K—shel1分

    解算法 .并给出该分解算法与其他各中心性算法的对

    比,表明该算法能排除度对节点的影响嘲。但是各项指

    标的研究主要提及的是思想或者更多的处于分析阶

    段,因为

    展开全文
  • 7种复杂网络算法
  • 复杂网络聚类算法在生物网络中的应用
  • 给出各类复杂网络聚类算法研究,用于聚类问题的分析
  • matlab复杂网络 gn算法

    2019-03-20 09:11:29
    matlab复杂网络代码,很好用希望大家喜欢
  • 复杂网络聚类算法的研究.pptx
  • 复杂网络matlab经典算法

    热门讨论 2014-05-10 09:12:50
    用matlab所写的复杂网络所用的经典算法,如BA无标度网络,ER随机网络,WS小世界网络和NS小世界网络,以及最近邻耦合网络等matlab算法,可以修改参数,可以绘制复杂网络图形。在matlab中直接可运行。
  • 复杂网络社团发现算法,对于研究复杂网络复杂网络社团特性的同学,进行聚类分析识别社团结构有较大的参考价值。
  • 复杂网络中的分区技术源代码,运行有效.复杂网络中的分区技术源代码,运行有效.
  • 基于局部探测的快速复杂网络聚类算法
  • 一篇复杂网络链路预测算法,个人感觉比较有借鉴意义
  • 网络算法复杂性理论,图论及其应用经典书籍,目录完整清晰,非常适合自学。最小树、网络优化、最短路径问题、二部图的匹配、一般图的匹配,NP完全理论,近似算法等。
  • 网络药理分析中复杂网络社区结构算法的比较研究
  • Infomap算法 复杂网络

    2014-07-19 23:25:03
    Infomap算法源码 一种高效的发现非重叠社区发现算法 输出必须是存放在dist/文件夹里面,而且如果该文件夹没有创建出来,程序将出错。 输入文件可以为各种文本格式.dat等,默认为无向网络 参考文献:Maps of random ...
  • 基于核心图增量聚类的复杂网络划分算法改进
  • MATLAB源码集锦-复杂网络BA算法计算过程代码
  • 7种复杂网络MATLAB经典算法,包含GN;ER;BA;WS;NW等算法,可直接使用,仅限个人
  • 算法复杂网络

    千次阅读 2019-09-26 11:46:12
    笔者最近一直在研究图算法,在研究图算法前,对复杂网络分析进行了研究,笔者的上篇博文就是对研究的复杂网络分析的内容进行的总结。图算法,字面意思上看,就是对图进行处理的算法。在学习前,笔者一直有个疑问,图...

    笔者最近一直在研究图算法,在研究图算法前,对复杂网络分析进行了研究,笔者的上篇博文就是对研究的复杂网络分析的内容进行的总结。图算法,字面意思上看,就是对图进行处理的算法。在学习前,笔者一直有个疑问,图究竟属不属于复杂网络?再学习了如下两本书中的内容后,笔者还是没有得到准确的答案。

    注:本书部分内容及观点总结自以下书籍:
    1.《Graph Algorithms》Mark Needham, Amy E.Hodler著,2019年5月版;
    2.《Spark GraphX》Micheal S.Malak, Robin East著,2017年4月版;
    3.《复杂网络算法与应用》孙玺菁,司守奎 著,2015年6月版。

    在图算范与复杂网络分析的书中,笔者学习到了很多内容相似甚至相同的处理算法,如中心性计算,路经查询等,包括复杂点的社团结构。那么,二者之间到底是什么关系?笔者个人认为,重要的事情说n遍,仅限作者个人意见,…,仅限作者个人意见,笔者认为图算法应该属于复杂网络分析中的一种特殊情况,而复杂网络分析并不是仅有图算法内容。

    下面笔者简单对基本图算法进行总结:
    1路径寻找
    路径寻找算法建立在图寻找算法之上,为了寻找两个节点间的最优路径。路径寻找算法包括最短路径、到所有点最短路径和单资源最短路径、最小生成树、随机游走。
    1.1最短路径
    加权最短路径
    输入:起始节点、终止节点
    输出:最短路径长度
    遍历方法:
    1)广度优先寻找:先遍历节点直接相连的节点,遍历完成后再遍历相邻节点直接相连的节点,以此类推。
    2)深度优先寻找:首先遍历节点相连的点,当遍历到该节点时,若该节点有其他相连节点,则继续遍历相邻节点,不需要折返。

    1.2全节点对最短路径
    1.2.1到所有点最短路径
    输入:起始节点
    输出:从起始节点到图其他节点的最短路径
    算法步骤:
    1)设定节点到本节点的距离为无穷大;计算并记录从起始节点经一跳可到达的节点及其路径权值;
    2)计算从起始节点经两跳可到达的节点及其路径权值和,与步骤1)中结果对比,若相同起始节点,路径权值和小于步骤1)中的,则更新权值路径;
    3)重复步骤2),可得出最终起始节点到全图各节点的最短路径。

    1.2.2单资源最短路径
    输入:起始节点
    输出:从起始节点到其他各节点的最短路径
    算法步骤:
    1)从起始节点开始,首先选择路径权值最小的边连接的节点;
    2)再从起始节点开始计算,选择到达路径权值最小的节点;
    3)不断重复步骤2),直到遍历完所有节点。

    1.3最小生成树
    输入:起始节点
    输出:由起始节点构建的最小生成树
    算法步骤:
    1)从起始节点开始,选择边权值最小的点,将被选中的节点添加到树中;
    2)重复选择边权值最小的点,当没有新的节点被添加入生成树的时候,算法介数。
    注:单资源算法和最小生成树算法的区别:单资源算法每次计算的是从根节点开始路径权值的总和,而最小生成树仅仅看下一步的权值。

    2中心性计算
    2.1度中心性
    节点的出边个数称为出度,入边个数称为入度。
    2.2紧密中心性
    紧密中心性标准化方程:
    在这里插入图片描述
    其中,u为节点,n为图中节点的个数,d(u,v)为节点v与节点u之间的最短距离。为了解决无连接图的干扰,引入调和中心性,其标准方程如下:
    在这里插入图片描述
    2.3介数中心性
    介数中心性计算公式如下:
    在这里插入图片描述
    其中,u为节点,p为节点s与节点t之间最短路径的个数,p(u)为节点s与节点t之间经过节点u的最短路径的个数。

    2.4 PageRank
    PageRank计算公式如下所示:
    在这里插入图片描述
    其中,我们假设u页有从T1页到Tn页的引文;d是取值为0至1之间的抑制参数,常设置为0.85;1-d表示不遵循任何关系直接到达节点的可能性;C(Tn)表示节点T的出度。

    3社团检测算法
    3.1三角计数和聚类系数用于分析总体关系密度
    测量节点产生三角计数和度的多少,为了决定哪些节点倾向于聚集在一起。
    节点u的聚类系数计算公式如下:
    在这里插入图片描述
    其中,u表示节点;R(u)表示通过u的三角计数;k(u)表示节点u的度。
    聚类系数能够使我们快速的找到明显的小团体。

    3.2强连通组件和连通组件用于找到连接的群集
    强连通组件:查找可以从同一组中的每个其他节点按照关系的方向访问每个节点的组;
    连通组件:查找可以从同一组中的每个其他节点访问每个节点的组,而不考虑关系的方向。

    3.3标签传递为了根据节点标签快速推断团体
    根据多数相邻节点,以标签传递的方式推断团体,是一个快速寻找社团的方法。
    标签传递算法:
    输入:带标签的节点
    输出:不同标签种类的社团
    算法步骤:
    1)首先确定带有标签的节点;
    2)将与标签节点直接相连的节点打上其对应的标签;
    3)最近标记的节点被激活,变为新的标签节点,重复步骤2);
    4)当遇到两不同标签节点都准备激活同一节点时,可根据设定关系(如根据边权值的大小)进行决定选择;
    5)标签传递结束。
    注:标签传递算法每次运行的结果都可能不一样,因为初始节点的选择可能不同。

    3.4 Louvain模块化为了查看团体质量和层次结构
    通过将关系权重和密度与定义的估计值或平均值进行比较,使团体的设定精确度最大化。
    一个团体的模块系数计算公式如下:
    在这里插入图片描述
    其中,L表示全团体的关系数量;Lc表示分隔中的关系的数量;kc表示分隔中所有节点的度值和。模块度的计算公式如下:
    在这里插入图片描述
    其中,u和v表示节点;m表示总的关系权重;Auv是节点u和v之间关系的权值;ku、kv分别是节点u和v关系权重的总和;最后类似激活函数一样的式子表示节点u、v是否在同一社团,若在同一社团,则其值为1,若不在,则为0。

    Louvain模块化算法:
    输入:节点个数及节点间的权值,及节点是否在同一社团
    输出:最优化的子图模块
    算法步骤:
    1)将图中的每个节点看成一个独立的社区,社区的数目与节点个数相同;
    2)对每个节点u,依次尝试把节点u分配到其每个邻居节点所在的社区,计算分配前与分配后的模块度变化Delta Q,并记录Delta Q最大的那个邻居节点,如果maxDelta Q>0,则把节点u分配Delta Q最大的那个邻居节点所在的社区,否则保持不变;
    3)重复2),直到所有节点的所属社区不再变化;
    4)对图进行压缩,将所有在同一个社区的节点压缩成一个新节点,社区内节点之间的边的权重转化为新节点的环的权重,社区间的边权重转化为新节点间的边权重;
    5)重复1)直到整个图的模块度不再发生变化。

    注:常见图算法工具NetworkX包,Spark GraphX,Neo4j等。

    展开全文
  • 计算机论文复杂网络社团算法及其信息辨识应用研究 本文是一篇计算机论文研究本文从文章开始介绍了复杂网络的研究背景从而引入复杂网络社团算法并由此引申社交网络上信息辨识方面的问题接着分别对复杂网络社团算法...
  • GCE算法用于复杂网络

    2014-07-19 23:46:51
    GCE算法用于复杂网络源码,linux环境 参考文献:Detecting Highly Overlapping Community Structure by Greedy Clique Expansion
  • 复杂网络中的社团挖掘算法可以划分到

    复杂网络中的社团挖掘算法可以划分到聚类算法中去。

    按照社团性质划分,可分为:单一社团发现和重叠社团发现

    按照算法思想划分,可分为:分裂算法和聚合算法

    按照算法流程划分,可分为:启发式算法和基于影响力算法


    经典算法:

    1,GN算法

      其基本思想是不断的移除介数最大的边

    改进:加入模块化度量

     将初始的每个节点都看做一个社团,对于有边相连的社团计算它们的模块度,选择最大的两个社团合并。


    continue...

    展开全文
  • LFM算法 复杂网络相关

    2014-07-19 23:11:04
    LFM算法源码 复杂网络相关 linux环境 输出文件是output.dat,最下面便是结果,分为了多少个社区,每个社区的元素是哪些
  • 为了提高复杂通风网络自然分风算法性能,将遗传算法与通风网络自然分风的基本理论和传统的非线性方程组求解算法相结合,提出基于遗传算法复杂通风网络自然分风算法。将遗传算法求解复杂通风网络自然分风算法分为直接...
  • 复杂网络中的GN算法

    热门讨论 2012-03-23 13:30:36
    复杂网络中Newman提出的GN算法算法思想删除网络中边介数最大的边从而把网络划分为社团,算法的主要缺点算法的时间复杂度很高
  • 图谱理论与复杂网络相关算法

    千次阅读 2020-05-13 20:57:36
    1.图谱问题研究背景 现实生活中的各种复杂网络都可以用图有效表示。...由于复杂网络节点规模巨大,通常很难找到特定网络拓扑结构与图谱性质间的直接相关性,求解复杂网络社团分割问题的精确解是一个NP难问题。 2

    1.图谱问题研究背景

    1. 现实生活中的各种复杂网络都可以用图有效表示。给定一组样本,可以用图来描述样本之间的相关性,其中每个数据样本看做图中的一个节点,样本之间的相似性决定节点间(边)的权重。这些复杂网络中存在一些子图,子图内部节点连接相对紧密,子图间节点连接相对稀疏。这写子图称为社团。社团结构反应了复杂网络代表的系统中节点间的拓扑关系。复杂网络社团结构分割属于图的划分问题。由于复杂网络节点规模巨大,通常很难找到特定网络拓扑结构与图谱性质间的直接相关性,求解复杂网络社团分割问题的精确解是一个NP难问题。

    2.基本概念与记号

    1. 一个图G由顶点V(G)和边E(G)构成,其中边是顶点集V(G)不同顶点的一对为序对。常用符合xy表示。如果xy是一条边,就可以说顶点x与顶点y相邻接,或者说顶点y是顶点x的邻居,表示x~y。如果一个顶点是一条边的两个端点之一,就说这个顶点和这条边是相关联的。比如计算机网络拓扑。

    2. 图G的邻接矩阵A是一个nxn的实对称矩阵定义为:在这里插入图片描述
      矩阵L(G)=D(G)-A(G)称为图G的Laplacian(拉普拉斯)矩阵,其中D(G)是对角元素{d1,d2,…,dn}的对角矩阵。矩阵L(G)也被称为Kirchhoff矩阵。

      定理:矩阵树定理:设L是图G的Lapacian矩阵,Li,j是从L中删去第i行和第j列后地道的矩阵L的子矩阵。则矩阵L的代数余子式就等于图G的生成树的数目τ(G)。表示为在这里插入图片描述
      式中:i,j=1,2,…,n

    3. 图G中的一条u-v的W通道(walk)是图G中的一个顶点序列,这个序列从顶点u开始,以顶点v结束,序列中连续的顶点是相邻接的,表示为W:u=v0,v1,…,vk=v,其中k≥0。通道中的顶点可以重复出现,如果u=v,则称通道w是闭的,否则是开的。通道中出现的变得数目就是通道的长度,长度为0的通道称为平凡通道(trivial walk)。所以W:v就是一个平凡通道。如果一条u-v通道中的边都是不同的,即从顶点u遍历到顶点v每条边只被遍历一次,则称这样的通道为迹(trail)。如果通道中的顶点都不重复,则称这样的通道为路(path)。

    3.复杂网络基本概念

    ​ 复杂网络是复杂系统(如社会学中的人际关系…)的一种表现形式,复杂系统中的一个实体在网络中表示为一个节点,而节点之间的边则属于两个实体之间的某种关系。由于这样的网络其节点数量规模较大,而且节点与节点之间的联系较为复杂,那么网络的复杂性就会随着节点与边之间的关系而增加,所以这样的网络就被称为“复杂网络”。

    ​ 图论是复杂网络研究的基础。如ER随机图、小世界网络、无标度网络。

    ​ 由于在复杂网络中,网络的连接错综复杂,而网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统,所以对复杂我拿过来结构的分析就是对网络中的节点和边的分析。

    社团结构,在社团结构内部的节点之间的连接相对紧密,在社团之间的连接相对来说却比较稀疏。在实际网络中,社团结构关系到网络中功能的划分,对网络整体了解和分析,发现网络中的动力学传播并找到网络中隐藏着的规律,甚至是预测网络的行为,所以发现实际网络中的社团结构的意义就显得十分重要。

    ​ 复杂网络划分的意义在于对网络中的单个节点进行分析:通过节点所在社团的位置揭示出该节点在社团中的功能——若节点位于社团比较中心的位置,即该节点的度比较大,则这个节点在社团中可能起到中心控制的功能;而位于社团边界的节点,则可能更多的担负着与其它社团间的信息传输功能。

    ​ 发现网络中的社团结构在一定程度上也揭示了现实大部分网络中的“分辨率”现象,即网络是由很多社团组成,但是这些社团本身又是由很多小社团所组成。例子。得到网络的“分辨率”后,就可以对网络的行为做进一步详细的观察和控制,使得处理和分析网络中的问题变得更加简单方便和有针对性。

    ​ 每个网络都可以抽象成一个节点集和边集组成的网络N=(V(N),E(N)),其中V(N)代表网络的节点集,E(N)代表网络的边集。集合E(N)中的每一条边都有V(N)中的一节点相对应,如果节点对(i,j)与节点(j,i)对应的是同一条边,那么N就是一个无向网络(undirected network);如果节点对(i,j)与节点(j,i)对应的是不同的边,那么N就是一个有向网络(directed network)。若给每条边都赋一个权值,那么该网络就是一个加权网络(weighted network),否则就是无权网络(unweighted network)。

    1.密度

    网络的密度(density)是指网络中(n个节点)实际存在的边的数量l与网络中最大的可能边数m的比值,即density=l/m,其中网络中最大的可能边数m=n(n-1)。

    2.平均路径长度

    网络中两个节点i和j之间的距离dij定义为连接这两个节点的最短路径上的边数,网络的平均路径长度L定义为任意两个节点之间的距离的平均值,即在这里插入图片描述
    式中:n为网络节点数,网络的平均路径长度也称为网络的特征路径长度(characteristic path length)。

    3.集聚系数

    复杂网络的集聚系数(clustering coefficient)在某种程度上类似于社会关系网络中的“物以类聚,人以群分”的特性,它描述网络中节点的邻点之间也互为邻点的比例。若网络中的节点a与有ki节点与其相连,那么这ki个节点就称为节点a的邻居。而这ki个节点之间的边数ei和最大的可能边数m之比就定义为节点i的聚类系数Ci,即在这里插入图片描述,其中m=ki(ki-1)。

    整个网络的聚类系数是指所有节点聚类系数的平均值,它是考查网络的集团化程度在这里插入图片描述,其中n为网络节点总数。

    4.节点的度

    ​ 节点的度是指与该节点直接相连的节点数量,

    5.度分布

    ​ 泊松分布、幂律形式

    6.中心度

    1.度数中心性

    ​ 度数最大的就是中心点。

    ​ 设网络具有n个节点,则节点x的度指标d(x)表示与节点x相邻接的节点数,为了根据度指标来比较不同规模的网络中的节点的中心化,需要对度指标进行归一化处理,设经过归一化处理后的度指标为CD(x),即在这里插入图片描述,其中n为网络节点数,n-1为最大可能邻接点数。

    2.介数中心度

    ​ 介数中心度(Betweenness Centrality)认为中心点应该是信息、物质或能量在网络上传输时负载最重的节点,也就是介数最大的节点。

    ​ 流介数中心度(Flow Betweenness Centrality)去除最短路径的概念来定义介数,由此定义在这里插入图片描述
    其中gjk为节点j与节点k之间的路径条数;gjk(X)为节点j与节点k之间经过节点x的路径条数。当节点的流介数中心度较大时,则说明在网络传输信息、物质或能量时,其负载较重,可以被认为是网络的中心节点之一。

    3.紧密度中心度

    ​ 紧密度中心度(Closeness Centrality)定义为节点到网络中其他节点的距离之和的倒数,紧密中心度表示了某节点到达其他节点的难易程度,也就是节点到网络中其他节点的总距离最小,在这里插入图片描述
    其中,dxy为节点x到节点y的最短路径,n为网络的节点数。

    度数中心性是描述节点在网络中产生的直接影响力

    紧密度中心度是描述节点通过完了对其他节点的影响能力。

    4.常见的社团划分算法

    1.Kernighan-Lin算法

    ​ Kernighan-Lin算法是一种试探优化的方法,其基本的思想是为网络引入一个试探函数Q,Q代表某两个准社团内部的边数减去两个准社团之间的边数的差值,然后得到使Q值最大的划分方法。

    ​ 首先将整个网络的节点随机的或根据网络的现有信息分为两个部分,在两个社团之间考虑所有可能的节点对,试探交换每对节点并计算交换后的ΔQ,ΔQ=Q交换后-Q交换前,记录ΔQ最大的交换节点对,并将这两个节点互换,记录此时的Q值。规定每个节点只能交换一次,重复这个过程直至网络中的所有节点都被交换一次为止。需要注意的是不能在Q值发生下降时就停止,因为Q值不是单调增加的,既使某一步交换会使Q值有所下降,但其后的一步交换可能会出现一个更大的Q值。在所有的节点都交换过之后,对应Q值最大的社团结构即被认为是该网络的理想社团结构。

    缺点:要求必须在计算前知道该网络的社团个数,,否则该算法也不确定要重复到哪一步停止。

    2.谱平分方法

    ​ 谱平分发是基于Laplacian(拉普拉斯)矩阵的性质而进行社团划分的方法。

    3.分裂方法

    ​ 划分网络社团结构的一种简单的方法就是将连通社团之间的边移除,这就是分裂方法的基本思想。而这个方法的主要难点就在于如何正确地找到社团之间的边。在分裂方法中,从整个网络出发,试图找到已经连接的相似性最低的节点对,然后移除它们之间的边,在某些极端情况下也有可能将节点也移除(由于连接该点的边都被移除)。分裂方法利用树状图来表示其分裂的流程,可以更好地描述整个网络逐步分裂成若干个越来越小的社团的过程。如下图所示,底部的各个圆代表了网络中的各个节点,当水平虚线从顶部逐渐向底部移动时,即表示整个网络逐渐分成若干个社团结构,在虚线移动到底部时,整个网络的节点就退化成独立的社团。在分裂方法中GN算法和快速分裂算法是比较有代表性的。

    在这里插入图片描述

    1)GN算法

    ​ 由Girvan和Newman提出的GN算法在近几年已成为社团结构分析的一种标准算法,他的基本思想是从网络的整体出发,不断地从网络中移除介数最大的边,从而获得最佳的社团结构。边介数定义为网络中经过每条边的最短路径的数目。GN算法的基本流程如下:

    ​ (1)对复杂网络中的每一条边,计算其对应的边介数;

    ​ (2)比较网络中所有的边介数,并将边介数最大的边从网络中移除;

    ​ (3)重复以上两个步骤,直至每个节点都是一个退化的社团。

    ​ 设一个网络的节点数为n,边数为m。每次进行一次广度优先搜索就可以得到一个节点与其他节点之间的最短路径,其算法复杂度为O(m)。在实际网络中,每个节点与其他节点之间的最短路径条数可能并不唯一,而是存在着几条长度相等的最短路径。设节点i的权值为从源节点到j节点的不同最短路径数目,如果节点i与节点j直接相连,且节点i比节点j距离源节点更近,则节点j通过节点j通过节点i到达源节点的最短路径与节点j到达源节点的最短路径总数之比为wi/wj,那么在最短路径条数不唯一的情况下计算边介数的步骤为:

    ​ (1)得到“最短路径树”中所有“叶子”节点l;

    ​ (2)对每个与“叶子”节点l相邻的节点i,从节点l到节点i之间的边赋权值wi/wl;

    ​ (3)从距离源节点最远的边开始,对于连接节点i和节点j的边(i,j),将位于其下方的且与该边相邻的权值相加,把得到的和加1再乘以wi/wj后,得到的值就作为该边的权值;

    ​ (4)重复第(3)步骤,直至遍历网络中所有的节点。

    ​ 每次从网络中移除一条边后,都要重复计算以上步骤。

    ​ 但是在不知道网络社团个数的情况下,GN算法无法判断何时停止,也不能直接从网络的拓扑结构来判断所得到的社团结构是否具有实际意义。为解决这个问题,Newman等人定义了模块度的概念,用来衡量网络社团结构划分的质量。在每次GN算法结束时,整个网络被分成了k个社团,定义一个kxk的对称矩阵E=(eij),其中eij表示连接社团i和j之间的边所占整个网络总边数的比例,这里的边值得是原网络的边,而不是将边移除后的网络,因此模块度的衡量标准是利用整个网络来进行计算的。

    ​ 定义在这里插入图片描述为矩阵的对角线上各元素之和,表示的是网络中所有社团内部的边占整个网络边数的比例,在这里插入图片描述为每行或每列各元素之和,表示的是与社团i的节点相连的边占整个网络边数的比例。模块度的衡量标准公式为:

    在这里插入图片描述

    其中,在这里插入图片描述为矩阵x的所有元素之和。Q的值在0到1之间,如果Q的值越靠近1,则说明网络的社团结构越明显。在实际的网络中,Q值一般位于0.3~0.7之间。

    ​ GN算法只是适用于中等规模的网络,如节点数量在10000以下的网络。

    2)快速分裂算法

    ​ Radicchi等人针对GN算法的时间复杂度问题,在GN算法的基础上提出了快速分裂算法。因为这个算法只需要计算局部的一些变量,从而在运算量上大大减少,复杂度也会相应下降。该算法的基本思想是根据边聚类系数来衡量连接不同社团之间的边,而不是GN算法的边介数。与节点聚类系数的定义类似,包含该边的三角形总数与所有可能包含该边的三角形的数目之比就是边聚类系数的定义。对于节点i和节点j之间的边定义为:

    在这里插入图片描述

    其中:在这里插入图片描述为实际包含该边的三角形数量,k为节点的度,也即所有可能的包含边(i,j)的三角形的总数。

    ​ 由于网络社团内部的节点之间连接比较紧密,则三角形的数目相对较多,那么在这里插入图片描述就相对比较大,而连接网络社团之间的边包含在极少的三角形内,甚至不被任何的三角形所包含,则在这里插入图片描述相对比较小。由此可见边聚类系数就可以代替GN算法中的边介数来作为衡量不同社团之间的边的标准。类似地,可以推广到多边形中,则有

    在这里插入图片描述

    其中:在这里插入图片描述为实际包含边(i,j)的g边形,](https://img-blog.csdnimg.cn/20200513204928156.png)为所有可能的包含该边的g边形的数目。在移除一条边是,就要检查整个网络是否分解成了若干个社团,并且在移除的边的小范围内更新其他边的聚类系数。

    ​ 快速分裂算法与GN算法有一定的相似性,因为通常情况下边介数比较大的边,其聚类系数都会比较小,所以该算法在结果上与GN算法非常相似,但是聚类系数最小的边不一定边介数最大,所以它们并不等价。

    ​ 由于算分非常依赖网络中存在的三角形结构,那么当网络相对稀疏时,其边的边聚类系数都会很小,所以得到的结果也就会出现错误,甚至不能找到社团结构,事实上非社会性网络的三角形结构就相对比较低。

    4.聚合方法

    ​ 与分裂方法不同,聚合方法是用某种方法计算出网络节点之间的相似度,然后再一个节点数为n边数为0的控网络中,将相似度最高的节点对相连。这个方法可以在任何时刻终止,在这一时刻所得到的结构即可以认为是组成网络的若干社团。

    1)Newman快速算法

    ​ 该算法是Newman在GN算法的基础上提出的,虽然GN算法属于分裂方法的一种,但Newman快速算法利用了聚合方法的思想进行社团划分。算法描述如下:

    ​ (1)首先,认为网络中的每个节点就是一个退化的社团结构,设网络中有n个节点,那么有变量eij和ai,满足在这里插入图片描述

    其中:ki为网络节点i的度,m为网络的边数。

    ​ (2)将有边相连的社团对依次合并,计算并记录合并后的模块度增量,Newman快速算法中的模块度增量定义为:

    在这里插入图片描述

    ​ 每次合并都要沿着使ΔQ减少最小的方向或者使ΔQ增大最多的方向进行。在每一次的合并后,需要对相应的eij进行更新。

    ​ (3)重复步骤(2),直至整个网络合并成为一个社团,其合并次数最多执行n-1次。

    ​ 算法在结束后便可得到对应的社团结构树状图,在树中选择一个局部最大的Q值所对应的结构即可得到在该算法下最理想的网络社团结构。

    2)结合谱分析的凝聚算法

    ​ 该算法结合了谱分析和聚合方法的特点,其基本思想是利用Laplacian矩阵把网络的节点在特征向量空间中描述出来,并引入一种衡量节点之间相似度的标准,利用聚合方法的思想将相似度比较高的节点聚合到一起作为一个社团,最终得到社团结构树状图,根据模块度的大小得出最佳社团结构。

    展开全文
  • 基于复杂网络的吉他和弦生成算法

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,002
精华内容 2,400
关键字:

复杂网络算法