精华内容
下载资源
问答
  • 复杂网络基本模型生成代码matlab

    热门讨论 2013-04-22 22:01:56
    复杂网络三大基本模型的matlab实现,可以生成三种具有基本模型特性网络。
  • 复杂网络的一些基本性质

    万次阅读 2017-03-11 19:53:35
    网络基本静态几何特征 度分布网络中所有节点viv_i的度kik_i的平均值称为网络的平均度,记为\,即 <k>=1N∑i=1Nki <k>=\frac{1}{N}\sum_{i=1}^{N}k_i 平均路径长度网络的平均路径长度L定义为任意两个节点之间的...

    一.网络的基本静态几何特征

    1. 度分布

      网络中所有节点vi的度ki的平均值称为网络的平均度,记为\,即

      <k>=1Ni=1Nki
    2. 平均路径长度

      网络的平均路径长度L定义为任意两个节点之间的距离的平均值,即:

      L=1C2N1i<jNdij
    3. 聚类系数

      节点viki个邻居节点之间实际存在的边数Ei和总的可能的边数C2ki之比就定义为节点vi的聚类系数Ci,即:

      Ci=EiCki2

    ​ 整个网络的聚类系数C就是所有节点vi的聚类系数Ci的平均值

    二.无向网络的静态特征

    无向图的静态特征量有:度及其分布特征,度的相关性,聚类系数及其分布特征,最短路径及其分布特征,介数及其分布特征,连通集团的规模分布等。

    1. 介数、核数和紧密度

      • 介数分为节点介数和边介数两种,它是一个全局特征变量,反映了节点或边在整个网络中的作用和影响力。定义:网络中不相邻的节点vjvl之间的最短路径会途径某些节点,如果某个节点vi被其他许多最短路径经过,则表示该节点在网络中很重要,其重要性或影响力可用节点的介数Bi来表示,定义为:

        Bi=1j<lN(jil)[njl(i)/njl]

      • 核数

      • 紧密度

    2. 中心性

      中心性反映了网络中各节点的相对重要性。在网络分析中,对图中某个节点的中心性的表征有多种方法,分别是度中心性、介数中心性、接近度中心性、特征向量中心性。

    三.赋权网络的静态特性

    • 点权、单位权和权重分布差异性

      • 点权(也叫点强度Vertex strength)

      与边权相互对照的一个概念是点权,它是无权网络中节点度的自然推广。

      定义:节点vi的点权Si定义为与它关联的边权之和,即:

      Si=jNiwij
      • 单位权

      单位权表示节点连接的平均权重,它定义为节点vi的点权Si与其节点度ki的比值,即:Ui=Si/ki

      • 权重分布的差异性

      定义:节点vi的权重分布差异性Yi表示与节点vi相连的边权分布的离散程度,定义为

      YI=jNi(wijSi)2
    展开全文
  • 02 复杂网络分析中的基本概念 2.1.复杂网络的表达方式 2.2.度、平均度、度分布 2.3.路径、距离与介数 2.4.集聚系数 2.5.网络稀疏性与联通性 2.6.度相关性 2.7.富人俱乐部 2.8.有向网络 2.9.加权网络 2.1复杂网络...

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

    • 2.1.复杂网络的表达方式
    • 2.2.度、平均度、度分布
    • 2.3.路径、距离与介数
    • 2.4.集聚系数
    • 2.5.网络稀疏性与联通性
    • 2.6.度相关性
    • 2.7.富人俱乐部
    • 2.8.有向网络
    • 2.9.加权网络

    2.1复杂网络的表达方式

    哥尼斯堡七桥问题
    1736年 欧拉定理

    如果图具有两个以上的奇数度的节点,则没有路径;如果图是连通的且没有奇数度节点,则它至少有一条路径。

    1. 网络的可视化表达 图表达
    1
    2
    3
    4
    5
    6
    组成部分 节点,顶点 N=6
    相互作用 连边,边 L=5
    系统 网络,图 (N,L)

    节点,顶点之间的相互作用,表达成连边或者是边,如此,网络变成了一个系统。该系统是由节点与节点之间相互作用抽象出来的连边所构成的
    2. 集合表达

    1
    2
    3
    4
    5
    6

    VV 点集 {\{1,2,3,4,5,61,2,3,4,5,6}\}
    EE 边集 {\{ee11,,ee22,ee33,,ee44,,ee55,}\}

    网络G=(V,E)G=(V,E),由点集V(G)V(G)和边集E(G)E(G)组成一个图,可分为无向、有向和加权网络
    eE(G)e∈E(G),每条边eeiiV(G)V(G)中的一对点(u,v)(u,v)与之对应;如果任意(u,v)(u,v)(v,u)(v,u)对应同一条边,则称无向网络,否则成为有向网络;如果任意e|eii|=1=1,则称无权网络,否则称为加权网络。
    3. 链接矩阵

    1
    2
    3
    4
    5
    6

    {001000001000110100001011000100000100}(A) \begin{Bmatrix} 0 & 0 & 1 & 0 & 0 &0 \\ 0 & 0 & 1 & 0 & 0 &0 \\ 1 & 1 & 0 & 1 & 0 &0 \\ 0 & 0 & 1 & 0 & 1 &1 \\ 0 & 0 & 0 & 1 & 0 &0 \\ 0 & 0 & 0 & 1 & 0 &0 \\ \end{Bmatrix} \tag{A}
    两个节点之间有边存在所对应的位置取值为1 无边则放0
    在链接矩阵基础上,构造Laplace矩阵L=KAL=K-A;AA为网络链接矩阵,KK为对角矩阵,对角线上的元素对应的网络中各个节点的度。
    链接矩阵及其对应的拉普拉斯矩阵的特征值和特征谱分析可以提供帮助。

    什么是网络拓扑

    网络是一个由多个节点组成的集合,节点之间有一定的连接。
    拓扑指的是节点之间相互联系的模式

    实例 节点 连接
    国际互联网 路由器 光纤
    科学引用网 文章 文章引用
    社会网络 个体人 人际关系

    2.2度、平均度、度分布

    • 节点的度:与节点直接相连的连边数
    1
    2
    3
    4
    k1=1 k2=3 k3=2 k4=2 *2节点的度最高*
    • 通常,节点的度值是一个离散型随机变量,在计算中主要涉及以下统计量
      • 均值
      • 方差
      • 标准差
      • n阶矩
      • x的分布
    1. 平均度
    1
    2
    3
    4
    • k=1Ni=0Nkik=\frac 1N\sum_{i=0}^Nk_i

    • k=2LNk=\frac {2L}N

      • NN:图中节点数
      • LL:图中连边数
    1. 度分布
    • 将网络中节点的度值从小到大排列,统计值为k的节点,占整个网络节点数的比例P(k)P(k),即P(k)Nk/NP(k)-N_k/N
      • NkN_k 度为k的节点数目
      • NN 网络中的节点总数
    • 连续性变量表述:节点的度的概率密度函数
    • 归一化条件
      0\sum_0^\infinpk=1p_k=1
      m\int_m^\infinp(k)dk=1p(k)dk=1
      • mm是网络所有节点的度值中的最小值,一般从1开始取。
    1. 正则网络的度分布
    • 全连接网络:n-1Δ\Delta
    • 最近邻居连接网络:Δ\Delta
    • 星型网络:中心点(特殊点):n-1;其他点(边缘点):1

    2.3路径、距离与介数

    1. 路径
    • 一条路径是指一个节点序列,其中每一对相邻的节点之间都有一条连边。
    • 一条从节点i0i_0ini_n的长度为n的路径P经过n+1个节点和n条连边。
    • 最短路径
      • 两个节点之间的最短路径是指连接这两个节点的变数最少的路径。
      • 两个节点之间的最短路径上的边数目,即两个节点之间的最短距离。
    • 两点之间路径的条数
      NNijij两点间路径的条数。
      • 如果节点iijj之间存在一条连边,则AAijij=1=1,反之,AAijij=0=0
      • 如果节点iijj之间存在一条长度为2的连边,则AAikikAAkjkj=1=1,反之,AAikikAAkjkj=0=0
      • ……
      • 长度为n,如果节点iijj间存在一条长度为n的路径,则AAikikA…Aljlj=1=1,否则,AAikikA…Aljlj=0=0
      • 在节点ij之间长度为n的路径数量:
        NNijij(n)(n)=[An][A^n]ijij
    1. 网络直径与平均距离
    • 直径ddmaxmax:网络中任意两点间的最短距离的最大值。
    • 平均路径长度(平均最短距离)d\langle d \rangle
      • 连通图 d\langle d \rangle12Li,j+1≡\frac1{2L}\sum_{i,j+1}ddijij
      • 无向图 d\langle d \rangle1Li,j+1≡\frac1L\sum_{i,j+1}ddijij
        将网络中任意一堆节点之间的最短距离求出来后进行求和,然后再除以这个网络当中节点对的数目。
    1
    2
    3
    4
    5
    6

    直径 3;平均距离9/5

    • 实例
      • 全连接网络:平均距离为1
      • 最近邻居网络:平均距离为N/8
      • 星型网络:平均距离为22-2(N1)N(N1)\frac{2(N-1)}{N(N-1)}
    1. 介数
    • 任意一堆节点间的最短路径所经过的次数
      • 点介数
      • 边介数
    • 介数反映了响应的节点或边在整个网络中的作用和影响力,是一个全局几何量。

    2.4集聚系数

    • 节点集聚系数的定义1
      • 节点iikik_i个邻居节点之间实际存在的变数EiE_i和总的可能边数之比。
        Ci=C_i=2eiki(ki1)\frac{2e_i}{k_i(k_i-1)}
        eie_i指i点邻居之间存在连边的个数;
        kik_i指i点的度值;
      • Ci=C_i=ii\frac{包含节点i的三角形数目}{以节点i为中心的连通三元组数目}
    • 网络集聚系数定义
      网络中所有节点的集聚系数的平均值
      • C\langle C \rangle=1Ni=1N=\frac1N\sum_{i=1}^NCiC_i
        网络的传递性
      • T=/3T=\frac{网络中三角形数目}{网络中连通三元组的数目/3}
        T[0,1]T∈[0,1]
        如果T=1,则任意两个节点有连接。
        如果T=0,则无三角形连接。

    2.5网络稀疏性与连通性

    • 完全连接网络
      定义:如果一个网络中任意两个节点之间都有连边存在,则称之为完全连接网络,平均度为N-1
      可能拥有的最大连边数:
      LLmaxmax=CN2C_N^2ma

    • 网络稀疏性
      定义:网络稀疏程度定义为网络中实际存在的边数与最大可能的边数之比。
      LL/LmaxLmax
      L:网络中实际存在的边数
      利用比值衡量稀疏程度,很多网络是稀疏网络

    • 无向网络的联通

      • 联通(无向)图:网络中任意两个节点之间都至少存在一条路径
      • 最大连通集团:含有节点数最多的连通子图
      • 对于不连通网络的邻接矩阵,所有的非零元素都存在于沿着矩阵对角线排列的一些方块中,其余部分元素均为零。
        +(一般会选择最大连通集团进行性质分析

    2.6度相关性

    • 众多的社会关系网络,呈现出正向匹配特性;信息网络和神经网络则呈现出负向匹配特性;而常用的ER模型和BA模型则没有任何倾向性。2
    • 网络中两个节点度值之间的关系
      • 同配:度大节点 倾向于连接 度大节点(对角线)
      • 异配:度大节点 倾向于连接 度小节点(两轴)
      • 中性:节点间的连接与它们自身的度值无关
    • 衡量网络的度度相关性
      • 可视化描述3
        • eejkjk:网络中随机选取的一条边的两个端点的度分别为jjkk的概率
        • qkq_k:网络中随机选取的一条边的断电的度为k的概率。
        • 如果网络不具有度相关性:eejkjk=qj=q_jqkq_k
        • 计算eejkjk,并对其进行可视化,观察分布,判断网络度度相关性。
      • 度相关函数4
        • 平均邻居度kknnnn(k)(k):度为k的节点的邻居节点的平均度。
          kknnnn(k)=akμ(k)=ak^\mu
        • μ>0\mu>0:同配
        • μ=0\mu=0:中性
        • μ<0\mu<0:异配
      • 相关系数
        如果网络是度相关的,eejkjk!=qjqk!=q_jq_k,可以考虑-的差值大小来刻画网络同配或异配的程度。
        正值,同配;0,中性;负值,异配。
        • 为了比较不同规模网络的同配或异配程度,通过归一化处理得到归一化的相关系数。
      • 皮尔逊相关系数
        取出网络中所有连边,计算每条连边两端节点的度值,并将其按从小到大排序,得到度小序列和度大序列,最后计算它们的皮尔逊相关系数。

    2.7富人俱乐部

    研究Internet的AS拓扑过程中发现,虽然AS拓扑具有异配特性,但高度节点之间仍然具有很高的连接概率,这个现象成为富人俱乐部现象。引入夫人俱乐部系数来对富人俱乐部现象进行量化描述。5

    • 富人俱乐部系数:$\phi(k)=22E<sub><sub>>k</sub></sub>/N<sub>N<sub>>k</sub>(N<sub></sub>(N<sub>>k</sub></sub>-1)$
      • EE>k>k:网络中度值大于k的节点之间的连边数。
      • NN>k>k:网络中度值大于k的节点数。
    • 标准化后的富人俱乐部系数6

    2.8有向网络

    • 有向网络:在网络的连边上面存在方向。方向体现在链接矩阵中为非对称性;对角线为0
      • AAijijA≠Ajiji
      • AAiiii=0=0
    • 度的进一步划分
      • 节点ii的出度 从节点i指向其他节点的边数目
      • 节点ii的入度 从其他节点指向节点i的边数目
      • 节点的度(总度) 节点的入度和出度的加和
      • 源 一个节点的入度kkinin=0=0
      • 汇 一个节点的出度kkoutout=0=0
    • 平均度
      • 平均入度
      • 平均出度
      • 总平均度
        总平均入度=总平均出度
    • 路径、最短距离
      在有向网络中,路径只能沿着箭头的方向。因此,在有向网络中,从A到B的最短距离可能不等于从B到A的最短距离。
    • 有向网络的集聚系数7
    • 有向网络的连通
      将有向网络中的所有有向边替换为无向边,替换后的无向网络是一个连通图,则称该有向网络是一个弱连通图。
      强定义:有向网络中必须任何两个节点之间都存在路径,强连通图。
    • 度相关8
      实例食物网:一条有向边由节点A指向节点B,表示物种B以物种A为食物。四种模式下的度度相关性。
      • (out,in)
      • (in,out)
      • (out,out)
      • (in,in)
    • 有向网络的模体9
      有向网络和随机网络模体,随机网络的生成方式10,随机交叉换边,并且保证每个节点的入度和出度不变。
      可以利用有向网络对实体系统进行抽象,再通过与随机化有向网络进行对比可以挑选出系统当中所存在的个数居多的模体模式。而模体模式可以揭示系统所具有的一些特征

    2.9加权网络

    1. 多条边网络
      节点之间对应的多条连边=>链接矩阵所对应位置上元素的数值表达。依旧可以利用无权网络的公式计算边数、平均度,链接矩阵也同时保持着对称的特征。
    2. 权重
      • 权重(点、边)
      • 加权网络中加权的赋予
        加权方式:
        a)利用网络中已有的物理量进行权重的抽象:因特网——带宽;电路网——电阻
        b)相互作用的抽象:科学家合作网——合著文章数;演员合作网——合作次数;中药网;菜肴网
    3. 双顶点网络的抽象
      顶点——事件 构成双顶点网
      广义合作网投影到单顶点网
    4. 关于权重的定义11
      • 相似权(Similarity Weight):概念与距离相反,边权越大,顶点之间越亲近(0为无连接)如合作次数
      • 相异权(Dissimilarity Weight):概念与距离相同,边权越大,顶点间距离越远(∞为无连接)如里程数
    5. 节点距离计算
      • 相异权 dd1313=w=w1212+w+w2323
      • 相似权 dd1313=1/w==1/w=1/w1/w1212+1/w+1/w2323
    w12
    w23
    1
    2
    3
    1. 加权网络集聚系数
      加权网集聚系数的定义满足以下4个条件12:
      • 在[0,1]之间
      • 权重为0则无边连接
      • 权重为1时回归无权网定义
      • 与三角形每条边上的权重相关
        文献给出了加权网络集聚系数的公式

    参考文献


    1. Watts, D.J. and Strogatz, S.H. (1998) Collective dynamics of “small world” networks. Nature, 393, 440-442. ↩︎

    2. Newman, M. E J . Assortative Mixing in Networks[J]. Physical Review Letters, 2002, 89(20):208701. ↩︎

    3. Maslov, S. Specificity and Stability in Topology of Protein Networks[J]. Science, 2002, 296(5569):910-913. ↩︎

    4. Pastor-Satorras, Romualdo, Vázquez, Alexei, Vespignani, Alessandro. Dynamical and Correlation Properties of the Internet[J]. Physical Review Letters, 87(25):258701. ↩︎

    5. Zhou S, Mondragon RJ. The rich-club phenomenon in the Internet topology. IEEE Communications Letters, 2004.8(3):180- 182. ↩︎

    6. Colizza, V.,Flammini, A.,Serrano, M. A., & Vespignani, A. . (2006). Detecting rich-club
      ordering in complex networks. Nature Physics, 2(3), 110-115. ↩︎

    7. Fagiolo, Giorgio. Clustering in Complex Directed Networks[J]. Phys Rev E Stat Nonlin Soft Matter Phys, 2006, 76(2):026107. ↩︎

    8. Jacob G. Foster, David V. Foster, Peter Grassberger,等. Edge direction and the structure of networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2010. ↩︎

    9. Milo R , Shen-Orr S , Itzkovitz S , et al. Network Motifs: Simple Building Blocks of Complex Networks[J]. Science, 298. ↩︎

    10. Maslov, S. Specificity and Stability in Topology of Protein Networks. Science, 2002, 296(5569):910-913. ↩︎

    11. FAN, YING, LI, MENGHUI, CHEN, JIAWEI,等. NETWORK OF ECONOPHYSICISTS: A WEIGHTED NETWORK TO INVESTIGATE THE DEVELOPMENT OF ECONOPHYSICS[J]. International Journal of Modern Physics B, 18(17n19):2505-2511. ↩︎

    12. Petter Holme, Sung Min Park, Beom Jun Kim,等. Korean university life in a network perspective: Dynamics of a large affiliation network[J]. Physica A Statistical Mechanics & Its Applications, 373(none):821-830. ↩︎

    展开全文
  • 复杂网络

    千次阅读 2018-10-28 16:31:28
    文章目录复杂网络复杂网络基本概念平均路径长度聚类系数度与度分布网络拓扑基本模型及其性质规则网络全局耦合网络最近邻耦合网络星型耦合网络随机图(ER随机图)小世界网络模型WS小世界模型NW小世界模型小世界网络的...

    复杂网络

    复杂网络基本概念

    平均路径长度

    两个点iijj之间的距离dijd_{ij}定义为连接这两个节点的最短路径上的边数。

    网络的平均路径长度LL定义为任意两个节点之间的距离的平均值,即:
    L=112N(N+1)ijdij L=\frac{1}{\frac{1}{2}N(N+1)}\sum_{i\ge j}{d_{ij}}
    其中,NN为网络节点数。

    一个含有NN个节点和MM条边的网络的平均路径长度可以用时间量级为O(MN)O(MN)的广度优先搜索算法来确定。

    网络的平均路径长度也称为网络的特征路径长度。

    聚类系数

    在你的朋友关系网络中,你的两个朋友很可能彼此也是朋友,这种属性称之为网络的聚类特性

    在网络中的节点iikik_{i}条边和其他节点连接,即有kik_{i}个邻居节点。在这kik_{i}个邻居节点之间最多可能有 ki(ki1)/2k_{i}(k_{i}-1)/2条边,而这kik_{i}个节点之间实际存在的边数EiE_{i}和总的可能的边数 ki(ki1)/2k_{i}(k_{i}-1)/2之比就定义为节点ii的聚类系数CiC_{i},即:
    Ci=2Eiki(ki1) C_{i}=\frac{2E_{i}}{k_{i}(k_{i}-1)}
    简单描述即是:
    Ci=ii C_{i}=\frac{与点i相连的三角形的数量}{与点i相连的三元组的数量}
    三元组包含三角形,三元组两种形式为:

    在这里插入图片描述

    整个网络的聚类系数CC就是所有结点i的聚类系数CiC_{i}的平均值。

    度与度分布

    度是单独节点的属性中简单而又重要的概念,分为出度和入度。直观上,一个节点的度越大,那么这个节点在某种意义下越重要。网络中的所有节点ii的度kik_{i}的平均值成为网络的(节点)平均度,记为k\langle k \rangle,网络中节点的度的分布情况用分布函数P(k)P(k)来描述。P(k)P(k)表示一个随机选定的节点的度是kk的概率。

    • 规则图为Delta分布
    • 随机网络和小世界网络为近似Poisson分布
    • 指数分布(暂未知是哪种网络!)
    • 无标度分布,即幂律分布

    无标度分布即是分布函数f(x)f(x)满足无标度条件
    f(ax)=bf(x) f(ax)=bf(x)
    当满足这个条件是必定有:(这里假设 f(1)f(1)0f(1)f&#x27;(1)\neq 0 )
    f(x)=f(1)xr,r=f(1)f(1) f(x) = f(1)x^{-r}, r = -\frac{f(1)}{f&#x27;(1)}
    证明见《复杂网络理论及其应用》中P12。

    幂指数一般为2r32\le r\le 3,绝大多数节点的度相对很低,只有少量节点的度相对很高,因此这类网络为非均匀网络,那些度相对很高的节点成为网络的集线器(hubs)

    网络拓扑基本模型及其性质

    规则网络

    全局耦合网络

    构成:任意两个点之间都直接相连接,如下图a所示

    平均路径长度:1

    最大聚类系数:1

    最近邻耦合网络

    构成:每个节点只和它周围的邻居节点相连,一般具有周期边界条件的最近邻耦合网络包含N个围成一个环的点,如下图b所示,每个节点与它最近的4个节点相连

    K:最近邻的个数,图b中为4

    N:节点的数目

    聚类系数为:
    Cnc=3(K2)4(K1)34 C_{nc}=\frac{3(K-2)}{4(K-1)}\approx \frac{3}{4}
    平均路径长度为:
    LncN2KN L_{nc} \approx \frac{N}{2K} \rightarrow \infty \quad \quad (N \rightarrow \infty )

    星型耦合网络

    构成:一个点为中心点,其他点与这个中心点直接连接,如下图c所示

    聚类系数为:
    Cstar=N1N1N C_{star}=\frac{N-1}{N} \rightarrow 1 \quad \quad (N \rightarrow \infty )
    平均路径长度为:
    Lstar=22(N1)N(N1)2N L_{star}=2- \frac{2(N-1)}{N(N-1)} \rightarrow 2 \quad \quad (N \rightarrow \infty )
    在这里插入图片描述

    总体而言,这三种规则网络在很理想的情况下进行建模,很大程度上无法反映真实网络世界情况,是复杂网络研究中最基本的模型,不过有必要对他们的三要素进行理解与学习。

    在人工构建的网络中,P2P为完全耦合网络,C/S为星型网络模型,路网在一定程度上可以认为是最近邻耦合模型(这个是自己想的)。

    随机图(ER随机图)

    构成:假设有大量的纽扣(N1N \gg 1)散落在地上,并以相同的概率pp给每对纽扣系上一根线,这样便可以得到一个有NN个点,约pN(N1)/2pN(N-1)/2条边的ER随机图实例。

    性质存在的定义:如果当NN \rightarrow \infty时产生了一个具有性质Q的ER随机图的概率为1,那么就称几乎每一个ER随即图都具有性质Q。

    ER随即图的许多性质都是突然涌现的。比如当概率pp大于某个临界值pc(lnN)/Np_{c} \propto (lnN)/N,那么几乎每一个图都是连通的。

    平均度:k=p(N1)pN\langle k \rangle=p(N-1) \approx pN

    平均路径长度:LERlnN/lnkL_{ER} \propto lnN/ln\langle k \rangle。在ER图中随机选择一个点,网络中大概有kLER\langle k \rangle^{L_{ER}}个其他的点与该点之间的距离等于或者非常接近于LERL_{ER},因此NkLERN\propto \langle k \rangle^{L_{ER}},变换一下形式即得原式。这种平均路径长度为网络规模的对数增长函数的特性就是典型的小世界特征

    聚类系数:C=p=k/N1C=p=\langle k \rangle/N\ll1,这意味着大规模的稀疏ER随机图没有聚类特征。

    ER图又称为“Poission随机图”,固定ER随机图的平均度k\langle k \rangle不变,则对于充分大的N,由于每条边的出现与否都是独立的,ER随机图的度分布可以用Poission分布来表示,即:
    P(k)=CNkpk(1p)Nkkkekk! P(k)=C_{N}^{k}p^{k}(1-p)^{N-k} \approx \frac {{\lang k \rang}^k e^{- \lang k \rang}}{k!}

    小世界网络模型

    考虑到规则的最近邻耦合网络具有高聚类特性,但是平均路径很大,不是小世界网络,而ER随机图有较小的平均路径长度,但是不具备高聚类特性。将这两者的性质结合,即可得小世界网络模型。

    WS小世界模型

    构造算法:从最近邻耦合网络这个规则网络开始,将它的边以概率pp进行随机化重连,一个节点固定,另一个节点随机选择。并保证任意两个不同节点之间至多一条边,节点不能有边与自身相连。p=0p=0p=1p=1的过程即是从完全规则网络到完全随机网络的过程。

    聚类系数
    C(p)=3(K2)4(K1)(1p)3 C(p)=\frac{3(K-2)}{4(K-1)}(1-p)^3
    平均路径长度(目前暂无精确解析表达式,利用重正化群方法可以得到如下公式):
    L(p)=2NKf(NKp/2) L(p)=\frac{2N}{K}f(NKp/2)
    其中f(u)f(u)为一普适标度函数,满足:
    f(u)={constantu1(lnu)/uu1 f(u)= \left \{ \begin{aligned} constant,u \ll 1 \\ (lnu)/u,u \gg 1 \end{aligned} \right.
    后来,基于均场方法有如下表达式:
    f(x)12x2+2xarctanhxx+2 f(x) \approx \frac{1}{2\sqrt{x^2+2x}}arctanh\sqrt{\frac{x}{x+2}}
    度分布:由于每个节点有KK个邻居节点,在随机化重连的过程中,对于每个节点而言,有K/2K/2条边是不会离开该节点的,因此,当k&lt;K/2k&lt;K/2时,P(k)=0P(k)=0,当kK/2k\geq K/2时,分布如下:
    KaTeX parse error: No such environment: equation* at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ P(k)= \sum_{n=…
    WS小世界模型构造方式中的随机化过程可能破坏网络的连通性,于是:

    NW小世界模型

    构造算法:从最近邻耦合网络这个规则网络开始,将它的边以概率pp进行随机化加边。并保证任意两个不同节点之间至多一条边,节点不能有边与自身相连。p=0p=0对应原始最近邻耦合网络,而p=1p=1对应全局耦合网络。

    聚类系数:
    C(p)=3(K2)4(K1)+4Kp(p+2) C(p)=\frac{3(K-2)}{4(K-1)+4Kp(p+2)}
    平均路径长度(同WS小世界模型):
    L(p)=2NKf(NKp/2) L(p)=\frac{2N}{K}f(NKp/2)
    其中f(u)f(u)为一普适标度函数,满足:
    f(u)={constantu1(lnu)/uu1 f(u)= \left \{ \begin{aligned} constant,u \ll 1 \\ (lnu)/u,u \gg 1 \end{aligned} \right.
    后来,基于均场方法有如下表达式:
    f(x)12x2+2xarctanhxx+2 f(x) \approx \frac{1}{2\sqrt{x^2+2x}}arctanh\sqrt{\frac{x}{x+2}}
    度分布:由于每个节点至少有KK个邻居节点,因此,当k&lt;Kk&lt;K时,P(k)=0P(k)=0,当kKk\geq K时,分布如下:
    KaTeX parse error: No such environment: equation* at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲*̲}̲ P(k)= C_{N}^{k…
    pp足够小且NN足够大时,NW小世界网络本质上等同于WS小世界网络。

    小世界网络的小波分析

    见《复杂网络理论及其应用》中P23。

    大概就是利用小波变化,在一个粗化的状态下,观察网络的统计特性,进而研究在粗化状态下,LL1LL_{1}低频区间所展现出来的网络特性,即网络的平均路径长度以及聚类系数。

    无标度网络模型(重点)

    基本性质

    ER随机图和WS小世界模型的一个共同特征是度分布近似为Poisson分布,这样度基本上存在于平均度k\langle k \rangle峰值附近,当kkk\gg\langle k \rangle时,度为kk的节点几乎不存在。而许多现实生活中的网络,如Internet、WWW、新陈代谢网络等的连接度分布函数具有幂律形式,由于这类网络的节点的连接度没有明显的特征长度(比如平均度k\langle k \rangle),因此,称之为无标度网络

    最初是的无标度网络模型:BA无标度网络,通过考虑现实情况下,网络的增长特性(每天都有新的节点和边加入)和优先连接特性(新的节点更加倾向于与那些高度节点相连接,“富者更富”“马太效应”)。该部分为我目前的研究重点。

    **BA无标度网络构造算法:**从一个具有m0m_{0}个节点的网络开始,每次加入一个节点并连接到mm个已存在的节点上,当然,必须满足mm0m \leq m_{0}。在连接时,一个新的节点与一个已经存在的节点ii之间的连接概率Πi\Pi_{i}与节点ii的度kik_{i}和所有其他节点的度关系如下:
    Πi=kijkj \Pi_{i}=\frac{k_{i}}{\sum\limits_{j}{k_{j}}}
    平均路径长度:
    LlogNloglogN L \propto \frac{logN}{loglogN}
    LLlogNlogN一个量级,表明该网络具有小世界特性

    聚类系数:
    C=m2(m+1)24(m1)[lnm+1m1m+1][ln(t)]2t C=\frac{m^2(m+1)^2}{4(m-1)}\big[ln\frac{m+1}{m}-\frac{1}{m+1}\big]\frac{[ln(t)]^2}{t}
    mm:每次一个新的节点与mm个已经存在的节点连接

    tt:经过tt步,即总共加入tt个节点,最后共有N=t+m0N=t+m_{0}个节点,大概mtmt条边

    与ER随即图类似,当网络规模充分大时,BA无标度网络不具有明显的聚类特征

    度分布:

    对于无标度网络的度分布研究主要有三种方法:连续场理论,主方程法,速率方程法。

    主方程法的结果:

    定义p(k,ti,t)p(k,t_{i},t)为在tit_{i}时刻记录的节点iitt时刻的度恰好是kk的概率。在BA模型中,当一个新节点加入到系统中来时,节点ii的度增加11的概率为mΠi=k2tm\Pi_{i}=\frac{k}{2t} (根据前文,可以推导出来),否则该节点的度保持不变。那么有:
    &lt;Empty Math Block&gt; &lt;Empty \space Math \space Block&gt;

    p(k,ti,t+1)=k12tp(k1,ti,t)+(1k2t)p(k,ti,t) p(k,t_{i},t+1)=\frac{k-1}{2t}p(k-1,t_{i},t)+(1-\frac{k}{2t})p(k,t_{i},t)

    网络的度分布为:
    P(k)=limt+(1ttip(k,ti,t)) P(k)=\lim_{t\to +\infty}\big(\frac{1}{t}\sum\limits_{t_{i}}p(k,t_{i},t)\big)
    它满足如下递推方程式:
    P(k)={k1k+2P(k1)km+12m+2k=m P(k)= \left \{ \begin{aligned} \frac{k-1}{k+2}P(k-1),k \geq m+1 \\ \frac{2}{m+2} \quad \quad ,k =m \qquad \end{aligned} \right.
    从而可得BA网络的度分布函数为:
    P(k)=2m(m+1)k(k+1)(k+2)2m2k3 P(k)=\frac{2m(m+1)}{k(k+1)(k+2)} \propto 2m^2k^{-3}
    mm:每次一个新的节点与mm个已经存在的节点连接

    kk:随机取一个节点,度为kk的概率P(k)P(k)

    表明:BA无标度网络的度分布函数可以由幂指数为3的幂律函数近似描述

    缺陷:BA无标度网络的幂指数固定为3

    鲁棒性与脆弱性

    见《复杂网络理论及其应用》中P29。

    无标度网络对随机故障策略,即随机移除一些点,有很高的鲁棒性;对蓄意攻击策略,即移除网络中部分度最高的节点,表现得非常脆弱。其中表现情况以整个图的连通性为标准。

    鲁棒但又脆弱是复杂系统的最重要和最基本的特征之一。

    Broder等人研究了更大规模WWW子网络的鲁棒性。他们发现只有删除所有度大于5的节点才能完全破坏WWW的连通性。这其实是因为WWW具有高度倾斜的度分布,度数大于5的节点在整个网络中所占的比例还是很小的。(这个发现以及相关的具体数值的研究,可能对我的研究有帮助

    适应度模型

    BA模型只能生成度分布的幂律指数固定为3的无标度网络,而各种实际复杂网络的幂律指数则不甚相同,且大多属于2到3的范围内。

    实际网络常常还具有一些非幂律特征,如指数截断,小变量饱和等。

    在BA无标度网络的增长过程中,节点的度也在发生变化并且满足如下幂律关系(流式处理中,应该很有用):
    ki(t)=(tti)12 k_{i}(t)=\big(\frac{t}{t_{i}}\big)^{\frac{1}{2}}
    ki(t)k_{i}(t):为第ii个节点在时刻tt的度

    tit_{i}:为第ii个节点加入到网络中的时刻

    则可以有一个很直观的认识:就是越老的节点具有越高的度,在完全随机的情况下,这一点基本成立。

    适应度模型构造算法:在原有的BA模型上,为每个节点增加了一个适应度权值

    从一个具有m0m_{0}个节点的网络开始,每次加入一个节点并连接到mm个已存在的节点上,当然,必须满足mm0m \leq m_{0},每一个节点的适应度按照概率分布$ \rho ( \eta )选取。在连接时,一个新的节点与一个已经存在的节点i之间的连接概率\Pi_{i}与节点i的度k_{i}以及适应度\eta_{i}$和所有其他节点的度关系如下:
    Πi=ηikijηjkj \Pi_{i}=\frac{\eta_{i}k_{i}}{\sum\limits_{j}{\eta_{j}k_{j}}}

    展开全文
  • 实验结果表明汉语依存句法网络具有复杂网络的两个基本性质:小世界效应和无标度特性,并在其他方面也体现了复杂网络的重要性质。汉语的这些句法上的统计特性,与捷克语、德语和罗马尼亚语等极为相似,说明虽然不同语言...
  • 复杂网络模型及其应用》清华大学出版社 包括第一章引论 第二章网络拓扑基本模型及其性质 第三章inter拓扑特性及建模 第四章复杂网络上的传播机理与动力学分析 第五章复杂网络上的相继故障
  • 1.1 复杂网络基本参数及其含义 复杂网络研究的一个重要方面就是刻画真实系统的网络模型,通过创建网络模型来帮助我们理解网络的这些特性是如何产生和出现的。研究者在很多不同领域的系统都发现了“小世界”(网络...

    1.1 复杂网络的基本参数及其含义

    复杂网络研究的一个重要方面就是刻画真实系统的网络模型,通过创建网络模型来帮助我们理解网络的这些特性是如何产生和出现的。研究者在很多不同领域的系统都发现了“小世界”(网络拥有较小的平均最短路径长度和较大的平均聚集系数)和“无尺度”(节点的度分布遵循幂律分布)的复杂网络特性。这些复杂网络研究的共同特点就是在网络形成的过程中,并没有强调任何全局规则的作用,而网络的整体行为特性的涌现往往是在一个局部规则作用线产生的结果。

    与传统图论研究的不同之处在于:复杂网络从统计角度考察网络中节点的分布及节点间连接的 性质,根据不同的网络组织结构来研究系统功能差异,为系统(结构。性能等)的优化提供理论基础。下面简单介绍下主要参数的基本概念、计算方法以及在软件工程学中的含义(implications for software engineering).

    1.平均最短路径长度(average shortest path length)
    网络的平均最短路径长度d是所有节点对之间距离的平均值,复杂网络研究一个重要的发现是绝大多数大规模真实网络的平均最短路径长度比想象的要小得多,称之为“小世界”效应。对面向对象软件系统来说,该参数对系统消息传递的设计与优化对象间通信代价的评估与控制系统响应能力的改进有着重要意义
    2. 聚集系数(clustering coefficient)
    聚集系数也称簇系数,描述网络中节点的聚集情况,即网络有多“紧密”。在社会网络中描述你朋友的朋友可能是你的朋友,假设节点v通过k条边与其他k个节点相连接,E为这k个节点间实际存在的边的数目。那么它与k(k-1)/2之比就是节点v的聚集系数C.在软件系统中,聚集系数反映了不同粒度的软件实体中组成元素的内聚程度以及系统组织分层(层次化)的趋势
    3.度分布(degree distribution)
    网络中节点的度分布用分布函数P(k)来表示,其含义是一个任意选择的节点恰好有k条边的概率,也等于网络中度为k的节点的个数占网络节点总数的比值。复杂网络的另一个重大发现是绝大多数大规模真实网络的度分布都服从幂律分布(“无尺度”现象),即P(k)-k-r(2<r<3),而不是泊松分布或正态分布。对于面向对象软件系统,度分布刻画了网络中每个节点的连通性**(connectivity),并从系统角度反映了节点的重用度和复杂度** 。
    这样看来,度分布可以用来表征系统结构的不均匀性,定性分析结构信息的不确定性,从而,从而估测其复杂性;还可以用来 以及MOOD度量方法中的CF指标
    4.介数(betweenness centrality)
    介数分为边介数和节点介数两种,节点介数指的网络中所有最短路径中经过该节点的路径数目占最短路径总数的比例;根据节点和边的介数,能够分析软件系统中任意一个类和类之间的某种关联被删除或失效时对整个系统的影响,为系统的重构和优化提供指导,而这正是传统软件度量方法所无法实现的。另一方面,根据社区中元素的聚集系数和社区间边的介数在较高层次分析软件设计的质量或复杂度(依据“高内聚,低耦合”原则),这里社区是指的粒度较大的软件实体,如软构件。包(package)等。
    5.度和聚集系数之间的相关性(correlation)
    网络中度和聚集系数之间的相关性被用来描述不同网络结构之间的差异,它包含两个方面的内容:连接度不同的节点之间的相关性节点的度与其聚集系数之间的相关性。前者指的是网络中与连接度高的节点相连接的节点的度偏向于高还是低;后者指的是连接度高的节点的聚集系数偏向于高还是低
    在软件系统中,度-度的相关性有助于分析不同类型的软件实体间的协作关系(由于功能的层次性,复杂的类或模块都倾向于由相对简单的类或模块组成,而不是直接调用其他复杂的类或模块,这体现了软件的构造性原则,也是软件中度-度负相关的原因)。另一方面,度和聚集系数间的相关性对于分析系统的层次性和模块化程度(度较小的类或模块倾向于聚集在一起,展现出较高的内聚性)。
    复杂网络基本参数在软件网络用处

    展开全文
  • 复杂网络理论及其应用-基本概念

    千次阅读 2020-12-02 16:24:30
    文章目录 前言 一、引文 1.1 Konigsberg七桥问题---图论 1.2 ER 随机图 1.3 小世界实验 二、基本概念 2.1.平均路径长度 2.2 聚类系数 ... 总结 以上就是今天要讲的内容,本文仅仅简单介绍了复杂网络的一些基本概念。
  • 复杂网络的研究

    千次阅读 2018-11-04 21:53:53
    1. 复杂网络定义 : 复杂网络概念最开始的时候是相对于规则网络和随机网络提出来的,即介于规则网络和随机网络之间的网络都可以称之为复杂网络。—狭义的复杂网络 从广义上说,任何网络都可以称之为复杂网络,...
  • 复杂网络综述

    万次阅读 多人点赞 2016-11-05 09:44:55
    本人毕业设计是关于复杂网络的,之前完全没听说过的概念,于是就在网上找了一些论文来看,顺便做下笔记,这篇文章主要讲了复杂网络的一些基础概述。 这里的网络不是(不仅仅是)计算机网络这门课中的网络,它表示的...
  • 复杂网络分析总结

    万次阅读 多人点赞 2018-04-08 15:31:40
    复杂网络的特点2. 社区检测3. 结构平衡4. 影响最大化5. 网络传播6. 补充7. 参考文献 在我们的现实生活中,许多复杂系统都可以建模成一种复杂网络进行分析,比如常见的电力网络、航空网络、交通网络、计算机网络...
  • 复杂网络研究及其前沿概述

    千次阅读 2019-02-22 21:25:26
    复杂网络研究及其前沿概述1 引言2 复杂网络研究史2.1 七桥问题2.2 随机图理论2.3 小世界网络、无标度网络3 复杂网络的研究特点3.1 网络规模大3.2 网络结构具有复杂性和多元性3.3 网络具有时空复杂性3.4 复杂网络存在...
  • 图与复杂网络

    千次阅读 2018-09-24 12:21:14
    图与复杂网络 图论 特点: 它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案,数学上把这种问题称为最优化或优化(optimization)问题 是它们都易于用图形的形式直观地描述和表达,数学上把...
  • 复杂网络理论是对复杂系统的高度抽象,它突出强调了...本文从复杂网络的统计特性、结构模型以及在航空网络中的应用3个层次系统回顾了复杂网络基本理论和应用现状,期望对航空网络规划问题的研究起到一定的借鉴作用。
  • 复杂网络概述

    千次阅读 2017-11-28 09:47:46
    复杂网络概述 1研究背景 通信网络、电力网络、生物网络、和社会网络等分别是通信科学、电力科学、生命科学、和社会学等不同学科的研究对象,而复杂网络理论所要研究的则是各种看上去互不相同的复杂网络之间的共性...
  • 复杂网络基础

    2019-09-26 02:40:55
    参考书籍:《复杂网络基础理论》(侵删) 第一章 绪论 人类把自己生存的世界变成了网络世界,网络越发达越有效,世界就越小,人的社会性就会得到强化(人是社会性动物可能就是...无标度性质的发现:指出在复杂网络...
  • 复杂系统与复杂网络

    千次阅读 2009-11-02 17:57:00
    复杂系统与复杂网络 20世纪90年代以来,以Internet为代表的信息技术的迅猛发展使人类社会大步迈入了网络时代。从Internet到WWW,从大型电力网络到全球交通网络,从大脑神经网络到各种新陈代谢网络,从科研合作网络到...
  • 复杂网络概括

    千次阅读 2014-09-11 17:20:18
    通信网络、电力网络、生物网络、和社会网络等分别是通信科学、电力科学、生命科学、和社会学等不同学科的研究对象,而复杂网络理论所要研究的则是各种看上去互不相同的复杂网络之间的共性和处理它们的普适方法。...
  • python复杂网络分析库networkx

    千次阅读 多人点赞 2019-10-13 23:00:35
    文章目录1 简介安装支持四种图绘制网络图基本流程2...networkx是一个用Python语言开发的图论与复杂网络建模工具,内置了常用的图与复杂网络分析算法,可以方便的进行复杂网络数据分析、仿真建模等工作。 利用networ...
  • 复杂网络问答

    2017-11-28 09:59:46
    复杂网络的相关研究进入中国已经十年,同时一年一度的全国复杂网络大会也已经进入了第九届。在过去的十年中,很多研究方向受到来自不同研究领域学者们的广泛关注,并极大的推动了复杂网络和复杂性科学的发展。同时,...
  • 复杂网络入门读物

    千次阅读 2015-11-22 10:09:18
    综合类专著中目前最全面的当属Newman的《网络引论》[1],最简洁的则是Dorogovtsev的《复杂网络讲义》[2]。2006年普林斯顿大学出过一本三巨头的专著,名字也很大气,叫做《网络结构与动力学》[3],但是不要有太高期望...
  • 网络分析的基本性质

    千次阅读 2018-06-06 10:21:27
    节点 (node):生态网络中的物种连接 (link):用于展示物种之间的联系,也叫边(edge)度(degree):某节点连接其它节点的个数路径(path):从一个节点到达...现实网络通常具有“小世界(Small-world)”特性。聚集系数...
  • 一文读懂复杂网络(应用、模型和研究历史)

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

    万次阅读 多人点赞 2017-11-28 09:42:18
    通俗易懂的复杂网络 1 什么是复杂网络 1.1 直观理解 什么是复杂网络?对普通人而言,在媒体上看到复杂网络,首先想到的是互联网,实际上网络已经成为Internet的代名词,确实Internet从只有几个结点的简单的网络,...
  • 复杂网络和社会网络

    万次阅读 2015-01-31 23:22:03
    很好的入门介绍 关于复杂网络(complex network)和社会网络(social network)。 第一次从学术意义上接触这两个词儿还是...已经记不得是谁的presentation里面有一幅很经典的复杂网络的图了(当时学到的东西太多
  • 复杂网络分析 03 ER网络学习笔记

    千次阅读 2020-03-08 11:06:52
    3.2ER网络基本性质 3.1 ER网络的生成方式 G(N,L)模型:一个随机图由N个节点构成,并且有L条连边随机放置在L对节点之间(不出现重边和自环)。 G(N,p)模型:一个随机图由N个节点构成并且任意两个不同节点之间存在一...
  • 复杂网络与大数据》第二章:复杂网络模型的学习笔记 目录 1动态演化网络 1.1以网络演化的部件划分 1.2以是否考虑权重划分 1.3以演化网络采用的演化机制划分 1.4以演化网络是否动态变化划分 2社区网络 2.1...
  • 复杂网络数据集整理

    千次阅读 2019-04-11 09:22:22
    复杂网络的研究很多都离不开数据集,下面这些是个人在做科研的过程中在互联网上搜集到的一些数据集网站,列举出来也方便同行们去使用。 1、http://vladowiki.fmf.uni-lj.si/doku.php?id=pajek:data:urls:index ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 254,278
精华内容 101,711
关键字:

复杂网络的基本性质