随着网络通信的发展,电子社交网络如Facebook,Twitter等,已成为人们日常生活中不可分割的社交渠道.为了丰富用户的Web社区生活,各社交网站推出了“社区推荐”及“好友圈”服务.由此而生的社区划分及社区推荐算法,已成为社会网络数据挖掘研究的热点.从社区划分算法的研究内容方面,可分为3个阶段:硬社区划分、重叠社区划分及语义社区划分.

其中,硬社区划分和重叠社区划分属于关系社区划分,其研究的出发点在于根据社会网络中节点的关系属性划分关系紧密“社交群落”.该领域早期的研究为硬社区划分,即,将社会网络拆分为若干个不相交的网络^{[ 1]},代表算法如GN^{[ 2]}.FN^{[ 3]}算法.随着社会网络应用的发展,社区结构开始出现彼此包含的关系,为此,Palla等人提出了具有重叠(overlapping)特性的社区结构,并设计了面向重叠社区发现的CPM算法^{[ 4]}.此后,重叠社区发现算法成为社区划分研究领域的主流,许多经典算法应运而生,如EAGLE^{[ 5]}、LFM^{[ 6]}、COPRA^{[ 7]}、UEOC^{[ 8]}、蚁群算法^{[ 9]}、拓扑势算法^{[ 10]}等.

由于社会网络的交流需要以文本作为载体,文本舆情的分类结果可指导社区的划分^{[ 11]}.为此,语义社区划分的出发点在于,根据社会网络中节点语义信息内容(如微博、社会标签等)的分类结果,将具有相似信息内容的节点划分为同一社区.由于所划分的社区结构基于信息相似性,其划分结果更能体现社区的凝聚性.由于语义信息需要以文本分析为基础,因此,目前的语义社区划分算法大多以LDA模型^{[ 12]}作为语义处理的核心模型.根据LDA模型的应用方式可分为3类.

(1) 关系语义信息的LDA分析

此类算法以网络拓扑结构作为语义对象,利用改进的LDA模型分析节点的语义相似性,将LDA分析结果作为社区推荐及社区划分参数.Zhang等人提出了SSN-LDA算法,将节点编号及关系作为语义信息内容,将节点的关系相似性作为训练结果^{[ 13]}.由于Henderson等人在SSN-LDA模型的基础上融入了IRM(infinite relational model)^{[ 14]}模型,提出了LDA-G算法.该算法有效地将LDA与图模型相结合,在社区发现的基础上可进行社区间的链接预测^{[ 15]}.随后,Henderson等人在LDA-G的基础上加入了节点多元属性分析,提出了HCDF算法,增加了社区发现结果的稳定性^{[ 16]}.Zhang等人也在SSN-LDA算法的基础上提了面向有权网络的GWN-LDA算法^{[ 17]}及面向层次化分的HSN-PAM^{[ 18]}算法.此类算法的优点在于结构模型简单,需要的信息量较少,适合处理大规模数据;缺点在于,此类算法所利用的语义信息并非文本信息,所挖掘的社区不具有文本内容相关性,属于利用语义分析的方法进行关系社区划分.

(2) 关系-话题语义信息的LDA分析

此类算法以节点的文本信息作为语义对象,将相邻节点的文本信息作为先验信息,使得LDA分析的语义相似性接近现实.此类算法大多以AT模型^{[ 19]}作为LDA分析的基本模型,代表算法有McCallum等人^{[ 20]}提出的ART模型.该模型在AT模型的基础上加入了recipient关系采样,将AT模型引入了语义社会网络分析领域.随后,McCallum等人在ART模型的基础上加入了角色分析过程,提出了RART模型,扩展了ART模型在社会计算领域的应用^{[ 21]}.Zhou等人在AT模型中加入了user分布取样,提出了CUT模型^{[ 22]}.Cha等人根据社交网络中跟帖人的topic信息抽取出树状关系模型,并利用层次LDA算法对树状关系模型中的文本信息进行建模,提出了HLDA语义社会网络分析模型.该模型可有效处理论坛类(非熟人关系)网站的用户分类问题^{[ 23]}.Nagarajan^{[ 24]}通过采集用户间传递的信息以及用户间的共享信息,建立了一种content sharing network,并提出了Link-Content model模型.该模型是一种以链接为研究对象的AT模型,在LDA取样过程中,根据链接关系加入了user选择community的过程.Sebastian^{[ 25]}以传统社会网络中的标签传播算法为基础,提出了SLTA算法.SLTA算法将话题作为标签的内容,并在标签传播的“听-说”过程中加入了LDA分析与节点关联性分析.Hu^{[ 26]}将AT衍生出FT (feature topic)和ST(social topic)模型,以用户的话题倾向属性进行社区倾向性分析.此类算法的优点在于,在节点关系基础上结合了文本信息分析,其划分的社区具有较高的内部相似性;缺点在于,此类算法仅在文本取样时考虑了网络的关系特性,缺少对网络局部社区特性的考虑,使得划分的社区结果中出现不连通的现象.

