聚类(Clustering)技术是机器学习中非常重要的一种非监督学习方式。通常，聚类算法依据某种准则将相似的样本指派到同一个类中、将不相似的样本指派到不同的类中。聚类算法最常见的输入是相似性(相异性)矩阵，矩阵中的元素表示对应两个样本间的相似性(相异性)。关联聚类是一种特殊的聚类技术，其输入是一个同时表示样本间相似性和相异性的符号网络，在符号网络中用正边表示对应样本之间的相似性、用负边表示对应样本之间的相异性。关联聚类的目标是使得到的聚类结果中正边尽量存在于类内、负边尽量存在于类间。
　　传统的关联聚类算法主要是建立在整数线性优化(Integer Linear Programming, ILP)模型上。这类算法的主要问题是算法运算效率低，在处理越来越常见的大规模社交网络、生物网络时往往力不从心。本文研究大规模符号网络的关联聚类问题，文中的研究按照两条技术路线来设计关联聚类算法。第一条技术路线基于对符号网络的规模约简(Reduction)和基于环形不等式的关联聚类ILP模型。符号网络规模约简针对无权和有权符号网络分别设计了规模约简算法，使得聚类算法可以在更小规模的符号网络上运行；基于环形不等式的ILP模型较原来的ILP模型具有更高的计算效率，将其作用在约简的符号网络上产生了两种关联聚类算法。第二条技术路线从针对无符号网络的分割算法中寻求突破口来设计关联聚类算法。无符号网络分割问题目前已经存在较多的研究成果和文献资料，我们借鉴其中的一些重要思想来设计关联聚类算法。具体来说本文的主要研究工作描述如下：
　　(1)基于网络结构特性的符号网络规模约简算法。
　　实际应用中的符号网络比如社会网络、生物网络等都遵循一些典型的网络结构特性，比如顶点的幂律分布(Power-law)、高聚类系数、相互性、传递性等。本文分析了这些网络结构特性对于聚类倾向的影响，并依此分别设计了适用于不同类型的符号网络的规模约简算法：针对无权符号网络提出了一种星型结构来约简网络规模，这种星型结构以符号网络中对聚类具有更高贡献的顶点为核心来搜索一步范围内的顶点并共同构成类原型；针对有权符号网络提出了基于滴水原理(Drop of Water)的网络约简算法，算法从重要顶点出发进行搜索，所有搜索路径上的点和原点一起构成类原型。无论是哪种类型的符号网络中得到的类原型最后都被设计成能够遍布于整个网络，从而得到最大的约简效果。
　　(2)基于环形不等式ILP模型的局部搜索。
　　传统关联聚类算法的ILP模型中的约束条件是基于三角不等式来构造的，因此当符号网络的规模增大时会导致约束条件的数量急剧增加，这是导致传统算法计算效率较低的根本原因。本文提出了一个改进的ILP模型，其约束条件建立在符号网络中实际存在的环之上，使用环形不等式约束代替三角形不等式约束，因此约束条件的数量由实际存在的环的数量来决定，基于环形不等式的ILP模型的效率大大优于原有模型。利用改进的ILP模型本文设计了一个针对约简符号网络的局部搜索策略来得到最终的关联聚类结果。
　　(3)基于随机游走的关联聚类算法。
　　随机游走(Random Walk)由于其直观、简单、有效而在无符号网络分割中得到广泛的应用。本文将随机游走机制应用在符号网络中，设计了称为随机游走间隔(RandomWalkGap，简称RWG)的机制来捕获符号网络的类结构信息。RWG首先从原符号网络构造出两个衍生网络并在两个衍生网络中进行多步随机游走，由此得到衍生网络的多步转移概率。研究发现，符号网络中具有不同聚类意义的边对应顶点的两个衍生网络中的多步转移概率值的变化具有不一样的规律，因此定义了三种类型的边并分析了各种类型的边对于聚类结果的影响。因此RWG机制能够发现对于聚类具有重要影响的边并修正这些边的权重，在此基础上配合使用一个简单的贪心聚类算法就能够取得非常好的关联聚类结果。
　　本文另外的工作包括设计人工符号网络生成算法。关联聚类问题研究进展缓慢的一个原因是缺少实验数据，因此本文设计了人工符号网络生成算法。算法能生成具有各种特性的人工符号网络，比如顶点的正度和负度的幂率分布、高聚类系数等。生成的人工符号网络使得算法性能的比较更完备。