复杂网络算法中K-shell与介数中心性算法的实现

复杂网络中实现节点的中心性有许多算法,这些算法可以让人们快速识别出各种社交环境中的核心人物与话题。常用的中心性指标有度中心性,介数中心性、紧密中心性、特征向量中心性和K-shell分解方法。但是现有的理论中,仅仅提及算法的概念,并且实现的复杂性过高,算法的提及更多是用于分析阶段。为了解决这个问题,主要提出介数中心性指标和K-shell分解方法的程序实现,以便更好地应用于各种场合。

一种基于K-shell和半局部信息的节点重要性排序方法

对复杂网络中的节点按照其重要性进行排序不仅具有重要的理论研究意义而且具有广泛的实际应用价值。传统的K-shell分解方法虽然具有较好的排序结果,但仍然具有排序结果分辨率不高的缺陷,针对这一问题,对传统的K-shell分解方法进行改进,并综合节点的半局部信息,进一步区分节点的重要性。在三个不同的显示网络中的实验表明,该方法能够有效解决传统方法的缺陷,提高排序结果分辨率。

基于标签传播能力的改进LPA算法

随着网络规模的不断增大,在时间复杂度上具有明显优势的标签传播算法受到广泛关注,但是其内在机制存在不确定性和随机性,导致社团发现结果不够准确和稳定。为此,提出一种新的改进标签传播算法。在K-shell分解算法的基础上,构造节点重要性计算方法,利用节点重要性分析标签传播算法中的标签传播能力,通过节点重要性排序和标签传播能力制定新的标签更新策略,得出最终的社团划分结果。在人工网络和真实网络上的实验结果表明,该算法有较高的准确性和稳定性。