您所在位置：网站首页 > 海量文档
 
&nbsp>&nbsp计算机&nbsp>&nbspJava
 

 
复杂网络的社区结构.pdf14页
 
本文档一共被下载：次,您可全文免费在线阅读后下载本文档。
 
 
 

 

 

 

 
下载提示
 
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
 
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
 
3.登录后可充值，立即自动返金币，充值渠道很便利
 
第 8卷第 1期 复 杂 系 统 与 复 杂 性 科 学 V0l_8No．1
 
2011年 3月 COMPLEX SYSTEMSAND COMPLEXITY SCIENCE Mar． 2011
 
文章编号 ：i672 3813(2011)01—0057—14
 
复杂网络的社区结构
 
程学旗 ，沈华伟
 
基
 
(中国科 学院计算技术研究所 ，北京 100190)
 
摘要：社 区结构作为真实复杂 网络所普遍具有的一个重要拓扑特性 ，在最近 10年
 
内得到 了广泛而深入 的研 究 。回顾 了近 几年 国内外社 区结构研 究 的主要进展 ，重
 
点介绍社 区发现的研究历程和研 究成果，并结合社会计算的背景展 望 了社 区结构
 
研 究的未来发展 方 向和潜在 的应 用价值 。
 
关键词 ：社 区结构 ；社 区发现 ；模块度 ；社会计算
 
中图分类号 ：N94 文献标识码 ：A
 
CommunityStructureofComplexNetworks
 
CHENG Xueqi，SH EN H uawei
 
(InstituteofComputingTechnology，ChineseAcademyofSciences，Beijing100190，China)
 
Abstract：Asacommonandimportanttopologica1characteristicOfrealworldcomplexnetworks，
 
communitystructurehasbeenextensivelystudiedinthelastdecade．Thispaperreviewsthemain
 
progressesinthescientificresearchoncommunitystructure．Especially，thispaperdescribesthe
 
developmentatthedetectionofcommunitystructurefrom variousdisciplines．Finally，thispaper
 
discussesthefutureresearchdirectionsofthecommunitystructureandthepotentialapplications
 
in socialcomputing．
 
Keywords：communitystructure；communitydetection；modularity；socialcomputing
 
0 引言
 
真实世界中的许 多复杂系统可 以表示成 图或 网络 ，包括社会 网络 、信息 网络、生物 网络和技术 网络
 
等u]。经验分析表 明，这些复杂网络可 以自然地分成一些节点组 ，使 同一个节点组 内的两个节点之间 比不
 
同节点组的两个节点之间更倾 向于有边相连，网络的这种拓扑特性被称为社区结构 ，相应地，每个节点组被
 
称为一个社 区 。
 
社 区结构刻画了网络中连边关系的局部聚集特性 ，也体现了网络中连边的分布不均匀性 。进一步 ，网络
 
中的社区通常 由功能相近或性质相似的网络节点组成，因此 ，社区被认为有助于揭示 网络结构和功能之间的
 
关系l7]。以万维网(WorldWideWeb)为例，通过超链接 紧密关联 的网页形成一个个的社 区，同一个社区的
 
网页具有相近的话题 [3]。社区结构的示例如图 1所示 。
 
收稿 日期 ：2010 10—29
 
基金项 目：国家 自然科学基金60933005)
 
作者简介 ：程学旗 (1971一)，男，研究员 ，博导 ，主要研究方 向为网络科学 、海量信息检索和数据挖掘 、社会计算 、分布式计算和网络模拟仿真 。
 
· 58 · 复 杂 系
 
发表评论
 
请自觉遵守互联网相关的政策法规，严禁发布色情、暴力、反动的言论。
 
用户名:
 
验证码:
 

 
匿名?
 
发表评论

 
复杂网络分析+数据集+代码实现
 
写在前面的话
学习资料
数据集
复杂网络
复杂网络的特性
小世界特性
性质
实际影响
   