(3) 社区-话题语义信息的LDA分析

此类算法在关系-话题类算法的基础上加入了社区因素,将LDA模型从邻接关系取样转向了局部区域取样,有效避免了关系-话题类算法的局部区域不连通现象,是成熟化的语义社区划分算法.代表算法有Wang等人^{[ 27]}提出的GT模型.该模型是ART模型的扩展,将group取样替代了ART模型的recipient取样.随后,Pathak等人^{[ 28]}论述了recipient取样的必要性,并在ART模型的基础上加入了community取样,提出了CART模型.近些年来,话题-社区的关系成为LDA模型研究的重点,Mei等人将社区话题分布与社区模块度相结合,提出了TMN模型并建立了话题-社区关系函数,以指导社区的优化过程^{[ 29]}.Sachan等人和Yin等人分别从话题-社区分布和社区-话题分布角度,在社区与话题间构建关联,并将其引入了LDA模型,分别提出了TURCM^{[ 30, 31]}及LCTA模型^{[ 32]},在增加社区划分结果的话题差异性的同时,增加了社区划分结果的合理性.Zhao等人^{[ 33]}提出的EWKM(entropy weighting K-means)方法建立了节点的语义相似度矩阵,将语义社会网络量化为有权网络.此类算法的优点在于语义社区划分准确性高,缺点在于模型复杂,容易产生过拟合现象.由于LDA模型需要预先确定先验参数的维数,因此,所划分的社区个数需要预先设定,且不同的预设社区个数所产生的社区划分结果差异较大.

图1为各类基于LDA模型算法的关联关系,其中,ART强调邻居的语义信息对节点的影响,而HLDA强调全局语义信息对节点的影响.本文在二者的基础上强调社区对节点的影响,为此提出了LBT(link-block-topic)算法.LBT算法融合了ART算法recipient取样及HLDA的hierarch取样方式.由于ART算法recipient取样的影响范围较小且HLDA没有考虑距离对取样的影响,为此,本文在ART算法与HLDA算法的基础上增加了Link取样,以扩大取样的影响范围;在HLDA基础上增加了Block取样,以满足社区的局部区域特性.

语义社会网络的语义社区发现算法需要兼顾两个方面的条件:

(1) 语义社区内部链接关系紧密;

(2) 语义社区内部节点的语义信息相似度高.

为避免社区-话题LDA分析中预设社区个数的问题,本文所设计的面向语义社会网络重叠社区发现算法创新建立节点语义信息到语义空间的量化映射,通过构造语义相似度的度量,提出语义社会网络的局部社区结构S-fitness模型,并根据S-fitness模型建立了局部语义聚类算法(LSC)及评价语义社区划分结果的SQ模型.最后,通过实验分析本文算法的有效参数选取及SQ评价性能.

1 Link-Block-Topic关系建模

对于有代表性半监督语义社区发现算法,如AT,ART及HLDA分别为“点、面、放射”的形式对语义网络中的节点进行文本取样,其文本话题生成过程(以节点i,j为例)的差别如图2所示,其中,

· 图2(a)为AT模型的文本生成过程.在全局文本分析时,分别对节点i,j进行单独取样,不考虑网络拓扑的相关性,其文本生成过程以author为单位.

· 图2(b)为ART模型的文本生成过程.由于ART模型以recipient作为author的桥梁,在对节点i进行文本生成取样时,加入了i相邻节点k₁,k₂,j的取样,并在对节点i进行文本生成时加入了j相邻节点k₃,k₄,k₅,i的取样,其文本生成过程以author的中心区域为单位.

