基于种子候选的贪心策略影响力最大化算法

爬山贪心算法的时间复杂度较高,不易扩展至大规模社会网络.为了解决此问题,文中从理论上分析节点集影响力评估可转化为局部概率解计算,能够提高算法运行效率.将局部概率解函数拓展到贪心算法中,提出基于种子候选的贪心影响力最大化算法和基于种子候选的偷懒贪心影响力最大化算法.在4个真实数据集上实验表明,文中算法与具有成本效益的惰性前向选择算法(CELF)性能一致,但在运行时间上快于CELF.     

基于反向可达集的影响力最大化算法

现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限,不适用于大规模社交网络。基于独立级联模型,结合反向可达集采样提出一种改进的影响力最大化算法D-RIS。在影响力传播函数满足单调性和子模性的前提下,通过自动调试确定反向可达集生成数量的临界值。在Slashdot和Epinions真实数据集上的实验结果表明,D-RIS算法在影响力传播范围上接近CELF算法且优于RIS、HighDegree、LIR和pBmH启发式算法,同时在运行时间上相比CELF算法减少近百倍,具有更好的通用性与稳定性,适用于拓扑结构变化和规模较大的社交网络。     

基于反向PageRank的影响力最大化算法

针对社会网络上的影响力最大化算法在大规模网络上难以同时满足传播范围、时间效率和空间效率要求的问题,提出一种混合PageRank和度中心性的启发式算法（MPRD）。首先,基于PageRank,引入一种反向PageRank思想来评估节点影响力;然后,结合局部指标度中心性,设计一种混合的指标来评估节点的最终影响力;最后,通过相似性方法去掉影响力重合严重的节点,选出种子节点集。在6个数据集和两种传播模型上进行实验,实验结果表明,所提的MPRD在传播范围上优于现有的启发式算法,在时间效率上比贪心算法快四、五个数量级,在空间效率上优于基于反向抽样的IMM算法。所提的MPRD在处理大规模网络上的影响力最大化问题时能够取得传播范围、时间效率和空间效率的平衡。     

基于MRLT模型多关系社交网络影响力最大化研究

社交网络影响力最大化问题是基于特定的传播模型,在网络中寻找一组初始传播节点集合,通过其产生最终传播影响范围最大的一种最优化问题。已有的相关研究大多只是针对单关系社交网络,即在社交网络中只存在一种关系。但在现实中,社交网络的用户之间往往存在着多种关系,并且这多种关系共同影响着网络信息传播及其最终影响范围。在线性阈值模型的基础上,结合网络节点间存在的多种关系,提出MRLT传播模型来建模节点间的影响力传播过程,在此基础上提出基于反向可达集的MR-RRset算法,解决了传统影响力最大化问题研究过程中由于使用贪心算法所导致的计算性能较低的问题。最后通过在真实数据集上的实验对比,表明所提方法具有更好的影响力传播范围及较大的计算性能提升。     

基于熵权TOPSIS的社会网络影响力最大化研究

在影响力最大化问题中,针对启发式方法精度不足和贪婪方法时间过载的问题,提出一种基于多属性决策方法的影响力最大化算法.首先,从社会网络节点的影响传播、节点之间的影响重叠和节点的信任度角度选取节点的重要性评价指标.然后,建立基于熵权TOPSIS的社会网络节点重要性评价模型,通过模型选择影响范围最广、与当前种子集的重叠最小且信任度最高的节点.最后,构建算法,并通过实验验证算法的性能.实验结果表明,与传统影响力最大化算法相比,所提算法在传播范围与时间效率上取得了较好的折中.     

基于信息偏好的影响最大化算法研究