无标度特性
性质
实际影响
   
社区结构特性
  
经典的复杂网络模型
规则图
ER随机网络模型
性质
实际影响
   
BA无尺度网络模型
性质
实际影响
无尺度网络
BA模型及其机制
BA模型的改进方向
   
   
小世界网络模型
WS小世界模型构造
NW小世界模型构造
NW和WS的区别
实际影响
  
 

 
写在前面的话
 
关于图的相关笔记，仅供参考。
 
学习资料
 
社交计算与社会网络分析
 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是一个Python软件包，用于创建，操纵和研究复杂网络的结构，动力学和功能。
 
复杂网络软件
 
图，有向图和多重图的数据结构
许多标准图算法 网络结构与分析措施
经典图，随机图和合成网络的生成器
节点可以是“任何东西”（例如，文本，图像，XML记录）
边可以保存任意数据（例如权重，时间序列）
开源3条款BSD许可证
经过良好测试，代码覆盖率超过90％
Python的其他好处包括快速原型制作，易学和多平台
 
pdf下载链接：
 https://networkx.org/documentation/stable/_downloads/networkx_reference.pdf
 
github：https://github.com/networkx/networkx

前言：最近刚定下的课题，现在主要学习网络基础概念的知识，凡是学习总是得做下总结笔记才能比较清楚。也分享给大家一起学习吧，如有错误可以提出私信我或者评论。
 

社会网络通常显示出较强的社区效应，网络中的节点趋于形成紧密联系的群组。
 
 
社区定义：社区结构是网络顶点的组。 在这些组内有密集的内部联系，但在组之间有较少的边缘。
 
 
社区特征：社团内部连接紧密，社团之间连接相对稀疏。
 
 
社区发现/社区检测/社团检测定义：将网络节点按照其内在的拓扑结构连接紧密程度划分成若干子图的过程。
 
 
社区结构划分的意义：社区往往代表了复杂网络中具有相同或者相似功能的元素的集合，这些元素相互协作或者相互作用，共同完成整个系统中某些相对独立的功能或者组成相对独立的组织结构。提取网络中的社区结构有助于我们理解网络的拓扑结构特性、揭示复杂网络系统内在的功能特性、理解社区内个体之间的关系及演化趋势。
 
 
均匀网络
 
泊松分布和幂律分布对应于均匀网络和非均匀网络。
 
服从泊松分布的网络叫均匀网络，均匀网络和非均匀网络（无标度网络）是一个对比。
 
 
BA 无标度网络
 
1999 年 Barabási 和 Albert 提出了无标度网络模型（简称 BA 模型）。无标度网络的重要特征为： 无标度网络的节点度分布服从幂律分布。
 
近年在复杂网络研究上的另一重大发现就是许多复杂网络，包 Internet WWW 以及新陈代谢网络等的连接度分布函数具有幂律形式。由于这类网 络的节点的连接度没有明显的特征长度，故称为无标度网络
 
①增长 (growth) 特性 即网络的规模是不断扩大的。例如每个月都会有大量的新 的科研文章发表，而 WWW 上则每天都有大量新的网页产生。
 
②优先连接 (preferential attachment) 特性 即新的节点更倾向于与那些具有较高 连接度的"大"节点相连接。这种现象也称为"富者更富 (rich get richer)" 或"马太效应 (Matthew effect)" 。
 
BA 无标度模型构造算法
 
①增长 从一个具有 mo 个节点的网络开始，每次引入一个新的节点，并且连到个已存在的节点上，这里 m<:mo
 
②优先连接:一个新节点与一个已经存在的节点 相连接的概率
 
与节点 i的度ki、节点j的度kj之间满足如下关系:
 
 
 
 
 
 
特征长度
 
幕律分布
 
