基于语义路径的异质网络社区发现方法

吴　奇,陈福才,黄瑞阳,常振超

(国家数字交换系统工程技术研究中心,河南郑州 450001)



基于语义路径的异质网络社区发现方法

吴奇,陈福才,黄瑞阳,常振超

(国家数字交换系统工程技术研究中心,河南郑州 450001)

社区发现是社会网络研究的热点问题,综合利用社会网络中不同对象间的异质信息,可以更加有效地挖掘网络中的社区结构.针对传统的社区发现方法无法有效地利用异质信息的问题,本文提出了一种基于语义路径的异质网络社区发现方法,该方法首先定义网络中的语义路径,通过语义路径来衡量不同类型对象间的异质信息相似度,然后以此构造可靠性矩阵,作为半监督非负矩阵分解的正则化约束项,进而实现异质网络的社区划分.在真实数据集上的实验结果表明,所提出的方法能够更准确地发现异质网络中的社区结构.

异质网络;社区发现;语义路径;非负矩阵分解

1　引言

随着Web2.0时代的到来,博客、微博等社交网络应用发展迅速.这些网络不仅包含不同类型的节点,还包含不同类型的关系.传统社会网络分析方法主要针对同质网络(homogenesis network),难以描述这种结构复杂的网络,针对包含多类型节点、多类型关系的异质网络(heterogeneous network)[1]的研究应运而生.目前,异质网络的研究已成为数据挖掘领域最为活跃的研究课题之一.

异质网络数据挖掘的核心研究问题之一是社区发现(community detection)[2].社区发现即根据网络包含的链接、内容等大量属性信息,对网络中功能或性质对等的潜在结构进行识别[3].挖掘异质网络中有用的、相对稳定的社区,对网络信息的挖掘、推荐及网络的演化预测具有重要的研究价值[4].

通过引入先验知识辅助社区划分,以半监督方式挖掘网络结构是目前社区发现的研究热点.Eaton和Mansbach利用统计物理中的spin-grass模型[5],将先验信息融入模块度Q的计算,辅助进行社区发现.Ma[6]等在研究对称非负矩阵分解模型时发现,预先指定部分节点信息,并将其融入邻接矩阵可以有效提高社区发现精度.Zhang[7]等扩展了这种方法,利用网络的先验信息直接修改邻接矩阵,扩展了模型的使用范围.这些方法虽然都利用网络的先验信息,进而优化社区划分,但它们只能利用同质网络中的先验知识,当网络为异质网络时,这些方法不再适用[8].因此,本文设计了一种基于语义路径的非负矩阵分解的方法(Semantic-Path Nonnegative Matrix Factorization,SPNMF),该方法利用语义路径计算异质网络中不同类型节点之间的相似度信息,以此作为社区发现的先验条件,进而指导异质网络的社区划分,提高社区发现的准确性.

2　传统非负矩阵分解方法

Lee和Seung[9]在Nature上首先提出了非负矩阵分解(Nonnegative Matrix Factorization,NMF)算法,NMF算法要求被分解的数据矩阵的元素值非负,该约束条件符合实际数据的物理属性,具有良好的可解释性和物理意义.NMF算法的目标函数为:

(1)

(2)

(3)

当且仅当W和H都是稳定点的时候,迭代停止.

Lee和Seung的NMF方法具有迭代简单,可以提取出局部特征的优点.但未对已知先验信息进行研究,算法精度不高.基于此,Yang[10]等提出了基于半监督聚类学习的NMF-LSE方法.方法假定网络数据经非负矩阵分解后,同一社区节点间的局部邻域结构能够在分解后的矩阵中保留,即高维空间中距离较近的向量映射到低维空间上时,距离依然较小.基于这一假设,方法引入正则化约束辅助NMF进行社区划分,使用式(4)衡量节点i和j的相似程度:

(4)

并进一步引入矩阵O,矩阵O的元素Oij由节点i和j的拓扑相似度确定,该矩阵可衡量节点间相似程度的可靠性:

(5)

(6)

修正后更新准则为:

(7)

(8)

NMF-LSE方法通过半监督学习方法引入了可靠性矩阵O,结合可信度参数λ,提高了NMF方法的发现精度,但该方法没考虑到异质网络中节点和链接的复杂关系,缺乏对多种属性的合理度量,该方法难以有效应用于异质网络的处理场景中.

