复杂网络分析大纲

本文最后更新于:2021年3月22日 晚上

学习复杂网络分析时提炼的大纲,供大家学习

复杂网络分析大纲

复杂网络分析概论

复杂网络分析在复杂性研究中的地位

  • 一个系统的两个维度

    1. 自由度:组成成分
    2. 相互作用:线性到非线性
  • 复杂网络是复杂系统的骨架和抽象:一个复杂系统=分解+组合

复杂网络分析的发展历程

  1. 欧拉七桥问题
  2. 随机图论
  3. 小世界网络,无标度网络

网络拓扑结构的统计性质

  • 度:节点的一阶邻居数
  • 聚集系数:节点的一阶近邻互相连接的情况
  • 最短路径:连接两个节点的边数最少的路径
  • 介数:任意一对节点间最短路径所经过的次数
  • 权:连边的强度
  • 度度相关性:不同度值的节点互相连接的倾向性
  • 社团结构:网络的中观特性,社团内的连边相对紧密,社团间的连边相对稀疏

复杂网络分析中的基本概念

复杂网络的表达方式

  • 图表达

    • 组成部分:节点,顶点
    • 相互作用:连边,边
    • 系统:网络,图
  • 集合表达 G=(V,E)

    • V:点集
    • E:边集
  • 链接矩阵:两点相连标1

    • Laplace 矩阵:L=KAL=K-A;其中 AA 为网络的链接矩阵,KK 为一对角矩阵,对角线上的元素对应网络中各个节点的度

网络拓扑:网络中节点的连接形式是怎样的

度、平均度、度分布

  • 节点的度:与节点直接相连的连边数
  • 平均度:网络中所有节点的度的平均值
  • 度分布:网络中的节点的度值从小到大排列,统计度值为 kk 的节点占整个网络节点数的比例 P(k)P(k),即 P(k)=NkNP(k)=\frac{N_k}{N}

路径、距离、介数

  • 路径:一条路径是指一个节点序列,其中每一对相邻的节点之间都有一条连边

  • 最短路径:连接两个节点的边数最少的路径

    • 最短距离:这两点之间的边数
  • 直径:网络中任意两点间最短距离的最大值

  • 平均路径长度:平均最短距离 d=12Lmaxi,jjdij\left \langle d \right \rangle=\frac{1}{2L_{max}}\sum_{i,j\ne j}d_{ij}

  • 介数:任意一对节点间最短路径所经过的次数

    • 点介数、边介数

    • 反映了相应节点或边在网络中的作用和影响力,是一个全局几何量

集聚系数

  • 节点的集聚系数:节点 iikik_i 个邻居节点之间实际存在的边数 EiE_i和总的可能边数之比

    • 公式法

    • 包含节点 ii 的三角形数目/以节点 ii 为中心的连通三元组的数目

  • 网络的集聚系数:网络中所有节点的集聚系数的平均值

  • 网络的传递系数 TT:网络中三角形数目/(3*网络中联通三元组的数目)

    • T=1T=1:任意两点都有边连接
    • T=0T=0:任意两点都没有边连接

网络稀疏性与连通性

  • 网络稀疏性:网络中实际存在的边数与最大可能的边数之比
  • 连通性
    • 连通图:网络中任意两个节点之间都至少存在一条路径
    • 最大连通集团:含有节点数最多的连通子图

度的相关性

  • 两个节点度值之间的关系

    • 同配:度大节点倾向于连接度大节点
    • 异配:度大节点倾向于连接度小节点
    • 中性:节点之间的连接与它们自身的度值无关
  • 衡量度度相关性的方法

    • 可视化描述
    • 度相关函数:平均邻居度
    • 相关系数
    • 皮尔逊相关系数

富人俱乐部

  • 富人俱乐部现象:具有异配特性的图高度节点之间仍然具有很高的连接概率
  • 富人俱乐部系数
    • 标准化富人俱乐部系数:更贴近现实

有向网络

  • 链接矩阵不具有对称性

    • 出度:点的出边条数
    • 入度:顶点的入边条数
    • 总度:出度、入度之和
    • 源:节点入度为0
    • 汇:节点出度为0
  • 路径:仅能沿着箭头的方向

  • 连通:把所有有向边替换成无向边,替换后的无向网络是一个连通图,则称为该有向网络是一个弱连通图;强连通图:有向图中任意两点之间都纯在路径

  • 模体:有向网络中少量个体之间存在一种模式

