复杂网络节点影响力度量与影响力最大化研究
发布时间：2021-01-30 12:57
网络影响力分析是复杂网络研究的热点内容,其包括节点影响力度量问题和影响力最大化问题,前者是评估网络中各个节点的影响力,后者是评估网络中节点集合整体的影响力,并从中选出传播范围最大的集合,这两项研究对于生物信息和基因学、市场营销、传染病控制和网络监控等均具有重要的现实意义。本文结合节点影响力度量与影响力最大化的研究现状及存在的问题,提出了一种新的影响力度量方法,并在此基础上提出了三个影响力最大化算法,具体内容概括如下:首先,由于K-shell是一种粗粒度的度量方法,并且不能有效地识别处于关键枢纽位置的节点,为此本文提出了一种将K-shell方法和结构洞指标相融合的节点影响力度量方法KSSH。通过相关性和分辨率指标表明KSSH方法具有良好的准确度和区分度。其次,本文将KSSH方法引入到影响力最大化问题中,并讨论了网络中节点之间的影响力重叠效应。本文采用KSSH方法评估各个节点的影响力,并基于节点的聚类系数、节点的邻居节点中被选为种子节点的个数、传播概率以及节点的一阶、二阶邻域提出了两个削弱重叠影响力的影响力最大化算法KSSHDisN与KSSHDi...
【文章来源】：兰州大学甘肃省 211工程院校 985工程院校 教育部直属院校
【文章页数】：69 页
【学位级别】：硕士
【部分图文】：
航空网络示意图
兰州大学硕士学位论文复杂网络节点影响力度量与影响力最大化研究9第二章复杂网络相关理论知识本章将详细介绍复杂网络研究必备的基础理论及本文后面章节涉及到的相关知识，包括网络的表示形式、网络的基本拓扑性质、节点影响力度量的常用方法、影响力最大化问题的定义和常用算法、经典的传播模型等。2.1网络基础理论概述2.1.1网络的图表示图是复杂网络的常用表示工具，它提供了一种用点和线来抽象地描述各种真实网络的规范化方法。网络可抽象为图=(,)，其中是节点的集合，是连边的集合，节点总数为=||，边的总数为=||。除此之外，节点间的连边分为不同的情况，即连边是否有方向和是否具有表示连接强度的权值，并据此将图分为四类：连边无方向无权值的无向无权图、连边无方向有权值的无向有权图、连边有方向无权值的有向无权图、连边有方向有权值的有向有权图。在图论中，通常用来描述图的结构有邻接矩阵和邻接表。图的邻接矩阵表示形式如下：图的邻接矩阵*()ijNNA=a是一个的方阵，若节点到节点之间存在有向连边，则在该矩阵的第行第列填上1或者权值；若它们之间存在无向连边，则在第行第列和第行第列分别填上1或者权值；若没有连边则填上0。实际上，大规模复杂网络中节点之间的连边一般是很稀疏的，这意味着与之对应的邻接矩阵中大多数元素是0，用这种方式存储稀疏图既浪费了存储空间又降低了利用率，故对于稀疏的无权图，还有另外一种表示方式——邻接表，它为每个节点创建一个单链表，链表中的元素即是与该节点直接相连的其他节点。图2-1是一个图表示的实例，其中最左边是一个无向无权图，中间是该图的邻接矩阵，最右边是该图的邻接表。图2-1图表示的实例
兰州大学硕士学位论文复杂网络节点影响力度量与影响力最大化研究15出值是种子集合。算法1：GeneralGreedy算法Input：(,),Output:1.Initialize=2.for=1todo:3.select=argmaxv{(∪{})()|∈\}4.=∪{}5.endfor6.returnS（2）CELF算法GeneralGreedy算法在每次筛选种子节点时，都必须重新计算网络中每个非种子节点能带来的影响力收益，而每次计算节点的影响力收益时又需要进行大量的蒙特卡洛模拟实验，这无疑大大增加了时间复杂度。Leskovec等人[48]利用影响力函数的子模性在GeneralGreedy算法的基础上提出了CELF算法，它通过减少需要进行蒙特卡洛模拟的节点数量来降低算法的时间复杂度。图2-2CELF算法的计算过程CELF算法的详细过程如下：首先计算网络中所有节点的影响力，将影响力最大的节点选为种子节点，在下次选取种子节点时，利用函数的子模性，只计算当前影响力增益最大的节点的新影响力增益，若比之前增益次大的节点的影响力增益值大，则将其加入到种子集合中，否则将重新计算所有非种子节点的影响力增益，重复上述过程直至选出个种子节点为止。图2-2是CELF算法的一个计算实例，首先计算网络中所有节点的影响力增益并按序存储，此时增益最大的是节点A，将节点A加入种子集合，再进行第二轮种子节点选择，计算当前增益最大的节点B的新影响力增益，若大于之前增益次大的节点C的增益10，则将B加入到种子集合中，不需要再计算节点C、D、E、F的影响力增益，这是因为影响力函数的子模性，这些节点在这一轮的新增益必定小于上一轮的增益，故直接
本文编号：3008940
【文章来源】：兰州大学甘肃省 211工程院校 985工程院校 教育部直属院校
【文章页数】：69 页
【学位级别】：硕士
【部分图文】：
航空网络示意图
兰州大学硕士学位论文复杂网络节点影响力度量与影响力最大化研究9第二章复杂网络相关理论知识本章将详细介绍复杂网络研究必备的基础理论及本文后面章节涉及到的相关知识，包括网络的表示形式、网络的基本拓扑性质、节点影响力度量的常用方法、影响力最大化问题的定义和常用算法、经典的传播模型等。2.1网络基础理论概述2.1.1网络的图表示图是复杂网络的常用表示工具，它提供了一种用点和线来抽象地描述各种真实网络的规范化方法。网络可抽象为图=(,)，其中是节点的集合，是连边的集合，节点总数为=||，边的总数为=||。除此之外，节点间的连边分为不同的情况，即连边是否有方向和是否具有表示连接强度的权值，并据此将图分为四类：连边无方向无权值的无向无权图、连边无方向有权值的无向有权图、连边有方向无权值的有向无权图、连边有方向有权值的有向有权图。在图论中，通常用来描述图的结构有邻接矩阵和邻接表。图的邻接矩阵表示形式如下：图的邻接矩阵*()ijNNA=a是一个的方阵，若节点到节点之间存在有向连边，则在该矩阵的第行第列填上1或者权值；若它们之间存在无向连边，则在第行第列和第行第列分别填上1或者权值；若没有连边则填上0。实际上，大规模复杂网络中节点之间的连边一般是很稀疏的，这意味着与之对应的邻接矩阵中大多数元素是0，用这种方式存储稀疏图既浪费了存储空间又降低了利用率，故对于稀疏的无权图，还有另外一种表示方式——邻接表，它为每个节点创建一个单链表，链表中的元素即是与该节点直接相连的其他节点。图2-1是一个图表示的实例，其中最左边是一个无向无权图，中间是该图的邻接矩阵，最右边是该图的邻接表。图2-1图表示的实例
兰州大学硕士学位论文复杂网络节点影响力度量与影响力最大化研究15出值是种子集合。算法1：GeneralGreedy算法Input：(,),Output:1.Initialize=2.for=1todo:3.select=argmaxv{(∪{})()|∈\}4.=∪{}5.endfor6.returnS（2）CELF算法GeneralGreedy算法在每次筛选种子节点时，都必须重新计算网络中每个非种子节点能带来的影响力收益，而每次计算节点的影响力收益时又需要进行大量的蒙特卡洛模拟实验，这无疑大大增加了时间复杂度。Leskovec等人[48]利用影响力函数的子模性在GeneralGreedy算法的基础上提出了CELF算法，它通过减少需要进行蒙特卡洛模拟的节点数量来降低算法的时间复杂度。图2-2CELF算法的计算过程CELF算法的详细过程如下：首先计算网络中所有节点的影响力，将影响力最大的节点选为种子节点，在下次选取种子节点时，利用函数的子模性，只计算当前影响力增益最大的节点的新影响力增益，若比之前增益次大的节点的影响力增益值大，则将其加入到种子集合中，否则将重新计算所有非种子节点的影响力增益，重复上述过程直至选出个种子节点为止。图2-2是CELF算法的一个计算实例，首先计算网络中所有节点的影响力增益并按序存储，此时增益最大的是节点A，将节点A加入种子集合，再进行第二轮种子节点选择，计算当前增益最大的节点B的新影响力增益，若大于之前增益次大的节点C的增益10，则将B加入到种子集合中，不需要再计算节点C、D、E、F的影响力增益，这是因为影响力函数的子模性，这些节点在这一轮的新增益必定小于上一轮的增益，故直接
本文编号：3008940
本文链接：https://www.wllwen.com/shoufeilunwen/benkebiyelunwen/3008940.html
