类簇结构或社区结构是复杂网络最普遍和最重要的拓扑结构属性之一。目前已有的聚类算法大多是基于非符号复杂网络（边上权重为正），对符号网络（signed network）（边上权重扩展为正、负）的研究少之又少。本项目利用图论技术，基于申请人在非符号复杂网络已有聚类算法的基础上，通过寻找稠密子图和收缩子图的方法，对符号网络的类簇结构进行研究，设计一个高效精确的层次聚类算法，并结合申请人在复杂网络核心节点寻找问题上已有结果，利用每个子类簇内核心节点的个数，对初始聚类结果进行二次迭代，提高算法精确性。该项目的研究，将解决目前符号网络聚类算法中存在的“无法实现一个对象可属于多个类簇的重叠聚类”和“类簇个数需要用户事先给定”这两个主要问题。本项目的研究结果可以广泛应用于社会网络分析（例如恐怖组织识别等），生物网络分析（例如蛋白质交互网络分析和未知蛋白质功能预测等）以及Web社区挖掘和文档聚类等众多领域。

Network community structure or network cluster structure is one of the most fundamental and important topological properties of complex networks, as well as the other two properties “small world” and “scale-free”. Complex networks can be modeled as graphs with nodes and edges, where nodes indicate individual actors and edges indicate the relationships between actors. Traditional clustering always assumes that all edge weights in the complex network are positive, and the task of clustering is to group the vertices of the graph into clusters taking into consideration the edge structure of the graph in such a way that there should be many edges within each cluster and relatively few between the clusters. But in many real complex networks, there are not only positive relationships but also negative relationships. For example, online news and review websites such as Epinions and Slashdot allow users to approve or denounce others. These kinds of networks can be modeled as signed networks where a positive relationship is denoted by a positive edge weight while a negative relationship is denoted by a negative edge weight. Thus, the clustering problem in signed networks is to find antagonistic clusters such that entities with the same cluster have a positive relationship with each other and entities between different clusters have a negative relationship with each other. While much research on graph clustering has been conducted on unsigned graphs which contain only positive edges, it is a very challenging project to design new clustering algorithms for signed networks since the goal of clustering changes. . In this project, we will design a novel algorithm for the clustering problem of signed networks based on graph theory. At first, we will construct an edge prediction model to predict the values between any pair of nodes. Then based on the valued complete network, we will give a new criterion named “density” to measure the tightness (or friendship) of a sub-graph. Graph clustering is a process that detects all dense sub-graphs in this complete graph, then contracts them, and repeats this process until there is only one vertex left or only negative edges left. We will construct a hierarchically nested system to illustrate their inclusion relation. Furthermore, we will refine the clustering result based on the number of most central nodes in each clusters. This project will solve "how to find the number of the clusters automatically" and "how to model overlapping clustering" these two important research problems in clustering of signed networks. This project is an extension for traditional complex network clustering, and can be used to social network analysis (e.g. terrorist organization detection), biological network analysis (e.g. protein function prediction) and other WEB text clustering.