考虑边聚类与扩散特性的信息传播网络结构优化算法

优化网络结构以促进信息在网络中传播一直是复杂网络研究的重点,网络中边的聚类特性和扩散特性对信息传播具有重要作用. K-truss分解算法是一种利用边的聚类特性识别网络关键节点的算法,然而K-truss算法会受到网络中局部聚类结果 (即相互连接的假核结构)的影响,而这些假核结构里的节点对信息扩散能力通常较弱.为此,本文提出一种衡量边扩散特性的指标,研究发现一些位于网络边缘的边具有很好的扩散性,但这类边的聚类很低,并不利于信息传播.通过同时考虑边的聚类特性和扩散特性之间的制约关系,提出一种信息传播网络结构优化算法.为了验证所提算法的有效性,使用该算法对四个真实的网络进行结构优化,并使用经典的独立级联模型来验证网络结构优化前后信息传播的有效范围.结果表明:使用提出的算法优化后的网络拓扑可以有效提高信息传播范围;并且,优化后的网络其叶子节点数目降低、聚类系数降低以及平均路径长度降低.

Network structure optimization algorithm for information propagation considering edge clustering and diffusion characteristics

Optimizing network structure to promote information propagation has been a key issue in the research field of complex network, and both clustering and diffusion characteristics of edges in a network play a very important role in information propagation. K-truss decomposition is an algorithm for identifying the most influential nodes in the network. We find that K-truss decomposition only considers edge clustering characteristics, without considering the diffusion characteristics, so it is easily affected by the local clustering structure in the network, such as core-like groups. There are mutually closely connected the core-like groups in the network, but the correlation between the core-like groups and the other parts of the network is less, so the information is easy to spread in the core-like groups, but not in the other parts of the network, nor over the whole network. For the reason, we propose an index to measure the edge diffusion characteristics in a network, and it is found that the diffusion characteristics of some edges in the periphery of the network are relatively high, but the clustering characteristics of these edges are relatively low, so they are not beneficial for rapid information propagation. In this paper, by considering the relationship between the clustering characteristics and diffusion characteristics of the edges, we propose a novel network structure optimization algorithm for information propagation. By measuring the comprehensive ability strength of the clustering characteristics and the diffusion characteristics of the edges, we can filter out the edges whose comprehensive ability is poor in the network, then determine whether the edges should be optimized according to the relative relationship between the clustering characteristics and the diffusion characteristics of the edges. To prove the effectiveness of the proposed algorithm, it is carried out to optimize the structures of four real networks, and verify the effective range of information propagation before and after the optimization of network structure from the classical independent cascade model. The results show that the network topology optimized by the proposed algorithm can effectively increase the range of information propagation. Moreover, the number of leaf nodes in the optimized network is reduced, and the clustering coefficient and the average path length are also reduced.