基于节点中心性和社区相似性的快速标签传播算法

为了减少标签传播算法(LPA)中不必要的更新、解决算法准确率低且稳定性差的问题,提出了基于节点中心性和社区相似性的快速标签传播算法(FNCS_LPA)。按照节点中心性度量对网络的节点从低到高进行排序后加入节点信息列表,利用节点信息列表来指导更新过程,提高社区发现的稳定性并避免不必要的更新;采取基于社区相似性的更新规则,提高了社区发现的准确率。在真实社会网络和LFR基准网络上进行实验:相比LPA和三种较好的LPA改进算法,FNCS_LPA在执行速度方面提升了几十倍,真实社会网络的模块度也相对较高,在社区结构比较模糊的LFR基准网络上的归一化互信息有明显的优势。实验结果表明FNCS_LPA在提高执行速度的基础上,提高了算法的稳定性和准确率。

基于马尔可夫相似性增强和网络嵌入的社区发现

社区结构普遍存在于自然界的各种复杂网络中,是网络结构的重要特征之一。社区发现算法可以识别网络中的有用信息,有助于分析网络的结构和功能,被广泛应用于社交网络、生物和医学等领域。文中针对目前基于局部相似性的复杂网络社区发现算法精确度不高的问题,提出了一种基于马尔可夫相似性增强和网络嵌入的社区发现算法。首先,受马尔可夫链思想启发,提出了一种马尔可夫相似性增强方法,通过对初始网络的马尔可夫迭代状态进行转移,来获取稳态的马尔可夫相似性增强矩阵,根据马尔可夫相似性指标对网络进行初始的社区划分。然后结合网络的拓扑结构和网络嵌入,提出了一种新的社区相似性指标,将初始社区结构中的小社区与其连接紧密的社区合并,得到网络社区结构。在7个真实网络和可变参数的人工网络上,通过与其他5个知名社区发现算法的比较,证明了所提算法具有良好的社区发现效果。

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community,LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWSOCD算法能够有效地发现带权无向图中的重叠社区。