第11卷第3期 智能系统学报 Vol.11 No.3 2016年6月 CAAI Transactions on Intelligent Systems Jun.2016 D0I:10.11992/is.201603341 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0919.014.html 面向用户兴趣与社区关系的微博话题检测方法 刘志雄12，贾彩燕12 (1.北京交通大学计算机与信息技术学院，北京100044：2.北京交通大学交道数据分析与挖掘北京市重点实验室， 北京100044) 摘要：微博话题检测是一种特殊形式的话题检测，传统的话题检测方法并不能取得很好的效果。提出了一种面向 微博用户社区的话题检测方法。该方法首先在用户发表的微博文本上，利用LDA主题模型分析用户的兴趣分布。 接着，结合微博用户关系网络与用户兴趣对用户进行社区划分，使得同一社区的用户不仅具有较稠密的链接关系， 还具有相似的兴趣。然后，面向用户社区，在每个社区内部检测用户关心的话题，给出了一种面向用户社区的、融合 词重要度与ε近邻图的微博话题发现方法。该算法能够有效地去除微博噪声、快速准确检测出每个用户社区内关 心的话题并对话题进行热度排行。 关键词：微博：社区：网络：文本：话题：兴趣：噪声：主题 中图分类号：TP393文献标志码：A文章编号：1673-4785(2016)03-0294-06 中文引用格式：刘志雄，贾彩燕.面向用户兴趣与社区关系的微博话题检测方法[J].智能系统学报，2016,11(3】：294-300. 英文引用格式：LIU Zhixiong,JIA Caiyan..Micro--blog topic detection based on users'interests and communities[J].CAAI transac- tions on intelligent systems,2016,11(3):294-300. Micro-blog topic detection based on users'interests and communities LIU Zhixiong'2,JIA Caiyan (1.School of Computer and Information Technology,University of Beijing Jiaotong,Beijing 100044,China;2.University of Beijing Jiaotong Beijing Key Lab of Traffic Data Analysis and Mining,Beijing 100044,China) Abstract:Microblog topic detection is a special type of topic detection.The traditional topic detection algorithms do not work well in special situations for Chinese microblogs.In this paper,a topic detection method cater to the user community of microblogs is proposed.Firstly,the users'interests were analyzed by using the LDA(Latent Dirichlet Allocation)topic model on the text of microblogs generated by users/bloggers.Then the user/follower network asso- ciated with users'interests was created and partitioned into different communities so that the users in the same group were not only densely connected but also shared similar interests.Then,the topics of interest in each community were detected.Together,this provides a microblog topic finding method that faces a user's community and combines the importance of words as well as an s neighboring graph.The experimental tests show that the method can effec- tively eliminate microblog noise,compute the importance of words,and rapidly and accurately obtain the topics of interest of each community. Keywords:microblog;community;network;text;topic;interest;noise;theme 在信息爆炸时代，从海量数据中挖掘出有用的 享、传播以及获取的平台也随之兴起。微博用户可 信息显得格外重要。随着Wb2.0的兴起，微博客 以通过PC端、手机端以及其他客户端组建个人社 即微博，这种基于用户关系与短文本特性的信息分 区，以140字左右的文字更新信息，并实现即时分 享。微博成为典型的Wb2.0应用之一。 收稿日期：2016-03-19.网络出版日期：2016-05-13. 在现实世界中，有很多系统都可以抽象为网络， 基金项目：国家自然科学基金面上项目(61473030)、中央高校基本科研 业务专项基金项目(2014JBM031). 这些网络中包含着一些潜在的社区结构，具有社区 通信作者：刘志雄.E-mail:523129791@qq.com
第 １１ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．３ ２０１６ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０３３４１ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０５１３．０９１９．０１４．ｈｔｍｌ 面向用户兴趣与社区关系的微博话题检测方法 刘志雄１，２ ，贾彩燕１，２ （１．北京交通大学 计算机与信息技术学院，北京 １０００４４； ２．北京交通大学 交通数据分析与挖掘北京市重点实验室， 北京 １０００４４） 摘 要：微博话题检测是一种特殊形式的话题检测，传统的话题检测方法并不能取得很好的效果。 提出了一种面向 微博用户社区的话题检测方法。 该方法首先在用户发表的微博文本上，利用 ＬＤＡ 主题模型分析用户的兴趣分布。 接着，结合微博用户关系网络与用户兴趣对用户进行社区划分，使得同一社区的用户不仅具有较稠密的链接关系， 还具有相似的兴趣。 然后，面向用户社区，在每个社区内部检测用户关心的话题，给出了一种面向用户社区的、融合 词重要度与 ε 近邻图的微博话题发现方法。 该算法能够有效地去除微博噪声、快速准确检测出每个用户社区内关 心的话题并对话题进行热度排行。 关键词：微博；社区；网络；文本；话题；兴趣；噪声；主题 中图分类号：ＴＰ３９３ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０３⁃０２９４⁃０６ 中文引用格式：刘志雄，贾彩燕．面向用户兴趣与社区关系的微博话题检测方法［Ｊ］． 智能系统学报， ２０１６， １１（３）： ２９４⁃３００． 英文引用格式：ＬＩＵ Ｚｈｉｘｉｏｎｇ，ＪＩＡ Ｃａｉｙａｎ．Ｍｉｃｒｏ⁃ｂｌｏｇ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｕｓｅｒｓ’ ｉｎｔｅｒｅｓｔｓ ａｎｄ ｃｏｍｍｕｎｉｔｉｅｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃ⁃ ｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６，１１（３）： ２９４⁃３００． Ｍｉｃｒｏ⁃ｂｌｏｇ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｕｓｅｒｓ’ ｉｎｔｅｒｅｓｔｓ ａｎｄ ｃｏｍｍｕｎｉｔｉｅｓ ＬＩＵ Ｚｈｉｘｉｏｎｇ １，２ ， ＪＩＡ Ｃａｉｙａｎ １，２ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ， Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ， Ｂｅｉｊｉｎｇ １０００４４， Ｃｈｉｎａ； ２．Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ Ｂｅｉｊｉｎｇ Ｋｅｙ Ｌａｂ ｏｆ Ｔｒａｆｆｉｃ Ｄａｔａ Ａｎａｌｙｓｉｓ ａｎｄ Ｍｉｎｉｎｇ， Ｂｅｉｊｉｎｇ １０００４４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｍｉｃｒｏｂｌｏｇ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ｉｓ ａ ｓｐｅｃｉａｌ ｔｙｐｅ ｏｆ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ． Ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｄｏ ｎｏｔ ｗｏｒｋ ｗｅｌｌ ｉｎ ｓｐｅｃｉａｌ ｓｉｔｕａｔｉｏｎｓ ｆｏｒ Ｃｈｉｎｅｓｅ ｍｉｃｒｏｂｌｏｇｓ． Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ａ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ ｃａｔｅｒ ｔｏ ｔｈｅ ｕｓｅｒ ｃｏｍｍｕｎｉｔｙ ｏｆ ｍｉｃｒｏｂｌｏｇｓ ｉｓ ｐｒｏｐｏｓｅｄ． Ｆｉｒｓｔｌｙ， ｔｈｅ ｕｓｅｒｓ＇ ｉｎｔｅｒｅｓｔｓ ｗｅｒｅ ａｎａｌｙｚｅｄ ｂｙ ｕｓｉｎｇ ｔｈｅ ＬＤＡ（Ｌａｔｅｎｔ Ｄｉｒｉｃｈｌｅｔ Ａｌｌｏｃａｔｉｏｎ） ｔｏｐｉｃ ｍｏｄｅｌ ｏｎ ｔｈｅ ｔｅｘｔ ｏｆ ｍｉｃｒｏｂｌｏｇｓ ｇｅｎｅｒａｔｅｄ ｂｙ ｕｓｅｒｓ／ ｂｌｏｇｇｅｒｓ． Ｔｈｅｎ ｔｈｅ ｕｓｅｒ／ ｆｏｌｌｏｗｅｒ ｎｅｔｗｏｒｋ ａｓｓｏ⁃ ｃｉａｔｅｄ ｗｉｔｈ ｕｓｅｒｓ＇ ｉｎｔｅｒｅｓｔｓ ｗａｓ ｃｒｅａｔｅｄ ａｎｄ ｐａｒｔｉｔｉｏｎｅｄ ｉｎｔｏ ｄｉｆｆｅｒｅｎｔ ｃｏｍｍｕｎｉｔｉｅｓ ｓｏ ｔｈａｔ ｔｈｅ ｕｓｅｒｓ ｉｎ ｔｈｅ ｓａｍｅ ｇｒｏｕｐ ｗｅｒｅ ｎｏｔ ｏｎｌｙ ｄｅｎｓｅｌｙ ｃｏｎｎｅｃｔｅｄ ｂｕｔ ａｌｓｏ ｓｈａｒｅｄ ｓｉｍｉｌａｒ ｉｎｔｅｒｅｓｔｓ． Ｔｈｅｎ， ｔｈｅ ｔｏｐｉｃｓ ｏｆ ｉｎｔｅｒｅｓｔ ｉｎ ｅａｃｈ ｃｏｍｍｕｎｉｔｙ ｗｅｒｅ ｄｅｔｅｃｔｅｄ． Ｔｏｇｅｔｈｅｒ， ｔｈｉｓ ｐｒｏｖｉｄｅｓ ａ ｍｉｃｒｏｂｌｏｇ ｔｏｐｉｃ ｆｉｎｄｉｎｇ ｍｅｔｈｏｄ ｔｈａｔ ｆａｃｅｓ ａ ｕｓｅｒ＇ｓ ｃｏｍｍｕｎｉｔｙ ａｎｄ ｃｏｍｂｉｎｅｓ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｗｏｒｄｓ ａｓ ｗｅｌｌ ａｓ ａｎ ε ｎｅｉｇｈｂｏｒｉｎｇ ｇｒａｐｈ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｔｅｓｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｍｅｔｈｏｄ ｃａｎ ｅｆｆｅｃ⁃ ｔｉｖｅｌｙ ｅｌｉｍｉｎａｔｅ ｍｉｃｒｏｂｌｏｇ ｎｏｉｓｅ， ｃｏｍｐｕｔｅ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｗｏｒｄｓ， ａｎｄ ｒａｐｉｄｌｙ ａｎｄ ａｃｃｕｒａｔｅｌｙ ｏｂｔａｉｎ ｔｈｅ ｔｏｐｉｃｓ ｏｆ ｉｎｔｅｒｅｓｔ ｏｆ ｅａｃｈ ｃｏｍｍｕｎｉｔｙ． Ｋｅｙｗｏｒｄｓ：ｍｉｃｒｏｂｌｏｇ； ｃｏｍｍｕｎｉｔｙ； ｎｅｔｗｏｒｋ； ｔｅｘｔ； ｔｏｐｉｃ； ｉｎｔｅｒｅｓｔ； ｎｏｉｓｅ； ｔｈｅｍｅ 收稿日期：２０１６⁃０３⁃１９． 网络出版日期：２０１６⁃０５⁃１３． 基金项目：国家自然科学基金面上项目（６１４７３０３０）、中央高校基本科研 业务专项基金项目（２０１４ＪＢＭ０３１）． 通信作者：刘志雄． Ｅ⁃ｍａｉｌ：５２３１２９７９１＠ ｑｑ．ｃｏｍ． 在信息爆炸时代，从海量数据中挖掘出有用的 信息显得格外重要。 随着 Ｗｅｂ２．０ 的兴起，微博客 即微博，这种基于用户关系与短文本特性的信息分 享、传播以及获取的平台也随之兴起。 微博用户可 以通过 ＰＣ 端、手机端以及其他客户端组建个人社 区，以 １４０ 字左右的文字更新信息，并实现即时分 享。 微博成为典型的 Ｗｅｂ２．０ 应用之一。 在现实世界中，有很多系统都可以抽象为网络， 这些网络中包含着一些潜在的社区结构，具有社区
第3期 刘志雄，等：面向用户兴趣与社区关系的微博话题检测方法 ·295· 内部节点链接稠密、社区之间节点链接稀疏的特点。 理对象，分为如下4个步骤：数据预处理、网络建模 通常，社区内部的节点具有相似的特性，在网络中扮 用户社区发现、微博话题检测（流程如图1）。其中， 演着相似的角色。对于微博用户关系网而言：同一 数据预处理主要对微博数据进行筛选和切词，并且 社区内的用户往往具有相同或者相似的兴趣与 过滤掉停用词以及微博平台常见的噪声。例如： 爱好。 “转发微博”、“分享图片”、“视频”等，然后采用基 目前对于微博的研究大多是对用户关系的分析 于吉布斯采样]的LDA)主题模型对用户微博进 或者微博内容的分析。在用户关系研究领域，主要 行降维处理，以得到用户的兴趣分布。网络建模是 研究其社区特性。大体思路是：以用户D为节点， 以用户D为节点，用户关注关系为边，构建网络模 用户关注关系为边构建用户关系网络图，然后采用 型。用户社区发现主要结合LDA模型提取的用户 社区划分算法将其划分为若干社区。往往同一社区 兴趣特征，对用户关系网络进行社区划分，使得找到 内的用户拥有共同的兴趣与爱好。在微博内容分析 的社区内的用户对相似的话题感兴趣。话题发现： 方面，致力于研究微博话题发现方法。大体思路是： 利用社区划分结果，对社区内微博进行话题检测，挖 以词为特征使用VSM[]模型将微博文本转化为空 掘出社区内关心的话题，并对社区内的话题进行热 间向量，并且使用T℉-DF算法计算每一维的权重， 度排行。 然后使用聚类方法将相同话题下的微博文本聚集成 一个个微博话题簇。例如：周刚等4)提出了一种基 预处理 网络建模 社区划分 话题检测 于组合相似度的微博话题发现方法MB-SinglePass 来提升聚类效果，他们将余弦相似度、雅各比相似 图1算法流程 度、语义相似度以一定的权值融合，改进了微博相似 Fig.1 flow of algorithm 度的计算方法：郑斐然等)提出了一种基于词聚类 1.1 数据预处理 的新闻话题发现方法：方然等]提出了一种基于情 微博是一种非结构化数据，携带信息具有碎片 感的微博话题检测方法，他们认为倾向消极的词更 化的特征。并且，携带着大量的垃圾信息（噪声）， 加具有话题表现力，从而依据词的情感分数改善了 使得对微博数据的预处理是微博数据分析的重要前 话题检测效果。然而微博文本被严格限制在140字 提。主要分为以下2个方面：1)针对微博用户的处 以内，单纯地使用VSM]空间向量模型对微博文本 理规则，2)针对微博文本内容的处理规则。 进行建模，存在严重的特征稀疏和维度过高问题。 1)针对微博用户 更严重的是聚类结果还受到微博噪声的影响，导致 由于某些用户发表微博数目较少，并不能很好 话题检测的效果不理想。 地反映用户的兴趣，故选取发表微博总长度大于 本文提出了一种面向用户兴趣与社区关系的微 5000的用户及其关注关系作为我们的数据集。 博话题检测方法，首先应用LDA[)]主题模型对微博 2)针对微博内容 文本进行降维，以用户微博在主题上的分布来表征 分词：汉语中词是最小、能独立活动、有意义的 用户的兴趣与爱好：然后，结合用户兴趣特征对用户 语言成分，但不像英语或者其他语言中词语之间有 关系网进行社区划分，使得同一社区内的用户不仅 明显的空格加以区分。因此分词是微博内容处理的 具有稠密链接的社区关系，还具有相似的兴趣：最 关键一步，分词的方法有多种，如基于字符串匹配的 后，使用了一种融合词重要度与ε近邻图[2)的微博 分词方法、基于统计的分词方法等。本文采用一种 话题检测方法得出每个社区（主题）对应的话题，并 基于最大匹配算法的中文单词识别系统(a word i- 实现相关社区内的话题热度排行。实验结果显示， dentification system for mandarin chinese text based on 该算法有效地对微博特征空间进行了降维、微博去 two variants of the maximum matching algorithm,MM- 噪，使得相似度的计算更加容易：实现了社区内的微 SEG)进行分词，MMSEG算法是一种简单、高效的基 博话题检测，以挖掘出社区内的用户共同关心的话 于词典的中文分词算法。 题，话题检测结果更加迎合社区内的用户兴趣与爱 去停用词：停用词是指在自然语言中具有一定 好，便于进行面向社区兴趣的话题推荐和排行。 功能但又没有什么实际意义的词。这些词往往以较 1 基于用户社区兴趣的话题发现方法 高的频率出现，会对文本处理造成一定干扰。另外， 微博文本中常会出现一些高频词，如：“转发”、“微 本文提出的微博话题检测方法以中文微博为处 博”、“分享”、“图片”等，这些高频词会对话题检测
内部节点链接稠密、社区之间节点链接稀疏的特点。 通常，社区内部的节点具有相似的特性，在网络中扮 演着相似的角色。 对于微博用户关系网而言：同一 社区内的用户往往具有相同或者相似的兴趣与 爱好。 目前对于微博的研究大多是对用户关系的分析 或者微博内容的分析。 在用户关系研究领域，主要 研究其社区特性。 大体思路是：以用户 ＩＤ 为节点， 用户关注关系为边构建用户关系网络图，然后采用 社区划分算法将其划分为若干社区。 往往同一社区 内的用户拥有共同的兴趣与爱好。 在微博内容分析 方面，致力于研究微博话题发现方法。 大体思路是： 以词为特征使用 ＶＳＭ ［３］ 模型将微博文本转化为空 间向量，并且使用 ＴＦ⁃ＩＤＦ 算法计算每一维的权重， 然后使用聚类方法将相同话题下的微博文本聚集成 一个个微博话题簇。 例如：周刚等［４］ 提出了一种基 于组合相似度的微博话题发现方法 ＭＢ⁃ＳｉｎｇｌｅＰａｓｓ 来提升聚类效果，他们将余弦相似度、雅各比相似 度、语义相似度以一定的权值融合，改进了微博相似 度的计算方法；郑斐然等［５］ 提出了一种基于词聚类 的新闻话题发现方法；方然等［６］ 提出了一种基于情 感的微博话题检测方法，他们认为倾向消极的词更 加具有话题表现力，从而依据词的情感分数改善了 话题检测效果。 然而微博文本被严格限制在 １４０ 字 以内，单纯地使用 ＶＳＭ ［３］空间向量模型对微博文本 进行建模，存在严重的特征稀疏和维度过高问题。 更严重的是聚类结果还受到微博噪声的影响，导致 话题检测的效果不理想。 本文提出了一种面向用户兴趣与社区关系的微 博话题检测方法，首先应用 ＬＤＡ ［１］ 主题模型对微博 文本进行降维，以用户微博在主题上的分布来表征 用户的兴趣与爱好；然后，结合用户兴趣特征对用户 关系网进行社区划分，使得同一社区内的用户不仅 具有稠密链接的社区关系，还具有相似的兴趣；最 后，使用了一种融合词重要度与 ε 近邻图［２］ 的微博 话题检测方法得出每个社区（主题）对应的话题，并 实现相关社区内的话题热度排行。 实验结果显示， 该算法有效地对微博特征空间进行了降维、微博去 噪，使得相似度的计算更加容易；实现了社区内的微 博话题检测，以挖掘出社区内的用户共同关心的话 题，话题检测结果更加迎合社区内的用户兴趣与爱 好，便于进行面向社区兴趣的话题推荐和排行。 １ 基于用户社区兴趣的话题发现方法 本文提出的微博话题检测方法以中文微博为处 理对象，分为如下 ４ 个步骤：数据预处理、网络建模、 用户社区发现、微博话题检测（流程如图 １）。 其中， 数据预处理主要对微博数据进行筛选和切词，并且 过滤掉停用词以及微博平台常见的噪声。 例如： “转发微博”、“分享图片”、“视频” 等，然后采用基 于吉布斯采样［７］ 的 ＬＤＡ ［１］ 主题模型对用户微博进 行降维处理，以得到用户的兴趣分布。 网络建模是 以用户 ＩＤ 为节点，用户关注关系为边，构建网络模 型。 用户社区发现主要结合 ＬＤＡ 模型提取的用户 兴趣特征，对用户关系网络进行社区划分，使得找到 的社区内的用户对相似的话题感兴趣。 话题发现： 利用社区划分结果，对社区内微博进行话题检测，挖 掘出社区内关心的话题，并对社区内的话题进行热 度排行。 图 １ 算法流程 Ｆｉｇ．１ ｆｌｏｗ ｏｆ ａｌｇｏｒｉｔｈｍ １．１ 数据预处理 微博是一种非结构化数据，携带信息具有碎片 化的特征。 并且，携带着大量的垃圾信息（噪声）， 使得对微博数据的预处理是微博数据分析的重要前 提。 主要分为以下 ２ 个方面：１）针对微博用户的处 理规则，２）针对微博文本内容的处理规则。 １）针对微博用户 由于某些用户发表微博数目较少，并不能很好 地反映用户的兴趣，故选取发表微博总长度大于 ５ ０００的用户及其关注关系作为我们的数据集。 ２）针对微博内容 分词：汉语中词是最小、能独立活动、有意义的 语言成分，但不像英语或者其他语言中词语之间有 明显的空格加以区分。 因此分词是微博内容处理的 关键一步，分词的方法有多种，如基于字符串匹配的 分词方法、基于统计的分词方法等。 本文采用一种 基于最大匹配算法的中文单词识别系统（ ａ ｗｏｒｄ ｉ⁃ ｄｅｎｔｉｆｉｃａｔｉｏｎ ｓｙｓｔｅｍ ｆｏｒ ｍａｎｄａｒｉｎ ｃｈｉｎｅｓｅ ｔｅｘｔ ｂａｓｅｄ ｏｎ ｔｗｏ ｖａｒｉａｎｔｓ ｏｆ ｔｈｅ ｍａｘｉｍｕｍ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ，ＭＭ⁃ ＳＥＧ）进行分词，ＭＭＳＥＧ 算法是一种简单、高效的基 于词典的中文分词算法。 去停用词：停用词是指在自然语言中具有一定 功能但又没有什么实际意义的词。 这些词往往以较 高的频率出现，会对文本处理造成一定干扰。 另外， 微博文本中常会出现一些高频词，如：“转发”、“微 博”、“分享”、“图片”等，这些高频词会对话题检测 第 ３ 期 刘志雄，等：面向用户兴趣与社区关系的微博话题检测方法 ·２９５·
·296 智能系统学报 第11卷 产生较强的干扰，也需要和停用词一起加以过滤。 划分过程中采用投票机制来规避这一缺陷，详情见 经过以上预处理步骤，我们过滤掉了一部分噪 文献[8]。 声。但即便如此，以词来表征微博文本的特征向量 1.3用户社区划分 的维度也是巨大的，会严重影响微博文本相似度计 以用户D为节点构建的用户关系网中，同一社 算的效率以及有效性。 区内的用户，通常具有相同或相似的爱好。因此，结 3)基于微博文本的用户兴趣特征抽取 合用户的链接关系和用户的兴趣分布，对用户进行 为了学习用户的兴趣特征，如果以用户发表的 聚类，也称为用户社区划分。 微博文本上的词为特征，则会面临维数灾难，我们将 本文延用我们设计的社区划分方法KRLC)对 一个用户发表的所有微博合并为一个长的文本，用 微博用户进行社区划分。具体过程如下： 以表征用户的兴趣，采用基于吉布斯采样法[]的 1)选取中心节点 LDA]主题模型进行降维。将用户的兴趣表示为其 采用K-rank[刿算法选取初始中心节点，即中心 在有限个主题上的分布向量。 节点不但要具有大的PageRank值，中心节点间的相 1.2网络建模 似度要尽可能小。 1.2.1建模 2)社区划分 本文使用有向无权图表示用户关系网。每一个 采用K-means算法进行社区划分，过程如下： 用户作为图中的一个节点，为每一个节点都分配一 输入用户网络G,用户微博长文本集LD,社 个D,ID值从1~n,用户之间的关注关系作为图的 区数K; 边。如果用户i(D为i的用户)关注了用户j,则有 输出划分好的社区列表CommunityList。. 一条由节点i指向节点j的有向边。 ①运行Signal[1]方法将网络的拓扑结构转换成 1.2.2相似度构造方式 一个N维欧式空间上的几何向量。 1)链接属性相似度度量 ②运行Gibbs--sampling--LDA)方法将节点的微 文献[19]提出了一种采用信号传递方法将网 博文档映射到K维特征空间（表示用户在K个主题 络的拓扑结构转换成一个N维欧式空间上的几何 上的兴趣分布)： 向量结构，N是网络中的节点数。我们以该几何向 ③采用K-means算法进行社区划分，将每个 量作为节点的链接属性向量。 用户节点分配得离它最近的中心所属的类中，用户 2)内容属性相似度度量 间节点的相似性计算方法用式(2)的联合相似性 用户微博通过LDA[]主题模型降维后，可以得 测度。 到一个该用户对应微博文档在主题上的分布向量， 对于已经划分的社区，我们根据社区内用户所 以该向量表示节点的内容特征向量。 发表微博在主题上的兴趣分布向量，可以求出该社 3)联合相似度 区关心的主题，如下： 本文采用余弦相似度计算两个节点的链接和内 以t(i)=(t(i,1),…,t(i,j),…,t(i,k)) 容相似度，公式为 表示社区i在各个主题上的兴趣分布向量，其中 6)×rG (i,)表示社区i在第j个主题上的分布值，则 k=1 t(i,)=∑t(k) (3) sim(i,j)= u(E)ec(i) x(i,k)×x(i,k)X ,k)×0,k) 式中：c(i)表示社区i,u(k)表示D为k的用户， (k,)表示用户k在第j个主题上的分布值。最 (1) 后，根据t()取主题分布值最大的3个分量对应的 如果将链接相似度表示为sim'(sim'由链接属性 主题作为社区i关心的主题。 向量采用式(1)求得)，将内容相似度表示为sim 1.4话题检测 (sim°由内容特征向量采用式(1)求得)，那么链接 话题是讨论、谈话的中心，在整个微博上，用户 与内容相结合的联合相似度可表示为sim“,sim“计 经常会针对某一事件、观点展开讨论。对于有大量 算公式为 用户参与讨论的事件和话题，我们称之为热点话题。 sim"a sim+(1 -a)sim (2)》 本文提出了一种融合词重要度与ε近邻图[] 式中α∈[0,1]表示链接相似度在联合相似度中占 的微博话题检测方法来检测话题。具体步骤如图2 的比例。由于参数α的选取通常很困难，故在社区 所示
产生较强的干扰，也需要和停用词一起加以过滤。 经过以上预处理步骤，我们过滤掉了一部分噪 声。 但即便如此，以词来表征微博文本的特征向量 的维度也是巨大的，会严重影响微博文本相似度计 算的效率以及有效性。 ３）基于微博文本的用户兴趣特征抽取 为了学习用户的兴趣特征，如果以用户发表的 微博文本上的词为特征，则会面临维数灾难，我们将 一个用户发表的所有微博合并为一个长的文本，用 以表征用户的兴趣，采用基于吉布斯采样法［７］ 的 ＬＤＡ ［１］主题模型进行降维。 将用户的兴趣表示为其 在有限个主题上的分布向量。 １．２ 网络建模 １．２．１ 建模 本文使用有向无权图表示用户关系网。 每一个 用户作为图中的一个节点，为每一个节点都分配一 个 ＩＤ，ＩＤ 值从 １～ ｎ，用户之间的关注关系作为图的 边。 如果用户 ｉ（ＩＤ 为 ｉ 的用户）关注了用户 ｊ，则有 一条由节点 ｉ 指向节点 ｊ 的有向边。 １．２．２ 相似度构造方式 １） 链接属性相似度度量 文献［１９］提出了一种采用信号传递方法将网 络的拓扑结构转换成一个 Ｎ 维欧式空间上的几何 向量结构，Ｎ 是网络中的节点数。 我们以该几何向 量作为节点的链接属性向量。 ２） 内容属性相似度度量 用户微博通过 ＬＤＡ ［１］ 主题模型降维后，可以得 到一个该用户对应微博文档在主题上的分布向量， 以该向量表示节点的内容特征向量。 ３） 联合相似度 本文采用余弦相似度计算两个节点的链接和内 容相似度，公式为 ｓｉｍ（ｉ， ｊ）＝ ∑ ｎ ｋ ＝１ ｖ（ｉ，ｋ） × ｖ（ｊ，ｋ） ∑ ｎ ｋ ＝１ ｖ（ｉ，ｋ） × ｖ（ｉ，ｋ） × ∑ ｎ ｋ ＝１ ｖ（ｊ，ｋ） × ｖ（ｊ，ｋ） （１） 如果将链接相似度表示为 ｓｉｍ ｔ （ｓｉｍ ｔ由链接属性 向量采用式（１） 求得），将内容相似度表示为 ｓｉｍ ｃ （ｓｉｍ ｃ由内容特征向量采用式（１） 求得），那么链接 与内容相结合的联合相似度可表示为 ｓｉｍ ｕ ，ｓｉｍ ｕ计 算公式为 ｓｉｍ ｕ ＝ α ｓｉｍ ｔ ＋ （１ － α） ｓｉｍ ｃ （２） 式中 α∈［０，１］表示链接相似度在联合相似度中占 的比例。 由于参数 α 的选取通常很困难，故在社区 划分过程中采用投票机制来规避这一缺陷，详情见 文献［８］。 １．３ 用户社区划分 以用户 ＩＤ 为节点构建的用户关系网中，同一社 区内的用户，通常具有相同或相似的爱好。 因此，结 合用户的链接关系和用户的兴趣分布，对用户进行 聚类，也称为用户社区划分。 本文延用我们设计的社区划分方法 ＫＲＬＣ ［８］ 对 微博用户进行社区划分。 具体过程如下： １）选取中心节点 采用 Ｋ⁃ｒａｎｋ ［９］算法选取初始中心节点，即中心 节点不但要具有大的 ＰａｇｅＲａｎｋ 值，中心节点间的相 似度要尽可能小。 ２）社区划分 采用 Ｋ⁃ｍｅａｎｓ ［１１］算法进行社区划分，过程如下： 输入 用户网络 Ｇ ，用户微博长文本集 ＬＤ，社 区数 Ｋ； 输出 划分好的社区列表 ＣｏｍｍｕｎｉｔｙＬｉｓｔ。 ①运行 Ｓｉｇｎａｌ ［１９］方法将网络的拓扑结构转换成 一个 Ｎ 维欧式空间上的几何向量。 ②运行 Ｇｉｂｂｓ⁃ｓａｍｐｌｉｎｇ⁃ＬＤＡ ［１］ 方法将节点的微 博文档映射到 Ｋ 维特征空间（表示用户在 Ｋ 个主题 上的兴趣分布）； ③采用 Ｋ⁃ｍｅａｎｓ ［１１］算法进行社区划分，将每个 用户节点分配得离它最近的中心所属的类中，用户 间节点的相似性计算方法用式（ ２） 的联合相似性 测度。 对于已经划分的社区，我们根据社区内用户所 发表微博在主题上的兴趣分布向量，可以求出该社 区关心的主题，如下： 以 ｔ（ｉ） ＝ （ｔ（ｉ， １）， …， ｔ（ｉ， ｊ）， …， ｔ（ｉ， ｋ）） 表示社区 ｉ 在各个主题上的兴趣分布向量，其中 ｔ（ｉ， ｊ）表示社区 ｉ 在第 ｊ 个主题上的分布值，则 ｔ（ｉ，ｊ） ＝ ｕ（ｋ∑ ）∈ｃ（ｉ） ｔ（ｋ，ｊ） （３） 式中：ｃ（ ｉ） 表示社区 ｉ，ｕ（ ｋ） 表示 ＩＤ 为 ｋ 的用户， ｔ（ｋ， ｊ）表示用户 ｋ 在第 ｊ 个主题上的分布值。 最 后，根据 ｔ（ｉ）取主题分布值最大的 ３ 个分量对应的 主题作为社区 ｉ 关心的主题。 １．４ 话题检测 话题是讨论、谈话的中心，在整个微博上，用户 经常会针对某一事件、观点展开讨论。 对于有大量 用户参与讨论的事件和话题，我们称之为热点话题。 本文提出了一种融合词重要度与 ε 近邻图［２］ 的微博话题检测方法来检测话题。 具体步骤如图 ２ 所示。 ·２９６· 智 能 系 统 学 报 第 １１ 卷
第3期 刘志雄，等：面向用户兴趣与社区关系的微博话题检测方法 ·297. 重要度分数并逆序排序。 提取重要词 剪枝 网络建模 3)剔除重要度低于阈值0的词语。 经过如上步骤，得到了微博文档D对应的重要 聚类 话题排行 检测话题 词库，记为精英词集elite。 1.4.2剪枝 将微博特征向量中不属于重要词汇库elite的 图2话题检测流程图 词语别除。若剔除后微博向量长度过短，则将该微 Fig.2 flow of topic detection 博从该社区剔除，本文设置长度阈值为3。去除了 1.4.1提取重要词 微博内与话题相关度很低的词语，保留了与话题相 由话题的定义可知，与话题相关的词语通常会 关度较高的词语。 具有更高的重要性。显然，重要性过低的词语，尽管 1.4.3微博文本￡近邻图构建 能够表达一定的含义，但并不能构成话题，会对我们 传统的微博相似度计算方法主要是对微博集合 话题检测造成一定影响。因此需计算词的重要性。 中每一条微博的词进行TF-DF的计算，并将微博中 TextRankt2)算法是在Google的PageRank[io]算 各个词表示成VSM)空间向量，然后采用余弦相似 法启发下，针对文本里的句子设计的权重算法。最 度计算两条微博之间的相似度。但考虑到微博具有 初的目标是对文章提取摘要，目前多用于给词语打 分，即计算词语的重要度。本文采用TextRank!]算 短文本高维、稀疏的特点，采用传统的TFDF向量 表示法计算得到的相似性（趋于0）不能反映两个微 法计算词语重要度并过滤掉重要度过低的词语，步 博文本的真实相似性。故本文以词语的重要度代替 骤如下： 1)将同一社区内所有微博（已切词）做拼接，构 TF-IDF值作为词的特征权重。由于经过社区划分 以及微博剪枝之后，社区内微博特征已相对稠密，故 成微博文档D。 2)采用TextRank2]算法对微博文档D求词语 可采用基于VSM)空间向量模型的余弦相似度计 算方法来计算两条微博之间的相似度，公式为 score(w,)x score(w,) icAnB sim(A,B)= (4) ∑score(w,)×score(w,)×,∑score(u,)×score(w,) ARjEA 个V!eB 式中：sim(A,B)表示微博A与微博B之间的相似 式中：fre(0:,j)表示词wi在话题簇j内的词频， 度，score(w:)表示词0，的重要度分数。 score(0:)表示词e,的重要度，num(j)表示话题簇j 我们给每一条微博分配一个D,D从1到n', 包含的微博数目，则主题选取过程如下： 然后以微博为节点，微博之间的相似度为边，构建一 1)对于所有话题簇，在话题簇内计算所有词的 张ε近邻图)。若微博i与微博j的相似度大于阈 主题度； 值e,则微博i与微博j之间存在一条边，且该边权 2)在话题簇内按主题度对词进行逆序排序，并 重为sim(i,j)。 保留主题度最大的15个词： 1.4.4微博聚类 3)将所有话题簇内所保留的词加入集合s: 本文采用社区划分的方法对微博文本进行聚类。 由于社区具有社区内部节点连接稠密、社区之间节点 4)遍历集合s,对于词w:,遍历所有社区，若心， 连接稀疏的特点，故社区（话题簇）内微博相似度更大， 在社区t内的主题度最高，则w,∈tw(t)。tw(t)表 社区（话题簇）间微博相似度更小。故对微博ε近邻图 示话题簇t对应的主题词集合。 进行社区划分，并选取社区节点数最多的T个社区作 1.4.6话题热度排行 为社区内关心的话题。本文采用经典社区划分算法 话题的热度表现在多个方面，本文以主题度来 BGLL1)对微博ε近邻图进行社区划分。 表征话题的热度。计算公式为 1.4.5话题检测 ∑topic(w,j) 本文以主题词来描述话题，提出了一种以主题 heat(j)= (6)》 度来选取主题词的方法。本方法以topic(w:,j)表 m(j) 示词心，在话题簇j内的主题度，计算公式如下： 式中：heat(j)表示话题簇j对应话题热度，m(j)表示 topic(w:,j)=fre(w:j)x score(w:)/num(j) 话题簇对应主题词集合包含词语个数。 (5) 最后按话题热度对话题进行逆序排序
图 ２ 话题检测流程图 Ｆｉｇ．２ ｆｌｏｗ ｏｆ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ １．４．１ 提取重要词 由话题的定义可知，与话题相关的词语通常会 具有更高的重要性。 显然，重要性过低的词语，尽管 能够表达一定的含义，但并不能构成话题，会对我们 话题检测造成一定影响。 因此需计算词的重要性。 ＴｅｘｔＲａｎｋ ［１２］算法是在 Ｇｏｏｇｌｅ 的 ＰａｇｅＲａｎｋ ［１０］ 算 法启发下，针对文本里的句子设计的权重算法。 最 初的目标是对文章提取摘要，目前多用于给词语打 分，即计算词语的重要度。 本文采用 ＴｅｘｔＲａｎｋ ［１２］ 算 法计算词语重要度并过滤掉重要度过低的词语，步 骤如下： １）将同一社区内所有微博（已切词）做拼接，构 成微博文档 Ｄ。 ２） 采用 ＴｅｘｔＲａｎｋ ［１２］算法对微博文档 Ｄ 求词语 重要度分数并逆序排序。 ３）剔除重要度低于阈值 θ 的词语。 经过如上步骤，得到了微博文档 Ｄ 对应的重要 词库，记为精英词集 ｅｌｉｔｅ。 １．４．２ 剪枝 将微博特征向量中不属于重要词汇库 ｅｌｉｔｅ 的 词语剔除。 若剔除后微博向量长度过短，则将该微 博从该社区剔除，本文设置长度阈值为 ３。 去除了 微博内与话题相关度很低的词语，保留了与话题相 关度较高的词语。 １．４．３ 微博文本 ε 近邻图构建 传统的微博相似度计算方法主要是对微博集合 中每一条微博的词进行 ＴＦ⁃ＩＤＦ 的计算，并将微博中 各个词表示成 ＶＳＭ ［３］空间向量，然后采用余弦相似 度计算两条微博之间的相似度。 但考虑到微博具有 短文本高维、稀疏的特点，采用传统的 ＴＦ⁃ＩＤＦ 向量 表示法计算得到的相似性（趋于 ０）不能反映两个微 博文本的真实相似性。 故本文以词语的重要度代替 ＴＦ⁃ＩＤＦ 值作为词的特征权重。 由于经过社区划分 以及微博剪枝之后，社区内微博特征已相对稠密，故 可采用基于 ＶＳＭ ［３］ 空间向量模型的余弦相似度计 算方法来计算两条微博之间的相似度，公式为 ｓｉｍ（Ａ，Ｂ） ＝ ｗ∑ｉ∈Ａ∩Ｂ ｓｃｏｒｅ（ｗｉ） × ｓｃｏｒｅ（ｗｉ） ∑ｗｉ∈Ａ ｓｃｏｒｅ（ｗｉ） × ｓｃｏｒｅ（ｗｉ） × ∑ｗｉ∈Ｂ ｓｃｏｒｅ（ｗｉ） × ｓｃｏｒｅ（ｗｉ） （４） 式中：ｓｉｍ（Ａ， Ｂ）表示微博 Ａ 与微博 Ｂ 之间的相似 度，ｓｃｏｒｅ（ｗｉ）表示词 ｗｉ的重要度分数。 我们给每一条微博分配一个 ＩＤ，ＩＤ 从 １ 到 ｎ′， 然后以微博为节点，微博之间的相似度为边，构建一 张 ε 近邻图［２］ 。 若微博 ｉ 与微博 ｊ 的相似度大于阈 值 ε，则微博 ｉ 与微博 ｊ 之间存在一条边，且该边权 重为 ｓｉｍ（ｉ， ｊ）。 １．４．４ 微博聚类 本文采用社区划分的方法对微博文本进行聚类。 由于社区具有社区内部节点连接稠密、社区之间节点 连接稀疏的特点，故社区（话题簇）内微博相似度更大， 社区（话题簇）间微博相似度更小。 故对微博 ε 近邻图 进行社区划分，并选取社区节点数最多的 Ｔ 个社区作 为社区内关心的话题。 本文采用经典社区划分算法 ＢＧＬＬ ［１３］对微博 ε 近邻图进行社区划分。 １．４．５ 话题检测 本文以主题词来描述话题，提出了一种以主题 度来选取主题词的方法。 本方法以 ｔｏｐｉｃ（ｗｉ， ｊ） 表 示词 ｗｉ在话题簇 ｊ 内的主题度，计算公式如下： ｔｏｐｉｃ（ｗｉ，ｊ） ＝ ｆｒｅ（ｗｉ，ｊ） × ｓｃｏｒｅ（ｗｉ） ／ ｎｕｍ（ｊ） （５） 式中：ｆｒｅ （ ｗｉ， ｊ） 表示词 ｗｉ 在话题簇 ｊ 内的词频， ｓｃｏｒｅ（ｗｉ）表示词 ｗｉ的重要度，ｎｕｍ（ ｊ）表示话题簇 ｊ 包含的微博数目，则主题选取过程如下： １）对于所有话题簇，在话题簇内计算所有词的 主题度； ２）在话题簇内按主题度对词进行逆序排序，并 保留主题度最大的 １５ 个词； ３）将所有话题簇内所保留的词加入集合 ｓ； ４） 遍历集合 ｓ，对于词 ｗｉ，遍历所有社区，若 ｗｉ 在社区 ｔ 内的主题度最高，则 ｗｉ∈ｔｗ（ ｔ）。 ｔｗ（ ｔ）表 示话题簇 ｔ 对应的主题词集合。 １．４．６ 话题热度排行 话题的热度表现在多个方面，本文以主题度来 表征话题的热度。 计算公式为 ｈｅａｔ（ｊ） ＝ ｗ∑ｉ∈ｔｗ（ｊ） ｔｏｐｉｃ（ｗｉ，ｊ） ｍ（ｊ） （６） 式中：ｈｅａｔ（ｊ）表示话题簇 ｊ 对应话题热度，ｍ（ｊ）表示 话题簇 ｊ 对应主题词集合包含词语个数。 最后按话题热度对话题进行逆序排序。 第 ３ 期 刘志雄，等：面向用户兴趣与社区关系的微博话题检测方法 ·２９７·
·298. 智能系统学报 第11卷 实验结果与分析 个类别作为主题，分别为亲子、体育、公益、娱乐、文 艺、时尚、时政、生活、科技、财经。然后将每个用户 2.1实验数据 发表的微博拼接成微博文档，选取微博文档长度大 本实验数据采用自主抓取的新浪微博数据，该 于5000字的3490个用户作为实验数据，并进行网 数据集于2013年9月一2013年12月采用自主开发 络建模。采用信号传递算法[1对用户关系网求链 的面向新浪微博的网络爬虫爬取。数据集包括用户 接属性向量，并采用该向量求节点链接相似度；采用 基本信息、用户关系信息、用户发表微博等3部分。 LDA主题模型对微博文档求主题分布向量（内容 2.2实验过程与结果 特征向量)，并采用该向量求节点内容相似度。然 2.2.1用户社区划分实验与结果 后采用KRLC算法[]对用户进行社区划分，最后采 根据新浪微博首页热门微博分类版块，选取10 用式(3)求出社区对应兴趣分布，具体结果如表1。 表1使用KRLC划分的社区兴趣分布 Table 1 The interest distribution of community by KRLC % 节点数 亲子 娱乐 生活 时政 财经 文艺 时尚 公益 体育 科技 类别 798 58.06 2.11 19.11 1.53 3.58 0.17 8.77 4.64 0.23 1.76 亲子 536 6.63 9.25 21.31 0.96 2.69 0.01 0.16 8.08 48.15 2.71 体育 204 11.14 5.16 12.27 6.92 6.81 0.70 1.70 50.71 1.60 2.92 公益 169 7.81 60.09 19.51 0.35 0.65 0.05 0.77 5.09 1.62 4.01 娱乐 122 10.89 5.00 4.46 7.25 6.27 45.64 2.50 15.07 0 2.86 文艺 70 11.85 2.71 15.34 0.10 2.28 0.49 56.22 4.00 0 6.95 时尚 567 10.52 1.27 3.14 46.45 9.66 0.50 0.51 27.27 0.16 0.48 时政 257 13.46 9.80 58.16 0.54 0.74 0.18 2.60 7.79 1.39 5.29 生活 609 9.38 2.71 8.37 0.14 4.31 0.07 6.97 1.38 0.08 66.53 科技 158 15.64 3.73 4.94 6.41 55.93 2.52 0.83 9.41 0.09 2.52 财经 2.2.2社区内话题检测结果 词语，相似度阈值ε设为0.15。由于亲子、文艺、时 根据划分的10个社区，在社区内检测话题，检 尚等3个主题出现话题几率较小，故本文没有在这 测算法如2.4所示。本文选取了2013.11.10一2013. 3个社区内检测话题。部分主题对应社区内话题检 11.12共3天的微博作为话题检测数据。其中词语 测结果如表2所示。 重要度阈值0设为40%，即保留重要度最高的40% 表2部分社区内微博话题检测结果 Table 2 Part of micro-blog topic detection result within community 主题 编号 主题词 热度 对应话题 1 男篮亚锦赛第一比赛易建联朱芳王治郅 2.13 男篮亚锦赛名单出炉 广州恒大2013亚冠联赛冠军足球夺冠 2.04 恒大亚冠联赛夺冠 体育 3 中国大奖赛车迷活动潘涌涌现场 1.95 车迷大奖赛潘涌涌现场解说 北京首钢支持陈磊吉哲球迷国安 1.70 明日CBA北京VS辽宁 5 央视羽毛球世锦赛林丹谌龙世界锦标赛男子单打 1.37 羽毛球世锦赛林丹战胜谌龙 河南大学生北京2013儿童家人电话平安 4.70 河南大学生失联 公益 汇聚长沙银行支行慈善拍卖会拍品展示作品 2.99 长沙银行娄底支行慈善拍卖会 3 头条汪峰离婚瞬间章子发布凌晨吴奇隆刘诗诗 1.89 汪峰悲催头条又被抢 白举纲丝带北京小白白菜节目录制 1.35 白举纲爱的绿丝带北京演唱会 娱乐 2 吴亦凡1106生日快乐祝福凡凡 0.92 11月06日吴亦凡生日快乐 3 非同凡响131102首尔青少年庆典领奖 0.84 非同凡响青少年庆典颁奖 根据表2我们可以看出，面向用户社区的话题 兴趣的话题，使得话题推荐和排行具有社区兴趣个 检测方法，可以针对社区内的用户兴趣找到用户感 性化
２ 实验结果与分析 ２．１ 实验数据 本实验数据采用自主抓取的新浪微博数据，该 数据集于 ２０１３ 年 ９ 月—２０１３ 年 １２ 月采用自主开发 的面向新浪微博的网络爬虫爬取。 数据集包括用户 基本信息、用户关系信息、用户发表微博等 ３ 部分。 ２．２ 实验过程与结果 ２．２．１ 用户社区划分实验与结果 根据新浪微博首页热门微博分类版块，选取 １０ 个类别作为主题，分别为亲子、体育、公益、娱乐、文 艺、时尚、时政、生活、科技、财经。 然后将每个用户 发表的微博拼接成微博文档，选取微博文档长度大 于 ５ ０００ 字的 ３ ４９０ 个用户作为实验数据，并进行网 络建模。 采用信号传递算法［１９］ 对用户关系网求链 接属性向量，并采用该向量求节点链接相似度；采用 ＬＤＡ ［１］主题模型对微博文档求主题分布向量（内容 特征向量），并采用该向量求节点内容相似度。 然 后采用 ＫＲＬＣ 算法［８］ 对用户进行社区划分，最后采 用式（３）求出社区对应兴趣分布，具体结果如表 １。 表 １ 使用 ＫＲＬＣ 划分的社区兴趣分布 Ｔａｂｌｅ １ Ｔｈｅ ｉｎｔｅｒｅｓｔ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｃｏｍｍｕｎｉｔｙ ｂｙ ＫＲＬＣ ％ 节点数 亲子 娱乐 生活 时政 财经 文艺 时尚 公益 体育 科技 类别 ７９８ ５８．０６ ２．１１ １９．１１ １．５３ ３．５８ ０．１７ ８．７７ ４．６４ ０．２３ １．７６ 亲子 ５３６ ６．６３ ９．２５ ２１．３１ ０．９６ ２．６９ ０．０１ ０．１６ ８．０８ ４８．１５ ２．７１ 体育 ２０４ １１．１４ ５．１６ １２．２７ ６．９２ ６．８１ ０．７０ １．７０ ５０．７１ １．６０ ２．９２ 公益 １６９ ７．８１ ６０．０９ １９．５１ ０．３５ ０．６５ ０．０５ ０．７７ ５．０９ １．６２ ４．０１ 娱乐 １２２ １０．８９ ５．００ ４．４６ ７．２５ ６．２７ ４５．６４ ２．５０ １５．０７ ０ ２．８６ 文艺 ７０ １１．８５ ２．７１ １５．３４ ０．１０ ２．２８ ０．４９ ５６．２２ ４．００ ０ ６．９５ 时尚 ５６７ １０．５２ １．２７ ３．１４ ４６．４５ ９．６６ ０．５０ ０．５１ ２７．２７ ０．１６ ０．４８ 时政 ２５７ １３．４６ ９．８０ ５８．１６ ０．５４ ０．７４ ０．１８ ２．６０ ７．７９ １．３９ ５．２９ 生活 ６０９ ９．３８ ２．７１ ８．３７ ０．１４ ４．３１ ０．０７ ６．９７ １．３８ ０．０８ ６６．５３ 科技 １５８ １５．６４ ３．７３ ４．９４ ６．４１ ５５．９３ ２．５２ ０．８３ ９．４１ ０．０９ ２．５２ 财经 ２．２．２ 社区内话题检测结果 根据划分的 １０ 个社区，在社区内检测话题，检 测算法如 ２．４ 所示。 本文选取了 ２０１３．１１．１０—２０１３． １１．１２ 共 ３ 天的微博作为话题检测数据。 其中词语 重要度阈值 θ 设为 ４０％，即保留重要度最高的 ４０％ 词语，相似度阈值 ε 设为０．１５。 由于亲子、文艺、时 尚等 ３ 个主题出现话题几率较小，故本文没有在这 ３ 个社区内检测话题。 部分主题对应社区内话题检 测结果如表 ２ 所示。 表 ２ 部分社区内微博话题检测结果 Ｔａｂｌｅ ２ Ｐａｒｔ ｏｆ ｍｉｃｒｏ⁃ｂｌｏｇ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ｒｅｓｕｌｔ ｗｉｔｈｉｎ ｃｏｍｍｕｎｉｔｙ 主题 编号 主题词 热度 对应话题 体育 １ 男篮 亚锦赛 第一 比赛 易建联 朱芳 王治郅 ２．１３ 男篮亚锦赛名单出炉 ２ 广州 恒大 ２０１３ 亚冠 联赛 冠军 足球 夺冠 ２．０４ 恒大亚冠联赛夺冠 ３ 中国 大奖赛 车迷 活动 潘涌涌 现场 １．９５ 车迷大奖赛潘涌涌现场解说 ４ 北京 首钢 支持 陈磊 吉哲 球迷 国安 １．７０ 明日 ＣＢＡ 北京 ＶＳ 辽宁 ５ 央视 羽毛球 世锦赛 林丹 谌龙 世界 锦标赛 男子 单打 １．３７ 羽毛球世锦赛林丹战胜谌龙 公益 １ 河南 大学生 北京 ２０１３ 儿童 家人 电话 平安 ４．７０ 河南大学生失联 ２ 汇聚 长沙 银行 支行 慈善 拍卖会 拍品 展示 作品 ２．９９ 长沙银行娄底支行慈善拍卖会 ３ 头条 汪峰 离婚 瞬间 章子 发布 凌晨 吴奇隆 刘诗诗 １．８９ 汪峰悲催头条又被抢 娱乐 １ 白举纲 丝带 北京 小白 白菜 节目 录制 １．３５ 白举纲爱的绿丝带北京演唱会 ２ 吴亦凡 １１０６ 生日 快乐 祝福 凡凡 ０．９２ １１ 月 ０６ 日吴亦凡生日快乐 ３ 非同 凡响 １３１１０２ 首尔 青少年 庆典 颁奖 ０．８４ 非同凡响青少年庆典颁奖 根据表 ２ 我们可以看出，面向用户社区的话题 检测方法，可以针对社区内的用户兴趣找到用户感 兴趣的话题，使得话题推荐和排行具有社区兴趣个 性化。 ·２９８· 智 能 系 统 学 报 第 １１ 卷
第3期 刘志雄，等：面向用户兴趣与社区关系的微博话题检测方法 ·299. 2.3局部算法对照试验 所关注，提高用户活跃度。并且，本文采用主题度计 由于本文提出的面向用户兴趣与社区关系的微 算话题热度并排序，使话题展示顺序更加合理。 博话题检测与已有研究不同，一是方法不同，二是研 3结束语 究数据不同，因此我们没有和已发表方法进行对比。 但我们对已选取的社区划分方法的差异而造成的结 本文提出了一种基于用户兴趣与社区关系的微 果差异，进行了一些分析。 博话题检测方法，该方法能够快速准确地在社区内 除了使用BGLL算法[1]对微博ε近邻图)进 部检测话题，并对话题按热度进行排行。并且，该方 行话题分割，我们采用被广泛使用的图聚类方法 法巧妙融合了新浪微博的社区特性与文本特性，检 metis]、经典社区划分算法infomap2o)、基于模块 测的话题更加迎合用户的兴趣。 度的快速社区划分算法fastnewman对微博e近 本文以主题词的形式来表现微博话题，但是本 邻图进行话题分割。为了更全面地分析我们的实验 文对主题词采用硬划分，导致同一主题词只能属于 结果，选取了CV[]值作为评价指标（表3中CV值 唯一主题。但在真实情况下，可能多个话题含有同 为该社区内所有话题CV值的平均值)，该评价指标 一主题词，如何实现将主题词划入多个话题，有待进 由Mimno!1]基于评估话题质量而提出。 一步研究。另外，以主题词表现话题并不是特别直 给定一个话题t和它的描述主题词V(t)= 观，如何实现以词组或句子表达主题，也有待进一步 ((t),2(t),…,w(t)),则CV值定义为 研究。 C(t,)= D(n0,y0)+1 ∑log (7) 参考文献： D(v() [1]BLEI D M,NG A Y,JORDAN M I.Latent dirichlet alloca- 式中：D()为包含词v的文档频次，D(,v')为同时 tion[J].The journal of machine learning research,2003,3 包含词v和'的文档频次。CV值基于描述同一话 (4-5):993-1002. 题的词往往同时出现于同一文档中。CV值越小， [2]VON LUXBURG U.A tutorial on spectral clustering J]. 所得话题簇的一致性越好。 Statistics and computing,2007,17(4):395-416. 实验结果如表3所示。由表3可以知道，选择 [3]郭庆琳，李艳梅，唐琦.基于VSM的文本相似度计算的 不同的方法对微博ε近邻图进行话题聚类，会得到 研究[J].计算机应用研究，2008,25(11)：3256-3258. 不同的结果。在本实验中，metis方法的效果总体上 GUO Qinglin,Li Yanmei,TANG Qi.Similarity computing 好于BGLL方法，但本文的方法只是面向用户兴趣 of documents based on VSM[J].Application research of 和社区关系的话题检测框架的一个尝试，这类方法 computers,2008,25(11):3256-3258. 都可以找到用户群兴趣个性化的话题。 [4]周刚，邹鸿程，熊小兵，等.MB-SinglePass:基于组合相 似度的微博话题检测[J].计算机科学，2012,39(10)： 表3BGLL算法与metis、infomap、fastnewman算法 198-202 对照试验结果 ZHOU Gang,ZOU Hongcheng,XIONG Xiaobing,et al. Table 3 The controlled Trials result of BGLL with metis, MB-SinglePass:microblog topic detection based on com- infomap、fastnewman bined similarity[J].Computer science,2012,39(10): 划分算法体育公益娱乐时政生活科技财经 198-202. bgll -15.8-6.3-16.3-22.3-14.3-15.3-14.0 [5]郑斐然，苗夺谦，张志飞，等.一种中文微博新闻话题 metis -17.3-0.5-17.3-8.8-17.0-8.0-7.0 检测的方法[J].计算机科学，2012,39(1)：138-141. infomap-4.0-4.2-8.0-3.2-8.4-6.0 -3.2 ZHENG Feiran,MIAO Duoqian,ZHANG Zhifei,et al. fastnewman-7.2-5.2-6.2-5.2-5.8-5.4-4.4 News topic detection approach on Chinese microblog[J]. Computer science,2012,39(1):138-141. 综上所述，本文提出的算法面向用户兴趣检测 [6]方然，苗夺谦，张志飞.一种基于情感的中文微博话题 话题，基于词重要度的词过滤方法使得社区内的特 检测方法[J].智能系统学报，2013,8(3)：208-213. 征向量维度更低、更稠密，有效地解决了微博话题检 FANG Ran,MIAO Duoqian,ZHANG Zhifei,et al.An e- 测过程中出现的特征稀疏问题。与普通话题检测方 motion-based method of topic detection from Chinese mi- 法相比，该算法所检测话题更有可能被社区内用户 croblogs [J ]CAAI transactions on intelligent systems
２．３ 局部算法对照试验 由于本文提出的面向用户兴趣与社区关系的微 博话题检测与已有研究不同，一是方法不同，二是研 究数据不同，因此我们没有和已发表方法进行对比。 但我们对已选取的社区划分方法的差异而造成的结 果差异，进行了一些分析。 除了使用 ＢＧＬＬ 算法［１３］ 对微博 ε 近邻图［２］ 进 行话题分割，我们采用被广泛使用的图聚类方法 ｍｅｔｉｓ ［１７］ 、经典社区划分算法 ｉｎｆｏｍａｐ ［２０］ 、基于模块 度的快速社区划分算法 ｆａｓｔｎｅｗｍａｎ ［１６］ 对微博 ε 近 邻图进行话题分割。 为了更全面地分析我们的实验 结果，选取了 ＣＶ ［１８］值作为评价指标（表 ３ 中 ＣＶ 值 为该社区内所有话题 ＣＶ 值的平均值），该评价指标 由 Ｍｉｍｎｏ ［１８］基于评估话题质量而提出。 给定一个话题 ｔ 和它的描述主题词 Ｖ （ ｔ） ＝ （ｖ１（ｔ）， ｖ２（ｔ），…， ｖＭ（ｔ）），则 ＣＶ 值定义为 Ｃ（ｔ，ｖ （ｔ） ） ＝ ∑ Ｍ ｍ ＝ ２∑ ｍ－１ ｌ ＝ １ ｌｏｇ Ｄ（ｖｍ （ｔ） ，ｖｌ （ｔ） ） ＋ １ Ｄ（ｖｌ （ｔ） ） （７） 式中：Ｄ（ｖ）为包含词 ｖ 的文档频次，Ｄ（ｖ， ｖ′）为同时 包含词 ｖ 和 ｖ′的文档频次。 ＣＶ 值基于描述同一话 题的词往往同时出现于同一文档中。 ＣＶ 值越小， 所得话题簇的一致性越好。 实验结果如表 ３ 所示。 由表 ３ 可以知道，选择 不同的方法对微博 ε 近邻图进行话题聚类，会得到 不同的结果。 在本实验中，ｍｅｔｉｓ 方法的效果总体上 好于 ＢＧＬＬ 方法，但本文的方法只是面向用户兴趣 和社区关系的话题检测框架的一个尝试，这类方法 都可以找到用户群兴趣个性化的话题。 表 ３ ＢＧＬＬ 算法与 ｍｅｔｉｓ、ｉｎｆｏｍａｐ、ｆａｓｔｎｅｗｍａｎ 算法 对照试验结果 Ｔａｂｌｅ ３ Ｔｈｅ ｃｏｎｔｒｏｌｌｅｄ Ｔｒｉａｌｓ ｒｅｓｕｌｔ ｏｆ ＢＧＬＬ ｗｉｔｈ ｍｅｔｉｓ、 ｉｎｆｏｍａｐ、ｆａｓｔｎｅｗｍａｎ 划分算法 体育 公益 娱乐 时政 生活 科技 财经 ｂｇｌｌ －１５．８ －６．３ －１６．３ －２２．３ －１４．３ －１５．３ －１４．０ ｍｅｔｉｓ －１７．３ －０．５ －１７．３ －８．８ －１７．０ －８．０ －７．０ ｉｎｆｏｍａｐ －４．０ －４．２ －８．０ －３．２ －８．４ －６．０ －３．２ ｆａｓｔｎｅｗｍａｎ －７．２ －５．２ －６．２ －５．２ －５．８ －５．４ －４．４ 综上所述，本文提出的算法面向用户兴趣检测 话题，基于词重要度的词过滤方法使得社区内的特 征向量维度更低、更稠密，有效地解决了微博话题检 测过程中出现的特征稀疏问题。 与普通话题检测方 法相比，该算法所检测话题更有可能被社区内用户 所关注，提高用户活跃度。 并且，本文采用主题度计 算话题热度并排序，使话题展示顺序更加合理。 ３ 结束语 本文提出了一种基于用户兴趣与社区关系的微 博话题检测方法，该方法能够快速准确地在社区内 部检测话题，并对话题按热度进行排行。 并且，该方 法巧妙融合了新浪微博的社区特性与文本特性，检 测的话题更加迎合用户的兴趣。 本文以主题词的形式来表现微博话题，但是本 文对主题词采用硬划分，导致同一主题词只能属于 唯一主题。 但在真实情况下，可能多个话题含有同 一主题词，如何实现将主题词划入多个话题，有待进 一步研究。 另外，以主题词表现话题并不是特别直 观，如何实现以词组或句子表达主题，也有待进一步 研究。 参考文献： ［１］ＢＬＥＩ Ｄ Ｍ， ＮＧ Ａ Ｙ， ＪＯＲＤＡＮ Ｍ Ｉ． Ｌａｔｅｎｔ ｄｉｒｉｃｈｌｅｔ ａｌｌｏｃａ⁃ ｔｉｏｎ［Ｊ］． Ｔｈｅ ｊｏｕｒｎａｌ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｓｅａｒｃｈ， ２００３， ３ （４⁃５）： ９９３⁃１００２． ［２］ ＶＯＮ ＬＵＸＢＵＲＧ Ｕ． Ａ ｔｕｔｏｒｉａｌ ｏｎ ｓｐｅｃｔｒａｌ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ］． Ｓｔａｔｉｓｔｉｃｓ ａｎｄ ｃｏｍｐｕｔｉｎｇ， ２００７， １７（４）： ３９５⁃４１６． ［３］郭庆琳， 李艳梅， 唐琦． 基于 ＶＳＭ 的文本相似度计算的 研究［Ｊ］． 计算机应用研究， ２００８， ２５（１１）： ３２５６⁃３２５８． ＧＵＯ Ｑｉｎｇｌｉｎ， Ｌｉ Ｙａｎｍｅｉ， ＴＡＮＧ Ｑｉ． Ｓｉｍｉｌａｒｉｔｙ ｃｏｍｐｕｔｉｎｇ ｏｆ ｄｏｃｕｍｅｎｔｓ ｂａｓｅｄ ｏｎ ＶＳＭ ［ Ｊ］． Ａｐｐｌｉｃａｔｉｏｎ ｒｅｓｅａｒｃｈ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００８， ２５（１１）： ３２５６⁃３２５８． ［４］周刚， 邹鸿程， 熊小兵， 等． ＭＢ⁃ＳｉｎｇｌｅＰａｓｓ： 基于组合相 似度的微博话题检测［ Ｊ］． 计算机科学， ２０１２， ３９（１０）： １９８⁃２０２． ＺＨＯＵ Ｇａｎｇ， ＺＯＵ Ｈｏｎｇｃｈｅｎｇ， ＸＩＯＮＧ Ｘｉａｏｂｉｎｇ， ｅｔ ａｌ． ＭＢ⁃ＳｉｎｇｌｅＰａｓｓ： ｍｉｃｒｏｂｌｏｇ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｃｏｍ⁃ ｂｉｎｅｄ ｓｉｍｉｌａｒｉｔｙ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１２， ３９ （ １０）： １９８⁃２０２． ［５］郑斐然， 苗夺谦， 张志飞， 等． 一种中文微博新闻话题 检测的方法［Ｊ］． 计算机科学， ２０１２， ３９（１）： １３８⁃１４１． ＺＨＥＮＧ Ｆｅｉｒａｎ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ＺＨＡＮＧ Ｚｈｉｆｅｉ， ｅｔ ａｌ． Ｎｅｗｓ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ａｐｐｒｏａｃｈ ｏｎ Ｃｈｉｎｅｓｅ ｍｉｃｒｏｂｌｏｇ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１２， ３９（１）： １３８⁃１４１． ［６］方然， 苗夺谦， 张志飞． 一种基于情感的中文微博话题 检测方法［Ｊ］． 智能系统学报， ２０１３， ８（３）： ２０８⁃２１３． ＦＡＮＧ Ｒａｎ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ＺＨＡＮＧ Ｚｈｉｆｅｉ， ｅｔ ａｌ． Ａｎ ｅ⁃ ｍｏｔｉｏｎ⁃ｂａｓｅｄ ｍｅｔｈｏｄ ｏｆ ｔｏｐｉｃ ｄｅｔｅｃｔｉｏｎ ｆｒｏｍ Ｃｈｉｎｅｓｅ ｍｉ⁃ ｃｒｏｂｌｏｇｓ ［ Ｊ ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， 第 ３ 期 刘志雄，等：面向用户兴趣与社区关系的微博话题检测方法 ·２９９·
·300· 智能系统学报 第11卷 2013,8(3):004:208-213. [16]NEWMAN M E J.Fast algorithm for detecting community [7]Heinrich G.Parameter estimation for text analysis[R]. structure in networks J].Physical review E,2004,69 Technical report,Darmstadt,Germany:Fraunhofer IGD, (6):066133. 2004. [17]KARYPIS G,KUMAR V.Metis-unstructured graph parti- [8]乔健.面向新浪微博的链接和内容相结合的社区划分方 tioning and sparse matrix ordering system,version 2.0[Z]. 法[D].北京：北京交通大学，2015. Minnesota:University of Minnesota,Department of Com- QIAO Jian.Community detection by using link and content puter,1995:202-205. and it's application in sina microblog[D].Beijing:Beijing [18]MIMNO D,WALLACH H M,TALLEY E,et al.Optimi- Jiaotong University,2015. zing semantic coherence in topic models[C]//Proceedings [9]JIANG Yawen,JIA Caiyan,YU Jian.An efficient communi- of the conference on empirical methods in natural language ty detection method based on rank centrality[].Physica processing.Stroudsburg,PA,USA,2011:262-272. A:statistical mechanics and its applications,2013,392 [19]HU Yanqing,LI Menghui,ZHANG Peng,et al.Commu- (9):2182-2194. nity detection by signaling on complex networks[J].Physi- [10]PAGE L,BRIN S,MOTWANI R,et al.The PageRank ci- cal review E,2008,78(1):016115. tation ranking:bringing order to the Web[R].Stanford In- [20]BURK C F,HORTON F W.Infomap:a complete guide to foab,1999:189-194. discovering corporate information resources[J].Lincoln: [11]KOJIMA K.Proceedings of the fifth Berkeley symposium Prentice Hall,1988. on mathematical statistics and probability[].American 作者简介： journal of human genetics,1969,21(4):407-408. 刘志雄，1990年生，男，硕士研究 [12]MIHALCEA R.TARAU P.TextRank:bringing order into 生，主要研究领域为数据挖掘、机器学 texts[C]//Proceedings of EMNLP 2004:association for 习、复杂网络。 computational linguistics.Barcelona,Spain,2004. 13 ]CHATURVEDI P,DHARA M,ARORA D.community de- tection in complex network via BGLL algorithm[J].Inter- national journal of computer applications,2012,48(1): 32.42. 贾彩燕，1976年生，女，副教授，博 [14]ZANGHI H,VOLANT S,AMBROISE C.Clustering based 士生导师，中国人工智能学会粗糙集与 on random graph model embedding vertex features[J].Pat- 软计算专业委员会委员，主要研究方向 tern recognition letters,2010,31(9):830-836. 为数据挖掘、社会计算、文本挖掘及生 [15]XU Zhiqiang,KE Yiping,WANG Yi,et al.A model- 物信息学。近年来主持国家自然科学 based approach to attributed graph clustering[C]//Pro- 基金面上项目、青年基金面上项目各1 ceedings of the 2012 ACM SIGMOD international confer- 项；参加国家自然科学基金重点项目、科技重大专项、北京市 ence on management of data.New York,NY,USA, 自然科学基金各1项：获湖南省科学技术进步二等奖1项。 2012:505-516
２０１３， ８（３）： ００４： ２０８⁃２１３． ［７］ Ｈｅｉｎｒｉｃｈ Ｇ． Ｐａｒａｍｅｔｅｒ ｅｓｔｉｍａｔｉｏｎ ｆｏｒ ｔｅｘｔ ａｎａｌｙｓｉｓ ［ Ｒ］． Ｔｅｃｈｎｉｃａｌ ｒｅｐｏｒｔ， Ｄａｒｍｓｔａｄｔ， Ｇｅｒｍａｎｙ： Ｆｒａｕｎｈｏｆｅｒ ＩＧＤ， ２００４． ［８］乔健． 面向新浪微博的链接和内容相结合的社区划分方 法［Ｄ］． 北京： 北京交通大学， ２０１５． ＱＩＡＯ Ｊｉａｎ． Ｃｏｍｍｕｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｂｙ ｕｓｉｎｇ ｌｉｎｋ ａｎｄ ｃｏｎｔｅｎｔ ａｎｄ ｉｔ’ｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｓｉｎａ ｍｉｃｒｏｂｌｏｇ［Ｄ］． Ｂｅｉｊｉｎｇ： Ｂｅｉｊｉｎｇ Ｊｉａｏｔｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２０１５． ［９］ＪＩＡＮＧ Ｙａｗｅｎ， ＪＩＡ Ｃａｉｙａｎ， ＹＵ Ｊｉａｎ． Ａｎ ｅｆｆｉｃｉｅｎｔ ｃｏｍｍｕｎｉ⁃ ｔｙ ｄｅｔｅｃｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｒａｎｋ ｃｅｎｔｒａｌｉｔｙ ［ Ｊ］． Ｐｈｙｓｉｃａ Ａ： ｓｔａｔｉｓｔｉｃａｌ ｍｅｃｈａｎｉｃｓ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１３， ３９２ （９）： ２１８２⁃２１９４． ［１０］ＰＡＧＥ Ｌ， ＢＲＩＮ Ｓ， ＭＯＴＷＡＮＩ Ｒ， ｅｔ ａｌ． Ｔｈｅ ＰａｇｅＲａｎｋ ｃｉ⁃ ｔａｔｉｏｎ ｒａｎｋｉｎｇ： ｂｒｉｎｇｉｎｇ ｏｒｄｅｒ ｔｏ ｔｈｅ Ｗｅｂ［Ｒ］． Ｓｔａｎｆｏｒｄ Ｉｎ⁃ ｆｏＬａｂ， １９９９： １８９⁃１９４． ［１１］ ＫＯＪＩＭＡ Ｋ． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｆｉｆｔｈ Ｂｅｒｋｅｌｅｙ ｓｙｍｐｏｓｉｕｍ ｏｎ ｍａｔｈｅｍａｔｉｃａｌ ｓｔａｔｉｓｔｉｃｓ ａｎｄ ｐｒｏｂａｂｉｌｉｔｙ ［ Ｊ］． Ａｍｅｒｉｃａｎ ｊｏｕｒｎａｌ ｏｆ ｈｕｍａｎ ｇｅｎｅｔｉｃｓ， １９６９， ２１（４）： ４０７⁃４０８． ［１２］ＭＩＨＡＬＣＥＡ Ｒ， ＴＡＲＡＵ Ｐ． ＴｅｘｔＲａｎｋ： ｂｒｉｎｇｉｎｇ ｏｒｄｅｒ ｉｎｔｏ ｔｅｘｔｓ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＥＭＮＬＰ ２００４： ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ ｃｏｍｐｕｔａｔｉｏｎａｌ ｌｉｎｇｕｉｓｔｉｃｓ． Ｂａｒｃｅｌｏｎａ， Ｓｐａｉｎ， ２００４． ［ １３］ＣＨＡＴＵＲＶＥＤＩ Ｐ， ＤＨＡＲＡ Ｍ， ＡＲＯＲＡ Ｄ． ｃｏｍｍｕｎｉｔｙ ｄｅ⁃ ｔｅｃｔｉｏｎ ｉｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋ ｖｉａ ＢＧＬＬ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｉｎｔｅｒ⁃ ｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１２， ４８（ １）： ３２⁃４２． ［１４］ＺＡＮＧＨＩ Ｈ， ＶＯＬＡＮＴ Ｓ， ＡＭＢＲＯＩＳＥ Ｃ． Ｃｌｕｓｔｅｒｉｎｇ ｂａｓｅｄ ｏｎ ｒａｎｄｏｍ ｇｒａｐｈ ｍｏｄｅｌ ｅｍｂｅｄｄｉｎｇ ｖｅｒｔｅｘ ｆｅａｔｕｒｅｓ［Ｊ］． Ｐａｔ⁃ ｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｌｅｔｔｅｒｓ， ２０１０， ３１（９）： ８３０⁃８３６． ［１５］ ＸＵ Ｚｈｉｑｉａｎｇ， ＫＥ Ｙｉｐｉｎｇ， ＷＡＮＧ Ｙｉ， ｅｔ ａｌ． Ａ ｍｏｄｅｌ⁃ ｂａｓｅｄ ａｐｐｒｏａｃｈ ｔｏ ａｔｔｒｉｂｕｔｅｄ ｇｒａｐｈ ｃｌｕｓｔｅｒｉｎｇ ［ Ｃ］ ／ ／ Ｐｒｏ⁃ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０１２ ＡＣＭ ＳＩＧＭＯＤ ｉｎｔｅｒｎａｔｉｏｎａｌ ｃｏｎｆｅｒ⁃ ｅｎｃｅ ｏｎ ｍａｎａｇｅｍｅｎｔ ｏｆ ｄａｔａ． Ｎｅｗ Ｙｏｒｋ， ＮＹ， ＵＳＡ， ２０１２： ５０５⁃５１６． ［１６］ＮＥＷＭＡＮ Ｍ Ｅ Ｊ． Ｆａｓｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｄｅｔｅｃｔｉｎｇ ｃｏｍｍｕｎｉｔｙ ｓｔｒｕｃｔｕｒｅ ｉｎ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｐｈｙｓｉｃａｌ ｒｅｖｉｅｗ Ｅ， ２００４， ６９ （６）： ０６６１３３． ［１７］ＫＡＲＹＰＩＳ Ｇ， ＫＵＭＡＲ Ｖ． Ｍｅｔｉｓ⁃ｕｎｓｔｒｕｃｔｕｒｅｄ ｇｒａｐｈ ｐａｒｔｉ⁃ ｔｉｏｎｉｎｇ ａｎｄ ｓｐａｒｓｅ ｍａｔｒｉｘ ｏｒｄｅｒｉｎｇ ｓｙｓｔｅｍ， ｖｅｒｓｉｏｎ ２．０［Ｚ］． Ｍｉｎｎｅｓｏｔａ： Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍｉｎｎｅｓｏｔａ， Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍ⁃ ｐｕｔｅｒ， １９９５： ２０２⁃２０５． ［１８］ＭＩＭＮＯ Ｄ， ＷＡＬＬＡＣＨ Ｈ Ｍ， ＴＡＬＬＥＹ Ｅ， ｅｔ ａｌ． Ｏｐｔｉｍｉ⁃ ｚｉｎｇ ｓｅｍａｎｔｉｃ ｃｏｈｅｒｅｎｃｅ ｉｎ ｔｏｐｉｃ ｍｏｄｅｌｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｃｏｎｆｅｒｅｎｃｅ ｏｎ ｅｍｐｉｒｉｃａｌ ｍｅｔｈｏｄｓ ｉｎ ｎａｔｕｒａｌ ｌａｎｇｕａｇｅ ｐｒｏｃｅｓｓｉｎｇ． Ｓｔｒｏｕｄｓｂｕｒｇ， ＰＡ， ＵＳＡ， ２０１１： ２６２⁃２７２． ［１９］ＨＵ Ｙａｎｑｉｎｇ， ＬＩ Ｍｅｎｇｈｕｉ， ＺＨＡＮＧ Ｐｅｎｇ， ｅｔ ａｌ． Ｃｏｍｍｕ⁃ ｎｉｔｙ ｄｅｔｅｃｔｉｏｎ ｂｙ ｓｉｇｎａｌｉｎｇ ｏｎ ｃｏｍｐｌｅｘ ｎｅｔｗｏｒｋｓ［Ｊ］． Ｐｈｙｓｉ⁃ ｃａｌ ｒｅｖｉｅｗ Ｅ， ２００８， ７８（１）： ０１６１１５． ［２０］ＢＵＲＫ Ｃ Ｆ， ＨＯＲＴＯＮ Ｆ Ｗ． Ｉｎｆｏｍａｐ： ａ ｃｏｍｐｌｅｔｅ ｇｕｉｄｅ ｔｏ ｄｉｓｃｏｖｅｒｉｎｇ ｃｏｒｐｏｒａｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｒｅｓｏｕｒｃｅｓ ［ Ｊ］． Ｌｉｎｃｏｌｎ： Ｐｒｅｎｔｉｃｅ Ｈａｌｌ， １９８８． 作者简介： 刘志雄，１９９０ 年生，男，硕士研究 生，主要研究领域为数据挖掘、机器学 习、复杂网络。 贾彩燕，１９７６ 年生，女，副教授，博 士生导师，中国人工智能学会粗糙集与 软计算专业委员会委员，主要研究方向 为数据挖掘、社会计算、文本挖掘及生 物信息学。 近年来主持国家自然科学 基金面上项目、青年基金面上项目各 １ 项；参加国家自然科学基金重点项目、科技重大专项、北京市 自然科学基金各 １ 项；获湖南省科学技术进步二等奖 １ 项。 ·３００· 智 能 系 统 学 报 第 １１ 卷
