新闻信息处理技术：挖掘和监控社团话题的互动模型研究

社团的概念来源于社会网络。通常，社会网络被认为是一种典型的复杂网络，它由社会实体（比如人、机构等）和实体之间的关系组成。社团挖掘（Community Mining，CM）旨在发现社会网络中在某些方面具有相似特点（如有共同的兴趣、话题）的实体组成的相对独立和封闭的团体（即社团）。话题监控，又称话题识别与跟踪，目前的研究也只局限在文本内容变化的识别上，除了在网络新闻上小范围的应用外，还未在海量数据（如整个社会网络）中应用。

互联网是当代社会网络最有特色的载体，它大大加深了社团的复杂性、隐蔽性和动态性，对已有的社团挖掘技术提出了新的挑战；同时，话题的产生和散布有了更强大的载体，这对已有的话题监控技术也提出了新的挑战。目前社团挖掘和话题监控的研究基本是各自独立进行的。本节内容充分考虑了社团和话题两者之间的密切关系，比如具有类似模型、互为对方特征、互为对方因果，以及社团为话题传播的载体等，提出了新的社团挖掘和话题监控的互动模型，使这两种技术更适于在互联网环境下的应用^[18]。

1.研究现状和相关工作

社会网络和社团挖掘的研究一般都采用图作为它们的数学模型。社团是社会网络中满足一定条件（称为社团条件）的一部分，可以用社会网络的子图来表示社团。社团挖掘的任务就是发现社会网络大图中满足社团条件的子图。因此，社团挖掘问题可以归结为子图挖掘以及搜索问题。目前的社团挖掘算法可以归纳为三大类：

（1）基于链接分析的算法，以HITS算法为代表；

（2）基于图论的方法，以最大流算法为代表；

（3）基于聚类的方法，以GN算法为代表。

话题识别与跟踪同前使用最普遍的算法步骤大致如下：

以输入一个新闻报道序列d₁，d₂，…为例，

（1）首先进行初始化，将第一个报道d₁，归为话题t₁；

（2）假设算法已经处理完前面i-1个报道，并且已经发现了k个话题，记为t₁，t2，…，tk，那么处理第i个报道d_i的方法如下：

1）计算报道d_i与每个话题的相似度，比如用sim（d_i，t_j）表示报道d_i与话题t_j（j=1，2，…，i-1）的相似度。

2）将计算出来的相似度sim（d_i，t_j）分别与预先没定的两个阈值TH_l和TH_h做比较：

①若sim（d_i，t_j）<TH_l，则报道d_i与话题t_j不相关；

②若sim（d_i，t_j）≥TH_h，则报道d_i与话题t_j相关，将d_i归为t_j；

③若TH_l≤sim（d_i，t_j）<TH_h，则报道d_i与话题t_j之间的关系不能确定。

（3）反复采用上面的方法，直到处理完所有报道。

目前的各种TDT算法大体是上述算法的变体，主要研究不同之处集中在话题的定义、向量空间模型以及数据类型等方面。另外，还有少数研究者引入支持向量机、最大熵、核回归等其他机器学习方法，但都没有取得显著的效果。

严格说来，目前还没有明确提出将两者结合起来的相关工作，不过出现了少量初浅的研究，简述如下：参考文献[13]的研究内容是，在不同时期采用相同的主题进行社团挖掘，然后对比挖掘结果，新结果中的新内容就视为那个时期的一个话题。参考文献[14]运用社群图和矩阵法对网络社会群体进行了分析，概括出BBS社团的基本特征，并对社团中成员地位的形成、意见领袖的特点和群体内部人际交往的特征进行了探讨。

2.社团挖掘和话题监控结合的基本思想

不同于已有的研究，本文认为社团和话题之间具有密切的关系，比如：

（1）具有类似模型。一个社团是多个相似实体凝聚的结果，一个话题是多个相似议论（网络文档）汇集的中心思想，因此两者都与采用相似性比较、关联性推理和聚类算法的模型相关。

（2）互为对方特征。一方面，特定社团往往具有特定的、代表性的话题；另一方面，有了共同话题的社会人员会形成新的社团。一个社团可以被一组特定话题完全定义，一个话题也可以被一组特定社团清楚刻画。

（3）互为对方因果。一方面，话题演变会导致社团的聚散和兴衰，往往是社团变化的原因，社团变化是话题演变的表象；另一方面，社团变化导致新话题的出现和旧话题的消亡，是话题演变的助推力。

（4）社团为话题的载体。话题的流通、传播是基于社团进行的，并具有一定的规律。比如往往先在某个社团内部传播，导致内部激荡，达到一定程度，扩展到邻近社团；然后进入新的循环，在该邻近社团内部内传播，再进入新的社团。

因此，社团挖掘和话题监控可以结合在一起研究，社团和话题可以相互定义。

社团是具有共同话题的社会实体组成的集合。即无论一些社会实体之间存在多么密切的外在联系，如果没有共同的话题，都认为没有组成社团。话题是在一个（或多个）社团中流行的内容，而不是流行在网页或新闻报道中的内容。即如果这些网页或报道没有形成社团，那么无论某个内容在它们之中如何流行，都认为没有形成话题。社团和话题都是动态的生命体，都有从诞生到发展到消亡的完整生命过程。因此，类似话题的发现和跟踪，社团挖掘中还包括社团跟踪的研究；其次，社团和话题的动态演变是相互影响、相互交织的。

从本质上讲，话题和社团都是聚类的结果，可以设计出发现它们的通用模型。此外，两者随时间变化的演变模型也非常相似，图5-7所示为以话题为例的示意图。

图5-7 话题和社团的通用演变模型