3　基于语义路径的非负矩阵分解方法

本文提出的基于语义路径的非负矩阵分解方法SPNMF,主要针对传统NMF方法无法分析异质网络的问题,通过优化NMF-LSE方法中的可靠性矩阵O,充分利用了异质网络的语义路径先验信息,将其作为监督项,进而指导异质网络的社区划分.

3.1语义路径相似度

以论文-作者-标签网络为例,如图1所示,若以论文(P)作为中心节点,则网络(图1(a))包含2种语义路径:论文(P)-标签(L)之间的内容关系(图1(b))和论文(P)-作者(A)之间的撰写关系(图1(c)),这两种语义路径都是论文引用网络的辅助划分信息.

3.2语义路径相似度的计算

为方便模型的构建及计算,语义路径的开始节点和结束节点需设置为同类型节点,仍以论文-作者-标签网络为例,则网络的两种语义路径可以表示为图1(b)和1(c).

由于中心节点被设定为论文(P),则语义路径论文(P)-标签(L)可以表示为P-L-P,如图1(b),可以使用关系矩阵计算语义路径P-L-P之间的语义路径相似度.

定义3关系矩阵若存在异质网络,即可定义语义路径P,则语义路径P的关系矩阵可以表示为

M=UA1A2UA2A3…UAl-1Al

(9)

sim(xi,xj)M=

(10)

针对某条语义路径P-L-P而言,其关系矩阵可以表示为MPL,则两个节点之间的语义路径相似度为:

sim(xi,xj)MPLP=

(11)

定义3、定义4有其物理意义,定义3给出的关系矩阵本质上就是将网络其他类型的节点看成中心节点的特征向量,而定义4给出的语义路径相似度就是利用余弦相似度计算中心节点多种特征之间的关系相似度.由于论文标签之间没有交互关系,定义3、定义4可以较为准确地衡量标签对中心节点的影响.

论文(P)-作者(A)关于中心节点的语义路径可以表示为P-A-P,但由于论文的作者之间存在论文标签之间没有的复杂合作关系,定义3中关系矩阵并不能很好的衡量语义路径P-A-P中包含的关系.如图2所示,论文101、论文102、论文103都是关于社区发现的文章,论文104是其它领域的文章,这些论文由A、B、C、D、E五个作者完成,他们相互之间存在合作关系,但A与C、D之间并没有直接合作过,若仅依靠定义4中语义路径相似度的计算,论文101和论文103并不属于同一个研究领域,这并不符合实际划分.

针对定义3中的关系矩阵并不适合例如作者合作网络等内部存在联系的网络的问题,考虑到这种内部网络本质上是同质网络,可以使用拓扑相似性指标对该类网络进行相似度计算,采用Jaccard相似度对关系矩阵进行优化:

(12)

其中,I表示节点Xi的邻居节点的集合,J表示节点Xi的邻居节点的集合.

计算得到的节点Jaccard相似度反映了作者合作网络内部的合作关系,将这些关系融入关系矩阵M的计算中:

(13)

针对语义路径P-A-P而言,其优化的关系矩阵变为:

(14)

优化后的关系矩阵可以较为准确衡量异质网络中同类节点间的直接交互关系对语义路径的影响.仍以图2为例,优化后矩阵如图3(b),可以看出,在优化后的关系矩阵中,论文101、论文102、论文103的作者A、作者B、作者C、作者D明显特征相关,可以将论文101、论文102、论文103划为同一社区;而论文104特征继续与其他论文无关,仍被看为另一社区,划分结果与真实划分相同.

最后计算优化后关系矩阵的语义路径相似度simMj:

(15)

针对语义路径P-A-P而言,其语义路径相似度变为:

sim(xi,xj)MPAP=

(16)

3.3基于语义路径的非负矩阵分解算法

将各条语义路径相似度矩阵融合:

(17)

其中Osim表示混合语义路径相似度矩阵,Osimh表示单条语义路径相似度矩阵,l表示网络中语义路径的数量.