实证研究表明,社会个体对于不同主题的信息有着不同的偏好,这对于社会网络中的信息传播过程起着非常重要的作用.影响最大化是社会网络信息传播领域中关于影响结点集挖掘的热点课题.它会从社会网络中寻找最具影响力的结点子集,以这些结点为目标进行影响传播时会获得最大的影响范围.以前关于影响最大化算法研究的大部分工作没有考虑社会个体的信息偏好,这大大降低了结果的准确性.为了提高影响最大化算法的效率和种子集的影响范围,提出一种基于信息偏好的2阶段启发式影响结点挖掘策略L_GAUP:第1阶段,基于网络中各结点对于信息主题的偏好程度,得到易感染结点网络;第2阶段,在易感染网络中,基于贪心策略进行影响结点的挖掘.实验中,在数据集douban上实现了L_GAUP,GAUP和CELF算法.实验结果表明,与基准算法GAUP相比,L_GAUP不仅在影响范围指标ISST和IS上有着更好的表现,在效率上也有大幅度的提高.     

融合节点覆盖范围和结构洞的影响力最大化算法

影响力最大化是社交网络分析中的一个重要问题,旨在挖掘可以使得信息在网络中传播范围最大化的一小组节点（通常称为种子节点）。基于网络拓扑结构的启发式影响力最大化算法通常仅考虑某单一的网络中心性,没有综合考虑节点特性和网络拓扑结构,导致其效果受网络结构的影响较大。为了解决上述问题,提出了一种融合覆盖范围和结构洞的影响力最大化算法NCSH。该算法首先计算所有节点的覆盖范围和网格约束系数;然后通过覆盖范围增益最大原则选择种子节点;其次,若存在多个节点增益相同,则按照网格约束系数最小原则选取;最后,重复上述步骤直至选出所有种子节点。NCSH在不同种子数量和不同传播概率条件下,在六个真实网络数据集上均保持着优异的效果,在影响力传播范围方面,比同类的基于节点覆盖范围的算法（NCA）平均提高了3.8%;在时间消耗方面,比同类的基于结构洞和度折扣的最大化算法（SHDD）减少了43%。实验结果表明,NCSH能有效解决影响力最大化问题。     

社会网中时间最优的利润最大化算法研究

影响最大化问题是在社会网上寻找最具影响力的种集。目前的研究工作忽略了影响传播最大化和利润最大化的区别,以及影响范围会随着时间的推移趋于平稳。考虑用户动作日志,提出了基于时间长度的影响力分配模型IVA-T(influence value allocation-T),在此基础上首次提出了时间最优的利润最大化问题(timeoptimal profit maximization,OTPM),并证明了该问题为NP-hard问题。为求解OTPM问题,提出了一个有效的近似算法Profit-Max,并证明了Profit-Max算法的近似比。多个真实数据集上的实验结果表明,该算法可以有效并高效地解决OTPM问题。     

基于演化深度强化学习的符号网络影响最大化研究

近年来,随着互联网信息传播以及新型冠状病毒COVID-19传播链阻断等重大应用问题的出现,社会网络影响最大化问题的研究受到了科学界广泛关注.影响最大化问题旨在根据特定应用问题的传播模型,识别出最优影响种子节点集,最大化其信息传播影响.现有影响最大化算法主要针对单连接影响传播模型,将影响最大化问题模拟为离散的影响力种子节点组合选取优化问题.然而,这些算法具有较高的计算时间复杂度,且无法解决具有大规模冲突关系的符号网络影响最大化问题.针对上述问题,首先,构建适用于符号网络的正负影响传播模型以及影响最大化优化模型.其次,通过引入由神经网络构成的deep Q network来选取种子节点集,将离散的种子节点组合选取问题转化为更易优化的网络权重连续优化问题.最后,提出基于演化深度强化学习的符号网络影响最大化算法SEDRL-IM.该算法将演化算法的个体视作策略,结合演化算法的无梯度全局搜索以及强化学习的局部搜索特性,实现对deep Q network权重优化问题解的有效搜索,从而找到最优影响种子节点集.在基准符号网络以及真实社交网络数据集上的大量实验结果表明,所提算法在影响传播范围与求解效率上都优...     

基于重叠社区搜索的传播热点选择方法

