考虑用户意愿的符号网络净积极影响力最大化问题

影响力最大化是近年来广泛研究的社交网络的核心问题.然而之前的研究较少考虑用户的意愿以及用户之间的友好或敌对关系.因此综合考虑这些因素,针对符号网络提出了考虑用户意愿的净积极影响力最大化问题,该问题可以描述如下：利用符号网络来刻画用户具有友好(积极)和敌对(消极)关系的社交网络,每个用户对传播的信息有自己的意愿,目标是要从网络中选择k个用户,使得最终的净积极影响的用户数量最多.通过对问题的细致分析,建立了考虑用户意愿的传播模型,证明了该模型下净积极影响力最大化问题是非次模和非单调的,随后给出了基于概率驱动的结构感知的求解算法,通过在三个数据集上的实验表明,利用提出的算法找到的种子集有更好的净积极影响力.     

基于启发式和贪心策略的社交网络影响最大化算法

为解决传统影响力最大化算法在影响范围和运行时间上存在的不平衡问题,提出了一种综合启发式和贪心算法的社交网络影响力最大化算法(MHG).该算法综合考虑了贪心算法和启发式算法的优势,将种子节点的选择分为2个阶段,即通过启发式算法选出候选种子节点集和使用贪心算法从候选种子节点集中筛选出种子节点集合.结果表明,与现有的启发式算法相比,MHG算法在影响范围上具有显著优势,且接近贪心算法,但其运行时间明显少于贪心算法,因而在效果和时间2个方面取得了较好的平衡.在真实数据集及不同传播模型下,MHG算法均表现出稳定的影响范围,体现了该算法在大规模社会网络处理中的可扩展性.     

基于集合覆盖的异构有向传感网寿命优化策略

在由感知半径、感知角度和携带能量不同的有向传感器节点组成的异构有向传感器网络中,对满足优先级不同的监测目标有不同覆盖要求条件下的网络寿命最大化问题进行研究。利用集合覆盖的思想,将有向传感器节点划分为满足目标覆盖要求的集合,通过集合之间的切换来达到延长网络寿命的目的。首先证明本文问题是NP-hard问题,然后利用改进的和声搜索算法进行求解,一方面引入带有混沌参数的微分变异因子,改进种群的多样性;另一方面,与模拟退火算法结合增强算法的局部搜索能力。同时为对比算法性能,提出一种贪婪算法。仿真结果显示:较之原始和声搜索算法和贪婪算法,改进和声搜索算法能有效延长网络的寿命,证明了改进算法的有效性。     

基于关键节点的影响力最大化算法

为解决LDAG( DAG Algorithm Based on Linear Threshold) 算法在处理关于社会网络影响力最大化过程中,优先考虑网络影响力传播模型、忽视社会网络的拓扑结构问题,利用社交网络社区的结构,有针对性地选择影响力传播的关键节点,对LDAG 算法进行了改进。利用关键节点简化了有向无环图的构造过程,保证了其高精度与运行效率高的特点,同时也优化了算法的时间复杂度和空间复杂度。通过两个有效的实验数据集对算法进行验证,结果表明改进的算法可以大幅度降低算法的运行时间,且对算法的精度影响很小。     

一种社交网络用户领导者挖掘算法

社交网络中的用户领导者挖掘是用户影响力分析的重要问题.提出一种基于用户影响力评估的社交网络用户领导者挖掘算法.首先,描述问题模型以及模型相关定义;其次,提出了基于用户影响力和用户活跃度计算的用户领导力评估方法;最后,依据用户领导力和用户中心度计算实现用户领导者的挖掘.实验印证了该方法对于社交网络挖掘用户领导者的可行性和有效性.     

求解组合拍卖问题最大值的贪婪算法

为有效解决组合拍卖问题,从基约束条件下,下模函数最大值问题的基本结论出发,逐步过渡到求解组合拍卖问题的贪婪算法,给出一种新的近似算法,分析了该算法的性能保证.该算法是一种改进的贪婪算法,即将部分穷举法与贪婪算法结合,从而使其具有更好的性能保证,并从理论上证明了该算法的可靠性和有效性.     

