基于网络拓扑与节点元数据的社团检测算法

刘宇廷,毕海滨,郭 强,倪颖杰

(江南计算技术研究所,江苏 无锡 214000)

0 概述

不同领域多样化的系统可以表示为复杂网络,例如科技系统、生物系统和社会系统[1]。针对复杂网络研究的一个热门方向是社团检测,社团结构在复杂网络中普遍存在[2]。通过挖掘网络中的社团,可以帮助理解网络拓扑结构特点,揭示复杂系统内在功能特性,理解社团内个体关系及行为的演化趋势[3]。

传统社团检测方法基于网络拓扑结构的统计特性建模进行分析与挖掘,研究人员通常假设得到的社团能够表示具有相似特性或功能的节点集合。当前,一些研究已经证实了这个假设下得到的社团与网络中元数据代表的团组是有区别的[4]。所以,许多研究人员期望能够结合其他信息进行社团检测,以发现网络中的真实社团结构。

在真实复杂网络中,网络除了拓扑信息之外,还有节点上的元数据与边上的元数据。例如,社交网络[5]如新浪微博包含用户的个人信息(姓名、年龄、爱好等),引用网络包括用户的姓名、关键词和文章的摘要信息、邮件网络中发送邮件的内容等。通常属于一个社团中的节点一定共享了某些相似的属性,反之可以认为节点的属性影响了社团的结构,结合这些元数据将会提高社团检测的准确性。近年来,研究者提出许多社团检测算法,以期能够通过元数据提高社团检测的准确程度。文献[6]利用2个节点之间共同好友的个数衡量节点之间的……