加权网络

  • 多条边网络

  • 加权方式:

    • 网络中已有的物理量:因特网——宽带
    • 相互作用的抽象:科学家合作网——合著文章数
      • 顶点——事件构成的双顶点网(广义合作网)
  • 相似权:边权越大,顶点越亲近。0为无连接

  • 相异权:边权越大,顶点越亲近。0为无连接

  • 节点的集聚系数:定义满足四个条件

    1. 在[0,1]之间
    2. 权重为0则无边连接
    3. 权重为1是回归无权网
    4. 与三角形每条边上的权重相关

ER网络

  • 随机网络

  • ER网络的生成方式

    • G(N,L)G(N,L) 模型:一个随机网是由 NN 个节点构成,并且有 LL 条连边随机放置在 LL 对节点之间(不出现重边和自环)
  • G(N,p)G(N,p) 模型:一个随即图由 NN 个节点构成,并且任意两点不同节点之间存在一条连边的概率为 pp

  • 边数分布: 二项分布——近似泊松分布

    • 边数分布的平均值:<k>=P(N1)P(N-1)

      亚临界 临界 超临界 连通
      <k><1 <k>=1 <k>>1 <k>>lnN
      不存在最大连通集团 唯一的最大连通集团 唯一的最大连通集团 只有一个连通图(最大连通集团稠密)

ER网络的基本性质

  • 度、距离(利用泊松分布近似)

  • 集聚系数:固定网络的平均度,集聚系数随网络规模 NN 的增大而减小

    • 实际网络的集聚系数往往币随机网络的大

小世界特性

  • Milgram 实验:信件传递

  • 《万物有别》——六度分离

  • 小世界特性的“小”:平均距离小、集聚系数大

    • 平均距离低于 ER 网络,集聚系数大于 ER 网络

WS 小世界模型

  • 小世界模型算法:首先给定一个含有 NN 个节点的环状最近邻连接网络,其中每一个阶都都与它左右相邻的各 mm 个节点相连。然后以概率 pp 随机重新连接网络中原有的每条边,得到 WS 小世界模型。

    1. 在环上按顺时针方向依次访问每个节点
    2. 假设节点 ii 为当前被访问的节点。顺时针选取与节点 ii 相连的 mm 条边中的每一条连边,边的一个端点仍然固定为 ii ,以概率 pp 随机的选取网络中的任一节点作为该点的另一端点,以概率 1p1-p 保持另一端点位置不变
    3. 在随机连边过程中,不允许出现重边和自环
  • NN 足够大时:平均距离的小世界特性展现出来

  • NN 固定是:p>12mNp>\frac{1}{2mN}

小世界网络中的导航

  • 引入问题:一个不知道全局网络结构的节点如何与网络中另一个节点通信

  • 网络的可导航性:一个网络的搜索事件复杂度随着网络的规模 NN 呈对数多项式增长,则称该网络可导航

  • Kleinberg 提出的分布式贪婪算法:只需要了解搜索目标的地理位置以及与当前信息传递者存在连边的所有节点的地理位置。整个搜索过程中,实验者都将信息传递给所有邻居节点中离搜索目标网络距离最近的节点。

    • 网络模型:一个添加了长程连边且规模为 nnn*n 的二维规则网络
    • 模型中每个节点都与它网格距离为 pp 的所有节点之间存在短程连边,同时该节点还有 qq 条长程连边
    • 节点u,v之间存在连边的概率与它们网络距离之间的幂函数成正比
    • 两个节点的距离是根据它们在网格上的坐标计算(坐标差之和)
  • 分布式贪婪算法步骤:

    1. 一个信息从 ss 发出,需要将信息传递给节点 TT

    2. ss 知道它自己在网格上的位置以及它的邻居的位置,也知道 TT 在网格上的位置

    3. 消息的持有者选择将其发送到离目标 TT 最近的邻居

      (这是一种分散式搜索,每一次传递都是发送给对于消息的持有者来说离目标最近的邻居,所以不一定会是最短路径)


无标度网络

幂律分布

  • 幂律分布:若一个随机变量 XX 服从幂律分布,则其概率密度函数位 f(x)=cxyf(x)=cx^{-y},其中 xx 为正的随机变量取值,c,yc,y 均为大于零的常数。

  • 幂律现象:80/20法则

  • 无标度:指一个概率分布函数 F(x)F(x) 对于任意给定常数 aa 存在常数 bb 使得 F(x)F(x)满足 F(ax)=bF(x)F(ax)=bF(x)幂律分布是为唯一满足无标度条件的概率分布函数。

  • 无标度网络:网络的度分布为幂律分布的网络

