APP下载

基于CW_UEOC社区检测算法的共词聚类研究

2022-03-08牛奉高邰志琴许超

关键词:聚类节点算法

牛奉高,邰志琴,许超

(山西大学 数学科学学院,山西 太原 030006)

0 引言

随着现代科学的发展,跨学科研究逐渐增多,学科交叉情况日益突出,科学体系日益复杂,预测和评估新的学科生长点越来越困难[1]。为了正确制定科学发展政策,规避科研投资风险,准确把握科学发展方向,挖掘潜在知识,分析科学知识网络的结构特征及其演化过程,我们还需要将目光关注在由文章关键词及其共现关系形成的共词网络上[2]。

共词分析主要是利用关键词和文献的共现关系,通过相似度度量反映关键词间的亲疏关系,以此为基础进行聚类分析,解读研究领域内的主题热点,分析学科的发展趋势。在关键词共现网络中,关键词相互关联,具有普遍意义的网络拓扑结构,随着复杂网络的逐渐成熟,越来越多的人借用复杂网络的方法来分析共词网络[3]。本文主要针对基于共词分析的聚类过程中没有统一的标准确定分类数目,关键词只能划分为一类的不足,基于复杂网络中的UEOC社区检测算法(unfold and extract overlapping communities)上进行改进,提出了应用于共词分析的CW_UEOC社区检测算法,通过实证,验证了算法的合理性,其结果也从侧面反映了该学科近年来的研究热点和动向,为今后该学科的研究提供了一定的参考价值。

本文第1部分对国内外关于共词分析和社区检测的相关研究进行介绍;第2部分综述共词网络的产生和UEOC社区检测算法;第3部分介绍本文提出的CW_UEOC社区检测算法;第4部分进行实证分析并结合战略坐标方法进行讨论;第5部分进行总结并给出下一步的研究工作。

1 国内外研究现状

共词分析的研究已经有很多相关研究工作,其最早由Callon和Courtial等人提出,其目的是深入文献内部[4]。在实际应用中,共词分析的流程可以概括为以下4个步骤:确定研究领域,提取关键词;构建共词矩阵,进行相似度测量;使用聚类算法,进行聚类分析;对聚类结果进行人工解读。作为一种研究方法,共词分析存在很多不足,虽然共词分析每个环节都需要改进,但是国内外研究人员对共词分析的研究主要集中在两个方面:一是基于关键词的选择和优化,一是共词聚类方法的改进。Persson对关键词的数量进行了划定,认为进行共词分析的关键词数量最好是40个~50个左右[5];杨爱青等提出将g指数作为关键词的选取指标[6];胡昌平等引入词语贡献度作为新的特征词选择方法[7];朱梦娴等引进Blondel社区检测算法进行关键词聚类,引入Z-value确定核心关键词[8];孙海生引入连边社区检测算法作为新的共词聚类方法[3];李纲等基于低频词、高频词、突发词提出三种关键词混合选择策略作为新的主题词的选择方法[9];虞秋雨等基于词频g指数构建了一种确定高频关键词阈值的方法[10]。