在线社交网络用户分析研究综述

在对国内外在线社交网络用户分析相关研究归纳总结的基础上,综述了在线社交网络用户分析的最新进展,主要包括通过用户影响力和用户偏好进行用户行为分析、采用隐式和显式的分类方法对用户属性预测算法进行综述,简述了基于用户属性特征或(和)用户关系拓扑结构的用户分类研究进展,并分析了动态社交网络、并行算法及社交用户语义信息给在线社交网络用户分析所带来的机遇和挑战,对该研究方向上的发展趋势进行了展望.     

基于贪婪搜索和变异操作的布谷鸟算法

作为一种新型的生物启发式群体智能算法,布谷鸟算法模拟了布谷鸟生育雏鸟以及鸟类的Levy flights行为,是一种全局最优搜索算法,为了更好地提高算法对不同问题的适应能力,提出一种基于贪婪搜索和变异操作的布谷鸟(GMCS)算法.根据最优位置设计一种贪婪搜索策略,贪婪搜索策略和Levy flights随机游动搜索策略按概率交替进行,加强算法的局部探索能力;引入差分进化算法中的变异操作,提高算法跳出局部最优的能力;加入一个新的参数,根据收敛状态自适应地调整参数阈值以控制贪婪搜索策略和变异操作的执行次数.通过8个标准测试函数进行数值实验,实验结果表明,与部分改进的布谷鸟算法以及一些其他改进的演化算法相比,GMCS算法具有较好的收敛性能和适应能力,验证了改进后算法的有效性.     

资源受限最小赋权树形图的一种贪婪分解启发式算法

资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.     

一种多QoS约束的网格资源调度算法

针对网格计算中资源调度问题,提出一种多QoS（Quality of Service）约束的贪婪推广算法.调度时以调度驱动函数为贪婪准则.调度驱动函数与网格用户提供的“deadline”,“budget”,“timeweight”和“costweight”等参数有关.每次根据调度驱动函数选择最经济的资源进行调度.通过在Gridsim环境下的分析与比较,该算法能够在满足用户QoS的同时,能够以最小的调度驱动函数值完成任务,最大化地实现用户的满意度.     

一种基于社会势能的网络影响力最大化算法

社会网络影响力最大化问题是对于给定k值,寻找k个具有最大影响范围的节点集.这是一个优化问题并且是NP-完全的.该问题已经被成功地用于解决诸多实际问题,例如社交营销领域,社交广告策略制定等优化问题.文章介绍了社会网络影响力最大化的基本工作原理,从提取知识类型角度详细阐述了社会网络影响力最大化算法的研究现状和进展,鉴于现存的算法不能够有效地给出全局最优解,我们提出了一种基于社会势能的网络影响力最大化算法,利用实验结果揭示算法的有效性和可行性.     

Flash媒体服务器的优化部署

越来越多的新型万维网(Web)应用开始提供在线音视频交流功能,而有效的Flash媒体服务器部署方案是提高服务质量的基础。该文给出了媒体服务器优化部署问题的数学模型,并证明即使用户需求和网络性能信息已知,求解最优部署方案仍然是NP-hard问题。提出了优化部署方案的贪婪算法和分别基于重要程度和拓扑特征的启发式算法,分析了它们的优缺点和复杂度。基于互联网的真实拓扑的实验表明:该几种算法的效果都明显优于随机部署,而贪婪算法和基于重要程度的启发式算法甚至能在有效节省成本的前提下,接近全局部署的效果。     

引入信任度传递机制的影响力最大化节点挖掘

基于渗流理论的影响力最大化节点识别问题没有考虑信任度传播对影响力最大化的影响。利用非回退矩阵图模型,通过引入节点信任度传递函数刻画影响力传播过程中"信任度递减,不信任度递增"现象,并利用渗流理论求解节点联合传播强度指数来刻画节点影响力大小,采用人工网络数据与真实网络数据集对算法的影响力进行了评估分析,与常用启发式算法进行比较验证算法性能,本文算法性能优于其他启发式基准算法。     