幂律分布的数据拟合

  • 最小二乘估计

    度分布:P(k)=CkγP(k)=Ck^{-\gamma}

    取对数:lnP(x)=lnCγlnklnP(x)=lnC-\gamma lnk

    寻找最优参数 γ\gamma 的估计值使得因变量的观察质与估计值之间的离差平方和达到最小

  • 极大似然估计:构似然函数

  • 累计度分布:可以减小数据波动

无标度网络的性质

  • 幂律分布的自相似结构

  • 幂律分布的弥散:m 阶矩

  • 无标度网络种的平均距离

    • const:γ=2const:\gamma=2
    • lnlnN:2<γ<3lnlnN: 2<\gamma<3
    • lnNlnlnN:γ=3\frac{lnN}{lnlnN}:\gamma=3
    • lnN:γ>3lnN:\gamma>3

BA无标度网络模型

  • 实际网络的两个重要特性

    • 节点网路的增长:实际网络在演化的过程中有新节点的加入,网络规模不断扩大。
    • 偏好连接:新节点更倾向于和连边多的节点进行连接
  • BA无标度网络模型的生成

    • 增长:在每个时间步,我们向网络中添加一个带有 m 条连边的新节点,这些边连接到网络中已存在的节点上。
    • 偏好连接:一个新节点与一个已存在节点相连的概率 Πi\Pi_i 与节点 ii 的度 kik_i 之间满足以下关系: Πi=kijkj\Pi_i=\frac{k_i}{\sum_jk_j}

    最终,BA模型生成了 γ=3\gamma=3 的无标度网络

  • 相关解释理论:平均场理论、速率方程

  • 增长和偏好连接缺一不可

满足给定度分布的网络生成模型

  • 配置模型

    • 基于给定度序列进行生成
    • 生成的网络可能有自环和重边
  • 隐藏参数模型

    • 每个节点被赋予一个隐藏参数,然后判断是否两点能够连边

社团结构

社团结构研究的意义

  • 社团结构是中观尺度网络性质的体现,对网络中社团结构的研究是了解这网络结构和功能的重要途经

社团结构的定义

  • 社团结构的类型

    • 一个节点仅属于某一个社团(非重叠社团)
    • 一个节点可能属于多个社团(重叠社团)
    • 仅给出某些节点的社团属性(非完全分类)
  • 社团结构的基本假设

    • 连通性
    • 局部相对稠密的连接密度
  • 社团结构(不重叠的社团)是对网络中节点的分组,组内连接相对紧密而组间连接相对稀疏

  • 派系:三个或三个以上的节点组成的全连通子图

  • k-core 子图:子图中的每个节点与子图内的其他节点至少有 k 条边相连

  • k-派系社团:网络中由所有彼此连通的 k-派系构成的集合

  • LS 集:一个 LS 集 是一个由节点构成的集合,它的任何真子集与该集合内部的连边都比该集合外部的连边多

  • 强社团:子图 V 中任何一个顶点与 V 内部顶点连接的度大于其与 V 外部顶点连接的度

  • 弱社团:子图 V 中所有顶点与 V 内部顶点的度之和大于 V 中所有顶点与 V 外部顶点连接的度之和

检验划分算法的网络及划分结果比较

  • GN 经典人造网:128个节点构成的网络,分成 4 组,构成 4 个社团,每个社团含有 32 个节点。每个节点度的期望为 16
  • GN benchmark:N 个节点,l 个社团,每个社团 g 节点;社团内的点连接社团内/外点的概率不同
  • LFR benchmark:节点度为幂律分布,社团规模(社团内节点数)也为幂律分布的网络
  • 划分结果比较:共同信息比较法
    • 互信息:信息论中一种有用的度量,它可以看成是一个随机变量中包含的关于另一个随机变量的信息量,可以衡量两个数据的吻合程度。
    • 度信息对于相似性的度量并不是理想方式。以为即使两种划分结果非常不同,但党划分的社团数比较多时,两种划分结果的互信息可能相同,为了更好的衡量划分结果的相似性,需要采用标准化互信息。