与本文相关的研究还包括复杂网络中社区检测算法的研究,社区检测是利用复杂网络拓扑结构中所蕴藏的信息从复杂网络中解析出其模块化的社区结构,挖掘复杂网络中的社区结构是复杂网络研究的基础性问题。在非重叠社区检测算法中,学者们依据对节点集采用的划分标准不同将目前流行的社区检测算法大致划分为以下四类:模块度优化算法、谱分析法、信息论方法、标签传播方法[11]。基于模块度Q值优化问题提出的算法是目前研究最多的一种算法[12]。2002 年,Newman 等[13]基于模块度的优化提出了自顶向下的分裂算法GN算法,2005年,Duch等[14]利用模块度提出直接寻优法——EO算法,2008年,Blondel等[15]基于模块度提出了自底向上的图凝聚算法Louvain算法,2017年,Pramanik等[16]提出了一种多层模块度指标QM,通过最大化该指标来衡量多层网络中社区的质量,该方法无须输入参数就能获得较好的社团结构。基于模块度优化的算法能够较为准确的识别网络中的社区结构,但是计算复杂度偏高,当网络的规模变大时,搜索空间将会变得非常大。谱分析法主要基于特定图矩阵的特征向量导出节点的特征,将节点对应的矩阵特征分量看作空间坐标,将网络节点映射到多维特征向量空间中,运用传统聚类方法将节点聚成社区。2004年,Donetti等[17]基于节点间的距离度量,在多维特征空间中建立聚类树图,选择全局模块度最大的聚类作为社区检测结果。从信息论方法考虑,Rosvall等[18]提出将网络的模块化看作对网络拓扑结构的一种有损压缩,从而将社区检测问题转换为寻找信息损失最小的问题。复杂网络的边是个体之间的信息传播的途径,基于节点标签按照相似度传播给相邻节点的思想,Raghavan等[19]提出一种快速标签传播算法(LPA算法)。2019年,Alimadadi等[20]提出了多层网络上的节点相似性度量,将单层网络标签传播算法扩展到多层网络中,该方法可以快速地挖掘出多层网络中的社团结构。然而,在现实世界中的网路模块并不总是分明的,因而许多研究者们提出了重叠社区检测算法。Xie等[21]提炼出14种重叠社区检测算法,并将算法分成5类,分别为团渗透算法(Clique Perco⁃lation Method)[22-23],边分割(line Partitioning),基于代理和动态算法(Agent based and Dynamic Al⁃gorithms)[24],局部扩展与优化(Local Expansion and Optimization)。以及模糊检测(Fuzzy Detec⁃tion)[25]。本文使用的重叠社区检测算法属于代理和动态算法,本文第2、3部分将详细介绍相关算法。

2 研究方法

2.1 共词网络概述

共词网络是由文章关键词与关键词之间的共现关系共同构成的一类表达科学知识领域结构的客观知识网络[1]。然而我们获得的初始数据通常是文章-关键词的二模网络。从文章-关键词的二模网络到我们所需的关键词-关键词一模共现网络的基本构建过程如图1所示。图1中存在 I、II、III、IV 四篇文章,分别拥有 3、4、4、3个关键词。我们将每一个关键词视为节点,利用在同一篇文献中产生的共现关系形成连线,这样我们就构成了共词网络。

图1 共词网络的基本构建过程模型Fig.1 Basic construction process model of the coword network

2.2 UEOC社区检测算法概述

社区是网络科学中的重要概念,社区是这样一些节点的集合:社区内部节点联系紧密,而社区间的联系远少于社区内部。2011年,Jin等人[24]在马尔科夫随机游走的基础上提出了在复杂网络上发现重叠社区的UEOC算法,社区检测基于最小化AC值(average conductance)上[26],实验结果表明,UEOC可以有效地发现重叠社区。

UEOC社区检测算法思想是:S1:选取度最大且未归属社区的节点s;S2:利用结合了退火网络约束策略的马尔科夫随机游走思想展开节点S的自然群落;S3:基于最小化连通度(con⁃ductance函数)的截断准则,提取出截断点之前的节点,将这些节点视为一个社区;S4:若仍有未归属给任何社区的节点,从S1重复,直到每个节点都有归属的社区。

UEOC社区检测算法的核心是展开(Unfold⁃ing a community)和提取(Extracting the emerged community)社区,S2和S3分别是用来展开和提取社区的方法。

2.2.1 展开社区的思想

a)计算转移概率,其计算方式由式(1)所示:

b)考虑同分布的退火网络R,计算退火网络的转移概率,其计算方式由式(2)所示:

2.2.2 提取社区的思想

a.将关联概率为0的节点从排序后的节点表L中删除;

b.计算节点表L中每个节点的连通度(conduc⁃tance函数值)φ(S)。φ(S)由式(5)可得:

连通度表示社区外连接边的个数与社区内节点度总和的比值。而截断准则要求在最小连通度处(社区之间的连接比社区内的连接的值最小)进行截断,将切割点前的节点序列构成一个社区。再从社区外的点选取度最大的节点重复实验,直至所有节点都被划分到特定社区中。

3 CW_UEOC社区检测算法