如图5-7所示，在一个互联网社区中，每个时刻都存在许多话题（或社团），随着时间变化，话题（或社团）也可能变化。图中每个圆点表示一个话题（或社团），每条虚线表示横向关系，每条实线表示纵向关系。

3.社团挖掘和话题监控的互动模型

最初，互联网上有许多个体，同时有许多言论；然后逐渐地个体之间有了关系，形成了社团，同时言论之间有了共同点，形成了话题。在该过程中，社团和话题是相互影响的，静态互动模型可以形式化地刻画在某个时刻发生的此过程。图5-8所示为这些概念和相互关系。

图5-8 各概念和函数的示意图

下面是对其中记号的一些解释：

（1）个体在互联网上发帖产生言论，该过程用函数PtoO（Person to Opinion）表示，满足：

性质1：∀p₁，p₂，如果p₁≠p₂，那么PtoO（p₁）≠PtoO（p₂）。

（2）言论聚集产生话题，该过程用函数cluso表示，即H=cluso（0）。每个言论都属于一个或多个话题，该映射关系用函数OtoH（Opinion to Huati）表示。每个话题包含一个或多个言论，用函数HtoO（Huati to Opinion）表示。满足：

性质2：|O|>>|H|。

（3）个体聚集产生社团，该过程用函数clusp表示，即C=clusp（P）。每个个体都属于一个或多个社团，这个映射关系用函数PtoC（Person to Community）表示。每个社团包含一个或多个言论，用函数CtoP（Community to Person）表示。满足：

性质3：|P|>>|C|。

（4）每个社团都有感兴趣的话题，用函数CtoH（Community to Huati）表示；反之，每个话题可能有多个社团感兴趣，用函数HtoC（Huati to Community）表示。

另外存在一些间接关系：

（1）个体与话题的关系，个体先产生言论，然后这些言论属于某些话题。该映射关系用函数PtoH表示，满足：(www.xing528.com)

性质4：∀p∈P，PtoH（p）=o∈P_t∪_oO（p）OtoH（o）。

（2）言论与社团的关系，言论属于某个个体，进一步属于个体所在的社团。该映射关系用函数OtoC表示，满足：

性质5：∀o∈0，OtoC（o）=PtoC（OtoP（o））。

下面的两个性质可以描述个体、社团、话题之间的关系：

性质6：∀p₁，p₂∈P，如果PtoH（p₁）≈PtoH（p₂），那么PtoC（p₁）∩PtoC（p₂）≠ϕ，或者说p₁和p₂很可能都属于某个（或某些）社团。

性质7：∀o₁，o₂∈O，如果OtoC（o₁）≈OtoC（o₂），那么OtoH（o₁）∩OtoH（o₂）≠ϕ，或者说o₁和o₂很可能都属于某个（或某些）话题。

性质1可以用一个二分图来示意，如图5-9所示，即如果个体集和话题集之间接近一个完全二分图，那么这个个体集就可能是一个社团。类似地，根据性质2，如果言论集与社团集也存在这样的二分图，那么这个言论集就可能是一个话题。

图5-9 社团挖掘和话题监控的二分图模型

如图5-9所示，社团成员为一个点集，话题成员为另一个点集，两个点集形成一个（近似）完全二分图。另外，社团成员之间具有相似性，可以利用这个特性挖掘社团和话题。

下面利用性质1来设计社团挖掘的算法，它等价于这样的数学问题：

问题1：已知个体集P和函数PtoO、OtoH，求解函数PtoC。

相应算法如下所示：

算法1：社团挖掘算法

For i=1 to|P|，遍历集合P，∀p_i∈P；

根据性质4计算PtoH（p_i），得到p_i的话题集H_i；

For j=1 to i-1。遍历已有的H_j，每个与H_i比较；

If H_j与H_i近似then

PtoC（p_i）=PtoC（p_i）∪PtoC（p_j）

End if

End for

If PtoC（p_i）≠ϕ then

建立一个新社团c，且PtoC（p_i）≠{c}

End if

End for

类似地，可以利用性质7来设计话题识别的算法，它等价于这样的数学问题：

问题2：已知言论集0和函数OtoP，PtoC，求解函数OtoH。相应算法如下所示。

算法2：话题识别算法

For i=1 to|0|，遍历集合0，∀o_i∈O；

根据性质5计算OtoC（o_i），得到o_i的社团集C_i；

For j=1 to i-1，遍历已有的C_j，每个与C_i比较；

If C_j与C_i近似then

OtoH（o_i）=OtoH（o_i）∪OtoH（o_j）

End if

End for

If OtoH（o_i）≠ϕ then

建立一个新话题h，且OtoH（o_i）≠{h}

End if

End for

在静态模型中增加时间维就可以得到社团演变和话题演变的动态互动模型，即把上面讨论的各个概念，比如P、O、C和H都放入到一个时间空间来考虑，那么它们都是动态变化的。特别地，社团跟踪和话题跟踪的任务就是找出不同时刻的社团、话题之间的关系，模型如图5-10所示。

图5-10 社团演变和话题演变动态互动模型图

社团挖掘和话题监控分别是Web信息挖掘和文本信息研究领域的研究热点，一直是各自独立研究的。目前的社团挖掘算法几乎完全基于图结构，没有考虑图中节点和边的语义；而话题监控则几乎完全从语义出发，没有考虑到发言者之间存在的拓扑结构。本节所提方法首次将两者结合起来研究，形式化地说明了社团，话题以及个体之间的关系，创建了社团挖掘和话题发现的静态互动模型，在此基础上设计了社团挖掘和话题识别算法；同时创建了社团演变和话题演变的动态互动模型，在此基础上设计了社团跟踪算法。互动模型的研究，使社团挖掘和话题监控技术能够共同挖掘以互联网为载体的复杂社会网络。