社团划分探测算法

  • 基于网路的拓扑结构
  • 基于网络上的动力学
  • Q 函数优化
  • 基于统计推断方法

基于节点相似性的社团划分法
  • 根据顶点距离或相似程度划分网络种的社团
  • 步骤:
  1. 定义相似性矩阵:相同社团的节点相似性会更高——拓扑重叠矩阵
  2. 计算社团间的相似性:基于节点的相似性矩阵,根据最短距离法、最长距离法、平均距离法来计算社团你的相似性
  3. 应用层次聚类
  4. 建立树状图
  • 结构等价定义顶点间的相似度

    • 结构等价:如果一个顶点与网络中其余顶点的来连接方式和另一顶点与网络中其余顶点的连接方式完全相同,则称这两个顶点结构等价
      • 欧式距离衡量
GN 算法
  • 根据社团的描述性定义:社团之间的联系性通道比较少,如果能够吧这些通道移除,那么网络自然而然地分成了各个社团

  • 用最短路径边介数标记每条百年对连通性的重要程度

    • 最短路径边介数:找出来每对顶点间的最短路径,计算每条边被多少条最短路径通过,这个之间就是这条边的最短路径边介数
  • 步骤:

  1. 计算网络中各条边的边介数
  2. 找出边介数最大的边并移除(如果不唯一,那么可以随机选一条断开,也可以都断开)
  3. 重新计算网络中剩余各边的边介数
  4. 重复上述步骤,直到所有的边都被移除

Q 函数及其优化算法

  • Q 函数:定量描述社团划分的模块化水平
    • 含义:网络中连接社团内部顶点间的边的比例与拥有相同社团结构但是顶点间随机连接的网络中连接社团内部顶点间的边的比例的期望值的差值
    • Q 函数值较大时,说明网络的这种社团划分是显著的

优化算法

  • 贪婪算法

    1. 初始时将网络中每个节点都视为一个社团,每个社团内只有一个顶点。即如果网络中有 n 个顶点,则有 n 个社团
    2. 两两合并社团,并计算社团合并所产生的 Q 值的变化量。选择使得 Q 值增加最大或者减小最小的方式进行合并
    3. 重复从上述操作,直至所有顶点被归于一个社团为止

    网络的最优划分为 Q 函数最大值所对应的划分方式

  • EO 算法:通过得到局部变量的极值,达到全局变量的极值

    1. 将网络中的点随机的分成等大的两部分,连通的部分构成社团
    2. 计算每个节点的适合度,将适合度最低的点从一部分移动到另一部分,计算全局 Q 值,并重新计算每点的适合度
    3. 重复上述过程,直至 Q 值最大。断开两部分之间所有的边
    4. 对每一子部分重复 1-3 过程,直至 Q 值不能进一步提高为止

重叠社团的划分算法

派系过滤算法
  • k-派系:k 个节点中任意两个节点都相连

  • k-派系相邻:两个k-派系含有 k-1 个公共节点

  • k-派系连通:一个k-派系可以通过若干干个相邻的k-派系达到另一个k-派系

  • k-派系社团:网络中所有彼此连通的k-派系构成的集合

步骤:

  1. 寻找网络中所有不同大小的派系
  2. 建立派系的重叠矩阵:该矩阵是一个对称方阵,每一行(列)对应一个派系,对角线元素表示相对应派系含有的节点数,非对角线元素表示两个派系之间的公共节点数
  3. 在派系的重叠矩阵中,将小于 k 的对角线元素以及小于 k-1 的非对角线元素替换为-,其它非零元素替换为 1,这样就就得到 k-派系社团的邻接矩阵,各个连通部分分别代表各个k-派系的社团
边聚类算法
  • 节点可能属于多个社团

  • 连边的含义比较明确,刻画了两个节点之间的关系,只能属于一个社团

    • 社团是一组紧密相连的连边的集合
    • 边聚类的思想就是将具有一定相似度的连边合并为一个社团
  • 步骤:

  1. 定义连边相似性
  2. 基于连边相似性的大小,使用层次聚类进行社团划分

加权网上的社团结构

聚类算法
  • WGN算法

  • WEO算法

共现矩阵
  • 极值优化算法的结果具有随机性,我们将一个具体的实际网络上运行 100 次,然后把这 100 次社团划分的结果在相应的共现矩阵上呈现
  • 共现矩阵能够定性衡量社团划分结果

网络的结构与功能

