杨海陆, 张健沛, 杨静

(1.哈尔滨理工大学 计算机科学与技术博士后流动站，黑龙江 哈尔滨150080； 2.哈尔滨理工大学 计算机科学与技术学院，黑龙江 哈尔滨150080； 3.哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨150001)

利用2-hop随机游走进行异质网络社区发现

杨海陆1,2,3, 张健沛3, 杨静3

(1.哈尔滨理工大学 计算机科学与技术博士后流动站，黑龙江 哈尔滨150080； 2.哈尔滨理工大学 计算机科学与技术学院，黑龙江 哈尔滨150080； 3.哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨150001)

摘要：针对异质社交网络社区识别问题，提出一种基于随机游走层次社区识别算法。提出异质网络层级吸引力度量函数，构建异质网络随机游走模型；设计了一种基于2-hop互随机游走的异质网络节点相似性度量函数；通过将该相似性函数推广到层次聚类并设计相应的相似矩阵校准方案，异质社区识别任务可以在较短的时间内迭代完成。人工合成网络和真实网络上的仿真实验验证了算法的可行性和有效性。

关键词：异质社交网络；社区识别；随机游走；相似性度量；层次聚类

网络出版地址：http://www.cnki.net/kcms/detail/23.1390.u.20151106.1328.018.html

张健沛(1956-)，男，教授，博士生导师.

社区识别是社会计算领域重要的研究内容。总体上讲，社区结构是一种介于宏观和微观之间的特殊结构[1]，它是网络节点的一种聚集形式，使得社区内部链接密度高于社区间的链接密度。社区的量化形式是模块度函数[2]，以模块度为优化目标的社区识别是当前最热门的方法之一，但精准求解模块度最大的社区划分是NP-完全问题[3]，因此现有研究多采用启发式方法[2-4]解决这一技术难点。……