我们将改进的共现加权UEOC社区检测算法(Co-occurrence weighting unfold and extract overlap⁃ping communities)命名为CW_UEOC社区检测算法。CW_UEOC社区检测算法的核心仍然是展开和提取社区。CW_UEOC社区检测算法在展开社区部分b~e部分pij替换成我们的共现加权权重cwij。再按照以下步骤进行社区检测:S1:选取度最大且未归属社区的节点s;S2:使用替换后的共现加权权重cwij结合约束策略的马尔科夫随机游走展开节点S的自然群落;S3:基于最小化连通度的截断准则,提取出截断点之前的节点,将这些节点视为一个社区;S4:若仍有未归属给任何社区的节点,从S1重复,直到每个节点都有归属的社区。

我们使用AC值评估社区检测算法性能,其计算由式(8)可得:

其中K:社区数量,Ci:第i个社区,φ(S):社区S的连通度。由于AC值表示社区间连接与社区内节点连接的比值,故AC值越小社区检测算法性能越好。我们选择使AC值最小的转移步数l。

4 实证分析

4.1 数据来源与处理

本文选取了web of science核心合集上2016-2020年五年间的Information Science&Library Sci⁃ence领域上JCR(期刊影响因子)排名前5的期刊的文献题录数据作为研究对象,其检索式如表1所示,研究过程中使用R语言的bibliometrix包[28],共计发文总数1 492 篇。设 D={D1,D2,…,Dn},其中 Di代表每篇文章,Di={AU,DE,ID,…,JI,…,PY},每个字段分别表示作者、关键词、补充关键词、期刊、出版年等。

表1 文献数据检索式Table 1 Formula for retrieving literature data

4.1.1 核心关键词选取

我们对获得的1 492篇文献数据作为研究对象,统计显示,这1 492篇文章共包含5 785个唯一关键词,共出现了9 147次,这意味着平均每篇文章的关键词为6.13个。

在统计了所有词汇的词频后,我们分析了他们的分布情况,如图2所示(图2中的横纵坐标均为对数坐标),由于关键词词频对数分布符合线性分布,表明所有关键词的词频分布符合幂律分布(p<2e-16)。这意味着词汇中存在少量且核心的关键词,这些关键词是科学知识发展的关键概念,具有重要的研究价值。我们使用词频大于10的关键词,其累计频次为14.58%,如表2所示。

图2 关键词词频对数分布Fig.2 Logarithmic distribution of keyword frequency

4.1.2 核心关键词共词网络

在复杂网络中常用的三个分析指标:密度、聚集系数和平均距离。而由表2关键词所构建的共词网络其密度、聚集系数和平均距离等统计结果由表3所示。统计显示核心关键词共词网络其聚集系数为0.277 5,大于其对应的随机网络,而网络的平均距离为1.997 3,与对应的随机网络的平均距离差别不大,这一结果表明共词网络具有小世界现象[29]。统计还显示该网络的密度是0.159 6,这表明该网络是十分稠密的网络,网络内的连接比较丰富,这意味着情报学与图书馆学研究已经趋于成熟。

表2 词频大于10的核心关键词Table 2 Core keywords with word frequency greater than 10

表3 共词网络的特征指标Table 3 Characteristic indexes of co-word networks

4.2 结果与分析

4.2.1 基于CW_UEOC社区检测算法的共词分析结果

为了可视化分析核心关键词共词网络的结构特征,由表4可得,当l=16时,算法收敛,且可得l=3时,其AC值最小,故令CW_UEOC算法的转移步数l=3,利用R语言绘制基于CW_UEOC社区检测算法得到的节点聚类可视化图(关键词序号与对应关键词如表2所示),如图3所示,共6个社区。图中归属于同一社区的节点使用同一颜色,重叠节点则属于多个颜色,可以看出近年来学科交叉,学科融合是情报和图书馆学科领域的发展趋势。根据社区检测结果,情报学与图书馆学的热点问题归纳为:①社会媒体与情感分析;②大数据与计算机技术;③计算机技术与物联网;④社交网络与物联网;⑤社交媒体与信息技术;⑥人工智能与电子商务。

表4 转移步数l与社区Table 4 Transfer steps l and community