考虑到语义路径的关系矩阵中包含大量的特征信息,计算语义路径相似度时利用全部信息会大大增加网络的分析成本.为提高算法的运行效率,本文利用主成分分析法(Principal Components Analysis,PCA)对网络各条语义路径的关系矩阵进行降维处理[11].此外,为提高相似度计算速度,算法采用随机映射方法[12],将节点特征映射为哈希信号,在哈希信号空间中计算节点的特征相似度.

计算得到的混合语义路径相似度矩阵即为NMF-LSE方法的可靠性矩阵O,利用该矩阵,可以充分利用网络的先验信息,进而监督异质网络的社区划分.SPNMF算法流程及相关说明如下:

算法1基于语义路径的非负矩阵分解算法(SPNMF)

输入:异质网络G,社区个数K,参数λ;

输出:基矩阵W,隶属矩阵H;

Step1:根据式(9)、式(13)计算M;

Step2:M←PCA(M)

Step3:根据式(10)计算simM;

Step4:根据式(15)计算simMJ;

Step5:根据式(17)计算O;

Step6:由K-Means方法初始化W,H;

Step7:由式(7)更新W;

Step8:由式(8)更新H;

Step9:根据式(6)计算F(H|X,O);

Step10:判断式(6)是否收敛,若不收敛,则返回Step7;否则转入Step11;

Step11:输出W,H.

其中,步骤6中非负基向量组W,H利用K-Means方法进行聚类初始化.设W0和H0分别为K-Means对邻接矩阵X的行与列的聚类结果.使用W←W0和H←H0来初始化W和H.

分步分析算法的时间复杂度.步骤2的复杂度为O(N×d),d为标签特征数;步骤3～5的最大复杂度为O(N×|Γi|×ln|Γi|),|Γi|为节点i的邻居节点个数,|Γi|一般远小于节点个数N;步骤6～10的复杂度为O((NK+M)K),M为边的个数.算法总复杂度为O(TN2K),T为迭代次数.

4　实验结果与分析

本节首先给出实验数据集来源以及验证方案,而后进行了三类实验:

(1)分析了可信度参数λ选择对算法精度的影响;

(2)分析了关系矩阵特征维数对算法性能的影响;

(3)验证SPNMF算法和NMF-LSE算法具有近似的运行速度的同时,SPNMF算法的社区划分精度相对于NMF-LSE算法有大幅度的提升.

4.1实验相关说明

(1)数据集

为了验证SPNMF算法在异质网络上的有效性,实验采用两种真实网络进行验证:

(a)Cora论文引用数据集[13],该数据集由30714篇学术论文、20224位作者以及17265个关键字组成,共包含7个研究领域:案例学习、遗传算法、神经网络、概率方法、增强学习、规则学习、理论研究.数据集存在关键字(K)、作者(A)和论文(P)这三种节点,实验选择论文作为中心节点,辅助利用论文-作者撰写网络和论文-关键字标签网络,对论文网络进行划分,划分所需要的语义路径分别为P-K-P和P-A-P.

(b)Digg数据集[14],Digg是集合了新闻信息和社交信息的网站,用户可以在该网站上发布、评论新闻,也可以在网站上进行交友活动.Digg数据集由9583个用户节点,44005条新闻和8596个关键字组成,共包含4个兴趣小组:游戏小组、政治小组、体育小组和商业小组.数据集中的3类节点可表示为:用户(U)、新闻(N)和关键词(K),实验选择用户作为中心节点,辅助利用用户-新闻关注网络和新闻-关键词标签网络,对用户网络进行划分,划分所需要的语义路径分别为U-N-U和U-N-K-N-U.

(2)度量标准

由于实验选择的数据集社区结构已知,这里采用两种通用的评价指标来衡量各种聚类算法的聚类质量.

定义5聚类准确率(clustering accuracy)定义为

(18)

定义6标准互信息(Normalized Mutual Information,NMI)定义为:

(19)

4.2实验及结果分析

(1)可信度参数选择

为了分析可信度参数λ对算法划分质量的影响,从0至3按照0.3为步长,调整参数λ的值,分析NMI值的变化.结果如图4所示.

从图4中可以看出,当没有任何语义路径信息,即λ=0时,算法变为标准NMF算法,社区划分效果较差.随着λ的增长,大量语义路径信息被加入,算法的划分效果有明显提高.但无论是Cora数据集还是Digg数据集,当λ=1.8时,算法的划分效果开始下降,这是由于过量的语义路径信息会降低网络中心节点本身结构信息的重要性,进而影响社区划分.在以下实验中.算法的可靠性参数均设为λ=1.8.