随着社交网络的蓬勃发展,信息传播问题由于具有广泛的应用前景而受到广泛关注,影响力最大化问题是信息传播中的一个研究热点.它致力于在信息传播过程开始之前选取能够使预期影响力达到最大的节点作为信息传播的初始节点,并且多采用基于概率的模型,如独立级联模型等.然而,现有的影响力最大化解决方案大多认为信息传播过程是自动的,忽略了社交网站平台在信息传播过程中可以起到的作用.此外,基于概率的模型存在一些问题,如无法保障信息的有效传播、无法适应动态变化的网络结构等等.因此,本文提出了一种基于重叠社区搜索的传播热点选择方法,该方法通过迭代式推广模型根据用户行为反馈逐步选择影响力最大化节点,使社交网站平台在信息传播过程中充分发挥控制作用,并提出一种新型的基于重叠社区结构的方法来衡量节点影响力,根据这种衡量方式来选择传播热点.本文提出了解决该问题的两种精确算法,包括一种基本方法和一种优化方法,以及该问题的近似算法.并通过大量实验验证了精确及近似算法的效率和近似算法的准确率以及迭代式传播热点选择方法的有效性.     

随机竞争策略在Monte Carlo算法中的性能分析

随机算法在组合优化问题中具有广泛的应用,Ｌａｓ Ｖｅｇａｓ算法和Ｍｏｎｔｅ Ｃａｒｌｏ算法是主要的两类随机算法,随机算法的性能和稳定性常常得不到保证,以往的研究针对Ｌａｓ Ｖｅｇａｓ算法提出了一种有效的性能改进策略－随机竞争策略,但其在Ｍｏｎｔｅ Ｃａｒｌｏ算法中的准确尚未被研究。文中研究了随机竞争策略对Ｍｏｎｔｅ Ｃａｒｌｏ算法性能和稳定性的影响,分析了使其效率大于１的条件,在求解ＴＳＰ问题时的     

磨矿破碎过程粒度分布的分布式参数蒙特卡洛动力学模拟及加速方法

本文针对磨矿破碎过程,提出一种分布式参数蒙特卡洛动力学方法的粒度分布预测模型和模拟算法.该算法采用了分段思想,将磨机沿着轴向分为若干个虚拟的子磨机;根据破裂、前向和后向移动三类微观事件定义了倾向函数和系统状态矩阵,并设计了分布式算法的调度策略.此外,针对蒙特卡洛动力学算法效率低的问题,提出了基于τ-leap的磨矿过程分布式参数蒙特卡洛模拟加速算法.为了解决分布式参数更新过程中状态不一致的问题,创新性地提出了一种基于缓冲区的同步方法.通过对仿真案例的分析表明,本文提出的分布式参数蒙特卡洛动力学算法具有较高的精度,提出的基于τ-leap的加速算法能够显著提高计算效率,同时保持较好的精度.     

Scalable influence maximization for independent cascade model in large-scale social networks

Influence maximization, defined by Kempe et al. (SIGKDD 2003), is the problem of finding a small set of seed nodes in a social network that maximizes the spread of influence under certain influence cascade models. The scalability of influence maximization is a key factor for enabling prevalent viral marketing in large-scale online social networks. Prior solutions, such as the greedy algorithm of Kempe et al. (SIGKDD 2003) and its improvements are slow and not scalable, while other heuristic algorithms do not provide consistently good performance on influence spreads. In this article, we design a new heuristic algorithm that is easily scalable to millions of nodes and edges in our experiments. Our algorithm has a simple tunable parameter for users to control the balance between the running time and the influence spread of the algorithm. Our results from extensive simulations on several real-world and synthetic networks demonstrate that our algorithm is currently the best scalable solution to the influence maximization problem: (a) our algorithm scales beyond million-sized graphs where the greedy algorithm becomes infeasible, and (b) in all size ranges, our algorithm performs consistently well in influence spread—it is always among the best algorithms, and in most cases it significantly outperforms all other scalable heuristics to as much as 100–260% increase in influence spread.     

