精华内容
下载资源
问答
  • 常见复杂网络分析方法

    万次阅读 多人点赞 2019-09-18 15:38:07
    常见的复杂网络分析方法基本分析方法关联分析方法 注:本文部分内容来自《复杂网络分析与应用》与《中国航空复杂网络的结构特征与应用分析》 1.赵正旭,郭阳,等.复杂网络分析与应用[M]北京:科学出版社,2018. 2.陈...

    常见的复杂网络分析方法


    注:本文部分内容来自《复杂网络分析与应用》与《中国航空复杂网络的结构特征与应用分析》
    1.赵正旭,郭阳,等.复杂网络分析与应用[M]北京:科学出版社,2018.
    2.陈航宇,李慧嘉.中国航空复杂网络的结构特征与应用分析[J].计算机科学,2019,s1:300-304.

    1.基本分析方法

    1.1.度和度的分布:
    度是指与该节点直接连接的节点个数。度值的大小反映了节点在整个网络中的重要性。度分布p(k)反映了网络节点中度值为k的节点所占的比例。

    1.2.平均路径长度
    相互连接的两个节点i和j之间边数最少的路径所包含的边数即为这两个节点间的距离dij。取尽网络中任意两节点的组合,网络的平均路径长度定义为所有组合之距离的平均值:
    在这里插入图片描述

    1.3.聚类系数
    聚类系数Ci是指所有与节点i相连的节点之间实际相连的边数占这些点可能的最大连边数目的比例,聚类系数反映网络节点的聚类情况:
    在这里插入图片描述
    其中,ki为与节点i连接的其他节点的个数;Ei为这ki个节点间相互连接的边数(两点之间的双向边和单向边都按1条计数)。整个网络C定义为网络中所有节点聚类系数的平均值:
    在这里插入图片描述
    其中,C取1说明网络中的所有节点都相连。

    1.4.介数
    网络中包含节点m的最短路径的条数定义为节点m的介数。介数的大小反映了节点在整个航空网络中的必要性和影响力,介数越大的节点在网络中的中枢性越强。(注意:介数与度值的概念,一个是必要性大,一个是重要性大)

    1.5.核数
    一个图的k-核是指反复去掉度小于或等于k的节点所剩余的子图。存在于k-核的节点,在(k+1)-核中被除去,则k就是该节点的核数。节点核数中的最大值称为网络的核数。节点的核数可以表明节点在核中的深度。图的核数大,说明图中大部分节点不会因为其他节点收到破坏而轻易脱离出网络,整个网络具有较深的层次。

    2.关联分析方法

    2.1.度度相关性
    首先计算节点的邻点平均度:
    在这里插入图片描述
    其中,k为节点度值,节点j与节点i相连。将网络中节点度值都为k的所有节点Nk的邻节点的平均度knn,i取平均,得到度为k的节点的邻点平均度:
    在这里插入图片描述
    如果knn(k)随k的增加而增加,即knn(k)-k曲线斜率大于零,则表示度大的节点倾向于连接其他度大的节点,成为度正相关(或同配性);反之,如果knn(k)随k的增加而递减,表示度大的节点倾向于连接其他度小的节点,成为度负相关(或异配性);如果knn(k)不随k的变化而变化,则称节点的度是不相关。

    2.2.度权相关性
    定义含权的节点i的所有邻节点j的平均加权度为:
    在这里插入图片描述
    分析邻节点平均加权度随节点的加权度值S的变化,以及邻节点平均加权度随节点的度值k的变化。
    分别分析邻节点平均加权度与节点度值之间,邻节点平均加权度与节点的加权度值之间的关系。若均呈现负相关性,则说明度大的节点偏好连接加权度小的节点;且若邻节点平均加权度随着节点度值与节点加权度值的增大,相关性趋势减弱,则说明权值对节点间的影响较大。

    2.3.介数相关性
    介数相关性描述的是节点根据介数相互选择的偏好。一个介数为g的节点i,与j节点相连,则节点i的邻点平均介数记为:
    在这里插入图片描述
    将网络中节点介数都为g的所有节点Ng的邻节点的平均介数gnn,i进行平均,得到“介数为g的节点的邻点平均介数”:
    在这里插入图片描述
    分析网络节点的邻点平均介数gnn与介数g的分布关系,若呈现明显的负相关性,说明介数大的节点偏好连接其他介数小的节点,反之,则说明介数大的节点偏好连接其他介数大的节点。

    2.4.簇度相关性
    节点的邻节点相互连接的集聚程度与节点度值的相关性成为簇度相关性。分析节点的度与平均聚类系数之间的关系。若度值大,聚类系数小,则说明度值大的为网络的中心。

    展开全文
  • Gephi是一款开源免费跨平台基于JVM的复杂网络分析软件, 其主要用于各种网络和复杂系统,动态和分层图的交互可视化与探测开源工具。可用作:探索性数据分析,链接分析,社交网络分析,生物网络分析等 Gephi的主要...
  • 复杂网络分析总结

    万次阅读 多人点赞 2018-04-08 15:31:40
    参考文献 在我们的现实生活中,许多复杂系统都可以建模成一种复杂网络进行分析,比如常见的电力网络、航空网络、交通网络、计算机网络以及社交网络等等。复杂网络不仅是一种数据的表现形式,它同样也是一种科学...
    
    

      在我们的现实生活中,许多复杂系统都可以建模成一种复杂网络进行分析,比如常见的电力网络、航空网络、交通网络、计算机网络以及社交网络等等。复杂网络不仅是一种数据的表现形式,它同样也是一种科学研究的手段。复杂网络方面的研究目前受到了广泛的关注和研究,尤其是随着各种在线社交平台的蓬勃发展,各领域对于在线社交网络的研究也越来越火。研究生期间,本人的研究方向也是一直与复杂网络打交道,现在马上就要毕业了,写一篇博文简单介绍一下复杂网络特点以及一些有关复杂网络研究内容的介绍,希望感兴趣的博友可以一起讨论,一起学习。

      下图分别是一个航空网络(上图)和Facebook网络全球友谊图(下图)。


    1. 复杂网络的特点

      钱学森对于复杂网络给出了一种严格的定义:具有自组织、自相似、吸引子、小世界、无标度中部分或全部性质的网络称之为复杂网络。言外之意,复杂网络就是指一种呈现高度复杂性的网络,其特点主要具体体现在如下几个方面:

      1.1 小世界特性

      小世界特性(Small world theory)又被称之为是六度空间理论或者是六度分割理论(Six degrees of separation)。小世界特性指出:社交网络中的任何一个成员和任何一个陌生人之间所间隔的人不会超过六个,如下图所示:

      在考虑网络特征的时候,通常使用两个特征来衡量网络:
      特征路径长度(characteristic path length):在网络中,任选两个节点,连通这两个节点的最少边数,定义为这两个节点的路径长度,网络中所有节点对的路径长度的平均值,定义为网络的特征路径长度。这是网络的全局特征。
      聚合系数(clustering coefficient):假设某个节点有kk条边,则这kk条边连接的节点(kk个)之间最多可能存在的边的条数为k(k1)/2k(k−1)/2,用实际存在的边数除以最多可能存在的边数得到的分数值,定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征,反映了相邻两个人之间朋友圈子的重合度,即该节点的朋友之间也是朋友的程度。
      对于规则网络,任意两个点(个体)之间的特征路径长度长(通过多少个体联系在一起),但聚合系数高(你是朋友的朋友的朋友的几率高)。对于随机网络,任意两个点之间的特征路径长度短,但聚合系数低。而小世界网络,点之间特征路径长度小,接近随机网络,而聚合系数依旧相当高,接近规则网络。
      复杂网络的小世界特性跟网络中的信息传播有着密切的联系。实际的社会、生态、等网络都是小世界网络,在这样的系统里,信息传递速度快,并且少量改变几个连接,就可以剧烈地改变网络的性能,如对已存在的网络进行调整,如蜂窝电话网,改动很少几条线路,就可以显著提高性能。

      1.2 无标度特性

      现实世界的网络大部分都不是随机网络,少数的节点往往拥有大量的连接,而大部分节点却很少,节点的度数分布符合幂率分布,而这就被称为是网络的无标度特性(Scale-free)。将度分布符合幂律分布的复杂网络称为无标度网络。

      下图为一个具有10万个节点的BA无标度网络的度数分布示意图:

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

      其实复杂网络的无标度特性与网络的鲁棒性分析具有密切的关系。无标度网络中幂律分布特性的存在极大地提高了高度数节点存在的可能性,因此,无标度网络同时显现出针对随机故障的鲁棒性和针对蓄意攻击的脆弱性。这种鲁棒且脆弱性对网络容错和抗攻击能力有很大影响。研究表明,无标度网络具有很强的容错性,但是对基于节点度值的选择性攻击而言,其抗攻击能力相当差,高度数节点的存在极大地削弱了网络的鲁棒性,一个恶意攻击者只需选择攻击网络很少的一部分高度数节点,就能使网络迅速瘫痪。

      1.3 社区结构特性

      人以类聚,物以群分。复杂网络中的节点往往也呈现出集群特性。例如,社会网络中总是存在熟人圈或朋友圈,其中每个成员都认识其他成员。集群程度的意义是网络集团化的程度;这是一种网络的内聚倾向。连通集团概念反映的是一个大网络中各集聚的小网络分布和相互联系的状况。例如,它可以反映这个朋友圈与另一个朋友圈的相互关系。

      下图为网络聚集现象的一种描述:


    2. 社区检测

      社区检测(community detection)又被称为是社区发现,它是用来揭示网络聚集行为的一种技术。社区检测实际就是一种网络聚类的方法,这里的“社区”在文献中并没有一种严格的定义,我们可以将其理解为一类具有相同特性的节点的集合。近年来,社区检测得到了快速的发展,这主要是由于复杂网络领域中的大牛Newman提出了一种模块度(modularity)的概念,从而使得网络社区划分的优劣可以有一个明确的评价指标来衡量。一个网络不通情况下的社区划分对应不同的模块度,模块度越大,对应的社区划分也就越合理;如果模块度越小,则对应的网络社区划分也就越模糊。

      下图描述了网络中的社区结构:

      Newman提出的模块度计算公式如下:



    其中mm为网络中总的边数,A是网络对应的邻接矩阵,Aij=1Aij=1代表节点ii和节点jj之间存在连边,否则不存在连边。kiki为节点ii的度数,CiCi为节点ii属于某个社区的标号,而δ(Ci,Cj)=1δ(Ci,Cj)=1当且仅当Ci=CjCi=Cj

      上述的模块度定义其实很好理解,我们可以根据一个网络的空模型去进行理解。网络的空模型可以理解为只有节点的而没有连边,这时候一个节点可以和图中的任意其他节点相连,并且节点iijj相连的概率可以通过计算得到。随机选择一个节点与节点ii相连的概率为kj/2mkj/2m,随机选择一个节点与节点jj相连的概率为kj/2mkj/2m,那么节点ii和节点jj相连的概率为pipj=kikj/(4m2)pipj=kikj/(4m2),边数的期望值Pij=2mpipj=kikj/(2m)Pij=2mpipj=kikj/(2m)所以模块度其实就是指一个网络在某种社区划分下与随机网络的差异,因为随机网络并不具有社区结构,对应的差异越大说明该社区划分越好。

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

      (1)模块度的提出成为了社区检测评价一种常用指标,它是度量网络社区划分优劣的量化指标;

      (2)模块度的提出极大地促进了各种优化算法应用于社区检测领域的发展。在模块度的基础之上,许多优化算法以模块度为优化的目标方程进行优化,从而使得目标函数达到最大时得到不错的社区划分结果。

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

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

      (1)基于图分割的方法,如Kernighan-Lin算法,谱平分法等;

      (2)基于层次聚类的方法,如GN算法、Newman快速算法等;

      (3)基于模块度优化的方法,如贪婪算法、模拟退火算法、Memetic算法、PSO算法、进化多目标优化算法等。


    3. 结构平衡

      结构平衡(Structural Balance)主要是针对社交网络的研究而被提出的,它最早源于社会心理学家Heider提出的一个结构平衡理论。

      3.1 网络平衡的发展

      网络平衡有时也称社会平衡(Social Balance),就网络平衡的发展来说,我们可以将其分为三个发展阶段。
      3.1.1 网络平衡理论的提出
      “网络平衡”一词最早是由Heider基于对社会心理学的研究而提出的,Heider在1946年的文章Attitudes and cognitive organization[1]中针对网络平衡的概念提出了最早的平衡理论:
      (1)朋友的朋友是朋友;
      (2)朋友的敌人是敌人;
      (3)敌人的朋友是敌人;
      (4)敌人的敌人是朋友。
      用常见的三元组合来表示上述的Heider理论如下:

      上述的平衡理论是有关网络平衡提出的最早的理论,它后来也被称为是强平衡理论。

      1956年,Cartwright和Harary对Heider的平衡理论进行了推广,并将其用在了图理论中(STRUCTURAL BALANCE: A GENERALIZATION OF HEIDER'S THEORY[2])。Cartwright和Harary指出对于一个符号网络而言,网络平衡的充要条件是网络中的所有三元组都是平衡的,该结论也可以陈述为一个符号网络平衡的充要条件是它所包含的所有回路(cycles)都是平衡的(“-”号的个数为整数个)。而且,在这篇文章中,他们还提出了著名的结构平衡理论:如果一个符号网络是平衡的,那么这个网络就可以分为两部分子网络,其中每个子网络内部中节点的连接都是正连接,网络之间的连接均为负连接。

      在这各阶段网络平衡的发展的重心主要在于构建网络平衡的心理学和社会学模型。

      3.1.2 网络平衡的数学模型

      在有了Heider等人的奠基工作后,有关网络平衡的发展主要是构建其数学模型,比如网络的动态表现,一个网络连接如何随时间的变化而变化,网络中节点之间的朋友或者敌人的关系如何演化等等。

      3.1.3 网络平衡的应用

      最新关于网络平衡方面的研究大都是研究一些在线网络,比如对某个网站用户属性的分析等等。而且,目前我们身处大数据时代,我们所要研究的网络规模也变为了大型甚至可以说是超大型网络,这这个背景下,如何计算一个网络是否平衡便成为该领域的主要热点问题。

      3.2 网络平衡的基本理论

      (1) Heider理论(强平衡理论SBT)。

      (2) 结构平衡理论(Structural Balance Theroem):在完全符号网络中,网络平衡的充要条件是其所有的三元组(回路)都平衡。

      结构平衡的推论:一个完全符号网络平衡的充要条件是它可以被分为两部分X和Y,X和Y内部的节点连接均为正连接,X和Y之间的连接均为负连接。

      (3) 弱平衡理论(A weaker form of structural balance,WSBT):如果完全符号网络中不存在这样的三元组:两个边为正,一边为负,则该网络称为是弱平衡网络。

      对于弱平衡理论而言,上图的三元组中,三边均为负连接的三元组也属于平衡三元组,也就是三元组的四种情况有三种属于平衡状态,一个属于不平衡状态(两边为正,一边为负)。

      弱平衡网络推论:如果一个网络为弱平衡理论,那么它可以分为多个部分,每部分内的连接为正,部分之间的连接为负。

      (4) 对任意网络平衡的定义.

      1) 对于一个任意网络而言,如果我们可以将它所缺失的边填充使它成为一个平衡的完全符号网络,那么原网络就是平衡网络;
      2) 对于一个任意网络而言,如果我们可以将它分为两部分,使得每个部分内的连接均为实线,部分之间的连接均为虚线。
      以上的两种定义是等价的。
      一个符号网络平衡的充要条件是它不包括含有奇数个负连接的回路。

      (5) 近似平衡网络(略)。

      3.3 网络平衡的计算(A spectral algorithm for computing social balance)
      命题1:节点i参与的三元组数目

      A为邻接矩阵,元素取值可能为:1,-1,0;
      G为邻接矩阵,元素取值可能为:0,1.
      命题2:对于节点i而言,bi为其参与的平衡三元组数目,ui为其参与的不平衡三元组数目,则

      理论1:对于完全符号图而言,

      平衡三元组所占的比例为

      理论2:对于任意符号网络,平衡三元组所占的比例为

      
      注:以上两个计算网络平衡的公式中,特征值可以随大到小选择前几个比较大的,就像PCA那样,这样可以使得计算的复杂度大大减小。


    4. 影响最大化

      随着各种在线社交平台的发展,社交平台(比如QQ、微博、朋友圈等)已经不仅仅是一种用户进行沟通的社交平台,它们更是社会信息产生和传播的一种主要的媒介。影响最大化(Influence Maximization)同结构平衡一样,也是针对社会网络的研究而被提出的,它来源于经济学的市场营销。2001年,影响最大化被Domins首次以一种算法问题的形式被提出。而影响最大化受到广泛的关注是在2003年Kempe等人在当年的KDD会议上发表的一篇有关影响最大化的论文之后,随后各种影响最大化算法被迅速提出,最近的十几年里,影响最大化的相关文章达到了上千篇,可见这个问题还是很值得关注的。

      影响最大化问题可以这样来描述:一个商家或者企业利用一种社交平台(比如为新浪微博)为自己的新产品或者新服务进行推广,如何在资金有限的情况下雇佣微博达人来做推广可以使得推广范围达到最大?

      我们再给出影响最大化的一般定义:

      给定一个网络GG和一个整数KK(一般小于50),如何在GG中找出KK个节点,使得这KK的节点组成的节点集合SS的影响传播范围σ(S)σ(S)达到最大。

      根据上述影响最大化的定义我们很容易可以知道,影响最大化本身属于一种组合优化问题。常用的影响最大化传播模型有独立级联传播模型(ICM)和线性阈值传播模型(LTM)。

      影响最大化方面的主要算法可以分为如下几类:

      (1)基于网络中心性的启发式方法:比如最大度方法、最短平均距离方法、PageRank方法等;

      (2)基于子模块性的贪婪方法:比如最经典的Greedy算法,CELF算法以及后来的NewGreedy和CELF++等;

      (3)基于社区结构的方法:比如CGA算法、CIM算法等;

      (4)基于目标函数优化的方法:比如模拟退火算法等。

    5. 网络传播

       网络传播领域涉及很多方面,比如网络节点重要性排序、网络鲁棒性分析、网络信息爆发阈值优化等。这些领域都很有意思,感兴趣的博友可以好好深入研究一下。

    6. 补充

      6.1 网络可视化工具

      首先在这里推荐两款我常用的网络可视化工具:Pajek (点击进入官方网站)、Gephi(点击进入官方网站)。

      下边为pajek可视化窗口下的一个网络拓扑结构图:

     

      这是Gephi的一个可视化效果:


      6.2 网络数据集

      常用的一些公开数据集整理:

      Pajek(可视化工具)数据集:http://vladowiki.fmf.uni-lj.si/doku.php?id=pajek:data:index;

      Newman(复杂网络科学领域大牛)个人数据集:http://www-personal.umich.edu/~mejn/netdata/

      Stanford大学大规模网络数据集:http://snap.stanford.edu/data/

      复旦大学网络数据集整理:http://gdm.fudan.edu.cn/GDMWiki/Wiki.jsp?page=Network%20DataSet

      KONECT数据集整理:http://konect.uni-koblenz.de/


    7. 参考文献

      [1] Grivan and Newman. Community structure in social and biological networks. PNAS, 2002.

      [2] Newman and Grivan. Finding and evaluating community structure in networks. PRE, 2004.

      [3] Newman. Networks: an introduction. 2010.

      [4] Cartwright and Harary. Structural balance: a generalization of Heider's theory. 1956.

      [5] Facchetti et al. Computing global structural balance in large-scale signed social networks. 2011.

      [6] Kempe et al. Maximizing the spread of influence through a social network. 2003.

      [7] Chen et al. Efficient influence maximization in social networks. 2009. 

      [8] 任晓龙,吕琳媛. 网络重要节点排序方法综述. 2014.


    出处:http://www.cnblogs.com/maybe2030/p/4665847.html#_labelTop


    展开全文
  • 复杂网络、社会网络分析工具pajek

    热门讨论 2012-06-29 08:32:43
    很好的复杂网络、社会网络分析工具,压缩包中含有中文使用手册。软件简单易用,计算效率高,能够以图形化的方式显示计算结果。非常适合于进行复杂网络、社会网络分析以及利用这两种技术解决其它问题的研究者们使用。
  • 提出了一种基于复杂网络的多维时间序列分析建模方法分析了收盘价的回报率顺序和上证指数,深成指,标准普尔500指数和道琼斯工业平均指数的交易量波动顺序。 二维时间序列被转换成一个复杂的网络。 我们分析网络的...
  • 利用python载入邻接矩阵绘制网络图,基于python语言的特点,对邻接矩阵加以处理后再进行应用,即将邻接矩阵去除第一列(节点序号列),复杂网络的基本拓扑结构可以用图论的方法表示成G =(V,E),V中元素称为节点或...
  • 复杂网络分析(一)

    千次阅读 2020-11-10 21:45:58
    网络分析的重要性体现在网络结构会影响功能,功能反过来也会影响结构。 理解复杂系统的行为可以从理解系统相互作用网络的拓扑结构开始。网络拓扑结构的信息是研究系统性质和功能的基础。 一个复杂系统由大量异质...

    一、复杂网络是复杂系统的骨架,复杂系统可以抽象成一个网络,来反映元素之间的相互作用;要想理解一个复杂系统,需要对复杂网络进行分解成单个元素,再研究他们之间的组合是如何相互作用起来的;网络分析的重要性体现在网络结构会影响功能,功能反过来也会影响结构。

    理解复杂系统的行为可以从理解系统相互作用网络的拓扑结构开始。网络拓扑结构的信息是研究系统性质和功能的基础。

    一个复杂系统由大量异质元素组成,且这些元素通过多种相互作用联系。

    二、复杂网络的历史

    欧拉 哥尼斯堡七桥➡️图论(网络研究的基础,网络结构是理解复杂世界的关键)➡️随机图论➡️小世界和无标度网络(Small World Network, Scale-free Network)

    复杂网络研究所关心的一些问题:
    1 如何建立复杂网络模型
    2 如何定量刻画复杂网络
    拓扑结构的统计性质
    -度
    -聚集系数:节点的一阶近邻相互连接的情况
    -最短路径
    -介数:任意一对节点间最短路径所经过的次数
    -权
    -度度相关性:不同度值的节点相互连接的倾向性
    -网络上的聚类分析-社团结构:网络的中观特性,社团内的连边相对紧密,社团间的连边相对稀疏
    3 网络是如何发展成现在这种结构的
    -时间演化性质
    -偏好性的检验
    -Small world network
    -Scale Free Network-BA模型
    网络的拓扑结构
    -规则网络:完全连接、最近邻居连接、星形连接、晶格网络、全局耦合网络
    -随机网络:网络的度分布是泊松分布
    -小世界网络
    -无标度网络:度分布是幂律分布、非齐次性(很少节点有很多连接、很多节点只有很少的连接)
    4 网络特定结构的后果是什么
    -网络的容错与抗攻击能力
    -网络上的动力学性质
    动力系统:自旋、振子或混沌的同步、可激发系统
    传播过程:信息传播与拥堵、网络搜寻、运输过程、疾病转播、谣言传播、舆论形成
    博弈与其他社会行为:囚徒困境、少数者博弈
    其他过程:电力网的级联失效等

    三 复杂网络的表达方式

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

    1 网络的图表达---可视化表达
    组成部分:节点/顶点 N
    相互作用:连边/边 L
    系统:网络/图(N,L)
    
    2 网络的集合表达
    点集:V={1,2,3,4,5,6}
    边集:E={e1,e2,e3,e4,e5}
    网络G=(V,E),由点集V(G)和边集E(G)组成的一个图,可分为无向、有向和加权网络
    
    3 网络的矩阵表达
    用临接矩阵表示,对角线元素全部为0
    拉普拉斯矩阵:L=K-A,K是度矩阵,是对角矩阵;A是图的临接矩阵
    
    网络拓扑:节点之间相互联系的模式
    -度
    节点的度是与节点直接相连的连边数
    度是离散型随机变量,可以求它的均值、方差、标准差、n阶矩、变量X的分布
    
    -网络的平均度
    N(图中节点数) L(图中连边数)
    平均度= 2L/N
    
    -网络的度分布
    Nk(度为k的节点数目) N(网络中的节点总数目)
    将网络节点的度值从小到大排列,统计度值为k的节点占整个网络节点数的比例P(k),即P(k)=Nk/N
    即 在网络中随机选择一个节点,其度值为k的概率
    
    在网络的平均度相等时,网络的度分布可能不同
    
    度分布的表述
    离散型度值pk:一个节点度值为k的概率
    连续型度值pk:节点的度的概率密度函数,p(k)在k1-k2的积分
    
    ##正则网络的度分布:
    全连接网络:delta函数--度都是n-1
    最近邻居连接网络:delta函数---度都相等
    星型网络:中心点度值是n-1,边缘点度值是1
    
    
    -路径
    一条从节点i0到in的长度为n的路径P经过n+1个节点和n条边
    最短路径:两个节点之间的最短路径是指连接这两个节点的边数最少的路径
    两点间路径的条数:如果节点i与j存在一条长度为n的路径,则Aik...Alj=1,反之,Aik...Alj=0
    Nlj=[An]ij
    
    -距离
    直径:网络中任意两点间的最短距离的最大值
    平均路径长度:任意两点之间的最短路径求和后除以边数
    -介数
    边介数、点介数
    任意一对节点间最短路径所经过该点/边的次数
    介数反映了相应的节点或边在整个网络中的作用和影响力,是一个全局几何量,对应着枢纽点或中介点
    
    -集聚系数
    节点i的ki个邻居节点之间实际存在的边数Ei和总的可能边数之比。
    或者通过 包含节点i的三角形数目/以节点i为中心的连通三元组数目 来计算
    
    -网络的传递性 
    T=网络中三角形数目/(网络中连通三元组的数目/3)
    0<T<1 T=1表示任意两个节点有连接;T=0表示无三角形连接
    
    -网络稀疏性与连通性
    完全连接网络:一个网络中任意两个节点之间都有连边存在,平均度为N-1
    网络的稀疏程度:网络中实际存在的边数与最大可能的边数之比 L/Lmax=2L/N(N-1),L是网络中实际存在的边数,N是网络中的节点数
    
    -无向网络的连通:
    连通图:网络中的任意两个节点之间都至少存在一条路径
    最大连通集团:含有节点数最多的连通子图
    对于不连通网络的邻接矩阵,所有的非零元素都存在于沿着矩阵对角线排列的一些方块中,其余部分元素均为0
    
    -度相关性
    网络中两个节点度值之间的关系:
    同配:度大节点倾向于连接 度大节点
    异配:度大节点倾向于连接 度小节点
    中性:节点间的连接于他们自身的度值无关
    衡量度度相关性:
    1 可视化描述
    2 度相关函数
    3 相关系数
    4 皮尔逊相关系数
    -富人俱乐部
    网络的度度相关是异配,但高度节点之间具有很高的连接概率,即富人俱乐部现象
    富人俱乐部系数:2(E>k)/(N>k)(N>k-1)
    E>k:网络中度值大于k的节点之间的连边数
    N>k:网络中度值大于k的节点数
    
    通过计算富人俱乐部系数,发现很多网络中都存在富人俱乐部现象,甚至于随机网中也有富人俱乐部现象,是不合理的,所以要使用标准化的富人俱乐部系数:
    pran(k)=y(k)/yran(k)
    参考文献: Colizza, V..(2006)Detecting rich-club ordering in complex networks. Nature Physics,2(3),110-115
    
    
    -有向网络
    体现在网络领接矩阵的非对称性
    源:网络中入度是0的节点,kin=0
    汇:网络中出度是0的节点,kout=0
    有向网可以计算:平均入度,平均出度,平均度(L/N)
    一个网络总的平均入度等于总的平均出度
    
    有向网的集聚系数:
    
    有向网的度相关:
    参考文献 J.G.Foster, D.V.Foster Edge direction and the structure of networks PNAS 107
    
    有向网络模体的个数:
    参考文献 Network Motifs:Simple Building Blocks of Complex Networks
    
    -加权网络
    1 边权重的赋予:网络中已有的物理量;相互作用的抽象
    2 权重的不同定义:
    ·相似权:概念与距离相反,边权越大,顶点之间越亲近(0为无连接),如合作次数、化学反应速率等
    ·相异权:概念与距离相同,边权越大,顶点之间距离越远(∞为无连接),如 航空线的里程
    
    

     

    展开全文
  • 此外,提出了一种利用复杂网络分析在配电系统 (EDS) 中找到微电网 (MG) 最佳位置的新方法。 本文中的最佳位置指向的位置将导致增强的电网弹性、降低功率损耗和线路负载、更好的电压稳定性以及在停电期间为关键负载...
  • 复杂网络中基于matlab的代码实现方法
  • 01 复杂网络分析概论 1.1复杂网络分析在复杂性研究中的地位 1.2复杂网络研究的发展历程 1.3复杂网络分析案例 1.1复杂网络分析在复杂性研究中的地位 1. 复杂系统 系统中存在的复杂性1 从两个维度来看 a) 系统...

    01 复杂网络分析概论

    • 1.1复杂网络分析在复杂性研究中的地位
    • 1.2复杂网络研究的发展历程
    • 1.3复杂网络分析案例

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

    1. 复杂系统

    • 系统中存在的复杂性1 从两个维度来看
      a) 系统自由度(系统组成成分的数目)degrees of freedom
      b) 相互作用(线性到非线性的转换)

    • 复杂网络是复杂系统的骨架(backbone)

      a) 复杂系统可抽象成一个网络,来反映元素间的相互作用

      b)复杂系统=分解+组合

    • 网络分析十分重要 因为网络结构影响功能,功能反过来也影响结构

    2. 复杂网络的重要性

    • 当研究复杂系统时应该考虑个体之间的关联和作用

    • 理解复杂系统的行为可以从理解系统相互作用网络的拓扑结构开始

    • 网络拓扑结构的信息是研究系统性质和功能的基础。

    • 一句话总结复杂网络的作用:复杂网络是研究复杂系统的一种角度和方法,它关注系统中个体相互关联作用的结构,是理解复杂系统型指和功能的一种途径。

    复杂网络是对复杂系统的一种抽象
    Created with Raphaël 2.2.0 *复杂系统*(由大量异质元素组成,并且这些元素通过多种相互作用相连。) 复杂网络(个体、相互作用)

    元素抽象成个体;相互作用抽象成网络中的连边。

    3. 复杂网络实例

    • 技术网络
      1. WWW
      2. 因特网
      3. 电力网
    • 社会网络
      1.科学引文网
      2.科学家合作网
      3.社交网
    • 交通运输网络
      1.航空网
      2. 城市公共交通网
      3.道路交通网
    • 生物网络2
    • 经济系统
      1.投入产出网
      2.国际贸易网
      我们可以利用构建复杂网络的模式对不同领域进行研究。

    1.2复杂网络研究的发展历程

    1. 复杂网络研究的历史

    1736 欧拉: 哥尼斯堡七桥问题
    1950 Erdos,Renyi: 随机图论
    1998 Strogatz;1999 Barabasi: 小世界和无标度网络
    图论提供了网络研究的基础
    网络的结构 :理解复杂世界的关键

    2.复杂网络的兴起

    • 计算机技术的发展
      拥有各种网络的数据库,并有可能对大规模的网络进行实证研究
    • 普适性发现
      许多实际网络具有相同的定性性质
      且已有的理论不能描述和解释
    • 理论研究的发展
      a)小世界网络(Small World Network),无标度网络(Scale-free Network)
      b)统计物理学的研究手段

    3.复杂网络研究 关心的一些问题

    • 如何建立复杂网络模型
    • 如何定量刻画复杂网络
    • 网络是如何发展成现在这种结构的
    • 网络特定结构的后果
      网络的拓扑结构——静态集合量及其统计性质
      如何针对网络拓扑结构做统计性质分析
    • 从微观上,关注几个统计量度、聚集系数、最短路径、介数、权、相关性
      • 度:节点的一阶邻居数
      • 聚集系数:节点的一节近邻互相连接的情况
      • 最短路径:连接两个节点的变数最少的路径
      • 介数:任意一对节点间最短路径所经过的次数
      • 权:连边的强度
      • 度度相关性:不同度值的节点互相连接的倾向性
      • 社团结构:网络的中观特性,社团内的连边相对紧密,社团间的连边相对稀疏。
      • 结构模型:
        • 规则网络:完全连接、最近邻居连接、星形连接、晶格网、全局耦合网络
        • 随机网络、小世界网络、无标度网络
    • 从中观上,网络 聚类分析
      网络的演化性质和机制模型
    • 时间演化性质、偏好性的检验
    • 小世界、无标度
      网络的结构与功能
    • 网络的容错与抗攻击能力
    • 网络上的动力学性质

    4.ER随机图模型Erdős–Rényi model

    1. N N N个节点,每对节点之间的连边概率为 p p p3
    • 特征:
      • 连通性 Poisson分布
      • 齐次特征 每个节点大约有相同的连接数
      • 节点数不增加

    5.WS小世界网络模型4

    1. N N N个节点构成环状最近邻耦合网络,每条边以概率 p p p随机重连。
      在最近邻居连接网络的基础之上进行断边重连所形成的。(会形成长程的连接 使得网络性质发生变化。)
    • 特征:
      • 齐次性 每个节点有大约相同的连接数
      • 节点不增加

    6.无标度网络

    • 特征:
      • 连通性:幂指数分布(幂律分布)
      • 非齐次性:很少的节点有很多连接,很多的节点只有很少的连接
      • 节点数增加

    7.网络的结构和功能

    1. 网络的鲁棒性和抗毁性
    2. 网络上的动力学行为和过程
      • 动力系统
      • 传播过程
      • 博弈与其他社会行为

    1.3复杂网络分析案例

    • 以科学引文网络为例5
      • 有向、无权、无环网络
      • 节点:论文
      • 连边:论文间的引用关系
      • 网络中的节点数与连边数随时间动态变化
        邻接矩阵 A = A= A=( A A A i j ij ij) N N N × \times × N N N
      • 若论文 i i i引用论文 j j j,则 A A A i j ij ij = 1 =1 =1
      • 若论文 i i i与论文 j j j不存在引用关系,则 A A A i j ij ij = 0 =0 =0
    • 基于不同的引文数据构建不同的引文网络6
    • 静态引文网络的统计特性6
      • 度分布
      • 度度相关性
      • 集聚系数
      • 距离
      • 社团结构
        增加了对科学引文网络结构上的认识
    • 引文网络的动态特性
      引文网络的社团随时间变化7
      论文的平均引用数随时间变化8
    • 引文网络的演化机制9
      引文网络的增长是因为它有复制的机制,基于此机制可以得出来与实际的引文网络性质定性相同的结果。
      →模拟了论文的平均惨老文献数量随时间的演化→进行理论模型和实际结果定性间的一个比较
    • 基于引文网络的知识扩散、思想传播
      使用SIR模型模拟引文网络上思想的传播10
      基于科学引文网 学科领域间知识的流动11
      网络模型提供了新角度/途径来理解一个实际系统

    参考文献


    1. Chialvo D R.Critical brain networks . Physica A,2004, 340(4):756-765. ↩︎

    2. Vidal M,Cusick M E, Barabási A L. Interactome networks and human disease[J].Cell,2011,144(6):986-998. ↩︎

    3. Erdös, P. & Rényi, A. Publ. Math. Inst. Hung. Acad. Sci. 5, 17- 61 (1960) ↩︎

    4. Watts D J, Strogatz S H. Collctive dynamics of‘small-world’networks[J].Nature, 1998, 393(6684): 440. ↩︎

    5. Physical Review E, 2009, 80(3):037101. ↩︎

    6. Scientific Reports, 2014, 4:6496. ↩︎ ↩︎

    7. Journal of Informetrics, 2010, 4(3):278-290. ↩︎

    8. Physical Review E, 2013, 88(1):012814. ↩︎

    9. Phys.Rev E 71(2005)036118. ↩︎

    10. Scientific Reports, 2014, 4:6663. ↩︎

    11. Nature Physics, 2015, 11(10):791-796. ↩︎

    展开全文
  • 复杂网络可视化分析工具,可分析多个网络重要参数
  • 针对网络的最小驱动点集并不唯一, 提出一种随机匹配方法来获取网络中不同的最小驱动点集, 并分析最小驱动点 集集合的平均度分布以及节点在最小驱动点集集合中的出现频率. 研究发现, 多数网络的最小驱动点集分布紧密...
  • 基于复杂网络的体系作战指挥与协同机理分析方法研究
  • 基于文献信息计量所获得的全球高被引科学家和高强度专利发明人信息,运用复杂网络大数据分析方法,构建全球科技领军人才流动网络模型,测度并分析全球主要国家(地区)及全球整体的科技领军人才流动特性。通过该模型的...
  • 利用复杂网络拓扑结构的分形特性,分析网络效率与节点关联和的关系,用部分节点关联和来估计网络全局效率。此外,为了快速判断复杂网络的分形特性,提出基于节点关联和的分形特性判别方法。在构造网络和真实网络中...
  • 复杂社会网络节点重要性可拓聚类动态分析方法.pdf
  • 采用相空间重构方法将一维脑电信号转换成复杂网络进行研究。将一维时间序列构造成多维相空间, 计算多维时间序列任两个向量点间的距离得到加权...因此, 此分析方法为利用复杂网络实现分析和辨识不同脑电提供了新的思路。
  • 复杂网络理论在城市交通网络分析中的应用,赵月,杜文,介绍了复杂网络的基本概念并详细分析了城市交通网络的特征;列举了两种描述城市交通网络的方法,探讨了各自存在的不足;从网络实
  • 复杂适应系统理论角度出发对无线传感器网路的自组织、自适应、主体性等特征进行了分析,认为随着传感技术、通信技术和计算机技术的飞速发展以及 MEMS技术的日益成熟与完善,无线传感器网络将引领未来信息技术迅猛...
  • 创新地提出利用复杂网络方法分析和可视化移动相册,将照片看做一个节点,利用照片的多维元数据之间的相关性建立照片之间的边,这样所有在相册中的照片就组成了一个多维复杂加权网络。分析了照片复杂加权网络的统计...
  • 复杂网络分析——networkx的使用

    千次阅读 2020-11-10 21:18:40
    1. 基本图操作 导包 import networkx as nx import matplotlib.pyplot as plt 建立一个空的无向图G G = nx.Graph() # DiGraph() 有向图 添加一个节点a G.add_node('a') ...G.add_nodes_from(['b','c','d',...2. 其他方法
  • 1)Degree_Distribution.m -- 复杂网络度分布计算的Matlab程序,这个Matlab程序是一个对复杂网络的度分布进行计算的程序,用于复杂网络分析。 2)复杂网络节点度及度分布的MATLAB代码.txt -- 复杂网络节点度和度...
  • 针对现有态势预测方法大都是对态势值的预测,并未揭示网络态势要素动力学特征的问题,提出了一种基于复杂网络的网络安全态势预测机制,可方便而又直观地追溯安全态势中数值波动的动力学特征。其次在该机制中提出基于...
  • 行业分类-作业装置-基于复杂网络的生物活动时间序列分析方法和装置.7z
  • 复杂网络分析拓扑指标

    千次阅读 2019-07-30 23:51:50
    无向图研究节点i所有连接的边的权重和作为点i的点强度,在复杂网络分析中,节点的点强度越大,说明该节点转换至其他节点的频数越多,该节点越重要。平均点强度就是所有点强度和除所有点的个数所得到的值 2.加权...
  • 为了评估软件缺陷的风险,提出了一种基于复杂网络分析的软件缺陷评估方法。该方法首先用一个网络模型表达程序实体之间的关系,将源代码中的方法抽象为节点,方法间的调用关系抽象为有向边,以此构造程序源代码网络;...
  • 网络游戏-基于复杂网络的推特大选数据分析方法.zip
  • 电力系统复杂网络分析(CAN) 利用复杂网络分析方法,求解配网系统中微电网最优位置的新,该位置将增强电网的弹性,减少电力损失和线路负荷,提高电压稳定性,并在停电期间向关键负荷供电。基于复杂网络理论中的中心性...
  • 为研究灾害间的内部关联, 提出根据灾害发生的时间跨距来计算灾害间的共现率和引发率, 然后依据引发率对灾种建立复杂网络模型, 通过度、点权、点介数等方法来研究复杂网络中每个节点的重要性, 为灾害阻断策略提供依据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 416,956
精华内容 166,782
关键字:

复杂网络分析方法