拓扑结构与节点属性综合分析的社区发现算法

张振宇，朱培栋，王 可，胡慧俐

(国防科学技术大学 计算机学院，湖南 长沙 410073)

0 引 言

20世纪90年代以来，国际互联网、社交网络、新陈代谢网络、电力网络、交通网络、脑细胞网络等使得人们生活的世界处于各种不同类型的复杂网络之中，对各类复杂网络性质的研究随之成为必要。社交网络中社区结构的发现，不仅有助于网络功能的发掘、网络内部连接层次的识别、社交网络上复杂用户行为及群体行为的理解[1]，同时其分析理论也广泛应用于其他学科。

现有的一些经典社区发现算法，如GN算法、FastNewman算法、遗传算法、系派过滤法、纽带社区等，均只是基于网络拓扑结构[2]进行社区发现。但是，社交网络节点往往蕴含丰富的属性信息，这些信息对社区结构的形成具有重要影响，目前带有节点属性的社区发现，如基于随机游走的边权值节点属性相似度NAS算法[3]，衡量拓扑结构和节点属性的距离概念[4]，边稳定稀疏模型[5]，联合拓扑和属性的分析[6]，这些均将节点属性作为影响因素进行了考虑，但都没有很好地解决两者之间的相关关系，使其联合分析无可避免地产生相关性误差。目前联合拓扑结构和节点属性的社区发现技术有待进一步深入分析。

文中综合考虑社交网络中的拓扑结构和节点属性，通过对两因素进行去相关性操作和赋权处理，从而建立社交网络的社区距离关系矩阵，最后针对得到的关系矩阵，设计一种依据模糊关系相关原理的社区发现算法。……