网络拓扑结构的聚类方法比较范文

近几年，在探索复杂网络拓扑结构的过程中，研究者除发现小世界与无标度特性外，还发现复杂网络还存在一个基本属性:社团结构(communitystruc-ture)［1］。复杂网络是由若干个社团组成，社团内部节点的连接非常紧密，社团之间节点的连接相对比较稀疏。结构决定功能，研究网络的社团结构有助于分析复杂网络的功能、探索复杂网络的隐藏规律以及预测复杂网络的发展趋势。为了能够精确界定网络中的社团结构，必须选择一种优秀的聚类方法。现有的复杂网络聚类方法主要分为两大类，一类是基于图论的算法，如Ker-nighan－Lin法、谱平分法、随机游走法(Walk-trapalgorithm)和标签传播法(Labelpropagationalgorithm);另一类是层次聚类方法，层次聚类本身又分为凝聚与分裂算法，其中凝聚算法包括New-man快速算法和最大模块度算法(BGllalgo-rithm)等，分裂算法中最为经典的是Girvan和Newman提出的边介数算法(Girvan－Newmanalgo-rithm)。此外，近几年又有许多从其他不同角度提出的划分网络社团结构的聚类算法，如基于电阻网络性质的算法、基于信息论的算法等。在文献领域，以语义相似性算法构造出的论文相似网络能够直接反映文献内容的相似程度。因而以此网络为基础，分析该网络的社团结构，可以清晰地描述出学科结构的动态变化与专业主题的研究热点，并为文献影响力的评价提供新的视角。为了找到最适合论文相似网络的聚类算法，本文以语义相似算法构造论文相似网络，并针对性地选择了4种代表性聚类方法(基于图论的随机游走算法和标签传播算法，层次聚类中的最大模块度法和边介数法)对构建出的网络进行聚类分析，并结合样本数据的金标准和网络社团划分评价指标D函数［10］比较4种算法的准确性和稳定性。

1材料与方法

在OHSUMED试验数据集中选择6个查询提问(queries)作为研究主题，收集与其明确相关(defi-nitelyrelated)的109篇文献作为样本数据。其中6号主题19篇，27号主题36篇，32号主题14篇，42号主题13篇，84号主题22篇，98号主题5篇。为了直接反映文献内容的相关性，采用语义相似性算法［11］构造论文相似网络，即用文献的主题词代表论文，通过计算主题词间的相似性得出文献间的相似程度。利用本地PubMed检索系统中基于语义相似性的PANS(PaperNetworkonSimilarity)算法直接生成论文相似矩阵(表1)，矩阵中的元素代表相应两篇文献间内容上的相似性。为使聚类结果更准确，选择0．08作为相似度阈值，移除相似度小于等于0．08的边，得到简化后的相似矩阵(表2)。在R语言的igraph程序包中，以上述两个相似矩阵为邻接矩阵构造论文网络，得到原始的论文网络(简称网络1，图1)和简化的论文网络(简称网络2，图2)，并进行可视化处理。网络1和网络2都是无向加权图，每个节点代表1篇文献，边的权重代表文献间的相似度值。其中网络1共109个节点，5886条边;网络2含109个节点，1621条连接(图中标签代表金标准的主题号)。利用igraph程序包的复杂网络处理算法功能，分别采用4种聚类算法对网络1和网络2进行聚类分析，探索论文相似网络的社团结构，最后结合金标准的主题分类和网络社团划分评价指标D函数比较4种算法的准确性和稳定性。

2结果

按照金标准的主题分类，论文相似网络拥有6个社团(图3)，其中社团1(第98号主题)5个节点，社团2(第27号主题)36个节点，社团3(第6号主题)19个节点，社团4(第84号主题)22个节点，社团5(第32号主题)14个节点，社团6(第42号主题)13个节点。采用4种算法对网络1和网络2聚类的结果如图4－图11所示。图中节点标签数字代表金标准的主题号，标签颜色相同的节点属于同一个社团，社团内连线为黑色，社团间连线为红色。4种算法得出的聚类结果的具体数据如表3和表4所示。采用随机游走算法分析论文相似网络，并对网络进行聚类分析，如图4所示，准确率高达96．3%，社团数为6，但第6号主题的一个节点与98号主题的5个节点被错误归为一类。简化剪枝后，准确率为100%，聚类结果(图5)与实际社团划分情况完全相同。采用标签传播算法对网络1进行聚类分析，如图6所示，准确率高达81．3%。它将27号主题与98号主题归为一类，因此社团数目只有5。但对网络2的聚类结果跟随机游走算法一样(图7)，也是与实际一致。采用最大模块度算法对论文相似网络聚类分析时，网络处理前后的结果是一致的(图8和图9)，二者都是将42号主题与98号主题聚为一类，从而得到5个社团，但在处理两个网络时得到的Q值都是最大的。边介数算法对于原始网络的聚类效果较差，如图10所示，模块度Q仅为0．045，57个社团中仅1个社团的节点数超过1，其余社团均只含1个节点。网络剪枝后，GN法得到6个社团(图11)，准确率高于90%，仅98号主题有2个节点被错误归为42号主题。

3讨论

由于不同主题文献之间的相似性大都较低(全部＜0．1)，导致同一主题内的任意两篇文献与其他主题文献的相似性差异很小。这符合随机游走算法的前提，即若两个节点同属于一个社团，那么分别从两个顶点跳跃到整个网络的其他节点的概率相近:如果顶点i和顶点j属于同一社团，则对于任一顶点k有Ptik≈Ptjk。标签传播算法的两次聚类结果差距较大，说明其稳定性较差。这是由于它的更新顺序是随机的、邻接节点标签数量相同时选择标签也是随机的，算法的鲁棒性遭到严重破坏，社区结构的稳定性也就受到严重损害。最大模块度算法则更为稳定，具有以下优点:计算速度快，可用于大型网络;整个过程自下而上，不会遗漏小规模的社团结构;适用于大规模的加权网络。边介数算法的前提是连接不同社团间的边的介数值较大，而连接社团内部边的介数值则较小。但由于原始论文相似网络中任意两点之间都存在连接，无法满足此前提，因此聚类结果无意义。

4结语

在构建文献相似网络的基础上，通过比较4种聚类算法的聚类精度和聚类稳定性，我们发现，随机游走算法是一种优秀的论文相似网络聚类算法，准确性高、稳定性好;标签传播算法的准确性次之，但稳定性不高;最大模块度算法稳定性好，但聚类精度有待提高;边介数算法对相似网络的预处理要求很高，聚类结果不稳定。另外，我们还发现，选择阈值处理相似网络后聚类效果显著提高，说明选择不同的相似度阈值会对聚类结果产生影响，可见复杂网络的预处理也是一个影响其聚类效果的重要因素。本研究为今后选择更为准确和稳定的论文相似网络聚类算法提供了依据。在今后的研究中，应选择随机游走算法对文献相似性网络进行聚类分析，并且可以尝试通过阈值的选取来提高文献相似网络的聚类精度。文本聚类分析技术的进一步改进，一是有助于揭示学科结构及其动态变化，在精确计算论文相似性基础上，形成准确的网络并精确地聚类分析，随时反映不同学科专业主题当前研究的热点和结构;二是有助于成簇检索相关文献，可以将基于随机游走算法镶嵌在文献检索系统中，将用户检索到的文献集合中相似论文按照类别提供给检索用户，提高信息咨询服务的准确度和针对性。

作者：黄鹏 崔雷 单位：中国医科大学医学信息学院