复杂网络中重要节点挖掘的算法研究与设计

• 作 者: 郭春谷
• 出 处: 电子科技大学
• 发表日期: 2020年01期
• 关键词: 复杂网络 重要节点组 概率传播 信息熵 影响力最大化

复杂的系统通常由大量相互联系的组件所构成,这些复杂的系统往往可以通过网络对系统进行描述。在数学和计算机科学的视角中,复杂网络是描述庞大而复杂的现实世界的系统图数据结构。在不同系统中,各个组成成分扮演着不同的角色,在不同任务和场景中发挥着不同的作用,对系统而言有着不同的重要性。寻找复杂系统中的重要节点,吸引了越来越多的计算机科学家和物理社会学家的关注。从对网络影响角度出发,重要节点一般被分为两类:KPP-POS（以优化传播为目标的关键节点）和KPP-NEG（以破坏网络结构为目标的关键节点）。KPP-POS指的是寻找一个或多个种子节点进行传播活动,使得最终传播的范围最大;KPP-NEG指的是寻找一个或多个节点,从网络中移除这些节点使得网络被破坏的程度最大化。本文主要针对KPP-POS问题进行研究,寻找网络中影响力最大的传播者。对于该问题,一般又分为单点排序问题和影响力最大化问题（Influence maximization problem,IMP）,本文重点在于研究如何寻找影响力最大的一组节点。对该问题的研究由早期简单地将重要性高的单个节点组合的贪心策略及其改进算法,慢慢演变到更复杂的启发式策略算法。本文根据现有的算法研究,从不同的角度提出了两种新颖的重要节点组挖掘算法。本文的研究内容及创新点如下:（1）本文提出了基于节点信息熵的启发式节点挖掘算法EnRenew,该算法以节点信息熵为衡量单个节点重要性的基础指标,然后借鉴VoteRank算法的选点策略并进行改进。EnRenew算法有很低的时间复杂度,能应用于大规模网络。此外通过SIR和SI传播模型的仿真实验,算法在真实网络数据中均表现出更大的传播规模。其中,在Hamster网络中,EnRenew算法相较于最优的对比算法其感染规模提升了31%,在CEnew网络中提升了17%。（2）本文提出的PPS_pro值是一种新颖的有效的节点组重要性的评估指标。本文对原始概率传播模型进行了改进,使其更接近SIR单点传播模型的传播过程。并将改进后的概率传播模型应用于多感染源的传播过程中,通过概率传播模型对节点组能够达到的感染范围的概率估计值PPS_pro,该值越大则说明节点组具有更大的影响力。（3）本文基于概率传播模型以及得到的PPS_pro值,将PPS_pro作为适应性函数,通过改进的遗传算法进行重要节点组挖掘,从而提出了SPGA算法。通过实验分析,在SIR和SI传播模型中,SPGA算法效果相对于对比算法在大多数网络中均有大幅度提升。尤其是小规模网络CEnew、Email和Hamster中,SPGA算法比最优的对比算法最终感染规模均高出20%以上。EnRenew算法相较于VoteRank算法而言,加强被选中节点邻居的重要性的削弱,从而使得所选邻居更加分散,提升算法效果。但是目前对被选中节点邻居影响力的削弱大多是启发式的人为设置,没有理论研究其最优取值,这将是未来启发式类算法的研究点之一。此外SPGA算法虽然效果提升明显,并且通过概率传播模型得到的PPS_pro值计算复杂度很低,但是遗传算法大量的搜索导致SPGA算法效率不高,如何优化此过程同样是未来关注的方向。