精华内容
下载资源
问答
  • 2020-10-27 16:09:31

    本文主要针对数模美赛中复杂网络模型的相关知识进行了总结,此外,其余需要使用复杂网络的情况也可以参考本文

    目录

    分类

    均匀性分类

    关联性分类

    一些基础

    复杂网络上的传播机理与动力学分析

    免疫网络

    免疫模型

    免疫类型

    复杂网络的传播动力学

    复杂网络上的相继故障

    复杂网络中的搜索:(搜索需要的数据)

    复杂网络中的社团结构(可区分层次)

    分裂模型

    凝聚算法

    复杂网络中的同步

    无标度网络的完全同步

    局域世界演化网络模型的完全同步

    应用

    各因子与完全同步的关系

    改进复杂网络同步的方法

    相位同步

    复杂动态网络的控制

    应用

    描述节点间相互作用

    各种模型

    路网可达性

    节点重要性

    度中心性(degree)

    接近中心性(Closeness Centrality)

    中介中心性/中间中心性(Between Centrality)  

    特征向量中心性(Eigenvector Centrality)

    度的分布(常为幂律分布)

    复杂网络的性质分析

    衡量影响度

    排名算法汇总

    PageRank

    Hits Algorithm

    TrustRank


    分类

    均匀性分类

    均匀网络(如WS小世界模型) 度数分布较均匀

    非均匀网络(如BA无标度网络) 度数分布极度不均匀

    关联性分类

    无关联网络:任何一个节点的度与它的邻居节点的度是相互独立的

    关联网络:节点的度与它的邻居节点的度不是相互独立的


    一些基础

    1. WS、NW小世界模型:描述朋友关系
    2. BA无标度网络:描述持续的社会连接,如发表论文总会优先找已经写过论文的人。

    鲁棒性和脆弱性并存。有限支撑、无限支撑“赢者通吃”。

    1. 局域世界演化网络模型:优先连接不是整个网络而是局域,如找导师时想获取本校的学位只能找本校的导师,而不是外国知名导师。
    2. 等级网络:模块以某种迭代的方式生成一个等级网络。
    3. 超家族:自相似。
    4. 运用自相似性质来粗粒化。
    5. AS层面Internet拓扑:多层次连接
    6. 技术网络一般是异配的,而社会网络通常是同配的
    7. PFP模型:富人俱乐部,少量节点具有大量的边(富节点),它们倾向于彼此之间相互连接。
    8. DP模型:消费者-供应商关系或者对等关系,连接度低的为消费者,连接度较高的为供应商;消费者决定将要接到哪些供应商上,即由消费者来选择供应商。
    9. 多局域网模型:当一个新节点加入到一个区域网络时,它对其他局域网中的节点影响非常小,而它反过来主要受本区域网中的节点的影响。

    复杂网络上的传播机理与动力学分析

    免疫网络

    免疫模型

    1. SIR模型  易感染群众被感染,然后恢复健康并具有免疫性。(新闻传播等,知道某条新闻后对此事后不再感兴趣;娱乐信息传播与之对比,知道信息后部分人会变得更感兴趣,容易受感染)
    2. SIS模型  易感染群体被感染后,又返回到易染状态

    免疫类型

    1. 随机免疫
    2. 目标免疫:选取少量度最大的节点进行免疫
    3. 熟人免疫:从很多节点中随机选出一定比例的节点,再从每一个被选出的节点中随机选择一个邻居节点进行免疫

    复杂网络的传播动力学

    病毒、灾难、火灾、通信网络中的堵塞都可作为对象。

    1. 红色代码蠕虫的随机常数传播模型 假设:一是忽略了系统可能被打补丁、关闭或切断连接;二是认为易被攻击的目标数在这一模型中是常数;三是把Internet看作一个无向完全连接图。
    2. 电子邮件病毒的传播模型 对朋友寄来的邮件都予以(充分)信任,以一定概率打开邮件
    3. 谣言在复杂网络中的传播 可类似的用SIR模型来描述

    复杂网络上的相继故障

    1. 负荷—容量模型 由于某种原因某个节点的负荷超过其容量从而产生故障
    2. 二值影响模型 应用于随机网络相继故障分析
    3. 沙堆模型 随着沙堆的逐渐变大,它的坡面变陡,这时新添加的沙子引发沙崩的可能性也越来越大。
    4. OPA模型 由初始状态向自组织临界状态转化,各种小型故障的防护性工程反应,是导致电网状态向自组织临界状态发展的一个不可缺少的动因。对小型事故的防护和避免实际上是在为一次大规模相继故障作累积
      慢动态 负荷缓慢增长
      快动态 描述相继故障发生和传播,速度很快
    5. CASCADE模型 相继故障频率和故障规模的概率分布,其假设
      网络中具有很多类似的节点,并且各自具有随机的初始负荷及初始扰动
      某一结点过载后会失效并将一个固定大小的负荷传给其他节点

      复杂网络中的搜索:(搜索需要的数据)

    应用 社会网络中两个人之间的最短关系链寻找最短关系链寻找、WWW中网页的搜索和P2P网络结构及其搜索技术。

    1. 层次树结构网络模型 个体根据职业、地理位置、兴趣等聚集成一些比较小的群,这些群又根据它们共同的特性聚集成规模更大的群,这样一层一层向上聚集,最高的一层代表整个网络,从而产生一个树状的层次结构。如某大学研究生组成的网络,某实验中的个体属于实验室,然后又属于某个系,然后又都属于某个学院,最后都属于这个大学。
    2. 全局 广度优先搜索策略:可用来寻找任意两点之间的最短路径
    3. 局部 随机游走搜索策略:
    4. P2P网络中的搜索:在个人计算机之间直接进行资源和服务的共享,而不像传统的客户端/服务器结构那样需要经过服务器的介入和服务。
    5. Gnutella网络中的广播搜索:采用广度优先搜索。这样的搜索方法是十分高效的,用户可以在很短的时间内找到所需的目标文件。但是,这样的处理方式会在网络中产生大量查询数据流量,很容易形成网络流量堵塞。

    改进方法:1、迭代加深     2、有向广度优先搜索    4、K遍历器随机游走   

    1. 基于Gnutella网络中节点的度分布的改进搜索算法
    2. 同时研究复杂网络中的搜索和拥堵的模型

    复杂网络中的社团结构(可区分层次)

    分裂模型

    1. Kernighan-Lin算法:要求必须事先知道该网络的两个社团大小,否则,很可能不会得到正确的结果。这个缺陷使得它在实际网络分析中难以应用
    2. 谱平分法:最大的缺陷就是它每次只能将网络平分,如果要将一个网络分成两个以上的社团,就必须对子社团多次重复该算法。
    3. 线性时间的物理方法:不仅可以求出网络的社团结构,还可以在不考虑整个网络的社团结构的情况下,寻找一个已知节点所在的整个社团。
    4. 基于Normal矩阵的谱平分法:克服需要事先知道社团个数的缺陷,使对于社团结构不是十分明显的网络也能取得较好的效果。
    5. GN算法:GN算法弥补了一些传统算法的不足,近几年来已成为社团结构分析的一种标准算法。GN算法存在一个缺陷,即它对于网络的社团结构并没有一个量的定义。不能直接从网络拓扑结构判断它所求的社团是否是实际网络中的社团结构,从而需要一些附加的关于网络意义。在不知道社团数目的情况下,GN算法也不知道这种分解要进行到哪一步终止。
    6. 采用节点集的GN算法:和GN算法相比,显著地提高计算速度,但也降级了计算的准确度。
    7. 自包含GN算法:克服了GN算法的两个缺陷。与GN算法的效果相当,计算速度却有了较大的提高。
    8. 快速分裂算法:仅需要计算一些局部变量,因此大大减小了运算量。
    9. 基于相异性的算法:可将网络划分为一系列具有等级性的社团。其中,每一个社团都由一个相异性的上下阈值来表征,可表示出不同社团之间的差异程度。可以运用于无权网络和加权网络。
    10. 基于信息中心度的算法
    11. 极值优化算法:基本思想是通过调整局部极值来优化全局的变量,从而提高运算效率。

    凝聚算法

    1. Newman快速算法:相比GN算法,可以用于分析节点数高达100万的复杂网络。
    2. 堆结构的贪婪算法(CNM算法):复杂度低,已接近线性复杂度。
    3. 结合谱分析的凝聚算法:结合了谱分析和凝聚算法两者特点的算法。

    派系过滤算法:

    一个社团从某种意义上可以看成是一些互相连通的“小的全耦合网络”的集合,这些“全耦合网络”成为“派系”。


    复杂网络中的同步

    大量的看似巧合的同步行为可以用数学来给出解释,每个个体是一个动力学系统,而诸多的动力学个体之间存在着某种特定的耦合关系。

    Lyapunov指数

    类型1、2、3网络需要判断为哪一种网络

    假设网络是连通的,那么只要网络的耦合强度充分大,类型1网络就一定可以实现同步;

    而只有当耦合强度属于一定范围时的类型2网络才会同步,也就是说,太弱或太强的耦合强度都会使类型2网络无法实现同步。

    无标度网络的完全同步

    同步最优网络: 同步化性能要比BA无标度网络的同步化性能强,但由于存在极少量的‘hub’点,这样在恶意攻击下它要比BA无标度网络更容易奔溃

    同步优先网络:对于随机去除节点和恶意攻击都很鲁棒的同步优先网络模型。

    局域世界演化网络模型的完全同步

    一般来说,与无标度网络相比,局域世界演化网络能够在保持鲁棒性的同时,还能提高网络对恶意攻击的抗脆弱性。

    应用

    1. 规则网络:星形耦合网络
    2. 平均模型:网络中的每个节点都与其他节点相连,对于平均模型而言,耦合强度只需很小就能大幅降低同步阈值,从而提高网络的同步化性能。
    3. 闪烁小世界网络:前面的小世界模型都是长程边固定的模型,即随机选中一条长程边后,这条边就永远存在。此模型最初始最近邻耦合网络基础上,随机选中的长程边只会在一段时间内存在,而在下一段时间内,该长程边会消失,再重新选择一条长程边出现。更确切的说,在时间间隔内每条长程边都以概率连接。这与其他长程边是否连接无关,也与它本身在上一时间段内是否已经连接无关。
    4. 具有耦合时滞的连续时间网络完全同步判据: 复杂网络在传输和相应过程中常常会由于传播速度的物理限制和网络拥塞的存在而产生时滞现象
    5. 离散时间耦合网络完全同步依据

    各因子与完全同步的关系

    最近邻耦合网络在N趋近∞时不可能达到同步,但通过加入少量的长程边将网络的平均路径明显缩短,它的同步化能力便会有明显提高。

    对于小世界网络,当加边或重连概念不断变化时,会对应产生多个具有不同网络基本特性的小世界网络模型;随着概率的增加,网络变得更加非均匀,无论是新加入长程边(NW小世界)或是重新连接长程边(WS小世界),网络中度的最大值都会增加。

    对于无标度网络,当幂律指数不断变化时,也会得到多个不同的无标度网络模型;随着幂律指数的增大网络度分布变得比较均匀,因此网络的平均路径就会增加,同时平均度变小。

    单纯用度的大小、度分布或平均路径长度等指标都无法统一表征复杂网络的同步化能力。

    想要提高网络的同步化能力应该降低节点的最大介数。

    改进复杂网络同步的方法

    1. 无序扰动改进同步特性:通过小波变换来提高同步
    2. 通过时滞提高网络同步特性:在有明显时滞时,网络达到为稳定同步流形时所需要的耦合强度,要比无时滞网络达到同样的同步流形所需要的耦合强度小很多。
    3. 加权耦合提高网络同步特性:可用于耦合不对称,并且网络是有向、加权时参数对同步性能的影响。

    相位同步

    如果两个耦合节点的相位之间以一定的比率锁定,那么就称这两个节点达到相位同步。相位同步是一类同步化程度比较弱的同步现象,发生相位同步时,各节点的相位可能已经锁定,但幅值却会完全不同


    复杂动态网络的控制

    牵制控制利用无标度网络结构的非均匀行,有针对地对网络中的少数关键节点施加反馈控制,由此牵一发而动全身,从而能够将规模庞大的复杂动态网络稳定到平衡点,获得很高的控制效率。

    规则网络时空混沌的牵制控制

    可将时空混沌控制到周期轨道和非混沌状态,可控制达到混沌状态或强混沌状态。

    应用

    社团检测:潜在客户挖掘、关联群体风险分析等;

    网络中心性分析:网页排名(PageRank),供应链核心企业识别,信息传播枢纽节点识别等;(PageRank无法解决悬空节点问题)

    网络传播预测:流行病传播,金融风险传播,舆论传播;

    网络关系渗透:节点之间的关系(三度影响);

    关联交易分析及投融资黑洞:虚假交易,担保圈分析等。


    描述节点间相互作用

    各种模型

    1. 微分方程模型
    2. 神经网络
    3. 离散动力系统
    4. 线性时变系统,信号与系统

    这些模型都具有预测能力

    也可以用显式的网络结构来确定网络的局部和全局性质,或者忽略任何一种网络结构,用经典的数据挖掘和元素聚类来标识属性。

    路网可达性

    路网可达性是城市小区或路网节点相互之间居民出行或车辆行驶平均时间的倒数。表示交通难易程度的一项技术指标,计算值愈大,则可达性愈好。1959年,汉森首次提出了交通可达性的概念,这被定义为接受道路网络中节点之间相互作用的机会。


    节点重要性

    Freeman’s research[1979] 详见2014C—25318 P6

    度中心性(degree)

    度中心性(Degree Centrality)是在网络分析中刻画节点中心性(Centrality)的最直接度量指标。网络中与该节点直接相连的节点个数,一个节点的节点度越大就意味着这个节点的度中心性越高,该节点在网络中就越重要。

    接近中心性(Closeness Centrality)

    反映在网络中某一节点与其他节点之间的接近程度。某点到网络中其他点的距离总和。将一个节点到所有其他节点的最短路径距离的累加起来的倒数表示接近性中心性。即对于一个节点,它距离其他节点越近,那么它的接近性中心性越大

    中介中心性/中间中心性(Between Centrality)  

    主要描述某个节点在整个网络中的中心程度,说明整个网络的集中程度,即整个网络围绕某一结点或一组节点来运行的程度。以经过某个节点的最短路径数目来刻画节点重要性的指标。中介中心性指的是一个结点担任其它两个结点之间最短路的桥梁的次数。一个结点充当“中介”的次数越高,它的中介中心度就越大。如果要考虑标准化的问题,可以用一个结点承担最短路桥梁的次数除以所有的路径数量

    特征向量中心性(Eigenvector Centrality)

    一个节点的重要性既取决于其邻居节点的数量(即该节点的度),也取决于其邻居节点的重要性。

    用中心度的时候最好都把这几种中心度进行说明,然后说明我们为什么选择这一种中心度

    选择中心度的时候都说明了这几者的对比,表明了选择某一项的理由

    信息流网络考虑重要性时需考虑度数大的点,“桥”的作用的点,非流网络考虑度数大的点


    度的分布(常为幂律分布)

    Newman提出的模块度具有两方面的意义:

    1. 模块度的提出成为了社区检测评价一种常用指标,它是度量网络社区划分优劣的量化指标;
    2. 模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。在模块度的基础之上,许多优化算法以模块度为优化的目标方程进行优化,从而使得目标函数达到最大时得到不错的社区划分结果。

    当然,模块度的概念不是绝对合理的,它也有弊端,比如分辨率限制问题等,后期国内学者在模块度的基础上提出了模块度密度的概念,可以很好的解决模块度的弊端,这里就不详细介绍了。

      常用的社区检测方法主要有如下几种:

    1. 基于图分割的方法,如Kernighan-Lin算法,谱平分法等;
    2. 基于层次聚类的方法,如GN算法、Newman快速算法等;
    3. 基于模块度优化的方法,如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等。

    复杂网络的性质分析

    “小世界”网络在信息传递和处理的过程中具有相对高的局部效率和全局效率; 而无标度网络中节点的重要性具有极端的两极分化, 表明网络中存在超级重要的核心节点, 这些核心节点在维持整个网络的完整性和连通性中发挥着不可估量的作用。 这两大重要发现引发了复杂网络研究的热潮。 越来越多的研究表明来自不同领域的网络, 包括社会网络、经济网络、生物网络等都具有“小世界”性和无标度性。 这使得人们认识到, 真实网络既不同于规则网络, 也不同于随机网络, 而是介于规则网络和随机网络之间, 具有与两者不同的统计特征的复杂网络。

    实际上小世界和 random network 的度分布相似,点与点之间的连接是随机的,所以都是钟形正态分布,但是小世界的点点之间路径最短。

    无标度网络有巨集团和剩余度的涌现,也就是说巨集团基本代表网络的连接密度,少数的点有大量的连线,大多数点有少量或没有连线。无标度的度分布也引发了相关的对自组织临界和熵厥的讨论,是当今研究主要课题。

    分析完是否是小世界/无标度之后,写出其性质。还有一些基本性质,比如有向无向,有权无权,有环无环


    ​​​​

    衡量影响度

    1. 行为对网络的影响分为两类:自己对自己的影响和自己对别人的影响
    2. 影响分为广度和深度(2014C--25318),广度用度中心度来反映,深度用特征向量中心度来度量,这两个加上中介中心度可以反映对整张复杂网络的影响PageRank或者Hits Algorithm, 然而,它们都涉及矩阵乘法和重复迭代过程,这是不太有效的。 由于网络满足有向无环图(DAG)的特性,我们借鉴拓扑排序的思想来设计更有效的算法。 在该引文网络中,存在共同作者网络中不存在的传递关系。(2014C--27688
    3. 影响的传递可以与食物链中的能量转移进行类比,还可以找到模型的推广(2014C--27688

    排名算法汇总

    GOOGLE PageRank最为广泛使用

    Hilltop 算法

    ExpertRank

    HITS

    TrustRank

    PageRank

    可计算,特征向量中心性(Eigenvector Centrality):一个节点的重要性既取决于其邻居节点的数量(即该节点的度),也取决于其邻居节点的重要性。

    PageRank无法解决出度为零的节点(悬空节点)的问题

    传统的PageRank只适用于点有权值的图。对于加权边的图,可以根据边的权值制定一套规则转化为点的权值进行修正,然后PageRank可以适用于(可以参考2014C--25318

    Hits Algorithm

    HITS算法通过两个评价权值——内容权威度(Authority)和链接权威度(Hub)来对网页质量进行评估。其基本思想是利用页面之间的引用链来挖掘隐含在其中的有用信息(如权威性),具有计算简单且效率高的特点。HITS算法认为对每一个网页应该将其内容权威度和链接权威度分开来考虑,在对网页内容权威度做出评价的基础上再对页面的链接权威度进行评价,然后给出该页面的综合评价。内容权威度与网页自身直接提供内容信息的质量相关,被越多网页所引用的网页,其内容权威度越高;链接权威度与网页提供的超链接页面的质量相关,引用越多高质量页面的网页,其链接权威度越高。

    HITS算法也有其明显的不足。首先是权威性的确定因为权威页面必须针对某一主题或关键词而言。例如某一页面对一确定主题具有较大权威性,但这并不意味在其他与其无关的主题方面同样具有权威性。其次是非正常目的的引用。

    TrustRank

    以前依靠链接和相关性来决定排名的方式,已遭到了各种各样作弊行为的挑衅,Spam的横行,直接导致了Google必须找到一种新的反作弊机制,以确保高质量的站点来获得搜索引擎的青睐。这种情况下SandboxTrustRank被提了出来。意图确保好的站点能获得更高的搜索表现,并加强对站点的审核。Google自己关于TrustRank的最初论述也提到了这些。

    1. 域名注册时间在五年或五年以上;
    2. 网站托管在专用服务器上;
    3. 网站加载时间快;
    4. 网站内容是原创的;
    5. 访客在每个网页的停留时间超过90秒;
    6. 网站被多个国际IP段引用;
    7. 网站在其所属行业中拥有权威性。

    这些都是商业网站和博客所应有的素质,而不是那些利用垃圾内容和虚假入站链接赚些快钱的网站所具备的

    更多相关内容
  • 各种复杂网络生成模型代码,如BA,WS,NW网络等等 (all kinds of models for complex networks such as BA, WS,NW etc) 复杂网络中基本网络模型的matlab实现\Aver_Path_Length.m 复杂网络中基本网络模型的matlab...
  • 复杂网络基本模型生成代码matlab

    热门讨论 2013-04-22 22:01:56
    复杂网络三大基本模型的matlab实现,可以生成三种具有基本模型特性网络。
  • 用来生成各种复杂网络模型的程序,比如无标度网络和随机网络以及所属的各种测量指标。
  • 复杂网络与大数据》第二章:复杂网络模型的学习笔记 目录 1动态演化网络 1.1以网络演化的部件划分 1.2以是否考虑权重划分 1.3以演化网络采用的演化机制划分 1.4以演化网络是否动态变化划分 2社区网络 2.1...

    《复杂网络与大数据》第二章:复杂网络模型的学习笔记

    目录

    1动态演化网络

    1.1以网络演化的部件划分

    1.2以是否考虑权重划分

    1.3以演化网络采用的演化机制划分

    1.4以演化网络是否动态变化划分

    2社区网络

    2.1复杂网络中社区结构的分类

    2.2社区结构评价标准

    3权重网络

    3.1加权网络的度量

    3.2实际加权网络

    3.3加权网络建模

    4相依网络

    4.1相依网络的子网络

    4.2相依网络的相依边

    4.3相依网络的组合方式

     


    1动态演化网络

    演化网络是随着时间的变化而变化的网络。

    1.1以网络演化的部件划分

    1.基于点边的网络演化模型:顾名思义,基于点边的网络演化模型就是指在网络演化过程中网络的结点和边都可以增加或删除的演化模型。

    典型的如BA模型。BA模型是基于增长和择优连接两个原理提出的,增长原理强调了网络节点的演化,择优连接强调了网络边的演化。BA模型具有幂律度分布的特性

    目前大多数的网络演化模型都是基于点边的网络演化模型。

    2.基于边的网络演化模型:即网络演化过程中,节点数不变,但是边可以增加或删除的演化模型。

    例如:ER模型在给定的节点之间采用随机连边策略产生随机图模型;WS模型在给定的节点之间采用边重连的策略产生小世界网络模型;NW模型给定的节点之间采用随机加边的策略产生小世界模型;

    两种网络演化模型谁更合理目前并没有定论。

    1.2以是否考虑权重划分

    1.无权网络演化模型:如果对所研究网络的边没有赋予相应的权值,则该网络就称为无权网络。基本的ER模型、WS小世界模型、NW小世界模型以及BA模型都属于无权网络演化模型。目前基于BA模型产生了大量的无权网络演化模型。根据BA模型的网络增长和择优连接两条规则,这些模型大体可以分为两类:修改增长规则的无权网络演化模型和修改连接规则的无权网络演化模型。

    无权网络演化模型主要针对网络的拓扑演化机制进行研究,不考虑网络的功能、承载业务等,演化结论主要也是通过对网络拓扑结构的评判(是否具有幂律度分布特性、小世界效应等)验证。因此,无权网络演化模型与实际网络演化还有一定差距。

    2.含权网络演化模型:如果对所研究网络的边赋予了相应的权值,则该网络就称为含权网络或加权网络。现实世界的网络几乎都是含权网络。含权网络演化模型的研究对理解真实网络的演化过程具有重要意义。具有代表性的含权网络模型有DW模型, YJ BT模型 , Barrat、Barthelemy和Vespignani提出的简单加权演化网络模型(BBV模型) 以及中国科技大学复杂系统研究小组提出的TDE模型及其改进模型。

    含权网络演化模型认为网络承载的业务与网络拓扑结构是一种共生演化关系,相互驱动。BBV模型(特别是TDE模型) 通过将网络业务耦合人网络拓扑演化过程, 不仅得到网络的幂律度分布,同时得到网络强度的幂律分布、网络权重的幂律分布以及高聚集性和非相称混合性等特征,更加成功地刻画出真实技术网络的特性。

    1.3以演化网络采用的演化机制划分

    1.单一演化机制模型:指演化过程中只采取一种演化机制的模型。ER模型、WS小世界模型、NW小世界模型、BA模型以及众多基于这些模型的改进模型都是单一演化模型。单一演化机制模型能有效研究某一演化机制对网络演化性质的影响,但对处于复杂多变环境中的真实网络而言,采用单一演化机制模型往往太过理想化,因此单一演化机制模型与实际网络相比还存在一定的差距。

    2.混合演化机制模型:混合演化机制模型是指网络在演化过程中采取多种演化机制的模型。为了描述确定性与随机性和谐统一的世界以及增长过程的复杂性和多样性,中国原子能科学研究院网络科学小组的方锦清等人提出并发展了统一的混合网络模型,形成网络理论模型的三部曲。数值模拟和理论分析揭示了统一混合网络演化模型随多个混合比变化的若干特性,将其应用于一些现有的无权和含权复杂网络演化模型,可以得到更接近实际网络的特性。虽然混合演化机制模型能描述网络增长过程的复杂性和多样性,但是真实网络究竟采用了哪些演化机制以及各种演化机制所占比重的确定仍是一个需要解决的难题。

    1.4以演化网络是否动态变化划分

    1.静态网络演化模型:在相邻两个时间步内,网络节点及节点之间的关系一直保持不变,则称这类网络为静态网络。目前研究的网络演化模型基本上都属于此类型。

    2.动态网络演化模型:在相邻两个时间步内,网络节点及节点之间的关系(边)具有可变性,则称这类网络为动态网络。动态网络系统中,节点的状态和拓扑都是动态演化的,节点的状态和网络的拓扑之间可能是相互影响的,且系统在整体层面上会展示出各种各样的集体行为。当前的研究重点主要是系统具有什么样的集体动力学行为、如何干预或控制此系统等。

    2社区网络

    目前,社区还没有明确的定义。一般而言,社区是指网络中具有相似属性的节点集合,社区内部关系紧密,社区之间节点关系稀疏。Fortunato从网络节点相似度,局部和全局3个角度总结了常见的社区的定义。

    1. 节点相似度定义:社区是由网络中相似节点构成的集合。同一个社区中的节点在异构的网络中呈现相似的特征,所以可以根据节点的相似度划分社区。通常采用层次聚类方法度量节点相似度和发现社区结构。
    2. 局部定义:社区是与网络中其他部分只有少量关联的部分。即社区内部个体关系紧密。
    3. 全局定义:社区是整个网络系统的一种划分,整个网络构成一棵层次树状图,根据某种特征函数值进行划分,得到最优的社区结构。这种特征函数也就是一种社区划分的衡量标准,对社区结构给出了一种量化定义。最常见的特征医数是 Newman 等人提出的模块度函数。

    综合以上3中定义可以看出,节点相似度是利用节点属性对网络进行划分,社会网络分析领域经常采用这种定义。然而,在复杂网络中,由于节点的属性非常复杂,很难获得有效的信息,因此大多数复杂的网络社区都使用后两种定义,利用网络拓扑来发现社区结构。

    2.1复杂网络中社区结构的分类

    在复杂网络中,有两种类型的社团结构:层次结构和重叠结构,它们可能同时存在于复杂网络中。
    1.层次结构

    社区层次结构是对社会网络中不同层次、不同粒度社区的整合。现实世界中的大多数网络系统都显示出层次的形态。真实网络通常由社区组成,而这样的社区中包含较小的社区,小社区中可能包含更小的社区等。社区层次结构的意义在于揭示复杂网络中社区之间的上下包含关系。层次结构在社会网络中普遍存在,如篮球和羽毛球俱乐部都属于球类俱乐部,围棋和象棋俱乐部都属于棋牌俱乐部,而球类和棋牌类俱乐部都属于体育俱乐部。发现网络社区层次结构,可以深人理解不同尺度下网络结构及网络结构之间的关系,从而更好地反映真实系统的情况,有利于进行系统分析。目前发现社区层次结构较多采用层次聚类的方法,按照网络图中节点之间的距离或者相似度进行聚类,将整个网络结构构建成为一棵树状图。树状图表示了网络社区的层次结构,如图所示,每个节点是树状图中的叶子,然后通过连接构成树状图,组成一个完整的网络。树状图中的每一层代表不同的社区,从底层到高层社区数量越来越少,社区规模越来越大。


    2.重叠结构


    研究发现,现实世界中许多网络社区之间通常并不是彼此独立的,而是相互关联的。换言之,网络由相互关联,彼此重叠的社区组成,社区之间存在重叠的节点。社区的重叠结构是指社区中每个节点并非只属于一个独立的社区,而是存在某些节点可能属于多个社区。例如,在社会网络中,根据不同的分类方法,每个人可能会划分到多个不同的社区(如家庭、公司、兴趣小组、学校等):在科学家合作网络中,一个物理学家同时也可能是一个数学家,因此他将同时处于分别由物理学家和数学家构成的两个社区中。社区重叠结构更加符合真实世界的社区之间的关系,反映了更加真实的网络结构。复杂网络中层次重重社区如图所示,从图中可以发现某些节点在不同的社区之间起着桥梁的作用,同时属于两个不同的社区。

    2.2社区结构评价标准

    采用层次聚类算法是针对已知社区数目(层次)的网络,你需要先构成网络的层次树状图,每一层对应网络的一个划分。但是实际中网络的社区数目往往是未知的。

    如何从树状图中获得最优的社区划分,需要一个度量标准。这里介绍一个划分标准——模块度

    所谓模块性,是指在  一个真实社团内部的节点的边在该网络中所占的比例期望值  与   在保持该网络节点社团属性不变的情况下,边根据节点的度随机链接时,社团内部节点的边占该网络全部边的比例期望值   的比值。社团结构划分的越好,该比值越大。通常用Q函数定量描述社团划分的模块水平:

    Q=(一个真实社团内部的节点的边在该网络中所占的比例期望值)/( 在保持该网络节点社团属性不变的情况下,边根据节点的度随机链接时,社团内部节点的边占该网络全部边的比例期望值)

    其中,m为边数,ki,kj为节点vi,vj的度,它们中间有边的可能性为(ki*kj)/2m,若有边Aij=1,否则等于0。ci,cj分别是vi,vj所属的社区,当ci=cj时δ(ci,cj)=1,否则等于0。

    Q值范围【-0.5,1),值越大,社区划分越准确。在实际中,Q值最高点一般在0.3~0.7之间.

    3权重网络

    权重网络就是带权重的网络。之前只讨论边是否存在的二进制网络只是纯粹的拓扑模型,不足以解释实际系统观察中的丰富而复杂的性质。

    3.1加权网络的度量

    加权图一般表示为G=(V,E,W)。首要特征是权分布Q(w),即特定边的权为w的概率。

    下面介绍的度量是无权网络中一些概念的拓展与补充,并将权与拓扑相结合。

    1.点的强度,强度分布与相关性

    强度是度概念的推广:由边的个数推广为边权的和。

    s_{i}=\sum_{j\in N_{i}} w_{ij}

    当权与拓扑结构无关时,度数为k的点的强度S(k)约等于<w>*k,<w>为平均强度。

    点vi的边权可能均匀分布,也可能只有少数权占优势。权的不等性由Y_{i}度量,它的定义为
    Y_i=\sum _{j \in N_i }(\frac{w_{ij}}{S_i})^2 

    即每条边权占强度比值的平方和。如果边的权值都差不多,则Y(k)=1/k,若只有一条边起主要作用,则Y(k)=1。

    强度分布R(S)度量了点强度为S的概率,和度分布P(K)一起构成了加权网络的有用信息。点vi的最近邻度数的加权平均为:

    k^w_{nn,i}=\frac{1}{S}\sum_{j\in N_i} a_{ij}\omega _{ij}k_j

    这个量可以刻画加权网络的同类匹配性和非同类匹配性。当k^w_{nn,i}>k_{nn,i}时,权值大的点倾向于链接度大的点,否则相反。

    2.加权最短路径

    有些情况下边的物理长度是有用的,边的长度L可以定义为vi到vj的欧几里何空间距离。在一般加权网络中,边长可以用权的函数表示,如L=1/wij,尽管此假设不满足三角不等式。加权最短路径可以定义为vi到vj中边长和的最小值,此时最短路径不再是含有最少边的路径。

    3.加权聚集系数

    之前所说的聚集系数没有考虑到加权网络中有些邻居节点比其他点更重要,这里令vi的加权聚集系数定义为:

    C_i^w=\frac{1}{S_i(k_i-1)}\sum_{j,k}\frac{w_ij+w_ik}{2}a_{ij} a_{jk} a_{ki} ,取值【0,1】

    加权聚集系数既考虑了vi的邻居闭三角形个数,又考虑了总相对权。C^wC^w(k)分别表示所有点的加权聚集系数均值和所有k度点的加权聚集系数均值。对于大型随机网络,有C^w=C,C^w(k)=C(k)。然而实际情况却可能看到两种相反的情况,如果C^w>C,则顶点关联三元组更可能由权高的边组成;相反如果C^w<C,则表示网络的拓扑聚集由权低的边形成。​​

    3.2实际加权网络

    不同链接的权展示了不同的分布和幂律行为等复杂统计特征。权和拓扑的相关性为观察这类组织结构提供了互补的视角。

    1.生物网络(以代谢网络为例)

    若以E大肠杆菌的新陈代谢反应作为加权网络研究,节点vi,vj表示代谢物i,j,有向边eij代表代谢物 i 到 j 的反应,权wij代表从代谢物 i 到 j 的流量。

    在最优生长条件下,权分布很好的符合幂律分布:

    Q(w)\propto (w_0+w)^{-r_w},其中w0=0.003,rw=1.5。

    这代表越高的权出现的概率越小,即流量越高的反应出现的概率越小。

    同时在权的不等性方面,我们发现对于E大肠杆菌的代谢,其入度出度都符合

    Y(k)\propto k^{-0.27},即权的不等性与k^{-0.27}成正比。

    在之前2.6.1我们定义权的不等性时我们知道,如果权分布平均,则Y(k)越趋近于1/k。因此在E大肠杆菌代谢网络中,节点的度k越大,其权不等性Y(k)\propto k^{-0.27}与1/k的距离越远。即度越大的节点,权分布越不均匀。即某个代谢物生成或者消耗反应越多,越有可能某个反应携带了大多数的反应物。

    2.社会网络(以合作网为例)

    合作网是目前拥有广泛数据库的社会网络。以无权科学合作网为例,科学家作为端点,如果两位科学家合作过文章,则连一条边。但是合作多的科学家之间明显比合作少的科学家之间联系更紧密,为了解释这一现象,我们需要合作频数来衡量作者间的关系。比如我们可以定义作者i,j之间相互作用的为:

    w_{ij}=\frac{\sum_p \delta_i^p \delta_j^p }{n_p-1},p的定义域为所有的文章,如果作者i是文章p的作者之一,则\delta _i^p=1,否则为0 ,np是文章p的作者数。

    即合作过的文章越多,合作文章的共同作者越少,两位科学家之间的权越大,联系越紧密。

    现在我们根据这种权的定义,来研究一个N=12722的,1995-1998年间给凝聚态物理提交论文草稿的科学家的合作网。实际观察中,该网络具有以下特征:

    1. 该网络的分布R(S)和P(k)都是重尾分布的。
    2. 权与拓扑结构无关,即S(k)=<w>*k,度为k的节点的强度等于平均权乘以度数k。
    3. k>=10时,加权聚集系数C^w(k)>C(k),这意味着顶点关联三元组更可能由权高的边组成,即合作者多的科学家之间趋于相互合作,组成稳定的研究组就能产生大量文章。
    4. 点vi的最近邻度数的加权平均k^w_{nn,i}k_{nn,i}都随着k呈幂律增长,表明该网络呈现了一个社会网络的典型特征,同类匹配性。

    3.技术网络

    以世界航空网为加权网并进行分析。节点vi,vj表示机场i,j,权wij为机场i到机场j的航班的有效座位数。该实际网络展示了小世界和无标度属性。

    1. 特别的,该网络的度分布形势为p(k)=k^{-\gamma }f(k/k_x),其中\gamma=2.0;f(k/k_x)是指数断开函数,因为单个机场能提供的最大数目链接是有限的。
    2. 节点的强度分布R(S)是重尾的,且权与度之间存在非平凡关联:边的平均权和两端点的度数之间的关系为<wij>=(ki*kj)^θ,指数θ=0.5。
    3. 度数为k的点的强度服从幂律分布S(k)=AK^\beta,指数β=1.5,这表明机场越大,可处理的运输量越大。
    4. 在k的整个取值范围内,加权聚集系数C^w(k)有更多有界变化,即度数高的机场易形成具有高运输量的相关组。
    5. 由于高流量链接在网络中枢上,所以有高度数的点趋于和同样具有高度数的点结成派系的现象,即“富人俱乐部”现象。

    3.3加权网络建模

    1.YJBT模型

    YJBT模型是加权无标度网络的最小模型,模型中随着网络增长,拓扑和权都受择优连接规则驱动。

    1. YJBT模型的拓扑结构与BA网络相同。开始于m0个点,每一时步,添加一个具有m<m0条边的新节点vj。点vj与已有的点vi相连的概率为\frac{k_i}{\sum_lk_l},即vi节点的度/全部节点的度
    2. 每条边权为w_{ij}=\frac{k_i}{\sum_ik_i},即vi节点的度/要连接的节点的度之和。可以发现新节点的边权之和为1 。

    YJBT模型产生了无标度网络,度为幂律分布P(k)~k^{-3} ,强度也为幂律分布R(S)=S^{-\gamma _s} ,其中指数\gamma _s强烈依赖于m,渐进的强度分布最终收敛于度分布。

    因为YJBT模型生成过程的演示在网络上没有找到,所以我自己写了一个:https://github.com/changyaoxing/ComplexNetworkModel_YJBT

    2.ZTZH模型

    ZTZH模型是YJBT模型的一般化,在点的度和适应度的权值分配上加入了随机因素。对于每条新建连接l_{ji},以概率p按照YJBT模型的形式w_{ij}=\frac{k_i}{\sum_ik_i}赋予其权值,以概率1-p按照w_{ij}=\frac{\eta _i}{\sum_i\eta _i}的形式赋予权值,其中\eta _i是赋予点vi的适应度参数,服从区间【0,1】上的均匀分布\rho (\eta )。p=1时,模型就还原成了YJBT模型,p=0时,权值完全有适应度决定。模型产生了强度幂律分布R(S)~S^{-r_s},其指数r_s的特征是对概率p高度敏感,r_s从p=0时的值r_s=3随着p的增加而连续递减。和YJBT模型一样,关于P(k)的差异是对数修正项的结果,可以用p调整,当p=0时,差异消失。YJBT模型发现对所有p>0都有r_s依赖m的变化,仅当p=0时,r_s独立于m在一个依赖于点连接和适应度的边形成机制模型中也发现了类似的结果。

    3.AK模型

    AK网络的结构增长与边权相耦合。模型定义如下:

    1. 每一个时间步,加入一个新点vj,连接到一个目标点vi,连接概率与点vi的强度成正比:\prod _{j\rightarrow i}=\frac{S_i}{\sum_l S_l},此规则放宽了\frac{k_i}{\sum_lk_l}的度择优连接规则,考虑强度连接规则。
    2. 对每一条边赋予一个从分布ρ(w)取出的权值。

    所得网络是树,其强度分布R(S)当S趋近于无穷时,逼近静态胖尾分布R(S)~S^(-γ),与边权分布ρ(w)无关。特别的,当ρ(w)为指数分布时,R(S)为所有的代数分布。

    4.BBV模型

    之前的YJBT、ZTZH、AK模型都是基于网络拓扑增长,即产生边的同时为其赋予一个权值,以后就不再变化。这种模型忽略了新节点和边的加入可能引发的权的动态变化,忽略了演化和增进的相互作用是自然的网络的普遍特征。例如,一条新航线的开辟会影响其他航线的流量。

    BBV模型是基于加权驱动动力学和与局域网络增长相结合的权增加机理,这种结合模仿了实际情况中观察到的相互作用的变化。

    1. 模型开始于m0个初始点,连接权为w0;
    2. 每一时间步添加新点vj和m条边,权值是w0。以\prod _{j\rightarrow i}=\frac{S_i}{\sum_l S_l}的概率随机与已有的节点vi连接;
    3. 新边eji的出现引起vi何其邻居vl之间的权的局部调整,按照w_{il}\rightarrow w_{il}+\Delta w_{il}的格式进行。其中\Delta w_{il}=\delta \frac{w_{il}}{S_i},即vi因为新边eji的出现,强度增加了\delta,每条边按权重占强度比例分配\delta
    4. 此时vi的强度变化为S\rightarrow S+w_0+\delta 。

    BBV模型生成的网络展示了权、度和强度分布的幂律行为、指数是非平凡的且与w0和\delta相关。若令w0=1,这时的模型只考虑一个单独参数\delta,即由于添加新边而增加的点的强度。当时间无穷大,即点无穷多时,权分布呈幂律分布Q(w)~w^{-r_w}r_w=2+\frac{1}{\delta }。点的度数分布和强度分布服从于有相同指数r=r_s=\frac{4\delta +3}{2\delta +1}的幂律分布P(k)\propto k^{-r_s}R(S)\propto S^{-r_s}

    5.DM模型

    BBV模型中强度高的点吸引新边,然后修正这些点的边权。DM模型中,权高的边增加权值并吸引新的连接。一种指向强的点,一种指向强的边。DM模型规则如下:

    1. 以权成比例的概率选择一条边,并将其权增加常数δ。
    2. 新点连接到该边的两个端点,并赋予权值1 。

    结果边权、点的度数、点的强度都成幂律分布,指数分别等于r_w=2+\frac{2}{\delta }r=r_s=2+\frac{1}{1+\delta } 。

    4相依网络

    现实中的网络或多或少的都与其他的网络相关联,比如物理依附,信息交换等。2003年的意大利停电事故就是因为电网的某个节点故障,导致其相连的计算机控制节点断电,结构控制网络无法有效调控电网,造成全国性的断电。研究相依网络对设计更健壮的网络系统,提高网络设施抵御风险的能力具有重要意义。

    相依网络有三个要素:相依网络的子网络,相依网络的相依边,相依网络的组合方式。

    4.1相依网络的子网络

    相依网络的鲁棒性受子网络的影响很大。子网对相依网络的鲁棒性的影响主要是靠子网络的类型节点数、平均度等特性。

    子网络的类型可以是ER网络、RR网络、SF网络、BA网络、WS网络等。其他条件相同时,这些网络作为子网组成的相依网络的鲁棒性表现如下:

    RR-RR>ER-ER>SF-ER>SF-SF,这是子网络节点度分布决定的,子网络的度分布越均匀,相依网络的鲁棒性越好。

    网间相似性:子网络内部度数高的节点间倾向于产生相依关联。例如机场网和港口网组成的系统中,令相依关联为地理位置相同,则重要的港口节点倾向于链接重要的机场节点。

    在研究港口-机场的相依网络时发现:网间相似性越高,相依网络在面临随机失效时的鲁棒性越好。即我们可以通过提高度高节点间的相依边的可靠性,增强相依网络的鲁棒性。

    4.2相依网络的相依边

    相依边是相依网络的存在基础,也是影响相依网络鲁棒性的最直接因素。相依边主要通过其方向、类型以及比例等属性影响整个网络的鲁棒性。

    相依边分为有向和无向两种,当其他条件相同时,有向相依边的相依网络鲁棒性较差。因为有向系统可能产生更长的相依链

    相依链指在两个子网A、B组成的相依模型中,A中的节点u支持B的节点v,而v反过来又支持A的节点w,如此循环往复形成的相依节点集。相依链上节点的故障会通过相依链在子网间传播,还可能扩散到与相依链链接的其他节点上,引起故障的级联,降低系统的鲁棒性。

    相依边类型有连接边(connectivity links)和依赖边(dependency links)两种。连接边的作用是连接不同网络的节点,使子网络能够协同工作;依赖边表示某个节点的功能依赖于其他节点。据此可以将相依网络分为三种,即子网络间只存在依赖边/只存在连街边/同时存在连接边和依赖边的相依网络。

    相依网络的相依强度q指的是相依网络中有相依关系的节点所占的比例:q=0表示子网络间无相依关系;q=1表示子网络完全相依,即节点之间具有一一对应的相依关系。当相依强度p由0向1变化时,相依网络的鲁棒性会变差。

    4.3相依网络的组合方式

    随着研究的深入,学者们从子网络规模和组合方式的角度对相依网络进行了拓展,目前研究的重点是网络组成的网络——多层网络(network of network,NON)的鲁棒性。

    目前研究较多的是由ER、RR等网络作为子网络,以链形、星形、树形和环形组合方式组成的NON的性质。

     

    展开全文
  • 复杂网络-4种网络模型

    千次阅读 2019-07-05 09:57:01
     规则图差不多是最没有复杂性的一类图,random_graphs.random_regular_graph(d, n)方法可以生成一个含有n个节点,每个节点有d个邻居节点的规则图。  下面一段示例代码,生成了包含20个节点、每个节点有3个邻...

    https://www.cnblogs.com/forstudy/archive/2012/03/20/2407954.html

     

    一. 规则图

      规则图差不多是最没有复杂性的一类图,random_graphs.random_regular_graph(d, n)方法可以生成一个含有n个节点,每个节点有d个邻居节点的规则图。

      下面一段示例代码,生成了包含20个节点、每个节点有3个邻居的规则图:

    复制代码

     1 import networkx as nx
     2 import matplotlib.pyplot as plt
     3 
     4 # regular graphy
     5 # generate a regular graph which has 20 nodes & each node has 3 neghbour nodes.
     6 RG = nx.random_graphs.random_regular_graph(3, 20)
     7 # the spectral layout
     8 pos = nx.spectral_layout(RG)
     9 # draw the regular graphy
    10 nx.draw(RG, pos, with_labels = False, node_size = 30)
    11 plt.show()

    复制代码

     

     


     

    二、ER随机图

      ER随机图是早期研究得比较多的一类“复杂”网络,模型的基本思想是以概率p连接N个节点中的每一对节点。用random_graphs.erdos_renyi_graph(n,p)方法生成一个含有n个节点、以概率p连接的ER随机图:

    复制代码

     1 import networkx as nx
     2 import matplotlib.pyplot as plt
     3 
     4 # erdos renyi graph
     5 # generate a graph which has n=20 nodes, probablity p = 0.2.
     6 ER = nx.random_graphs.erdos_renyi_graph(20, 0.2)
     7 # the shell layout
     8 pos = nx.shell_layout(ER)
     9 nx.draw(ER, pos, with_labels = False, node_size = 30)
    10 plt.show()

    复制代码

     

    三、WS小世界网络

      用random_graphs.watts_strogatz_graph(n, k, p)方法生成一个含有n个节点、每个节点有k个邻居、以概率p随机化重连边的WS小世界网络。

      下面是一个例子:

    复制代码

     1 import networkx as nx
     2 import matplotlib.pyplot as plt
     3 
     4 # WS network
     5 
     6 # generate a WS network which has 20 nodes,
     7 # each node has 4 neighbour nodes,
     8 # random reconnection probability was 0.3.
     9 WS = nx.random_graphs.watts_strogatz_graph(20, 4, 0.3)
    10 # circular layout
    11 pos = nx.circular_layout(WS)
    12 nx.draw(WS, pos, with_labels = False, node_size = 30)
    13 plt.show()

    复制代码

    四、BA无标度网络

      用random_graphs.barabasi_albert_graph(n, m)方法生成一个含有n个节点、每次加入m条边的BA无标度网络。

      下面是一个例子:

    复制代码

     1 import networkx as nx
     2 import matplotlib.pyplot as plt
     3 
     4 # BA scale-free degree network
     5 # generalize BA network which has 20 nodes, m = 1
     6 BA = nx.random_graphs.barabasi_albert_graph(20, 1)
     7 # spring layout
     8 pos = nx.spring_layout(BA)
     9 nx.draw(BA, pos, with_labels = False, node_size = 30)
    10 plt.show()

    复制代码

     

    展开全文
  • 复杂网络分析+代码实现写在前面的话学习资料复杂网络复杂网络的特性小世界特性性质实际影响无标度特性性质实际影响社区结构特性经典的复杂网络模型规则图ER随机网络模型性质实际影响BA无尺度网络模型性质实际影响无...

    写在前面的话

    关于图的相关笔记,仅供参考。

    学习资料

    社交计算与社会网络分析
    NetworkX复杂网络分析教程
    全面介绍图论及其应用
    图论与图学习(一):图的基本概念
    图论与图学习(二):图算法

    数据集

    复杂网络数据集(Facebook, Google+, Slashdot, Twitter, Epinions等等)

    复杂网络

    随机网络:两个节点之间是否有边连接根据概率决定。

    规则网络:两个节点之间是否有边连接是确定的。

    复杂网络:绝大多数的实际网络并不是完全随机的,既不是规则网络,也不是随机网络,而是具有与前两者皆不同的统计特征的网络。

    复杂网络的特性

    具有自组织、自相似、吸引子(网络的内聚倾向)、小世界(相互关系的数目可以很小但却能够连接世界的事实)、无标度中部分或全部性质的网络称为复杂网络。

    小世界特性

    小世界特性(Small world theory):六度空间理论或者是六度分割理论(Six degrees of separation)。

    六度空间理论:社交网络中的任何一个成员和任何一个陌生人之间所间隔的人不会超过六个

    特征路径长度(characteristic path length):在网络中,任选两个节点,连通这两个节点的最少边数,定义为这两个节点的路径长度,网络中所有节点对的路径长度的平均值,定义为网络的特征路径长度,这是网络的全局特征

    聚合系数(clustering coefficient):假设某个节点有k条边,则这k条边连接的节点(k个)之间最多可能存在的边的条数为k(k−1)/2,用实际存在的边数除以最多可能存在的边数得到的分数值,定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征,反映了相邻两个人之间朋友圈子的重合度,即该节点的朋友之间也是朋友的程度。

    性质

    规则网络:任意两个点之间的特征路径长度长(通过多少点连在一起),但聚合系数高(共同邻居或共同间接邻居多)。

    随机网络:任意两个点之间的特征路径长度短,但聚合系数低。

    小世界网络:点之间特征路径长度小,接近随机网络,而聚合系数依旧相当高,接近规则网络。

    实际影响

    实际的社交、生态等网络都是小世界网络,这里面信息传递速度快,并且少量改变几个连接,就可以剧烈地改变网络的性能。

    例如:蜂窝电话网,改动很少几条线路,就可以显著提高性能。

    无标度特性

    无标度网络:少数的节点拥有大量的连接,而大部分节点少,并且节点的度数分布符合幂率分布。

    性质

    异质性:其各节点之间的连接状况(度数)具有严重的不均匀分布性。

    例如:网络中少数称之为Hub点的节点拥有极其多的连接,而大多数节点只有很少量的连接。少数Hub点对无标度网络的运行起着主导的作用。从广义上说,无标度网络的无标度性是描述大量复杂系统整体上严重不均匀分布的一种内在性质。

    实际影响

    无标度特性与鲁棒性:网络中的关键节点和链路往往成为攻击的对象。

    社区结构特性

    集群特性:复杂网络中普遍存在着聚类特性,每一个类称之为一个社团(community)。

    例如,社会网络中总是存在熟人圈或朋友圈,其中每个成员都认识其他成员。

    集群程度的意义:网络集团化的程度,这是一种网络的内聚倾向。

    连通集团概念:一个大网络中各集聚的小网络分布和相互联系的状况。

    例如,它可以反映这个朋友圈与另一个朋友圈的相互关系。

    经典的复杂网络模型

    经典网络模型的原理和构造方法,包括规则图,ER随机网络模型、BA无尺度网络模型和WS小世界模型。

    规则图

    规则图:一个含有n个节点,每个节点有d个邻居节点的规则图。

    import networkx as nx
    import matplotlib.pyplot as plt
    
    RG = nx.random_graphs.random_regular_graph(3, 20)
    pos = nx.spectral_layout(RG)
    nx.draw(RG, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    ER随机网络模型

    ErdOs-Renyi随机网络模型(ER):在网络节点间随机地布置连接,是个机会均等的网络模型.

    import networkx as nx
    import matplotlib.pyplot as plt
    
    ER = nx.random_graphs.erdos_renyi_graph(20, 0.2)
    pos = nx.shell_layout(ER)
    nx.draw(ER, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    性质

    户:给定一定数目的节点,它和其他任意一个节点之间有相互连接的概率相同。

    因为一个节点连接k个其他节点的概率,会随着k值的增大而呈指数递减。

    这样,如果定义是为每个节点所连接的其他节点的数目,可以知道连接概率p(k)服从钟形的泊松(Poisson)分布,有时随机网络也称作指数网络。

    尽管连接是随机安置的,但由此形成的网络却是高度民主的,也就是说,绝大部分节点的连接数目会大致相同。实际上,随机网络中连接数目比平均数高许多或低许多的节点,都十分罕见。

    实际影响

    在过去40多年里,科学家习惯于将所有复杂网络都看作是随机网络。在1998年研究描绘万维网(以网页为节点、以超级链接为边)的项目时,学者们原以为会发现一个随机网络:人们会根据自己的兴趣,来决定将网络文件链接到哪些网站,而个人兴趣是多种多样的,可选择的网页数量也极其庞大,因而最终的链接模式将呈现出相当随机的结果。

    然而,事实并非如此。因为在万维网上,并非所有的节点都是平等的。在选择将网页链接到何处时,人们可以从数十亿个网站中进行选择。然而,我们中的大部分人只熟悉整个万维网的一小部分,这一小部分中往往包含那些拥有较多链接的站点,因为这样的站点更容易为人所知。只要链接到这些站点,就等于造就或加强了对它们的偏好。这种“择优连接(Preferential Attachment)”的过程,也发生在其他网络中。在Internet上,那些具有较多连接的路由器通常也拥有更大的带宽,因而新用户就更倾向于连接到这些路由器上。在美国的生物技术产业内,某些知名公司更容易吸引到同盟者,而这又进一步加强了它在未来合作中的吸引力。类似地,在论文引用网络(论文为节点,引用关系为边)中,被引用次数较多的科学文献,会吸引更多的研究者去阅读并引用它。针对这些网络的“择优连接”的新特性,学者提出了BA无尺度网络模型。

    BA无尺度网络模型

    主要特征:节点的度分布服从幂次定律。

    import networkx as nx
    import matplotlib.pyplot as plt
    
    BA = nx.random_graphs.barabasi_albert_graph(20, 1)
    pos = nx.spring_layout(BA)
    nx.draw(BA, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    性质

    BA模型系统的成长性(Growth)和择优连接性。

    BA模型的扩充可以考虑三个因素:择优选择的成本、边的重新连接、网络的初始状态。

    实际影响

    无尺度网络

    1999年,丸Barabasi和兄Albert在对互联网的研究中发现了无尺度网络,使人类对于复杂网络系统有了全新的认识。过去,人们习惯于将所有复杂网络看作是随机网络,但Barabasi和Albert发现互联网实际上是由少数高连接性的页面组织起来的,80%以上页面的链接数不到4个。只占节点总数不到万分之一的极少数节点,却有1000个以上的链接。这种网页的链接分布遵循所谓的“幂次定律”:任何一个节点拥有是条连接的概率,与1/k成正比。它不像钟形曲线那样具有一个集中度很高的峰值,而是一条连续递减的曲线。如果取双对数坐标系来描述幂次定律,得到的是一条直线。

    Scale-free网络指的是节点的度分布符合幂律分布的网络,由于其缺乏一个描述问题的特征尺度而被称为无尺度网络。其后的几年中,研究者们在许多不同的领域中都发现了无尺度网络。从生态系统到人际关系,从食物链到代谢系统,处处可以看到无尺度网络。

    BA模型及其机制

    为什么随机模型与实际不相符合呢?Barabasi和Albert在深入分析了ER模型之后,发现问题在于ER模型讨论的网络是一个既定规模的,不会继续扩展的网络。正是由于现实当中的网络往往具有不断成长的特性,早进入的节点(老节点)获得连接的概率就更大。当网络扩张到一定规模以后,这些老节点很容易成为拥有大量连接的集散节点。这就是网络的“成长性”。

    其次,ER模型中每个节点与其他节点连接时,建立连接的概率是相同的。也就是说,网络当中所有的节点都是平等的。这一情况与实际也不相符。例如,新成立的网站选择与其他网站链接时,自然是在人们所熟知的网站中选择一个进行链接,新的个人主页上的超文本链接更有可能指向新浪、雅虎等著名的站点。由此,那些熟知的网站将获得更多的链接,这种特性称为“择优连接”。这种现象也称为“马太效应(Matthew Effect)”或“富者更富(Rich Get Richer)”。

    “成长性”和“择优连接”这两种机制解释了网络当中集散节点的存在。

    BA模型的改进方向

    BA无尺度模型的关键在于,它把实际复杂网络的无尺度特性归结为增长和优先连接这两个非常简单的机制。当然,这也不可避免地使得BA无尺度网络模型和真实网络相比存在一些明显的限制。比如,一些实际网络的局域特性对网络演化结果的影响、外界对网络节点及其连接边删除的影响等。

    一般自然的或者人造的现实网络与外界之间有节点交换,节点间连接也在不断变化,网络自身具有一定的自组织能力,会对自身或者外界的变化作出相应的反应。因此,在BA模型基础上,可以把模型的动力学过程进行推广,包括对网络中已有节点或者连接的随机删除及其相应的连接补偿机制。

    对每一个时间步长,考虑如下三种假设:

    1、成长假设:一个带有m个择优连接的新节点加入网络,这个新节点选择网络中m个节点,即对于每一个连接,一个度为是的节点作为目标
    被选择的概率正比于k;

    2、删除假设:考虑网络中若干个节点,这些节点与其他节点之间的连接边被随机地选作目标边而被删除,导致网络的演化;

    3、补偿假设:网络中失去一个连接,同时产生n个连接进行补偿,其中”有上确界,是一个受网络补偿能力限制的量,这里的补偿连接所选择的目标节点也遵循择优连接原则。

    利用以上三种假设,很多学者已经对BA模型进行了有效的改进,读者可参考相关文献,此处不再详述。

    小世界网络模型

    “小世界现象”/“六度分离(Six Degrees of Separation)”:绝大多数大规模真实网络的平均路径长度比想象的小得多。

    小世界现象:每个人只需要很少的中间人(平均6个)就可以和全世界的人建立起联系。

    WS小世界模型:介于规则网络和完全随机网络之间的单参数小世界网络模型,该模型较好地体现了社会网络的小平均路径长度和大聚类系数两种现象。

    import networkx as nx
    import matplotlib.pyplot as plt
    
    WS = nx.random_graphs.watts_strogatz_graph(20, 4, 0.3)
    pos = nx.circular_layout(WS)
    nx.draw(WS, pos, with_labels = False, node_size = 30)
    plt.show()
    

    在这里插入图片描述

    WS小世界模型构造

    从规则图开始,考虑一个含有N个节点的规则网络,它们圈成一个环,其中每个节点都与它左右相邻的各K/2个节点相连接,K为偶数;

    随机化重连,以概率户随机地重新连接网络中的每条边(将边的一个端点保持不变,而另一个端点取为网络中随机选择的一个节点),其中规定,任意两个不同的节点之间至多只能有一条边,并且每一个节点都不能有边与其自身相连。

    在WS小世界模型中,p=0对应于规则网络,p=l则对应于完全随机网络,通过调节声的值就可以控制从规则网络到完全随机图的过渡。因此,WS小世界网络是介于规则网络和随机网络之间的一种网络。

    WS小世界模型构造算法中的随机化过程有可能破坏网络的连通性。

    NW小世界模型构造

    从规则图开始,考虑一个含有N个点的规则网络,它们圈成一个环,其中每个节点都与它左右的相邻的各K/2节点相连,K是偶数;

    随机化加边,以概率p随机选取的一对节点之间加上一条边。其中规定,任意两个不同的节点之间至多只能有一条边,并且每一个节点都不能有边与自身相连。

    NW模型只是将WS小世界模型构造中的“随机化重连”改为“随机化加边”。

    NW和WS的区别

    NW模型不同于WS模型之处在于它不切断规则网络中的原始边,而是以概率p重新连接一对节点。这样构造出来的网络同时具有大的聚类数和小的平均距离。

    NW模型的优点在于其简化了理论分析,因为WS模型可能存在孤立节点,但NW模型不会。当户足够小和N足够大时,NW小世界模型本质上就等同于WS小世界模型。

    实际影响

    小世界网络模型反映了实际网络所具有的一些特性,例如朋友关系网,大部分人的朋友都是和他们住在同一个地方,其地理位置不是很远,或只在同一单位工作或学习的同事和同学。另一方面,也有些人住得较远的,甚至是远在异国他乡的朋友,这种情形好比WS小世界模型中通过重新连线或在NW小世界模型中通过加入连线产生的远程连接。

    小世界网络模型的主要特征之一是节点之间的平均距离随远程连接的个数而指数下降。对于规则网络,平均距离L可估计为L正比于N;而对于小世界网络模型,L正比于ln(N)/1n(K)。例如,对于一个千万人口的城市,人与人的平均接触距离是6左右,这使得生活人群之间的距离大大缩短。该模型由一个规则的环组成,通常是一个一维的几乎具有周期性边界条件的环(即环中每个节点几乎都连接到一固定数目的邻近节点)和少量的随机选取节点连接成的“捷径” (重新连接现存的边)。小世界网络同时具有“高网络聚集度”和“低平均路径”的特性。

    从小世界网络模型中可以看到,只要改变很少的几个连接,就可以剧烈的改变网络的性能。这样的性质也可以应用其他网络,尤其是对已有网络的调整方面。例如,蜂窝电话网,改动很少几条线路(低成本、低工作量)的连接,就可以显著提高性能。也可以应用到互联网的主干路由器上,以改变流量和提高传输速度。同样的思路也可以应用到电子邮件的快速传递、特定Web站点的定位等。

    展开全文
  • Networkx的四种网络模型一. Networkx的下载安装二. 规则图三、ER随机图四、WS小世界网络五、BA无标度网络 NetworkX提供了4种常见网络的建模方法,分别是:规则图,ER随机图,WS小世界网络和BA无标度网络。 一. ...
  • 复杂网络建模总结

    千次阅读 2020-10-27 23:29:38
    本文针对数学建模美赛中的复杂网络题,做了一些总结,具体涉及一些该题的注意事项。 注意事项 定义点和边的意义 制定连接规则,删除孤立节点(代表影响很小的点),可以限制网络的大小,减小运算量,同时也可以...
  • 无标度网络生成模型

    万次阅读 多人点赞 2018-10-08 11:55:51
    本文采用由 Barabási 和 Albert 于 1999 年提出的增长网络网络模型(BA 模型)。在该模型中,网络初始时具有 m0 个节点,两两互连。 之后每过一个时间单位增加一个新节点。新节点从当前网络中选择m(m ≤ m0)个节点...
  • 7种复杂网络MATLAB经典算法,包含GN;ER;BA;WS;NW等算法,可直接使用,仅限个人
  • 生成式对抗网络(GAN,Generative Adversarial Networks)   无监督深度学习,...  它由两个成对的网络协同运作,即生成模型(Generative Model)和判别模型(Discriminative Model),两者的的互相博弈学习产生...
  • 一文读懂复杂网络(应用、模型和研究历史)

    万次阅读 多人点赞 2018-05-02 09:40:05
    摘要:随着近几年关于复杂网络(Complex network)理论及其应用研究的不断深入,已有大量关于复杂网络的文章发表在Science,Nature,RL,NAS等国际一流的刊物上,侧面反映了复杂网络已经成为物理界的一个新兴的研究...
  • 复杂网络实验3:BA模型(matlab)

    万次阅读 多人点赞 2019-04-04 23:45:18
    m_add:每次引入新节点时新生成的边数 m_after_growth:增长后的网络规模 pp:初始网络节点的连接选择 pp=1 节点均孤立 pp=2 节点间构成完全图 pp=3 随机连接一些边(随机图) 代码中这些参数都在最前面给出,可以...
  • 复杂网络是一个非常庞大的研究领域,有众多研究方法与研究对象,社交网络、科学家网络、生物网络、交通网络、生物网络等等。在进行仿真时候,有的网络过于庞大无法用实际的数据进行仿真,例如社交网络。而有一些网络...
  • 复杂网络】网络级联模型

    千次阅读 2019-05-24 11:04:18
    网络级联模型的一些补充:https://www.jianshu.com/p/9f36b8649335 独立级联模型 首先,我们将社交网络抽象为一个有向图,其中,为节点的集合,是边的集合,网络中的节点有两个状态——激活...
  • python 复杂网络中的 SIR 模型

    千次阅读 热门讨论 2020-11-26 00:58:19
    python 实现 复杂网络(小世界网络)中的 SIR 传染病模型
  • 复杂网络

    千次阅读 2018-10-28 16:31:28
    文章目录复杂网络复杂网络基本概念平均路径长度聚类系数度与度分布网络拓扑基本模型及其性质规则网络全局耦合网络最近邻耦合网络星型耦合网络随机图(ER随机图)小世界网络模型WS小世界模型NW小世界模型小世界网络的...
  • 生成式对抗网络模型(GAN)是基于深度学习的一种强大的生成模型,可以应用于计算机视觉、自然语言处理、半监督学习等重要领域。生成式对抗网络最最直接的应用是数据的生成,而数据质量的好坏则是评判GAN成功与否的关键...
  • 基于NetworkX构建复杂网络的应用案例

    千次阅读 2021-12-11 18:42:18
    本文主要完成了networkx的安装以及校园网络拓扑图的绘制,又完成了根据权重筛选节点的功能。这里面比较使用的功能在于可以固定生成节点的位置,添加节点的自定义图标,以及根据权重,出入度等值完成节点筛选。
  • 生成模型就属于无监督学习的一种 生成模型 生成模型的目标是给定训练数据,希望能获得与训练数据相同的新数据样本。我们的目标是找到训练数据的分布函数 生成模型在很多场景有非常好的应用 ...
  • # 深度学习-52:生成式对抗网络GAN(原理、模型和演进)。GAN模型演化出WGAN、WGAN GP、LS GAN、DRAGAN、BEGAN等GAN模型变体。Goodfellow认为正确使用数据的方式,先对数据集的特征信息有insight之后,再干活。在2014年...
  • 复杂网络实验2:WS小世界模型(matlab)

    万次阅读 多人点赞 2019-03-28 22:49:56
    复杂网络实验2:WS小世界模型(matlab) 一.思路 1.小世界模型3个参数,N为点的数目,K表示每个点左边K/2个邻居,右边K/2个邻居,一共K个邻居,P代表每条边以多少概率重连 2.首先给定这三个参数(源码是人工输入...
  • 生成对抗网络(GANs)是一种能“教会”计算机胜任人类工作的有趣方法。一个好的对手能让你成长更快,而GANs背后就是“从竞争中学习”的思路。 GANs最先是由蒙特利尔大学的Ian Goodfellow提出,已在图像生成和风格...
  • 【机器学习】生成对抗网络 GAN

    千次阅读 2021-10-26 20:09:35
    GAN的设计初衷GAN 的基本原理(大白话)生成对抗网络(GAN)由2个重要的部分构成训练过程GAN的总结GAN的提出:“Generative Adversarial Networks”(2014NIPS)GAN的优缺点GAN 的实际应用GAN的一些经典变种1....
  • 顺便一提,本文基于SI模型,如果需要SIR模型还是SIS还是SIER模型的可以自己改进。 1 效果展示——树状网络 照例,先来一波效果展示。 在可视化中红色是已被感染的节点,绿色是健康节点。 这里我先展示一下3个分支5...
  • 第五章:深度生成模型

    万次阅读 2020-03-31 11:48:22
    常见的深度生成模型的结构图如下:深度玻尔兹曼机和深度信念网络都是以受限的玻尔兹曼机为基本单元,区别就是深度信念网络的最高层的两层是无向图的连接,下面的两层是采用有向图的连接;深度自编码网络可以看做由...
  • 机器学习与深度学习里生成模型和判别模型的理解

    万次阅读 多人点赞 2018-05-10 15:20:51
    这篇博客是自己在学习生成模型与判别模型过程中的一些记录,整理了相关的文章后写成,感谢前辈们的辛苦总结转载自:...
  • pytorch 生成模型Detailed instructions for constructing generative adversarial neural networks (GANs) using the example of two models implemented using the PyTorch deep learning framework. 使用通过...
  • 复杂网络】自学笔记整理

    万次阅读 多人点赞 2020-06-29 17:15:45
    一、复杂系统与复杂网络 1.研究目的        复杂网络是研究复杂系统的一种角度和方法,它主要关注系统中个体相互关联的作用。(一种拓扑结构) 2.当今应用    &...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 228,474
精华内容 91,389
关键字:

复杂网络生成模型