· 图2(c)为HLDA模型的文本生成过程.由于HLDA模型以分层的方式进行文本生成取样,在对节点i进行文本生成时,将与节点i直接相邻的节点k₁,k₂,j作为一次取样,与节点i间接相邻的节点k₃,k₄,k₅进行二次取样,其文本生成过程是以author的放射区域为单位;ART模型和HLDA模型是AT在网络拓扑关系中的应用,ART模型的文本生成取样区域半径为1,导致以author为中心的区域规模较小,文本生成取样结果仅代表直接邻接关系,不具有社区的规模关系特性;HLDA模型的文本生成取样过程是对放射区域的无权取样,忽略了社会网络中关系距离对社区成员间的影响.为此,本文将ART与HLDA的取样思想相结合,以link为中心的关系区域(block)作为取样区域,设计了LBT(link-block- topic)文本取样模型.

· 图2(d)为本文LBT模型的文本生成过程.在进行文本生成时,以link作为中心(如图2(d)中link_i,j),并将与link_i,j直接相邻的节点k₁~k₅作为取样节点,其文本生成过程是以link-block为单位.

本节对语义社会网络中的局部语义信息和总体语义信息的LBT建模过程进行描述,所涉及到的数学符号如下:

· G表示全局网络,G_i表示网络中的节点i.

· |G|表示语义社会网络中节点的个数.

· L表示网络G中的边(链接)集合,L_i,j表示节点G_i与节点G_j之间的边.

· |L|表示语义社会网络中边(链接)个数.

· α_L表示与本文取样链接L相邻的author节点集合.

· x表示集合α_L中抽取的一个元素.

· N表示语义社会网络中的关键字个数,N_i表示节点G_i的关键字个数.

· D表示语义社会网络中语料信息个数.

· w表示关键字的集合,w_i为集合w中第i个关键字所对应的编号.

· z表示与关键字的集合w对应的话题编号集合,z_i表示w_i所隶属的话题编号.

· T表示话题个数.

· θ表示话题分布概率.

· φ表示关键字的分布.

· α表示各节点的话题分布先验参数.

· β表示某一话题内部,关键字分布的先验参数.

图3分别为LDA,AT,ART及LBT模型的对比关系图.

其概率生成关系式如下:

· x|α_L~Uniform(α_L):表示从α_L集合中选作一个元素作为L的扩展author.

· z|θ~Multinomial(α):表示从给定的L及选定的扩展author本文信息中抽取一个话题,该话题服从以θ为参数的多项式分布.

· θ|α~Dirichlet(α):表示θ服从以α为参数的狄利克雷分布.

· w|φ~Multinomial(φ):表示话题中的关键字w服从以φ为参数的多项式分布.

· φ|β~Dirichlet(β):表示φ服从以β为参数的狄利克雷分布.

$p(\theta ,\varphi ,x,z,w|\alpha ,\beta ,L,{a_L}) = \prod\limits_{i = 1}^{|L|} {\prod\limits_{j = 1}^{|G|} {p({\theta _{ij}}|\alpha )} } \prod\limits_{t = 1}^T {p({\varphi _t}|\beta )} \prod\limits_{d = 1}^D {\prod\limits_{n = 1}^N {(p({x_{dn}}|{a_L})p({z_{dn}}|{\theta _{L,x}})p({w_{dn}}|{\varphi _{dn}}))} } $

(1)

其中,x_dn表示第d个语料信息中,第n个关键字所隶属的与L直接邻接的author号;z_dn表示在L直接相邻的节点中,第d个语料信息的第n个关键字所隶属的话题号;w_dn表示在L直接相邻的节点中,第d个语料信息的第n个关键字在语义字典中的编号.θ_L,x和φ_dn分别表示生成d个语料信息的第n个关键字时,话题z_dn及关键字w_dn出现的概率.公式(1)中,p(θ_ij|α)表示在link-block区域中话题出现的概率,p(φ_t|β)表示被选择的话题的先验参数出现的概率,p(x_dn|a_L)表示在link-block区域中某一节点的文本信息的概率,p(z_dn|θ_L,x)表示从给定的L及选定的扩展author本文信息中抽取一个话题的概率,p(w_dn|φ_dn)表示以φ为参数的关键字w出现概率.对公式(1)用积分表示形式,以消除变量θ和φ,得出LBT模型的w生成公式:

$$\eqalign{ & p(w|\alpha ,\beta ,L,{a_L}) = \cr & \int {\int {\prod\limits_{i = 1}^{|L|} {\prod\limits_{j = 1}^{|G|} {p({\theta _{ij}}|\alpha )} } \prod\limits_{t = 1}^T {p({\varphi _t}|\beta )} \prod\limits_{d = 1}^D {\prod\limits_{n = 1}^N {\sum\limits_{{x_{dn}} = 1}^{|G|} {(P({x_{dn}}|{a_L}))} \sum\limits_{{z_{dn}} = 1}^T {(p({z_{dn}}|{\theta _{L,x}})p({w_{dn}}|{\varphi _{dn}}))} } } {\text{d}}\varphi {\text{d}}\theta } } \cr} $$

(2)

经文献^{[ 21]}的推导过程可知:

$P({x_{dn}},{z_{dn}}|{x_{ - dn}},{z_{ - dn}},w,\alpha ,\beta ,L,{a_L}) \propto {{{\alpha _{{z_{dn}}}} + {n_{L,{x_{dn}},{z_{dn}}}} - 1} \over {\sum\nolimits_{t = 1}^T {({\alpha _t} + {n_{L,{x_{dn}},t}}) - 1} }}{{{\beta _{{w_{dn}}}} + {m_{{z_{dn}},{x_{dn}}}} - 1} \over {\sum\nolimits_{v = 1}^V {({\beta _v} + {m_{{z_{dn}},v}}) - 1} }}$

(3)

参数θ及φ后验估计为

${\hat \theta _{ijz}} = {{{\alpha _z} + {n_{i,x,z}}} \over {\sum\nolimits_{t = 1}^T {({\alpha _t} + {n_{L,x,t}})} }},{\hat \varphi _{tw}} = {{{\beta _w} + {m_{t,w}}} \over {\sum\nolimits_{v = 1}^V {({\beta _v} + {m_{t,v}})} }}$

(4)

其中,V为语义字典中关键字的个数,n_i,x,t表示第i号Link-Author对中属于话题t的关键字个数,m_tv表示关键字v属于话题t的个数.θ_ijz表示第i号link与author G_j的混合文本中话题z出现的概率.Gibbs取样过程如下:

initialize the author and topic assignments randomly

repeat

for d=1 to D do

for i=1 to N do

draw x_dn and z_dn from P(x_di,z_di|x_-di,z_-di,w,α,β,L,α_L)

update ${n_{L,{x_{dn}},{z_{dn}}}}$ and ${m_{{z_{dn}},{w_{dn}}}}$

end for

end for

until the Markov chain reaches its equilibrium

calculate the posterior estimates of θ and φ

2 语义链接权重的量化映射

本文为避免LDA语义分析模型中需要预先设定社区个数的问题,实现社区发现的无监督化,需要在语义网络中建立节点的量化关系,并依据量化关系建立启发式社区发现算法.为此,本节的主要内容是根据LBT模型的结果建立网络链接的语义链接权重度量,从语义关系及网络拓扑关系角度量化文本分析结果.

根据上一节的分析,对LBT模型进行Gibbs迭代取样后,可根据公式(4)计算link-author的3维话题概率分布θ_lat,其中,l表示link维度,共有|L|个不同元素;a表示与l直接相邻的author维度,共有|G|个不同元素;t表示话题维度,包含了T(话题个数)维向量.根据上一节的LDA模型分析可知,该T维向量表达了link-author的话题隶属度.由于LBT的文本生成过程是以link为核心的中心区域为单位,3维话题概率分布θ_lat中,author维度可作为link维度的从属(如图2(d)中link_i,j与k₁~k₅的关系),因此,可以以link维度作为θ_lat的主属性对topic维度进行加和消除author维度,从而将3维话题概率分布θ_lat转化为2维${\theta '_{lt}}{\rm{,}}$即${\theta '_{lt}} = \sum\nolimits_{a = 1}^{|G|} {{\theta _{lat}}} {\rm{.}}$

