精华内容
下载资源
问答
  • 提升链路预测精度是复杂网络研究的基础问题之一,现有的基于节点相似的链路预测指标没有充分利用网络节点的重要性,即节点在网络中的影响力。针对以上问题提出基于节点重要性的链路预测算法。该算法在基于局部相似性...
  • 复杂网络关键节点挖掘算法
  • 基于复杂网络节点介数的IP阻断算法,童绥,双锴,近年来,复杂网络分析作为一种应用性很强的社会学研究方法,越来越受人瞩目。而 如何计算图中点的重要性,选取其中的关键节点又��
  • 介数中心性和接近中心性指标, 虽然具有较好的刻画节点重要性的能力, 但计算复杂度太高, 难以在大规模网络上使用. 为了权衡算法的效率和效果, Chen 等人提出了一种基于半局部信息的节点重要性排序方法,简称半局部中心...

    介数中心性和接近中心性指标,  虽然具有较好的刻画节点重要性的能力,  但计算复杂度太高,  难以在大规模网络上使用.  为了权衡算法的效率和效果,  Chen 等人提出了一种基于半局部信息的节点重要性排序方法, 简称半局部中心性(semi-local  centrality).  首先定义N(w)为节点Vw的两层邻居度,其值等于从 Vw出发 2步内可到达的邻居的数目,  然后定义

    其中 表示节点 vj的一阶邻居节点的集合.  最终节点 vi的局部中心性定义为  

    可见,  半局部中心性涉及了节点的四阶邻居信息. 

    #%%
    import networkx as nx
    #定义图的节点和边 
    nodes=['1','2','3','4','5','6','7','8','9','10','11',
           '12','13','14','15','16','17','18','19','20',
           '21','22','23'] 
    edges=[('1','2',1),('1','3',1),('1','4',1),('1','5',1),
           ('1','6',1),('1','7',1),('1','8',1),('1','9',1),
           ('2','3',1),('3','4',1),('6','10',1),('7','8',1),
           ('8','9',1),('10','11',1),('10','23',1),('11','12',1),
           ('11','21',1),('11','23',1),('12','13',1),('12','14',1),
           ('12','15',1),('13','14',1),('13','15',1),('13','22',1),('14','15',1),
           ('14','23',1),('15','16',1),('16','17',1),('16','18',1),
           ('16','22',1),('17','18',1),('17','20',1),('17','21',1),
           ('18','19',1),('18','22',1),('19','20',1),('19','21',1),
           ('20','21',1),('20','23',1),('22','23',1)] 
    #%%
    #定义无向图 
    G = nx.Graph()
     
    #往图添加节点和边 
    G.add_nodes_from(nodes)
    G.add_weighted_edges_from(edges) 
    #%%
    N = {}
    Q = {}
    CL = {}
    for node in G.node:
        node_nei = list(G.neighbors(node))
        for n_i in node_nei:
            node_nei = node_nei + list(G.neighbors(n_i))
        node_nei = list(set(node_nei))
        N[node] = len(node_nei)-1
    
    for node in G.node:
        node_nei = list(G.neighbors(node))
        t = 0
        for n_i in node_nei:
            t = t + N[n_i]
        Q[node] = t
        
    for node in G.node:
        node_nei = list(G.neighbors(node))
        t = 0
        for n_i in node_nei:
            t = t + Q[n_i]
        CL[node] = t
    
    for node in G.node:
        print(node,'N-value:',N[node],'Q-value:',Q[node],'CL-value:',CL[node])
    

    结果: 

    1 N-value: 9 Q-value: 67 CL-value: 145
    2 N-value: 8 Q-value: 17 CL-value: 92
    3 N-value: 8 Q-value: 25 CL-value: 101
    4 N-value: 8 Q-value: 17 CL-value: 92
    5 N-value: 8 Q-value: 9 CL-value: 67
    6 N-value: 11 Q-value: 18 CL-value: 104
    7 N-value: 8 Q-value: 17 CL-value: 92
    8 N-value: 8 Q-value: 25 CL-value: 101
    9 N-value: 8 Q-value: 17 CL-value: 92
    10 N-value: 9 Q-value: 37 CL-value: 111
    11 N-value: 12 Q-value: 41 CL-value: 166
    12 N-value: 9 Q-value: 38 CL-value: 157
    13 N-value: 8 Q-value: 39 CL-value: 157
    14 N-value: 9 Q-value: 40 CL-value: 166
    15 N-value: 9 Q-value: 37 CL-value: 156
    16 N-value: 11 Q-value: 39 CL-value: 158
    17 N-value: 9 Q-value: 39 CL-value: 158
    18 N-value: 9 Q-value: 40 CL-value: 148
    19 N-value: 8 Q-value: 28 CL-value: 119
    20 N-value: 10 Q-value: 40 CL-value: 158
    21 N-value: 9 Q-value: 39 CL-value: 148
    22 N-value: 12 Q-value: 42 CL-value: 170
    23 N-value: 14 Q-value: 52 CL-value: 200

    参考:

    Duanbing Chen, Linyuan Lü, Ming-Sheng Shang, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(4):1777-1787.

    任晓龙, 吕琳媛. 网络重要节点排序方法综述[J]. 科学通报, 2014(13):1175-1197.

    http://www.xiaowangyun.com/wyblog/detail/?id=121

     

     

    展开全文
  • 基于Python2.7实现的LeaderRank复杂网络节点排序算法算法输出排序后每个节点的重要性值 参考论文:2011-Leaders in Social Networks, the Delicious
  • 山区复杂地形的无线传感器网络节点定位算法
  • python算法: # 定义计算半局部中心性的函数 def local_centrality(A, n): # A为邻接矩阵,n为节点个数 N = np.zeros(n) # N为最近邻和次近邻个数和 for i in np.arange(n): neibor = np.where(A[i, ...

    Chen 等考虑节点最近邻居和次近邻居的度信息,提出半局部中心性。
    Γ(u)为节点u的最近邻节点集合,N(w)为节点w的最近邻和次近邻节点数量,CL(v)为节点v的半局部中心性
    python算法:

    # 定义计算半局部中心性的函数
    def local_centrality(A, n):  # A为邻接矩阵,n为节点个数
        N = np.zeros(n)  # N为最近邻和次近邻个数和
        for i in np.arange(n):
            neibor = np.where(A[i, ]==1)  # 求最近邻节点下标
            for k in neibor[0][np.arange(len(neibor[0]))]: 
                neibor2 = np.where(A[k, ]==1)  # 次近邻节点下标
                neibor = np.union1d(neibor, neibor2) # 合并得到邻居节点和次邻居节点和当前节点下标
            N[i] = len(neibor)-1  # 去除当前节点
        Q = np.zeros(n)
        for i in np.arange(n):
            Q[i] = sum(N[np.where(A[i, ]==1)])
        # 计算局部中心性
        LC = np.zeros(n)
        for i in np.arange(n):
            LC[i] = sum(Q[np.where(A[i, ]==1)])
        return LC
    

    参考文献:
    1.Chen, Duanbing & Lü, Linyuan & Shang, Ming-Sheng & Zhang, Yi-Cheng & Zhou, Tao, 2012. “Identifying influential nodes in complex networks,” Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(4), pages 1777-1787.
    参考博客(R语言版本):
    https://www.xiaowangyun.com/wyblog/detail/?id=121

    展开全文
  • 利用matlab求解复杂网络节点介数,首先求出各节点的最短路径,然后利用对应算法求解介数。 输入:复杂网络邻接矩阵;输出:各节点的介数值
  • 构建随机网络模型,固定网络节点数量,找寻节点关联关系,构建边迭代网络模型,最后依据找出的节点关系进行相似性的算法模型计算,实现对不确定性复杂网络节点相似性数理的统计。与传统统计模型进行对比实验研究,...
  • PAGE 28 密级 保密期限 硕士研究生学位论文 题目复杂网络节点角色发现算法研究 学 号 2011110765 姓 名 于兴隆 专 业 计算机科学与技术 导 师 吴斌 学 院 计算机学院 2013年12月20日 独创性或创新性声明 本人声明...
  • 因此,网络聚类方法对于研究复杂网络具有重要意义。 当前,许多典型的聚类算法都有一些缺点,例如不准确和收敛缓慢。 在本文中,我们通过计算节点的核心影响力提出了一种聚类算法。 聚类过程是对社会学中聚类形成...
  • 2)复杂网络节点度及度分布的MATLAB代码.txt -- 复杂网络节点度和度分布计算的MATLAB代码,用来计算复杂网络的节点度和度分布以及度的累积概率分布。 3)网络重要节点排序方法综述_任晓龙(带附表).pdf
  • 复杂网络中平均节点能量的改进标签传播算法
  • 基于复杂网络节点重要性的链路预测算法[J]. ,2016, 36(12) : 3251-3255
  • 复杂网络中Top-k节点的快速高效挖掘算法
  • 一种低复杂性的无线传感器网络分布式节点定位算法,冯贤文,苏进,针对目前无线传感器网络节点定位存在的问题,提出了一种基于FastMap降维法的低复杂性分布式节点定位算法算法根据FastMap降维法原�
  • 为了准确、快速地发现大规模复杂网络中的局部社区,提出了一种基于节点接近度的局部社区发现算法。该算法以最大度节点作为起始节点,利用节点...针对稀疏网络,该算法的时间复杂度为O(nlog(n)),n为网络节点数。
  • 本文基于有向加权复杂网络模型,借鉴PageRank排名算法,并结合复杂网络节点重要性评估特点,提出节点重要性评估的新指标―――DWCN - NodeRank和相应评估方法,该指标既反映出节点局部连接的特性,又从全局体现了有向加权...
  • 图谱理论与复杂网络相关算法

    千次阅读 2020-05-13 20:57:36
    1.图谱问题研究背景 现实生活中的各种复杂网络都可以用图有效表示。...由于复杂网络节点规模巨大,通常很难找到特定网络拓扑结构与图谱性质间的直接相关性,求解复杂网络社团分割问题的精确解是一个NP难问题。 2

    1.图谱问题研究背景

    1. 现实生活中的各种复杂网络都可以用图有效表示。给定一组样本,可以用图来描述样本之间的相关性,其中每个数据样本看做图中的一个节点,样本之间的相似性决定节点间(边)的权重。这些复杂网络中存在一些子图,子图内部节点连接相对紧密,子图间节点连接相对稀疏。这写子图称为社团。社团结构反应了复杂网络代表的系统中节点间的拓扑关系。复杂网络社团结构分割属于图的划分问题。由于复杂网络节点规模巨大,通常很难找到特定网络拓扑结构与图谱性质间的直接相关性,求解复杂网络社团分割问题的精确解是一个NP难问题。

    2.基本概念与记号

    1. 一个图G由顶点V(G)和边E(G)构成,其中边是顶点集V(G)不同顶点的一对为序对。常用符合xy表示。如果xy是一条边,就可以说顶点x与顶点y相邻接,或者说顶点y是顶点x的邻居,表示x~y。如果一个顶点是一条边的两个端点之一,就说这个顶点和这条边是相关联的。比如计算机网络拓扑。

    2. 图G的邻接矩阵A是一个nxn的实对称矩阵定义为:在这里插入图片描述
      矩阵L(G)=D(G)-A(G)称为图G的Laplacian(拉普拉斯)矩阵,其中D(G)是对角元素{d1,d2,…,dn}的对角矩阵。矩阵L(G)也被称为Kirchhoff矩阵。

      定理:矩阵树定理:设L是图G的Lapacian矩阵,Li,j是从L中删去第i行和第j列后地道的矩阵L的子矩阵。则矩阵L的代数余子式就等于图G的生成树的数目τ(G)。表示为在这里插入图片描述
      式中:i,j=1,2,…,n

    3. 图G中的一条u-v的W通道(walk)是图G中的一个顶点序列,这个序列从顶点u开始,以顶点v结束,序列中连续的顶点是相邻接的,表示为W:u=v0,v1,…,vk=v,其中k≥0。通道中的顶点可以重复出现,如果u=v,则称通道w是闭的,否则是开的。通道中出现的变得数目就是通道的长度,长度为0的通道称为平凡通道(trivial walk)。所以W:v就是一个平凡通道。如果一条u-v通道中的边都是不同的,即从顶点u遍历到顶点v每条边只被遍历一次,则称这样的通道为迹(trail)。如果通道中的顶点都不重复,则称这样的通道为路(path)。

    3.复杂网络基本概念

    ​ 复杂网络是复杂系统(如社会学中的人际关系…)的一种表现形式,复杂系统中的一个实体在网络中表示为一个节点,而节点之间的边则属于两个实体之间的某种关系。由于这样的网络其节点数量规模较大,而且节点与节点之间的联系较为复杂,那么网络的复杂性就会随着节点与边之间的关系而增加,所以这样的网络就被称为“复杂网络”。

    ​ 图论是复杂网络研究的基础。如ER随机图、小世界网络、无标度网络。

    ​ 由于在复杂网络中,网络的连接错综复杂,而网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统,所以对复杂我拿过来结构的分析就是对网络中的节点和边的分析。

    社团结构,在社团结构内部的节点之间的连接相对紧密,在社团之间的连接相对来说却比较稀疏。在实际网络中,社团结构关系到网络中功能的划分,对网络整体了解和分析,发现网络中的动力学传播并找到网络中隐藏着的规律,甚至是预测网络的行为,所以发现实际网络中的社团结构的意义就显得十分重要。

    ​ 复杂网络划分的意义在于对网络中的单个节点进行分析:通过节点所在社团的位置揭示出该节点在社团中的功能——若节点位于社团比较中心的位置,即该节点的度比较大,则这个节点在社团中可能起到中心控制的功能;而位于社团边界的节点,则可能更多的担负着与其它社团间的信息传输功能。

    ​ 发现网络中的社团结构在一定程度上也揭示了现实大部分网络中的“分辨率”现象,即网络是由很多社团组成,但是这些社团本身又是由很多小社团所组成。例子。得到网络的“分辨率”后,就可以对网络的行为做进一步详细的观察和控制,使得处理和分析网络中的问题变得更加简单方便和有针对性。

    ​ 每个网络都可以抽象成一个节点集和边集组成的网络N=(V(N),E(N)),其中V(N)代表网络的节点集,E(N)代表网络的边集。集合E(N)中的每一条边都有V(N)中的一节点相对应,如果节点对(i,j)与节点(j,i)对应的是同一条边,那么N就是一个无向网络(undirected network);如果节点对(i,j)与节点(j,i)对应的是不同的边,那么N就是一个有向网络(directed network)。若给每条边都赋一个权值,那么该网络就是一个加权网络(weighted network),否则就是无权网络(unweighted network)。

    1.密度

    网络的密度(density)是指网络中(n个节点)实际存在的边的数量l与网络中最大的可能边数m的比值,即density=l/m,其中网络中最大的可能边数m=n(n-1)。

    2.平均路径长度

    网络中两个节点i和j之间的距离dij定义为连接这两个节点的最短路径上的边数,网络的平均路径长度L定义为任意两个节点之间的距离的平均值,即在这里插入图片描述
    式中:n为网络节点数,网络的平均路径长度也称为网络的特征路径长度(characteristic path length)。

    3.集聚系数

    复杂网络的集聚系数(clustering coefficient)在某种程度上类似于社会关系网络中的“物以类聚,人以群分”的特性,它描述网络中节点的邻点之间也互为邻点的比例。若网络中的节点a与有ki节点与其相连,那么这ki个节点就称为节点a的邻居。而这ki个节点之间的边数ei和最大的可能边数m之比就定义为节点i的聚类系数Ci,即在这里插入图片描述,其中m=ki(ki-1)。

    整个网络的聚类系数是指所有节点聚类系数的平均值,它是考查网络的集团化程度在这里插入图片描述,其中n为网络节点总数。

    4.节点的度

    ​ 节点的度是指与该节点直接相连的节点数量,

    5.度分布

    ​ 泊松分布、幂律形式

    6.中心度

    1.度数中心性

    ​ 度数最大的就是中心点。

    ​ 设网络具有n个节点,则节点x的度指标d(x)表示与节点x相邻接的节点数,为了根据度指标来比较不同规模的网络中的节点的中心化,需要对度指标进行归一化处理,设经过归一化处理后的度指标为CD(x),即在这里插入图片描述,其中n为网络节点数,n-1为最大可能邻接点数。

    2.介数中心度

    ​ 介数中心度(Betweenness Centrality)认为中心点应该是信息、物质或能量在网络上传输时负载最重的节点,也就是介数最大的节点。

    ​ 流介数中心度(Flow Betweenness Centrality)去除最短路径的概念来定义介数,由此定义在这里插入图片描述
    其中gjk为节点j与节点k之间的路径条数;gjk(X)为节点j与节点k之间经过节点x的路径条数。当节点的流介数中心度较大时,则说明在网络传输信息、物质或能量时,其负载较重,可以被认为是网络的中心节点之一。

    3.紧密度中心度

    ​ 紧密度中心度(Closeness Centrality)定义为节点到网络中其他节点的距离之和的倒数,紧密中心度表示了某节点到达其他节点的难易程度,也就是节点到网络中其他节点的总距离最小,在这里插入图片描述
    其中,dxy为节点x到节点y的最短路径,n为网络的节点数。

    度数中心性是描述节点在网络中产生的直接影响力

    紧密度中心度是描述节点通过完了对其他节点的影响能力。

    4.常见的社团划分算法

    1.Kernighan-Lin算法

    ​ Kernighan-Lin算法是一种试探优化的方法,其基本的思想是为网络引入一个试探函数Q,Q代表某两个准社团内部的边数减去两个准社团之间的边数的差值,然后得到使Q值最大的划分方法。

    ​ 首先将整个网络的节点随机的或根据网络的现有信息分为两个部分,在两个社团之间考虑所有可能的节点对,试探交换每对节点并计算交换后的ΔQ,ΔQ=Q交换后-Q交换前,记录ΔQ最大的交换节点对,并将这两个节点互换,记录此时的Q值。规定每个节点只能交换一次,重复这个过程直至网络中的所有节点都被交换一次为止。需要注意的是不能在Q值发生下降时就停止,因为Q值不是单调增加的,既使某一步交换会使Q值有所下降,但其后的一步交换可能会出现一个更大的Q值。在所有的节点都交换过之后,对应Q值最大的社团结构即被认为是该网络的理想社团结构。

    缺点:要求必须在计算前知道该网络的社团个数,,否则该算法也不确定要重复到哪一步停止。

    2.谱平分方法

    ​ 谱平分发是基于Laplacian(拉普拉斯)矩阵的性质而进行社团划分的方法。

    3.分裂方法

    ​ 划分网络社团结构的一种简单的方法就是将连通社团之间的边移除,这就是分裂方法的基本思想。而这个方法的主要难点就在于如何正确地找到社团之间的边。在分裂方法中,从整个网络出发,试图找到已经连接的相似性最低的节点对,然后移除它们之间的边,在某些极端情况下也有可能将节点也移除(由于连接该点的边都被移除)。分裂方法利用树状图来表示其分裂的流程,可以更好地描述整个网络逐步分裂成若干个越来越小的社团的过程。如下图所示,底部的各个圆代表了网络中的各个节点,当水平虚线从顶部逐渐向底部移动时,即表示整个网络逐渐分成若干个社团结构,在虚线移动到底部时,整个网络的节点就退化成独立的社团。在分裂方法中GN算法和快速分裂算法是比较有代表性的。

    在这里插入图片描述

    1)GN算法

    ​ 由Girvan和Newman提出的GN算法在近几年已成为社团结构分析的一种标准算法,他的基本思想是从网络的整体出发,不断地从网络中移除介数最大的边,从而获得最佳的社团结构。边介数定义为网络中经过每条边的最短路径的数目。GN算法的基本流程如下:

    ​ (1)对复杂网络中的每一条边,计算其对应的边介数;

    ​ (2)比较网络中所有的边介数,并将边介数最大的边从网络中移除;

    ​ (3)重复以上两个步骤,直至每个节点都是一个退化的社团。

    ​ 设一个网络的节点数为n,边数为m。每次进行一次广度优先搜索就可以得到一个节点与其他节点之间的最短路径,其算法复杂度为O(m)。在实际网络中,每个节点与其他节点之间的最短路径条数可能并不唯一,而是存在着几条长度相等的最短路径。设节点i的权值为从源节点到j节点的不同最短路径数目,如果节点i与节点j直接相连,且节点i比节点j距离源节点更近,则节点j通过节点j通过节点i到达源节点的最短路径与节点j到达源节点的最短路径总数之比为wi/wj,那么在最短路径条数不唯一的情况下计算边介数的步骤为:

    ​ (1)得到“最短路径树”中所有“叶子”节点l;

    ​ (2)对每个与“叶子”节点l相邻的节点i,从节点l到节点i之间的边赋权值wi/wl;

    ​ (3)从距离源节点最远的边开始,对于连接节点i和节点j的边(i,j),将位于其下方的且与该边相邻的权值相加,把得到的和加1再乘以wi/wj后,得到的值就作为该边的权值;

    ​ (4)重复第(3)步骤,直至遍历网络中所有的节点。

    ​ 每次从网络中移除一条边后,都要重复计算以上步骤。

    ​ 但是在不知道网络社团个数的情况下,GN算法无法判断何时停止,也不能直接从网络的拓扑结构来判断所得到的社团结构是否具有实际意义。为解决这个问题,Newman等人定义了模块度的概念,用来衡量网络社团结构划分的质量。在每次GN算法结束时,整个网络被分成了k个社团,定义一个kxk的对称矩阵E=(eij),其中eij表示连接社团i和j之间的边所占整个网络总边数的比例,这里的边值得是原网络的边,而不是将边移除后的网络,因此模块度的衡量标准是利用整个网络来进行计算的。

    ​ 定义在这里插入图片描述为矩阵的对角线上各元素之和,表示的是网络中所有社团内部的边占整个网络边数的比例,在这里插入图片描述为每行或每列各元素之和,表示的是与社团i的节点相连的边占整个网络边数的比例。模块度的衡量标准公式为:

    在这里插入图片描述

    其中,在这里插入图片描述为矩阵x的所有元素之和。Q的值在0到1之间,如果Q的值越靠近1,则说明网络的社团结构越明显。在实际的网络中,Q值一般位于0.3~0.7之间。

    ​ GN算法只是适用于中等规模的网络,如节点数量在10000以下的网络。

    2)快速分裂算法

    ​ Radicchi等人针对GN算法的时间复杂度问题,在GN算法的基础上提出了快速分裂算法。因为这个算法只需要计算局部的一些变量,从而在运算量上大大减少,复杂度也会相应下降。该算法的基本思想是根据边聚类系数来衡量连接不同社团之间的边,而不是GN算法的边介数。与节点聚类系数的定义类似,包含该边的三角形总数与所有可能包含该边的三角形的数目之比就是边聚类系数的定义。对于节点i和节点j之间的边定义为:

    在这里插入图片描述

    其中:在这里插入图片描述为实际包含该边的三角形数量,k为节点的度,也即所有可能的包含边(i,j)的三角形的总数。

    ​ 由于网络社团内部的节点之间连接比较紧密,则三角形的数目相对较多,那么在这里插入图片描述就相对比较大,而连接网络社团之间的边包含在极少的三角形内,甚至不被任何的三角形所包含,则在这里插入图片描述相对比较小。由此可见边聚类系数就可以代替GN算法中的边介数来作为衡量不同社团之间的边的标准。类似地,可以推广到多边形中,则有

    在这里插入图片描述

    其中:在这里插入图片描述为实际包含边(i,j)的g边形,](https://img-blog.csdnimg.cn/20200513204928156.png)为所有可能的包含该边的g边形的数目。在移除一条边是,就要检查整个网络是否分解成了若干个社团,并且在移除的边的小范围内更新其他边的聚类系数。

    ​ 快速分裂算法与GN算法有一定的相似性,因为通常情况下边介数比较大的边,其聚类系数都会比较小,所以该算法在结果上与GN算法非常相似,但是聚类系数最小的边不一定边介数最大,所以它们并不等价。

    ​ 由于算分非常依赖网络中存在的三角形结构,那么当网络相对稀疏时,其边的边聚类系数都会很小,所以得到的结果也就会出现错误,甚至不能找到社团结构,事实上非社会性网络的三角形结构就相对比较低。

    4.聚合方法

    ​ 与分裂方法不同,聚合方法是用某种方法计算出网络节点之间的相似度,然后再一个节点数为n边数为0的控网络中,将相似度最高的节点对相连。这个方法可以在任何时刻终止,在这一时刻所得到的结构即可以认为是组成网络的若干社团。

    1)Newman快速算法

    ​ 该算法是Newman在GN算法的基础上提出的,虽然GN算法属于分裂方法的一种,但Newman快速算法利用了聚合方法的思想进行社团划分。算法描述如下:

    ​ (1)首先,认为网络中的每个节点就是一个退化的社团结构,设网络中有n个节点,那么有变量eij和ai,满足在这里插入图片描述

    其中:ki为网络节点i的度,m为网络的边数。

    ​ (2)将有边相连的社团对依次合并,计算并记录合并后的模块度增量,Newman快速算法中的模块度增量定义为:

    在这里插入图片描述

    ​ 每次合并都要沿着使ΔQ减少最小的方向或者使ΔQ增大最多的方向进行。在每一次的合并后,需要对相应的eij进行更新。

    ​ (3)重复步骤(2),直至整个网络合并成为一个社团,其合并次数最多执行n-1次。

    ​ 算法在结束后便可得到对应的社团结构树状图,在树中选择一个局部最大的Q值所对应的结构即可得到在该算法下最理想的网络社团结构。

    2)结合谱分析的凝聚算法

    ​ 该算法结合了谱分析和聚合方法的特点,其基本思想是利用Laplacian矩阵把网络的节点在特征向量空间中描述出来,并引入一种衡量节点之间相似度的标准,利用聚合方法的思想将相似度比较高的节点聚合到一起作为一个社团,最终得到社团结构树状图,根据模块度的大小得出最佳社团结构。

    展开全文
  • 关于解决复杂网络最小节点覆盖问题的尝试算法:结合进化算法的全局搜索能力与博弈算法的局部搜索能力,提出了基于雪堆博弈的自然进化算法,变异搜索算法
  • 设计了评价复杂网络节点重要度的DH指标,构造了用于DH指标快速分布式计算的并行随机距离渐进(parallel random distance approach,简称PRDA)算法.通过网络最大连通率、网络均衡熵、算法有效性和算法效率的评价实验...
  • 复杂网络节点重要性评价方法初探 复杂网络社区结构发现算法-基于igraph C library 复杂网络社区结构发现算法-基于python networkx clique渗透算法 复杂网络社区结构发现算法-基于igraph 标签传播算法 复杂...
    展开全文
  • 复杂网络算法

    2015-06-29 06:53:31
    简单复杂网络算法,运行效果好,效率高。 N=input('请输入最近邻耦合网络中节点的总数N:'); %%参数输入 K=input('请输入最近邻耦合网络中每个节点的邻居数K:'); if K > floor (N-1) | mod (K,2) ~=0 disp ('参数...
  • 水下无线传感器网络节点定位算法

    千次阅读 2017-06-10 17:31:27
    目前存在着大量的基于水下的无线传感器网络节点定位算法,根据采集或处理数据方式的不同,可将这些定位算法划分为以下几种类型:  (1)根据位置计算过程中是否测量节点间的角度或距离信息,可将定位算法分为两类:...
  • 识别重要节点复杂网络研究的基础性问题。现有理论框架主要以“点-边”这种低阶结构为基本单元,往往忽略了多个节点之间可能存在的交互性、传递性等重要因素。为了更加精确地识别重要节点,对网络中以模体为基本...
  • 传统的回路法、节点法由于要进行回路或迭代加速系数的计算,程序复杂,对于大规模网络计算时间较长。采用基于节点压能的网络分风算法避开了回路和迭代加速系数的计算,具有风量初始值任选,迭代次数少等优点,结果精度...
  • 复杂网络节点重要性评价方法初探

    万次阅读 2016-04-18 08:13:28
    在使用复杂网络分析业务问题时,如何区分网络中不同节点的重要性程度,就是一个需要考虑的问题。为了解决我们自己的业务问题,顺便了解了一下相关的方法,特记录一下,若有益于相关领域的同学,则幸甚。  一、要...
  • 算法利用基于模块度的聚类思想 , 首先计算出节点对之间的模块度增量 , 然后迭代查找出所有模块度增量最大的节点对 , 对所有节点对进行合并操作 , 并更新节点对之间的模块度增量 , 进而实现大规模复杂网络社区...
  • 为避免早熟收敛和局部最优,设计了一种基于复杂网络进行个体交互的粒子群算法(CNS-PSO)。该算法在粒子与网络节点间建立映射关系,并根据节点的邻居集合,获得粒子的动态飞行邻居。每个飞行邻居集合是一个独立又...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 138,653
精华内容 55,461
关键字:

复杂网络节点算法