幂律分布是指某个具有分布性质的变量，且其分布密度函数是幂函数（由于分布密度函数必然满足“归一律”，所以这里的幂函数，一般规定小于负1）的分布。
 
 
幂律分布表现为一条斜率为幂指数的负数的直线,这一线性关系是判断给定的实例中随机变量是否满足幂律的依据。
 
幂律分布也称为无标度 (scale- free) 分布，具有幂律度分布的网络也称为无标度网络，这是由于幂律分布函数具有如下无标度性质。即系统中个体的尺度相差悬殊,缺乏一个优选的规模。
 
当样本数据较多时，变量x的概率密度函数：f(x)~x^(-α-1)。
 
模块性
 
系统的模块化程度。系统中的模块内聚程度越高，模块之间耦合度越低，系统的模块性越好。
 
模块度（modularity）
 
是常用的社团划分质量评价指标，基本想法是把社团划分后的网络与相应的零模型进行比较，度量社团划分的质量。
 
 
零模型：与原网络具有相同节点数目、相同连边数目、相同度序列的随机网络。
 
*互信息NMI（Normalized Mutual Information ）
 
互信息的概念大家都不陌生，它基于香农熵，衡量了两个随机变量间的依赖程度。而不同于普通的相似性度量方法，互信息可以捕捉到变量间非线性的统计相关性，因而可以认为其能度量真实的依赖性。
 
模体
 
模体是网络的基本拓扑结构之一, 它的大小介于网络个体和社团之间, 一般由少数几个节点连接构成, 模体也揭示了网络的演化规律, 它是社团内部成员之间基本的连接模式
 
超家族
 
从共同祖先进化而来、但相似性较少的一组（基因）或（蛋白质）。
 
 
自相似性
 
如果一个物体自我相似（Self-similarity），表示它和它本身的一部分完全或是几乎相似。
 
自相似包含两种，一种是部分和整体严格的相似，另一种指的是统计上的相似，比如海岸线。
 
 
 
层次性
 
（实际双向连接的边的数量）/（可能双向连接的边的数量,即C(n,2)）
 
我们假想在一个企业的命令传达网络中，如果命令都是从上到下单向传递的，那么我们认为整个的网络很有层次，所以双向连接的数量就很少，层次度就更加接近于1。反之，如果一个企业中，A可以向B传达命令，同时B也可以对A下达命令，那么这个组织就不是那么的有层次性。
 
 
结构冗余性
 
 
模块化
 
 
网络进化
 
 
鲁棒性
 
鲁棒是Robust的音译，也就是健壮和强壮的意思。它也是在异常和危险情况下系统生存的能力。
 
在复杂网络中，如果在移走少量节点后网络中的 绝大部分节点仍是连通的，那么就称该网络的连通性对节点故障具有鲁棒性。
 
 
脆弱性
 
存在致命缺点
 
 
同配性(assortatvity)与异配性(disassortatvity)：
 
在不改变节点度分布的情况下，可以使度大的节点倾向于和其它度大的节点连接。网络中的这个重要的结构特性，称之为节点之间的相关性(Correlation)。如果网络中的节点趋于和它近似的节点相连，就称该网络是同配的(Assortative)；反之，就称该网络是异配的(Disassortative)。
 
网络同配性(或异配性)的程度可用同配系数(也称Pearson Coefficient----皮尔森系数)r来刻画。r>0表示整个网络呈现同配性结构，度大的节点倾向于和度大的节点相连；r<0表示整个网络呈现异配性；r=0表示网络结构不存在相关性
 
 
核数
 
一个节点的核数，就是网络在进行k核分解（k-core decomposition）是的k-shell指数。对于一个网络，0核是原图；1核就是去掉所有孤立点的图；2核就是先去掉所有度小于2的点，然后再剩下的图中再去掉度小于2的点，依次类推，直到不能去掉为止；一个节点的核数定义为这个节点所在的最大核的阶数——比如一个节点最多在5核而不在6核中，就说这个节点的核数=5。
 
 
介数
 