2维link-topic矩阵θ'中的l行元素${\theta '_{l, \cdot }},$可看作以链接l为核心的区域(l-block)在语义社会网络整体结构中的话题隶属度.为衡量各l-block的语义凝聚力,需要建立链接l的语义链接权重度量,语义链接权重较大的l-block紧致性更强,更能体现社区的结构性.在语义链接权重度量方面,链接l的话题隶属度${\theta '_{l, \cdot }}$体现了链接l在全局网络中的T维权重.为实现T维权重的可度量化,本文利用PCA主成分加权法,将矩阵θ'各行向量的相关矩阵的T个特征值所构成的向量Λ=(l₁,…,l_T)作为权重向量,将${\theta '_{l, \cdot }}$与Λ的内积作为链接l的权重W_l,由W_l所形成的邻接矩阵W即为语义网络G的语义链接权重邻接矩阵.

本文以清华大学ArnetMiner系统Quantifying Link Semantics-Publication(QLSP)数据集的部分数据为例(其中包含108篇论文、155条引用关系).本文分别在每篇论文的摘要中抽取5个关键字作为论文节点的语义信息,以话题个数T为5进行Gibbs取样迭代(所提取的话题见表1),并利用PCA加权法计算语义链接权重邻接矩阵W,其关系拓扑图及权重邻接矩阵分别如图4和图5所示.

3 Link-Block聚类算法

本节根据上一节的LBT量化分析结果,建立了以block为聚类单位的重叠社区发现算法LBTC(LBT cluster).由上一节的分析可知,link权重的大小表现了以link为核心的局部区域的语义凝聚力大小.因此,可将权重较大的link-block作为社区的基本局部块,并可将彼此关系紧密的局部块聚合为社区,从而实现社区发现.因此,经语义链接权重的量化映射所得出的语义网络G的有权邻接阵W可作为语义凝聚力大小的度量,即,W_ij表示link_i,j的link-block的语义凝聚力.量化聚类算法的描述过程,对link-block作如下定义:

定义1(核心链接). 核心链接是指link-block的中心链接如图2(d)中的链接link_i,j,link-block(i,j)表示以链接link_i,j作为核心链接的link-block.

定义2(核心节点). 核心节点是指核心链接的端点.

定义3(边缘链接). 边缘链接是指link-block中的非核心链接.

定义4(边缘节点). 边缘节点是指link-block中的非核心节点.

图6为link-block的3种相交关系示例,其中,图6(a)中link-block(2,5)与link-block(9,10)的相交部分仅含边缘节点k₇,这种情况称为边缘节点相交;图6(b)中link-block(2,5)与link-block(7,9)的相交部分包含了二者的边缘链接link_5,7,这种情况称为边缘链接相交;图6(c)中link-block(2,5)与link-block(5,7)的相交部分包含了二者的核心链接及核心节点,这种情况称为核心相交.

由于语义链接权重表达的是以该链接作为核心链接的link-block的整体语义凝聚力,可将语义链接权重较大的两个相交link-block进行聚类合并.同时,对于如图6(a)和图6(b)所示的边缘节点相交及边缘链接相交情况,两个link-block的相交部分仅含彼此的局部语义凝聚力,不体现两个link-block的共同语义凝聚力,不适合作为link-block合并的备选情况.由此,本文以核心相交的link-block作为聚类的基本单位.由于核心相交的link-block的语义凝聚力是以link-block为取样区域的LDA求解结果,其仅代表link-block区域的紧致性,无法代表link- block合并后的聚簇紧致性,为此,本文采用非增量式聚类的形式,即,聚类过程再不涉及权重的重新计算.其聚类过程如下:① 按语义链接权重对link-block进行降序排序,其结果为link-block-queue;② 从link-block-queue中选择前c个link-block,使得这c个link-block恰好覆盖整个网络;③ 以语义链接权重大小为顺序,合并c个link- block中核心相交的link-block,将各个聚类簇作为社区,并将各社区间相交的边缘节点(非核心节点)作为重叠节点.QLSP数据集的聚类过程如图7所示,其中,聚类簇c1,c2及c3即为所发现的社区,其聚类结果如图8所示.

4 语义重叠社区的评价标准

一般的社会网络重叠评价标准以节点关系结构为输入,文献^{[ 5]}所建立的重叠社区模块度EQ模型为

$EQ = {1 \over X}\sum\limits_t {\sum\limits_{i \in {C_t},j \in {C_t}} {{1 \over {{O_i}{O_j}}}\left[ {{A_{i,j}} - {{{R_i}{R_j}} \over X}} \right]} } $

(5)

其中,R_i为节点i的度数,X为网络节点的总度数,A为网络邻接矩阵,O_i为节点i所隶属的社区个数,C_t表示第t个社区.语义重叠社区需要以节点关系结构和节点语义信息作为基础,其评价标准不仅要考虑社区内部的关系合理性,而且需要考虑节点间的语义信息相似性.由语义链接权重的量化映射分析可知,节点间的语义关系可由 2维link-topic矩阵θ'及语义链接权重邻接矩阵W表达.其中,2维link-topic矩阵θ'中的元素${\theta '_{(i,j),k}}$表示链接link_i,j对第k个话题的隶属度,${\theta '_{(i,j), \cdot }}$可作为link_i,j在T维话题空间中的坐标;W_i,j表示link_i,j的语义链接权重,可作为节点i与节点j的相似度.为此,本文根据EQ模型分别以θ'及W为参数,建立可评价标语义重叠社区的模块度模型SQ1及SQ2,其表达式分别为 其中,P_(i,j)为link_i,j的度数,Y为网络链接的总度数,L为网络链接的邻接矩阵,B_(i,j)为link_i,j所隶属的社区个数,$U({\theta '_{(i,j), \cdot }},{\theta '_{(i',j'), \cdot }})$为向量${\theta '_{(i,j), \cdot }}$与${\theta '_{(i',j'), \cdot }}$的余弦相似度函数;

$SQ2 = {1 \over {2Z}}\sum\limits_t {\sum\limits_{i \in {C_t},j \in {C_t}} {{1 \over {{O_i}{O_j}}}\left[ {{W_{i,j}} - {{{S_i}{S_j}} \over {2Z}}} \right]} } $

(7)

其中,S_i为与节点i相连的所有边的语义链接权重之和,Z为网络中所有link的语义链接权重之和,W_i,j为link_i,j的语义链接权重,O_i为节点i所隶属的社区个数,C_t表示第t个社区.

5 实验分析 5.1 话题个数T取值分析

话题个数T是本文算法(LBTC)的输入参数,为验证话题个数T对语义社区划分结果的影响,本文选用如下3组数据作为测试数据:① 图4所示的清华大学ArnetMiner系统QLSP数据集;② 图9所示的Krebs建立的美国政治之书网络(Krebs polbooks network),其中,每本书的政治倾向分为3类,每类只有0或1两种选择,因此,为实现语义化模拟,将与某一节点i具有直接相邻关系(距离为1)的节点j和间接相邻关系(距离为2)节点k的信息向量之和作为节点i的信息向量;③ 图10所示的Newman建立的海豚家族(dolphins network)关系网络,为模拟语义社会网络的特性,本文实验借用polbooks网络及dolphins网络的社会关系特性,并为每个节点生成6维随机数作为节点的语义坐标.

图11为话题个数T在不同取值条件下,3组数据的社区个数、EQ、SQ1及SQ2对比结果.为对比话题个数T不同取值的语义社区划分结果,图12分别选取了3组数据在T=(6,12,18)下的社区划分结果,其中,黑色节点为重叠节点.

本实验分析了话题个数对LBTC的结果所产生的影响,从图11的对比可知:

1) 当话题个数增加时,所划分的社区个数增加.其原因在于:话题个数的增加,导致LDA取样分析的结果差异性增加,即全局的语义相似度的可区分性增加,有利于局部社区识别.

2) 当话题个数大于某一临界值时,EQ,SQ1及SQ2出现下降趋势,说明LDA分析结果存在最优取值;当话题个数小于最优值时,随着话题个数的增加,全局语义分析的结果逐渐充分;当话题个数大于最优值时,随着话题个数的增加,语义分析的结果出现“过拟合”现象,其有效性下降.