A probabilistic solution discovery algorithm for solving 0-1 knapsack problem

Abstract

In this paper, a probabilistic solution discovery algorithm is developed to solve the NP-hard 0-1 knapsack problem. The proposed method consists of three steps: strategy development, strategy analysis, and solution discovery. In the first step, Monte Carlo simulation is used to generate the strategies based on a vector defining the probability that each item is included in the knapsack. In the second step, we analyse the capacity imposed by each strategy previously generated and penalise the objective value for those strategies exceeding the capacity of the knapsack. At the last step, a subset of ordered strategies is used to update the vector that defines the probability of choosing each item. Two numerical examples are used to demonstrate the efficiency and the performance of the proposed method.     

A bi-objective approach for shortest-path network interdiction

In the literature, solution approaches to the shortest-path network interdiction problem have been developed for optimizing a single figure-of-merit of the network configuration when considering limited amount of resources available to interdict network links. This paper presents a newly developed evolutionary algorithm that allows approximating the optimal Pareto set of network interdiction strategies when considering bi-objective shortest path problems. Thus, the paper considers the concurrent optimization of two objectives: (1) maximization of shortest-path length and (2) minimization of interdiction strategy cost. Also, the paper considers the transformation of the first objective into the minimization of the most reliable path reliability. To solve these multi-objective optimization problems, an evolutionary algorithm has been developed. This algorithm is based on Monte Carlo simulation, to generate potential network interdiction strategies, graph theory to analyze strategies’ shortest path or most reliable path and, an evolutionary search driven by the probability that a link will appear in the optimal Pareto set. Examples for different sizes of networks and network behavior are used throughout the paper to illustrate and validate the approach.     

在线影响力最大化研究综述

影响力最大化是指在给定的影响力传播模型下选取种子节点使其传播信息范围最广。此问题的应用场景十分广泛,包括推荐系统、病毒营销、信息扩散和链接预测等。在实际应用中,信息传播模型中的点对点传播概率通常是未知的,而在线学习算法可以在交互过程中自主学习未知参数,逐步逼近最优解。文中首先讨论了影响力最大化问题的定义,介绍了常用的影响力传播模型,归纳了常见的离线影响力最大化算法;随后介绍了经典的在线学习框架——多臂老虎机问题,分析了在线影响力最大化问题的研究现状,并通过实验对常见的在线影响力最大化算法在真实社交网络中的性能表现进行对比;最后总结了该课题面临的挑战并展望了未来的研究方向。     

变质品生产、库存控制与预防维修联合建模与优化

针对产品变质带来库存损耗的问题,在经济生产批量模型的基础上加入零库存时间,提出新的库存控制策略.该策略以预防维修周期和零库存时间为联合决策变量,利用更新定理建立了单位时间内总成本的期望模型.为了提高对此期望的计算速度,设计基于矩阵运算的蒙特卡罗仿真算法,并与遗传算法结合,大大提高了模型的优化速度.通过比较研究,验证了仿真算法的显著优势,并通过敏感性分析明确了相关参数的变化对最优策略的影响.     

Maximizing three-hop influence spread in social networks using discrete comprehensive learning artificial bee colony optimizer

Aiming at resolving the influence maximization (IM) problem in social networks, this paper proposes a three-layer-comprehensive-influence evaluation (TLCIE) model to measure the spread range of combinational nodes in the independent or weighted cascade models. The TLCIE is an enhanced three-hop influence spread model by integrating the intra- and inter-layer’s propagation effect, which improves the accuracy of propagation simulation and the reliability of parameter estimation. Then, an adaptive discrete artificial bee colony algorithm (ADABC) is devised to resolve the TLCIE model efficiently. In ADABC, the comprehensive-learning guided (CLG) updating rules, the degree-improvement initialization method and the semi-abandonment scout bee strategy are incorporated to enhance the search ability. Finally, the proposed model and algorithm are tested on a set of real-world social network instances, and the experimental results validate their effectiveness and efficiency.