网络同质性原理和图划分问题的近似算法

网络同质性原理表明，在复杂网络中，一个顶点总是与它的邻居具有相同或相似的属性。从这一基本原理出发，我们提炼出两个简单而有趣的组合优化问题：最大满意边问题和最大满意顶点问题。最大满意边问题的一个自然变化是最大k-补割问题。这三个问题都属于图划分问题。巧合的是，它们与经典的多路割问题、最小k-割问题有着密切的联系。这三个问题都是NP难的，因而使用近似的方法对其研究就成为一种自然的途径。从正的方面，项目组主要采用线性规划和半正定规划等方法，对问题设计出具有最好近似比的近似算法；从负的方面，开发新的归约技术，证明问题最好的或改进的近似难度。本项目有两个显著的特色：其一是从算法的角度研究网络科学中的问题，属于交叉研究；其二是研究问题是全新的图划分问题，属于前沿研究。对这些图划分问题的研究，能够深化对复杂网络结构和演化规律的认识，推进图划分问题的发展前沿，并对近似算法和组合优化学科的发展做出贡献。

The homophyly principle of networks shows that in a complex network, a vertex tends to have the same or similar attributes with its neighbors. Starting from this basic law, we extract two simple and interesting combinatorial optimization problems, that is, the Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem. A natural variant of MHE is the Max k-Uncut (MkUC) problem. All these three problems belong to the graph partitioning problems. Coincidentally, they are closely related to the classical Multiway Cut and Min k-Cut problems. Since these three problems are NP-hard, the approximation method is a natural approach to study them. From the positive aspect, we shall design approximation algorithms with the best ratios for these problems using the methods such as linear programming and semidefinite programming. From the negative aspect, we shall prove the best or improved approximation hardness results for the problems by developing new reductions. Our project has two distinguished properties: Firstly, it is an interdisciplinary research since we study the algorithmic aspects of the homophyly law of networks. Secondly, we actually conduct a cutting-edge research since our research problems are the newest graph partitioning problems. The research on the graph partitioning problems, including MHV, MHE, and MkUC, will deepen our understanding to the structures and evolution rules of complex networks, push forward the cutting edge of the graph partitioning problems, and contribute to the theory of approximation algorithms and combinatorial optimization.