网络的鲁棒性和抗毁性

  • 鲁棒性:如果再移走少量节点后网络中的绝大部分节点仍然是连通的,那么就称该网络的连通性对节点故障具有鲁棒性。
    • 度分布相同网络的细致结构未必相同,对应的网络的鲁棒性和抗毁性也是不同的

网络上的动力学

网络上的疾病传播

SIS 模型
  • 易感人群 S,感染人群 I

  • 易感人群以一定概率 β\beta 成为感染个体,感染个体又以一定概率 γ\gamma 成为易感个体

  • 有效扩散速率 :βγ\frac{\beta}{\gamma}

SIR
  • 易感人群 S,感染人群 I,免疫人群 R

  • 个题处于免疫状态是指个体被治愈后获得了免疫能力或者死亡,该个体不能被感染疾病或是传播疾病

  • 易感人群以一定概率 β\beta 成为感染个体,感染个体又以一定概率 γ\gamma 成为免疫个体

  • 有效扩散速率 :βγ\frac{\beta}{\gamma}

网络上的疾病传播
  • 网络上的 SIS 模型

    • 小世界网络上的 SIS 模型

      假设一个易感节点被一个感染节点感染的概率为 β\beta ,而一个感染节点恢复为易感节点的概率为 γ\gamma,有效扩散速率 λ=βγ,γ=1\lambda=\frac{\beta}{\gamma},\gamma=1

      利用平均场理论计算被感染顶点密度随时间变化

    • BA 物标度网络上的 SIS 模型

      同样利用平均场理论计算被感染顶点密度随时间变化

    • 一般网络下的 SIS 模型

      得不出精确解

      可以利用平均场理论计算近似解

  • 网络上的 SIR 模型

    • 无标度网络:疾病传播——渗流
    • 一般网络:键逾渗模型
网络免疫技术
  • 熟识者免疫:从含有 N 个节点的网络中随机选择比例为 p 的节点,再从每一个被选出的节点中随机选择它的一个邻居节点进行免疫。这种免疫策略不需要网络的全局信息
  • 针对 SIS 模型的目标免疫:通过有选择地对少量关键节点进行免疫的一种策略
  • 针对 SIR 模型的免疫问题:等价为网络上的座-键混合逾渗问题(随机选择个体进行免疫)

网络上的随机游走

  • 随机游走:指以网络节点为载体,按照一定概率从网络上任一节点转移到与之连接的其他节点的状态转移过程

  • 转移概率矩阵:描述了一个随机游走者从一个节点转移到另外节点的概率,是一个非对称矩阵

    • 在无向无权网络中,随机游走者将以相等的概率从当前节点转移到它的任意一个邻居节点
      • 在无向无权网络中,随机游走的平稳分布依赖于节点的度值大小
  • 几个重要特征量

    • 平均首达时间
    • 平均通勤时间
    • 平均返回时间
    • 覆盖时间:一个游走着访问所有节点所需要的时间
  • 应用:网络中的搜索、节点中心性度量、节点的相似性度量、社团划分、网络分解

    • 节点的相似性度量:几种衡量方式
      • 平均通勤时间:两点的平均通勤时间越小,则两节点越接近
      • 基于随机游走的余弦相似性
      • 重启的随机游走
      • SimRank 指标:如果两节点所连接的节点相似,那么这两节点就相似
      • 局部随机游走指标
      • 叠加的局部随机游走指标
    • 社团划分
      • Walktrap 算法:把每个节点看成是一个社团,然后基于节点间的距离进行层次聚类,直到所有节点都归于一类,最终应用 Q 函数来判定最优的社团划分

网络上的同步

  • (精准)同步:两个或多个动力学系统,除了自身的演化外,其间还有相互作用(耦合),这种作用既可以是单向的,也可以是双向的。当满足一定条件时,在耦合的影响下,这些提供的状态输出就会逐渐趋同进而完全相等,称为(精确)同步

    • 广义的同步还包括相同步和频率同步等等
  • 一般连续时间耦合网络的完全同步问题

  • 小世界特性与网络同步能力的关系:网络特征根比率随着概率的增加而减小,说明小世界网络的同步化能力会随着“小世界”操作(概率 p 增加)而增强

  • 无标度特性与网络同步能力的关系:幂律指数越大,网路的同步化能力越强


网络节点重要性

网络节点重要性