(2)关系矩阵特征维数的选择

由于数据集中各语义路径的关系矩阵的行向量包含大量特征元素,全部计算会大大增加运算成本,实验中采用PCA方法对这些特征集合进行降维,其中特征信息保留多少主成分元素,取决于保留部分的累计方差在方差总和中所占百分比.本文选取百分比为85%时的主成分信息作为特征信息,其中,Cora数据集中语义路径P-K-P关系矩阵的行向量特征由17265维降为6300维,语义路径P-A-P关系矩阵的行向量特征由20224维降为7000维.Digg数据集中语义路径U-N-U关系矩阵的行向量特征由44005维降为7200维,语义路径U-N-K-N-U关系矩阵的行向量特征由8596维降为3500维.

图5表示Cora数据集中两条语义路径P-K-P和P-A-P的关系矩阵经PCA特征降维后SPNMF算法的准确率和运行时间,图6表示Digg数据集中两条语义路径U-N-U和U-N-K-N-U的关系矩阵经PCA特征降维后SPNMF算法的准确率和运行时间.图5和图6表明,对数据集中关系矩阵的行向量特征进行合理的降维,可以有效减少噪声特征对算法划分的影响,在保证算法精度的同时,大大提高算法的运行时间.

(3)实验结果

为了验证算法的有效性,算法与经典K-Means算法,NMF算法和NMF-LSE算法对比,其中经典K-Means算法和NMF算法只分析同质网络,算法只对Cora数据集中的论文网络和Digg数据集中的用户网络进行划分;NMF-LSE算法通过引入半监督学习的方法,利用网络拓扑构建可信度矩阵,辅助对论文网络和用户网络进行划分;SPNMF算法利用各类节点与关系信息,可以综合网络的异质信息构建可信度矩阵,进而对论文网络和用户网络进行划分.

实验利用方法[15]得到论文网络和用户网络的社区数量,该方法已被证明可以很好地预测网络社区数.实验在数据集上运行5次,计算度量指标的均值.4种算法的运算时间、聚类准确率和标准互信息如表1所示.

表1　真实网络数据集中4种算法的性能

从表1中可以看出,运算时间方面,K-Means聚类速度最快,在四种方法中运行时间最短;而其余三种算法都应用了非负矩阵分解的方法,涉及到大量的矩阵乘法迭代运算,计算复杂度较高,其中NMF算法的运算时间最短,SPNMF与NMF-LSE算法的时间复杂度类似,SPNMF的运行时间相对较短,表明充分利用异质网络的先验信息可以提高算法的运行效率.

准确率方面,K-Means和NMF两种方法的聚类质量一般都比较差,因为它们都没有利用异质网络中蕴含的结构信息.NMF-LSE算法比单纯的NMF算法性能略优,这是因为NMF-LSE算法引入了先验信息,使用半监督学习的方法指导网络的社区发现.SPNMF算法的准确率比其他三种算法都要高,表明适当利用异质网络中多种节点间的关系信息,可以有效提高算法的精度.

5　结束语

异质网络中存在多种不同属性的节点和关系信息,迫切需要新的方法应对这种需求.本文提出了一种新的异质网络社区发现方法,该方法有效融合了语义路径和非负矩阵分解方法,利用异质网络中不同类型节点之间的语义路径相似度,得到其社区划分的先验信息,精确指导社区划分.算法适用于异质网络,可以提高社区划分的精度,并通过对比实验验证了算法的有效性.目前,算法的计算复杂度仍然较高,如何优化算法,使算法适用于大规模网络的分析是本文下一步的研究内容.

[1]Jiang F,Hong X,Peng Z,et al.Finding dimensions for text based on heterogeneous information network[A].International Conference on Software Engineering and Service Science[C].Beijing:IEEE,2014.819-823.

[2]程学旗,沈华伟.复杂网络的社区结构[J].复杂性系统与复杂性科学,2011,8(1):57-70.

CHENG Xue-qi,SHEN Hua-wei.Community structure of complex networks[J].Complex Systems and Complexity Science,2011,8(1):57-70.(in Chinese)