3) 不同数据集的最优话题个数取值不同,即LDA类算法的最优参数取值需要人为经验确定,该问题为LDA类算法的普遍缺陷.

5.2 SQ1 和SQ2的比较分析

本节实验以文献^{[ 34]}的有权benchmark为标准,分别生成4组节点个数为3 000,4 000,5 000,6 000的网络,其社区个数分别为215,282,348,405,并对每个链接分配5维权重数据,构造2维link-topic矩阵θ',以模拟经LDA分析后的语义量化数据.为对比SQ1及SQ2的评价性能,分别在以上4组数据中增加每个社区的内部链接(所有邻接链接均与其在同一社区的链接)的权重,以相对减少社区的边界链接(非内部链接)的权重.通过以上的权重变化,可逐步增加社区语义凝聚力,其EQ,SQ1,SQ2取值如图13所示,其中,x轴表示内部链接相对边界链接的权重倍数.

本次实验仅增加了链接权重,各组数据的社区结构无变化,因此EQ取值不变.从图13的4组数据对比可知: SQ1随着权重的增加呈收敛趋势,SQ2呈线性递增趋势,即相对于SQ1,SQ2对权重的变化更加敏感,且更加符合权重的线性递增变化.因此,从对比分析可知,SQ2相对于SQ1更适合评价语义社区结构.

