大型网络中具有线性时间复杂度的影响最大化模型

发布时间：2021-08-29 07:56

　　影响最大化问题是社交网络和病毒传播领域的经典传播优化问题。它旨在从给定网络中寻找k个最优节点作为传播的初始点集合,使得传播结束后被影响的节点最多。影响最大化问题的实际应用广泛,如新产品或新理念的有效推广、病毒或灾害的有效控制、舆情预警以及社会安定的综合管理等。为了能更好地处理大型网络中的影响最大化问题,目前对该问题的研究主要集中在如何保证选取的节点集合不减少影响范围的前提下,尽可能提高选择种子节点的时间效率。针对目前具有线性时间复杂度的影响最大化算法还很少的现状,本文提出了两个具有线性时间复杂度的影响最大化模型:（1）基于多层邻居潜力和社区结构的线性时间复杂度模型和（2）基于节点邻域和迭代寻优的线性时间复杂度模型。基于多层邻居潜力和社区结构的线性时间复杂度模型充分利用了社区间连接稀疏,社区内连接紧密的特性,并假设后续被激活节点的影响力被限制在其社区内部。该模型假设传播分为两个阶段:第一阶段为传播初期种子,节点在不同社区间的扩张,即允许跨社区传播;第二阶段为已激活节点在社区内部的独立传播,即不同社区间不再相互传播。基于上述假设,本文推导出具有次模特性的目标函数并给出了具有线性时间复杂度的... 

【文章来源】：重庆大学重庆市 211工程院校 985工程院校 教育部直属院校

【文章页数】：60 页

【学位级别】：硕士

【部分图文】：

加权有向图

学位论文 一定存在边j iu u。无权意味着边的权值都相等，通常假，例图 2.4无向图向图，由于是无向图，所以边是没有方向的，即是对称的以边的权值都相等，例图 2.5。

10图 2.4 无权有向图Fig. 2.4 Unweighted directed graph这几种类型的图，我们也可以得到加权有向图、加权无向图间的相互转化关系，如图 2.6。加权有向图其实化处理得到，加权无向图是由加权有向图边的对称化


本文编号：3370233