介数通常分为边介数和节点介数两种.
 
节点介数：为网络中所有最短路径中经过该节点的路径的数目占最短路径总数的比例.
 
边介数：为网络中所有最短路径中经过该边的路径的数目占最短路径总数的比例.
 
介数反映了相应的节点或者边在整个网络中的作用和影响力，是一个重要的全局几何量，具有很强的现实意义。
 
 
最短路径
 
连接两个节点最少边数的路径
 
 
平均路径长度
 
网络中任意两个节点之间路径长度的平均值，
 
 
度分布
 
度分布指的是对一个图（网络）中顶点（节点）度数的总体描述。对于随机图，度分布指的是图中顶点度数的概率分布。
 
 
集聚系数
 
集聚系数（也称群聚系数、集群系数）是用来描述一个图中的顶点之间集结成团的程度的系数。具体来说，是一个点的邻接点之间相互连接的程度。例如生活社交网络中，你的朋友之间相互认识的程度。
 
公式为一节点的边数Ei比上全部可能的边数：
 
 
 
全局耦合网络 (globally coupled network) 中，任意两个点之间都有边直接相
 
连(图 2-1 (a 门。因此，在具有相同节点数的所有的网络中，全局藕合网络具有最小的平均
 
路径长度 gc =l 和最大的聚类系数 =1 。
 
 
最近邻藕合网络( nearest-neighbor  coupled network) ，
 
其中每一个节点只和它周围的邻居节点相连。真有周期边界条件的
 
最近邻藕合网络包含 个围成一个环的点，其中每个节点都与它左右各 K/2 个邻居点
 
相连，这里 是一个偶数(罔 2- l( b)) 。
 
 
星形藕合网络(star coupled network) ，它有一个中心点，
 
其余的 N-1 个点都只与这个中心点连接，而它们彼此之间不连接(图 2- l( c)) 。
 
 
WS小世界模型构造算法 
 
作为从完全规则网络向完全随机图的过渡，Watts Strogtz 1998 年引人了一个有趣 的小世界网络模型，称为 WS 小世界模型。 WS 小世界模型的构造算法如下:
 
①从规则图开始：考虑一个含有 N 个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各 K/2 节点相连 ，K是偶数。
 
②随机化重连：以概率 P 随机地重新连接网络中的每个边，即，将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。
 
 
NW 小世界模型构造算法 
 
WS 小世界模型构造算法中的随机化过程有可能破坏网络的连通性。另一个研究较 多的小世界模型是由 Newman Watts 稍后提出的，称为 NW 小世界模型。
 
该模型是通过用"随机化加边"取代 WS 小世界模型构造中的"随机化重连"而得到的 。具体构造算法如下:
 
①从规则图开始：考虑一个含有 N 个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各 K/2 节点相连 ，K是偶数。
 
②随机化加边：以概率 P 在随机选取的一对节点之间加上一条边 其中，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。
 
 
适应度模型构造算法 
 
①增长:从一个具有 m0 个节点的网络开始每次引入一个新的节点并且连到 m 个已存在的节点上，这里 m≤m0 每个节点的适应度按概率分布 ρ(η) 选取。
 
②优先连接:一个新节点与一个已经存在的节点 i 相连接的概率且∏，与节点 i 的度k 、节点 j 的度 kj 和适应度 ηi 之间满足如下关系
 
 
 
富人俱乐部 (rich-club)
 
Internet 中少量的节点具有大量的边，这些节点也称为"富节点 (rich nodes)"; 它们
 
倾向于彼此之间相互连接(图 3-11) ，构成"富人俱乐部 (rich-club)"。
 

待续……
 
 
如果有帮助就点个赞吧！嘻嘻~🤙🤙🤙
 
如果有帮助就点个赞吧！嘻嘻~🤙🤙🤙
 
如果有帮助就点个赞吧！嘻嘻~🤙🤙🤙