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

第３６卷第 １２期　 　 　 　 　 　 　 　 　 　 哈　 尔　 滨　 工　 程　 大　 学　 学　 报　 　 　 　 　 　 　 　 　 Ｖｏｌ．３６ №．１２ ２０１５年１２月　 　 　 　 　 　 　 　 　 　 Ｊｏｕｒｎａｌ ｏｆ Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ 　 　 　 　 　 　 　 　 　 　 　 Ｄｅｃ．２０１５ 利用２⁃ｈｏｐ 随机游走进行异质网络社区发现 １，２，３ ３ ３ 杨海陆 ，张健沛 ，杨静 （１．哈尔滨理工大学计算机科学与技术博士后流动站，黑龙江哈尔滨１５００８０；２．哈尔滨理工大学计算机科学与技术学院， 黑龙江哈尔滨１５００８０；３．哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨１５０００１） 摘　 要：针对异质社交网络社区识别问题，提出一种基于随机游走层次社区识别算法。 提出异质网络层级吸引力度量函 数，构建异质网络随机游走模型；设计了一种基于２⁃ｈｏｐ互随机游走的异质网络节点相似性度量函数；通过将该相似性 函数推广到层次聚类并设计相应的相似矩阵校准方案，异质社区识别任务可以在较短的时间内迭代完成。 人工合成网 络和真实网络上的仿真实验验证了算法的可行性和有效性。 关键词：异质社交网络；社区识别；随机游走；相似性度量；层次聚类 ｄｏｉ：１０．１１９９０／ ｊｈｅｕ．２０１４１１００８ 网络出版地址：ｈｔｔｐ：／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ／ ｋｃｍｓ／ ｄｅｔａｉｌ／ ２３．１３９０．ｕ１３２８．０１８．ｈｔｍｌ 中图分类号：ＴＰ３０１．６　 文献标志码：Ａ　 文章编号：１００６⁃７０４３（２０１５）１２⁃１６２６⁃０６ Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｉｎ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ２⁃ｈｏｐ ｒａｎｄｏｍ ｗａｌｋｓ １，２，３ ３ ３ ＹＡＮＧ Ｈａｉｌｕ ，ＺＨＡＮＧＪｉａｎｐｅｉ ，ＹＡＮＧＪｉｎｇ （１． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄＴｅｃｈｎｏｌｏｇｙ Ｐｏｓｔｄｏｃｔｏｒａｌ Ｗｏｒｋｓｔａｔｉｏｎ，Ｈａｒｂｉｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ １５００８０；２． Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ １５００８０，Ｃｈｉｎａ；３． Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ １５０００１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｏｒｄｅｒ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｉｄｅｎｔｉｆｙｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅｓｉｎ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｓｏｃｉａｌ ｎｅｔｗｏｒｋｓ，ａ ｈｉ⁃ ｅｒａｒｃｈｉｃａｌ ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｗａｓｐｒｏｐｏｓｅｄｂａｓｅｄｏｎｒａｎｄｏｍｗａｌｋｓ．Ａｈｅｔｅｒｏｇｅｎｅｏｕｓｒａｎｄｏｍｗａｌｋｍｏｄ⁃ ｅｌｗａｓｂｕｉｌｔｂｙ ｍｅａｓｕｒｉｎｇｔｈｅａｔｔｒａｃｔｉｏｎｂｅｔｗｅｅｎｎｅｔｗｏｒｋｌａｙｅｒｓａｎｄｔｈｅｔｒａｎｓｉｔｉｏｎｐｒｏｂａｂｉｌｉｔｙｂｅｔｗｅｅｎｎｏｄｅｓｉｎｈｏｍ⁃ ｏｇｅｎｅｏｕｓ ｎｅｔｗｏｒｋｓ． Ｔｈｅｎ，ａ ｈｅｔｅｒｏｇｅｎｅｏｕｓ ｎｅｔｗｏｒｋ ｎｏｄｅ ｓｉｍｉｌａｒｉｔｙ ｆｕｎｃｔｉｏｎ ｗａｓ ｐｒｏｐｏｓｅｄ ｂａｓｅｄ ｏｎ ２⁃ｈｏｐ ｍｕｔｕａｌ ｒａｎｄｏｍ ｗａｌｋｓ．Ｆｉｎａｌｌｙ，ｔｈｅｓｉｍｉｌａｒｉｔｙｆｕｎｃｔｉｏｎｗａｓｅｘｔｅｎｄｅｄｔｏｈｉｅｒａｒｃｈｉｃａｌｃｌｕｓｔｅｒｉｎｇｓｏｔｈｅｍｕｌｔｉ⁃ｒｅｌａｔｉｏｎａｌｃｏｍｍｕ⁃ ｎｉｔｙ ｓｔｒｕｃ