郭昆,郭文忠,邱启荣,张岐山
(1. 福州大学 数学与计算机科学学院, 福建 福州 350108; 2. 福州大学 管理学院, 福建 福州 350108)
近年来,以微博、Facebook、Youtube和Twitter等为代表的社交网络服务(SNS, social network service)在世界范围内得到迅速发展,越来越多人开始通过社交网络进行在线聊天、购物、聚会等活动。在社交网络中识别具有相近的年龄、背景、兴趣等特征的用户组成的社区,不仅在理论上是对复杂网络聚类研究的进一步深化和发展,在实践上对基于社交网络的搜索、推荐等商业应用也具有重要意义。因此,基于社交网络的社区识别已经成为数据挖掘领域的一个研究热点。
广义上,社交网络上的社区识别可以看作是一种复杂网络上的聚类[1]或图上的社区识别[2]。但社交网络也有一些其自身独有的特点。首先,社交网络通常具有庞大的用户群,例如,Facebook和腾讯微博的用户数量均达到亿级。这对社交网络上的社区识别算法的时间和空间复杂度提出了更加严格的要求,通常要求算法的复杂度降低至接近线性才能有效处理具有亿级节点的网络,而目前具有线性复杂度的算法还不多见[2]。其次,社交网络具有显著的动态性,网络内部节点及节点之间的联系经常随时间、地点而不断变化,这意味着任何一次数据采样只能得到某一个时间段某一部分用户和用户关联信息的样本数据。目前,多数复杂网络聚类算法均假设数据分析在一个完整的网络上进行,当部分节点和边的信息缺失时,数据分析的准确性将受到不同程度的影响。……