关键词: 节点相似度, NP难, 次模函数, 近似算法

Abstract: In general graphs, the similarity between any two nodes is usually characterized based on the topological structure of the graph. Based on node similarity, this paper proposes a concept named summary representing set. Finding a summary representing set with the minimum number of nodes in a graph is called the minimum summary representing set problem. It is proved that the minimum summary representing set problem is NP-hard (non-deterministic polynomials), which means it is unlikely to exist exact algorithms with poly-nomial time. A greedy approximation algorithm with polynomial time is proposed based on submodular function, which is used to solve the minimum summary representing set problem and get the approximate results.

Key words: node similarity, NP-hard, submodular function, approximation algorithm