在复杂网络中,重叠节点往往具备多种功能,在社团间往往起着枢纽作用,共词网络节点的重叠性,恰能反映主题归属的多样性,算法的结果表明有55个节点属于重叠节点,有6个重叠社区。其中节点归属最多的节点同时属于4个社区,同时归属于4个社区的节点有节点20、31、34、35、42、61(即MANAGEMENT、TECHNOLOGY、PRIVACY、INTERNETOFTHINGS、AFFORDANCES、CROWDFUNDING)。显然,图3显示CW_UEOC社区检测算法可以发现共词网络中节点的重叠。

图3 关键词节点聚类Fig.3 Keyword node clustering

4.2.2 实验结果对比

我们使用基于walktrap社区检测算法的战略坐标分析来扩展我们对情报学与图书馆学主题的分析,战略坐标系方法是Law等人最先提出,用来描述某一研究领域内部联系情况和领域间相互影响情况[30]。在战略坐标图中,关键词与其他类别关键词共现强度的总和为向心度值(centrality);关键词与同类其他关键词共现强度的总和为密度值(densi⁃ty),以向心度和密度分别为X轴和Y轴,以密度和向心度的平均值为原点绘制战略坐标图,分析情报学和图书馆学的热点方向,图4是基于walktrap社区检测算法的战略坐标分析。战略坐标将关键词划分为四个象限,用来描述各主题的研究发展状况。处于第一象限的关键词,其密度和向心度都较高,主题内部连接紧密,且与其他类别的联系也更大,研究趋向成熟,并且处于研究网络的中心位置。处于第二象限的关键词,主题领域内部连接紧密,其研究已经形成了一定的规模,有很多外围的社会组织加入研究,属于前沿研究领域。处于第三象限的关键词其密度和向心度都较低,是整个领域的边缘主题,研究尚不成熟。处于第四象限的关键词结构不紧密,研究尚不成熟,但研究人员都有兴趣,具有潜在的发展趋势[31-32]。

如图4所示,关键词17、20、31、34、35、37、42、45、46、47、48、49、54、55、59、61、66、67、72、75、77处于第一象限,其研究趋向成熟,而且由于在第一象限的关键词其向心度也高于其他关键词,更容易与其他类别产生交叉,而基于CW_UEOC社区检测算法共词分析聚类结果中同时归属于4个社区的节点也同样处于战略坐标图的第一象限,此外,图4第一象限中也存在一部分有CW_UEOC社区检测算法中识别的重叠数目为3的节点。对比可得,基于CW_UEOC的共词聚类算法识别的重叠节点同样是walktrap算法中向心度高的节点,即基于CW_UEOC的社区检测共词聚类算法可以识别出学科交叉节点。

图4 战略坐标图Fig.4 Strategic coordinate diagram

5 结论

本文利用web of science数据库中Information Science&Library Science领域上JCR排名前5的期刊的文献题录数据进行数据提取以后,得到了情报学与图书馆学领域的核心关键词,在对核心关键词进行社区检测后,得到情报学与图书馆学领域研究主题。实证表明,CW_UEOC算法能够检测出共词网络中的热点问题,并且可以识别出社区之间的重叠节点,可以解决共词分析聚类中关键词归属单一化问题,揭示重要关键词与各个主题之间的联系。

本文在研究过程中存在一些不足,虽然文章关键词都是研究者们认真选择可以代表其研究内容的技术术语,然而也有很多潜藏在文章中未被标引出的关键词。另外,本文使用的共词网络是静态网络,但是科学知识的增长是动态过程。下一步,我们将改进选取文章主题词和提取关键词间共现关系的增长规律以此构成更加丰富的共词网络。这些改进对研究者们进行学科热点挖掘、文本聚类精确化和科学发展具有重要意义。

猜你喜欢

聚类节点算法
一种傅里叶域海量数据高速谱聚类方法
哪种算法简便
基于图连通支配集的子图匹配优化算法
一种改进K-means聚类的近邻传播最大最小距离算法
AR-Grams:一种应用于网络舆情热点发现的文本聚类方法
结合概率路由的机会网络自私节点检测算法
面向复杂网络的节点相似性度量*
采用贪婪启发式的异构WSNs 部分覆盖算法*
Travellng thg World Full—time for Rree
进位加法的两种算法