近年来，边上带属性的网络即符号网络成为复杂网络研究领域新兴的数据表达形式，基于符号网络建模的优化问题变得尤为重要。同盟问题及信息传播问题是复杂网络研究领域的两个重要课题。以往对同盟问题的研究均是基于无符号网络，未区分边的"敌人"或"朋友"属性，本项目中拟将边的属性考虑在内，在符号网络中合理定义三类（防御、攻击、强力）同盟，刻画三类同盟子集的基数与符号网络的参数的关系，进而设计基于同盟的符号网络划分算法；另外，信息传播问题目前主要关注在影响范围的最大化，缺少对时间的限制，但由于现实生活中需要将时间因素考虑在内（例如舆情控制中，需要在短时间内控制舆论），因此本项目中拟利用图论技术，设计符号网络下的信息快速传播问题的高效算法。本项目两个研究课题是在实际问题驱动下提出的，研究结果可相互利用，同时研究过程需要引入新的图论概念，基于这些新概念会促生一系列图论问题的研究，丰富图论领域的研究成果。

Signed network is a new description of social networks, where each edge is with a sign of positive or negative which represents positive (friend/trust) or negative relationship (enemy/distrust) respectively. People have shown that signed networks contain more accurate information than unsigned networks, but there are few researches focusing on signed networks. Signed network can not be seen simply as the weighted version of unsigned network because the signs have particular meanings. In this project, we will mainly consider two important optimization problems in complex network analysis which are "alliances problem in signed network " and "fast information propagation problem in signed networks". The alliances for unsigned networks were first introduced in 2004 and a huge number of theoretical (algorithmic and computational) results are obtained in the last decade, but there is not any result for signed networks. It is the first time that alliance problem is proposed for signed networks in this project. We will first give reasonable definitions of three kinds of alliances (defensive alliance, offensive alliance and powerful alliance respectively), and then focus on studying mathematical properties of various parameters of different alliances, and also considering how to partition a signed network into alliances. Furthermore, we will study the information fast propagation problem in signed networks. Traditional information propagation problems are focusing on the maximization of influences ignoring the time restrictions. But in reality, time is a key factor which can not be ignored for information diffusion. Thus in this project we put the time factor into consideration and raise the following problem: for a given signed network and a given time T, find the minimum set of vertices that could influence all the nodes or a certain ratio of nodes in the signed network within the given time T. We will design efficient algorithms for this problem by the techniques of graph theory. These two problems are fundamental in complex network analysis and have various applications in many domains. To solve them, we will adopt the techniques from graph theory, and we also need to introduce new concepts, which will in turn promote the development of graph theory.