基于改进的局部结构熵复杂网络重要节点挖掘

Key node mining in complex network based on improved local structural entropy

识别复杂网络中的关键节点对优化网络结构以及信息的有效传播起着至关重要的作用。局部结构熵(LE)利用局部网络对整个网络的影响代替节点对整个网络的影响以识别重要节点,然而LE未考虑高聚集性网络和节点与邻居节点形成环的情况,存在一定的局限性。针对以上不足,首先,提出了改进LE的节点重要性评价方法PLE(Penalized Local structural Entropy),即在LE的基础上引入集聚系数(CC)作为惩罚项,从而适当惩罚网络中的高聚集性节点;其次,由于PLE的惩罚项对三元闭包结构上的节点惩罚力度过大,又提出了PLE的改进方法PLEA(Penalized Local structural Entropy Advancement),即在惩罚项前引入一个控制系数,以控制惩罚力度。对5个不同规模的真实网络进行选择性攻击实验,实验结果表明,在美国西部各州电网和美国航空网两个网络中,与LE方法相比,PLEA的识别准确率分别提升了26.3%和3.2%;与K-Shell(KS)方法相比,PLEA的识别准确率分别提升了380%和5.43%;与DCL(Degree and Clustering coefficient and Location)方法相比,PLEA的识别准确率分别提升了14.4%和24%。同时,PLEA识别的重要节点对网络造成的破坏更大,验证了引入CC作为惩罚项的合理性,以及PLEA的有效性和优越性。PLEA综合考虑了节点的邻居个数和节点的局部网络结构,计算简单,对于刻画大规模网络的可靠性与抗毁性具有十分重要的意义。

The identification of key nodes in complex network plays an important role in the optimization of network structure and effective propagation of information.Local structural Entropy(LE)can be used to identify key nodes by using the influence of the local network on the whole network instead of the influence of nodes on the whole network.However,the cases of the highly aggregative network and nodes forming a loop with neighbor nodes are not considered in LE,which leads to some limitations.To address these limitations,firstly,an improved LE based node importance evaluation method,namely PLE(Penalized Local structural Entropy),was proposed,in which based on the LE,the Clustering Coefficient(CC)was introduced as a penalty term to penalize the highly aggregative nodes in the network appropriately.Secondly,due to the fact that the penalty of PLE penalizing the nodes in triadic closure structure is too much,an improved method of PLE,namely PLEA(Penalized Local structural Entropy Advancement)was proposed,in which control coefficient was introduced in front of the penalty term to control the penalty strength.Selective attack experiments on five real networks with different sizes were conducted.Experimental results show that in the western US states grid and the US Airlines,PLEA has the identification accuracy improved by 26.3%and 3.2%compared with LE respectively,by 380%and 5.43%compared with K-Shell(KS)method respectively,and by 14.4%and 24%compared with DCL(Degree and Clustering coefficient and Location)method respectively.The key nodes identified by PLEA can cause more damage to the network,verifying the rationality of introducing the CC as a penalty term,and the effectiveness and superiority of PLEA.The integration of the number of neighbors and the local network structure of nodes with the simplicity of computation makes it more effective in describing the reliability and invulnerability of large-scale networks.