摘要: 现实世界中的诸多系统都可以建模成复杂网络。采用数学方法对复杂网络的特性进行定量的分析有助于我们深入理解这些系统。目前复杂网络已成为最前沿和最具挑战性的多学科性研究课题之一，其研究结果多次在《自然》和《科学》等著名杂志上报道。本文主要讨论符号网络（一种重要的复杂网络）的拓扑结构，即共体结构。符号网络是指包含正负两种关系的复杂网络。例如在社会网络中，“喜欢”、“尊重”和“表扬”属于正关系，而“厌恶”、“轻视”和“责备”属于负关系。类似的正负关系在生物网络和科技网络等其它复杂网络中也广泛存在。符号网络中的共体是指多个不相交的节点集合，集合内的正关系稠密而集合间负关系稠密。符号网络共体结构挖掘方法的研究对分析复杂网络的拓扑结构和发现复杂网络中的隐藏规律具有十分重要的意义，例如识别社会网中的恐怖组织，预测蛋白质的未知功能，万维网的网页自动分类等。 值得注意的是，当前有关万维网挖掘的工作都是基于只包含正关系的Web图模型，而忽略了负关系的存在，如公司之间的竞争关系。尽管目前已存在多种复杂网络共体挖掘算法（最早的工作是Girvan 和Newman提出的基于边介数的GN算法），但其中绝大多数都是针对只包含正关系的复杂网络提出，对符号网络并不适用，因此如何快速和准确地挖掘符号网络共体仍然是一个未被很好解决的问题。针对该问题，Doreian和Mrvar提出了基于局部搜索（Local Search）的DM算法。本质上，DM算法是一种启发式的贪心优化算法，它采用局部搜索方法能逐步逼近地为预先定义的目标函数找到一个近似最优解。该算法（时间复杂性为O(n2)）的主要不足是需要一定的先验知识（例如共体数目和每个共体的粗略大小），而这些先验知识事先难于获取，尤其当我们面对未知的符号网络。为解决这些问题，本文提出一种新的符号网络共体挖掘算 — MCS算法。MCS算法的基本原理是基于聚类测度（clustering centrality）概念的矩阵变换。其主要步骤描述如下：（1）迭代地计算出网络中所有节点的聚类测度；（2）根据聚类测度的排序将初始的邻接矩阵变换为一个近似对角矩阵；（3）根据预先定义的聚类标准将变换后的矩阵分割成两个子矩阵；（4）分别递归处理子矩阵直到找到隐藏在符号网络中的所有共体。与已有方法相比，本文算法具有如下三个特点：一，算法速度快，其时间复杂性是大约是网络规模（节点数目加连接数目）的线性阶；二，具有很好的聚类能力，尤其适合于挖掘那些共体结构不明显的复杂符号网络；三，不需要先验知识，并且算法性能对参数不敏感。值得说明的是，MCS算法也是一种启发式算法, 因此也具有启发式算法所具有的局限性，即MCS算法能够快速地找到一个最优解或者近似最优解，但没有从理论上保证它对任何的输入都能找到这样令人满意的解。但是通过试验，我们发现MCS算法对于多数基准数据集都能找到好的解。