5.3 重叠社区发现算法比较分析

本节实验的目的在于分析经典社区发现算法(非语义社区发现算法)在面向语义社会网络时划分结果存在的偏差,为此,本节实验仅以QLSP数据集进行举例说明.社区发现中,经典的社区发现算法包括GN,FN,LFM,COPRA,UEOC,EAGLE,CPM,其中,LFM,COPRA,UEOC,EAGLE,CPM为重叠社区发现算法.由于QLSP数据集仅包含1个clique社区(26,28,41,46,49,52),不适用于EAGLE,CPM算法,因此,本文仅对GN,FN,LFM,COPRA,UEOC算法进行求解.图14为以上各算法的社区划分结果,其中,黑色节点为重叠节点,各算法的SQ1,SQ2和EQ值见表2.

以上经典算法以链接关系优化划分为导向,从表2中的结果可分析出,经典算法的EQ值高于本文算法(0.524 6),但SQ2值均低于本文算法(0.647 6).由此验证了传统面向链接关系的社区划分算法(EQ值较高)在处理语义社区划分问题时SQ(SQ1,SQ2)值较低,所划分的社区结果与语义社区的理想结果偏差较大.

5.4 真实数据集比较

本实验以清华大学ArnetMiner系统的QLSP完整数据集(共805个节点)、Aminer-FOAF-DataSet(AFD)数据集(截取2 000个节点)、Citation Network Dataset(CND)数据集(共2 555个节点)、DBLP(April 12,2006)数据集(1 200 000个节点)中分别截取:(A) 15 000个节点数据集和(B) 20 000个节点数据集作为实验数据,分析本文算法与经典算法的比较结果.表3为各算法对上述数据集的执行结果,其中,本文LBTC算法的运行参数为T=5.

表3包括EQ,SQ1,SQ2及社区个数CS,图15~图17分别为各算法的EQ,SQ1和SQ2直方图,其中,图15的结果表示本文LBTC算法结果在EQ标准下的结果较差,而图16及图17的结果充分验证了本文LBTC算法的语义社区划分结果更精确.从图15~图17的比对可知:相较于传统经典算法,本文的LBTC算法更适合处理语义社会网络的社区发现问题.

5.5 语义社区发现算法比较分析

本节实验对比各类需要预先设定社区个数的语义社区发现算法,以语义社区发现算法中通用的Enron数据集作为实验数据集.Enron数据集是Enron公司150个用户的交互数据,共包含0.5M条数据,423M数据量.表4为经LDA分析后从Enron数据集中抽取的4组话题.表5为Enron数据集分别在TURCM,CART,CUT,LCTA算法下的EQ值及SQ(SQ1,SQ2)值,表中社区个数表示各算法执行前的社区预设数.从表4与表5的分析可知,Enron数据集社区的最佳个数为10.本文算法的社区个数为11,EQ,SQ1和SQ2取值分别为0.332,0.318和0.393.通过对比可知:本文算法的结果近于同类算法的最优值,且无需预先设定社区个数,由此验证了本文算法相对同类算法的优越性.

5.6 运行时间分析

为了分析LBTC的执行效率,本节实验对比了话题个数T与节点个数|G|对运行时间的影响.在数据集选择方面,本文利用人工数据集分别在网络拓扑关系及文本信息两方面进行模拟,其数据集生成过程如下:

