基于信息论的图K划分方法

Graph K-partitions based on information theory

图划分问题是一个NP完全问题,很难在多项式时间内获得一个最优解。为快速获得一个图划分的近似最优解,研究了信息论中的相关知识,设计了一个基于信息论的求解图K划分的近似算法。该算法通过快速求解各节点的自信息及熵,获得各节点集之间的相关性,从而获得相应的划分。经分析,该算法的时间复杂度为O(V2)。实验结果表明,该算法获得的解同工具metis的求解效果相当,且在时间上明显优于metis工具。

The graph partition is a NP-hard problem, and it is hard to find an optimal algorithm that using only polynomial time complexity. To get a faster algorithm, the relevant knowledge in information theory is studied and an approximate algorithm for the K-partition problem using theory of information area is designed. The relationship of nodes is gotten by the calculation of self-information and entropy and the partition is layout by the relationship of nodes. For the analysis, its time complexity is only O （V2）. Experiments show that proposed algorithm is the same as metis on effect and much better than metis on time.