[3]柴变芳,贾彩燕,于剑,等.融合内容和链接的网络结构发现概率模型综述[J].小型微型计算机系统,2013,34(11):2524-2528.

CHAI Bian-fang,JIA Cai-yan,YU Jian,et al.Survey of probabilistic models combining content and link for network structure detection[J].Journal of Chinese Computer Systems,2013,34(11):2524-2528.(in Chinese)

[4]张伟哲,王佰玲,何慧,等.基于异质网络的意见领袖社区发现[J].电子学报,2012,40(10):1927-1932.

ZHANG Wei-zhe,WANG Bai-ling,HE Hui,et al.Public opinion leader community mining based on the heterogeneous network[J].Acta Electronica Sinica,2012,40(10):1927-1932.(in Chinese)

[5]Eaton E,Mansbach R.A spin-glass model for semi-supervised community detection[A].Twenty-Sixth AAAI Conference on Artificial Intelligence[C].Toronto:AAAI,2012.900-906.

[6]Ma X,Gao L,Yong X,et al.Semi-supervised clustering algorithm for community structure detection in complex networks[J].Physica A:Statistical Mechanics and Its Applications,2010,389(1):187-197.

[7]Zhang Z Y.Community structure detection in complex networks with partial background information[J].Europhysics Letters,2013,101(4):005-021.

[8]Meng Q,Tafavogh S,Kennedy P J.Community detection on heterogeneous networks by multiple semantic-path clustering[A].International Conference on Computational Aspects of Social Networks[C].Porto:IEEE,2014.7-12.

[9]Lee D D,Seung H S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.

[10]Yang L,Cao X,Jin D,et al.A unified semi-supervised community detection framework using latent space graph regularization[J].IEEE Transactions on Cybernetics,2014,PP(99):1-14.

[11]柴变芳,赵晓鹏,贾彩燕,等.内容网络广义社区发现有效算法[J].计算机科学与探索,2014,8(9):1076-1084.

CHAI Bian-fang,ZHAO Xiao-peng,JIA Cai-yan,et al.An efficient algorithm for general community detection in content networks [J].Journal of Frontiers of Computer Science and Technology,2014,8(9):1076-1084.(in Chinese)

[12]Charikar M S.Similarity estimation techniques from rounding algorithms[A].Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing[C].Quebec:ACM,2002.380-388.

[13]McCallum A K,Nigam K,Rennie J,et al.Automating the construction of internet portals with machine learning[J].Information Retrieval,2000,3(2):127-163.

[14]Lin Y R,Sun J,Sundaram H,et al.Community discovery via metagraph factorization[J].ACM Transactions on Knowledge Discovery from Data,2011,5(3):1284-1310.

[15]Hopcroft John,Khan Omar,Kulis Brian,et al.Tracking evolving communities in large linked networks[J].PNAS,2004,101(1):5249-5253.

吴奇男,1991年生于江苏徐州.现为国家数字交换系统工程技术研究中心硕士研究生.主要研究方向为复杂网络和社区发现.

E-mail:wqstudyy@126.com

陈福才男,1974年生于江西高安.现为国家数字交换系统工程技术研究中心研究员、硕士生导师.主要研究方向为大数据处理.

E-mail:13503827650@139.com

Community Detection in Heterogeneous Network with Semantic Paths

WU Qi,CHEN Fu-cai,HUANG Rui-yang,CHANG Zhen-chao

(NationalDigitalSwitchingSystemEngineeringandTechnologicalR&DCenter,Zhengzhou,Henan450001,China)

Community detection is an important and crucial issue in social networks.Using different objects’ information can help detect the community structure.However,many existing community detection methods are hardly applied in heterogeneous networks.To address the above problem,we propose a semantic-path based community detection method.This method first calculates the similarity matrix based on semantic paths,obtaining the reliability matrix to build a graph regularization term.Then the nonnegative matrix factorization is employed to achieve the community detection in heterogeneous networks.Simulation on real web data demonstrates that our proposed algorithm can detect the community structure in heterogeneous networks.

heterogeneous network;community detection;semantic path;nonnegative matrix factorization

2015-04-28;修回日期:2015-07-16；责任编辑：覃怀银

国家科技支撑计划(No.2014BAH30B01)

TP393

A

0372-2112 (2016)06-1465-07