(1) 在网络拓扑关系模拟方面,本实验利用LFR benchmark^{[ 34]}设计生成了21组实验数据,其参数为(|G|= {1500,3000,…,31500},ad={4,5,…,24},dmax={30,32,70},cmin={10,15,…,110},cmax={100,110,…, 300},on={100,200,…,2100},om={4,5,…,24},mi=2.5).其中,参数|G|表示节点的个数;ad和dmax分别表示网络中节点的平均度和最大度;cmin和cmax分别表示最小社区和最大社区包含节点的数量;on表示重叠节点个数;om表示每个重叠节点连接的社区个数;mi为混合系数,表示节点与社区外部连接的概率.随着mi值的增大,网络社区结构越来越模糊;当mi>0.5时,网络的社区结构非常模糊.

(2) 在文本信息模拟方面,将各节点的节点编号作为节点的关键字,以COPRA算法^{[ 7]}的方式对节点的关键字进行传播.为模拟文本信息传播的衰减过程,以公式(8)所示的拓扑势公式对节点的关键字进行加权.文本信息的模拟过程保持了节点间的文本信息的关联性与独立性,使得隶属同一社区的节点语义坐标相近似,符合语义社区结构的特性.通过文献^{[ 10]}的分析可知,公式(8)中σ的最优取值为σ$ \in $(1,2).为此,本实验中σ=1.5.

$weigh{t_{i,j}} = \exp \left( { - {{\left( {{{dis({G_i},{G_j})} \over \sigma }} \right)}^2}} \right)$

(8)

本文所采用的实验环境为:Intel(R) Pentium(R)处理器,3.0GHz CPU,4.0GB内存,160GB硬盘,Microsoft Windows 7操作系统,编程语言为Matlab R2012b.由于算法的运行时间与实验环境的相关性较大,因此,本实验将|G|={1500,3000,…,31500},T={5,10,…,55}的运行时间与|G|=1500,T=5的运行时间的比值作为分析对象,其对比分析结果如图18所示.其分析如下:

1) 节点个数对比为T={10,20,30,40,50}时,运行时间随节点个数的变化对比.从对比可知:当T不变时,其运行时间随着节点个数的增加而增加;话题个数对比为|G|={6000,12000,18000,24000,30000}时,运行时间随话题个数的变化对比,其运行时间随着话题个数的增加而增加.结合节点个数对比与话题个数对比可知:当|G|>20000,T>30时,运行时间的增加率较高,运行效率下降较快.

2) 话题时间δ为T增加5且|G|不变时,时间比值的增加量,节点时间δ为|T|增加1500且T不变时,时间比值的增加量.从图18中的话题时间δ及节点时间δ统计直方图可知:话题时间δ的分布集中在(400,1000)区间内,节点时间δ的分布集中在(0,600)区间内.由此可知,话题个数的变化对总体运行时间的影响更大.

3) 图18的3维话题个数-节点个数对比关系图直观表达了当|G|>20000,T>30时,运行时间较高且变化强烈.话题个数维度的斜率高于节点个数维度,即,话题个数T对总体的运行时间影响更大.

为对比各算法的运行效率,本文选取21组实验数据中的5组数据作为实验数据,分别对TURCM,CART,CUT,LCTA及LBTC算法在C语言平台下的时间运行进行了对比.

表6为各算法的运行时间对比结果(单位:h).从对比结果可知:由于TURCM,CART,CUT,LCTA及LBTC算法的建模方式相类似,其运行时间也基本相同.

6 结束语

本文针对一般语义社会网络社区划分需要预先设定社区个数的问题,提出了LBTC算法.该方法将语义社会网络的语义特性和社会关系特性相融合,可有效地解决语义社会网络中的重叠社区发现问题.

本文算法设计的创新思想在于提出LBT模型,并建立了以link为核心的block区域取样方法;建立了可度量link-block区域的语义链接权重方法;提出以link-block为单位的重叠社区发现聚类算法(LBTC);提出了评价语义社区划分结果的SQ1及SQ2模型.

本文算法的实验分析验证了:在面向具有语义关系的社区划分问题时,LBTC相对于经典重叠社区发现算法更有效,且对于各类语义社会网络具有普遍适用性.另外,LDA模型的缺点在于求解过程(Gibbs取样过程)复杂度较高,对大数据的应对能力较弱.为此,下一步工作拟从并行取样角度出发,结合语义社会网络的结构特性,对LDA的求解过程进行优化.