基于聚类分析的网络论坛社团探测算法*

王长辉

(成都纺织高等专科学校)

0 引言

网络论坛(BBS)由于具有及时性、交互性、开放性等特点，因而也是网络舆论产生、形成和发展的主要场所，整个网络论坛的参与者呈现一种特性— —社团结构，即整个网络由若干个社团构成，每个社团内部的节点之间的连接相对紧密，各社团之间的连接相对稀疏.研究网络论坛的社团结构，对了解BBS中网络舆论的传播特点具有现实意义.

网络论坛中成员根据兴趣或背景而形成真实的社会团体，网络中的这些社区有助于更加有效地理解其成员结构和分析网络舆论传播特性.目前对网络社团结构研究主要有两类主要的方法——社会学中的分级聚类和计算机科学中的图形分割方法.分级聚类是探测网络社团的传统方法，基于各个节点间连接的相似性或强度将网络划分成子群，并根据划分时是往网络中添加还是移除边可分为凝聚算法和分裂算法，Girvan和Newman提出基于边介数的分裂算法(简称GN算法);Kemighan－Lin算法和谱平分法则是较为出名的图形分割算法，其中Kernighan－Lin算法根据使社团内部及社团间的边最优化的原则对原始的网络进行分类，谱平分法是根据网络图的Laplace矩阵进行向特征向量空间的谱映射［1，6－8］.该文算法是谱平分法的一种改进算法，将模块度函数与聚类分析算法结合进行社团结构探测.

1 算法简介

网络中的社团发现与数据的聚类分析有很多相似之处，聚类分析属于无监督的模式识别，其方法比……