经典指标

  • 度中心性:一个节点的邻居数目越多,影响力就越大
    • 这是网络刻画节点重要性最简单的指标
  • 介数中心性:网络中所有节点对的最短路径中,经过一个节点的最短路径数越多,这个节点就越重要
    • 这刻画了节点对网络中沿最短路径传输的网络流的控制力
  • 接近中心性:通过计算节点与网络中其他所有节点的距离的平均值来消除特殊值的干扰,即利用信息在网络中的平均传播时长来确定节点的重要性。
    • 一个节点与网络中其他节点的平均距离越小,该节点的接近中心性就越大
  • 特征向量中心性:一个节点的重要性既取决于其邻居节点是数量,也取决于每个邻居节点的重要性。
    • 从传播的角度看,特征向量中心性适用于描述节点的长期影响力
  • 利用动力学识别重要节点
    • 用网络的鲁棒性和脆弱性
      • 网络中最大连通集团的节点数量
      • 使用疾病传播模型:网络中被感染的节点数量

节点重要性判别方法

基于节点近邻的方法

  • 度中心性
  • 半局部中心性:节点两步可达的节点数量
  • K-壳分解:节点在网络中的位置也是至关重要的因素
  • H -index

基于路径的排序

  • 介数中心性
  • 离心中心性
  • 接近中心性
  • Katz 中心性:短路径比长路径更加重要
  • 流介数中心性:网络中所有不重复的路径汇总,经过一个节点的路径的比例越大,这个节点就越重要
  • 连通介数中心性

基于特征向量的排序

  • 特征向量中心性
  • PageRank 算法:Google 搜索引擎 的核心算法,迭代算法
    • 基于网页的链接结构给网页排序,它认为万维网中的一个页面的重要性取决于指向它的其他页面的数量和质量,如果它被很多高质量页面指向,则这个页面的质量也很高
  • LeaderRank 算法
    • 人们在内容丰富的热门网页(出度大的节点)上浏览的时候选择使用地址栏跳转页面的概率要远小于浏览信息量少的枯燥网页(出度小的节点)
    • 在有向网络的随机游走过程中,通过添加一个背景节点以及该节点与网络汇总所有节点的双向边来代替 PageRank 算法中的跳转概率,从而得到一个无参数且形式上更加简单优美的算法
  • Hits 算法:权威值+枢纽值
  • 基于节点移除和收缩的排序方法

二分网络

二分网络

  • 二分网络:由两类节点以及两类节点之间的连边组成,并且同类节点之间不存在连边。二分节点可以通过二分图 G=(,,E)G=(\bot,\top,E) 来描述,其中,\bot, \top 代表着两类节点, EE 为上述两类节点之间的连边。
    • eg:科学家——论文网络
  • 研究方法:二分网络的投影
    • 无权投影
    • 加权投影
其他网络类型的拓展
  • 超网(有点类似于 Venn 图)
  • 多层网

二分网络的基本性质

二模数据分析

  • 节点中心性
  • 集聚系数:根据四边形定义

二分网络的社团结构

  • 社团结构:二分网络根据连边的相对疏密程度来定义社团结构,社团你可以看作二分网络中的一组节点,是的社团内部异质节点之间的连边比较密集,二社团间的异质节点间的连边比较系数。

  • 社团结构的划分

    • Biclique 社团划分算法:

      Ka,bK_{a,b} 是由 a 个 top 类节点以及 b 个 bottom 类节点组成的全连接二分子图

      Ka,bK_{a,b}-团​ 是由若干个 Ka,bK_{a,b} 组成,它们两两之间至少共享 a-1 个top 类节点和 b-1 个 bottom 类节点

      • 步骤
        1. 给定参数 a、b,计算出网络中的全部 Ka,bK_{a,b}-团​,并建立两个团-团重叠矩阵
        2. 对以上两个矩阵作一些运算得到全图的重叠矩阵
        3. 基于该重叠矩阵计算出包含节点重叠的网络社团结构
    • 基于边集聚系数的聚类算法

      • 步骤
        1. 计算网络中所有边的集聚系数值,并计算网络模块化的值
        2. 找到并删除集聚系数最小的边,并计算删除边后网络模块化的值
        3. 重新计算剩余边的集聚系数值
        4. 重复所有步骤直到找到网络模块化的局部最大值为止
    • 衡量社团划分好坏:人造网络

  • 二分网络模块化函数现在还没有一个确切的定义


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!