社交网络中求最小正影响支配集的改进算法

网络中求解最小正影响支配集的问题已经被证明是NP难问题,且已有性能较好的贪心求解算法．通过分析现有的贪心近似算法（Wang-Greedy）和贪心启发式算法(Raei-Greedy),融合其贪心策略,提出了1个改进的贪心近似算法(Hybrid-Greedy)．理论分析表明,Hybrid-Greedy仍保持Wang-Greedy的近似比性能和时间复杂度．在一些较大规模的真实社交网络实例中的实验研究表明,Hybrid-Greedy在这些社交网络中所得解的质量较Wang-Greedy和Raei-Greedy有明显提高．     

预算型最大覆盖问题的近似算法

研究了给定预算常数的最大覆盖问题,给出了求解此问题的改进贪婪算法,得到了性能保证为1-e-1的近似算法.     

基于边际性价比的收益影响力最大化算法

传统的影响力最大化算法忽视了病毒式营销过程中的商业收益问题.?现实营销中,商家更加关注如何使用一个固定预算,在合理的时间内选出种子集,最大化营销收益.?为了解决这个问题,提出一种高效的启发式算法.?首先,定义边际性价比衡量用户节点的重要性;其次,分析出贪心算法的节点选取结果为一个自洽序列,提出MCPR(Marginal...     

CIC模型下基于社区检测的谣言抑制最大化方法

随着电子设备的日益普及和信息扩散的便利性,在线社交网络为各种负面信息的传播提供了高效的媒介.谣言是社交媒体上负面信息的突出形式之一,会引发社会动荡,造成经济损失,因此,快速有效地抑制谣言传播成为当前社交网络研究领域中的一个热点.提出一种有效的谣言抑制传播方法,从网络中选取多个正种子节点来传播真相,抑制谣言的传播.首先采用竞争性独立级联（Conpetitive Independent Cascade,CIC）模型来同时传播谣言和真相;其次,提出一种基于标签传播的社区检测算法对社交网络进行分解,并为各个社区分配正种子节点预算;最后,创新地提出节点强度来衡量网络中节点的重要性,并利用节点强度在各个社区中选取抑制谣言传播的初始正种子集.实验证明,该方法能达到与贪婪算法相匹配的抑制效果,且运行时间比贪婪算法快三个数量级.     

求解组合拍卖问题的一种贪婪算法

为有效解决组合拍卖问题,从下模集函数最大值问题的基本结论出发,将部分穷举法与贪婪算法相结合,给出了一种求解组合拍卖问题的新算法一改进的贪婪算法,并从理论上证明了所给算法具有更好的性能保证.     

基于概率与贪婪算法的商品在线租赁业务模型及应用

针对网络在线租赁这一新型业务,根据概率与贪婪算法的思想,对在线租赁业务的两个主要问题：商品储备量的最小化和客户满意度的最大化,进行了分析并建立模型求解．并对算法模型进行了求解实证．     

基于竞争性SIR模型的电力社会耦合网络谣言影响研究

为研究智能电网与在线社交网络耦合过程中,智能电网面对来自在线社交网络中谣言电价传播威胁问题,基于SIR模型分析谣言传播与控制的优势,构建了基于SIR模型的竞争性谣言与辟谣信息传播模型来表征在线社交网络中的谣言传播与控制过程来研究受谣言影响用户集合,接着以Louvain算法思想将在线社交网络用户社区化建模出电力网与在线社交网“部分一对多”耦合网络,针对所构建的模型设计了一种考虑不同用电群体的受影响用户负荷变化,对电力系统负荷变化的影响方法;进一步在IEEE30节点系统与Facebook在线社交网络构造的耦合网络中,得出不同的辟谣信息的开始传播时间、种子节点数量等因素在谣言传播情况下对电力系统负荷变化以及输电线路线路过载风险率的都具有显著影响.