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

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.

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

本项目研究主要来自于网络科学中的几个图划分问题，包括最大满意边问题、最大满意顶点问题、最大k-补割问题和标签s-t割问题等。项目组取得的主要成果包括：（1）对最大满意边问题和最大满意顶点问题给出了具有最好近似比的近似算法。（2）对最大k-补割问题给出了具有最好近似比的近似算法。（3）对标签s-t割问题给出了具有最好近似比的近似算法。（4）证明了标签s-t割的一个自然的线性规划的整性间隙为Omega(m^(1/3))，其中m为图的边的数目。（5）证明了最大k-补割问题和著名的稠密k-子图问题在可近似性上是等价的（忽略常数因子）。取得以上结果所采用的技术主要包括线性规划、随机和概率方法、组合技术以及归约等。. 项目组发表期刊论文25篇，其中CCF-A类论文1篇，CCF-B类论文9篇，SCI一区论文3篇，SCI二区论文2篇。这些论文发表在IANDC、Algorithmica、EJOR、JGO、TCS等算法领域的著名期刊上。项目负责人以第一作者发表IANDC论文一篇，Algorithmica论文两篇。其中，IANDC上的论文是山东大学软件学院首次在理论计算机科学CCF-A类出版物上发表论文。. 对这些图划分问题的研究，深化了对复杂网络结构和演化规律的认识，推进了图划分问题的发展前沿，对近似算法和组合优化学科的发展做出了新的贡献。项目所提出的算法，可在所解决的问题出现的场合获得直接的应用。