Generalized minimum dominating set and application in automatic text summarization

International Meeting on High-Dimensional Data-Driven Science 2015

Xu, Yi-Zhi^1 ; Zhou, Hai-Jun^1

State Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Zhong-Guan-Cun East Road 55, Beijing

100190, China^1

关键词: Automatic text summarization;    Belief propagation;    Cardinalities;    Limiting case;    Minimum dominating set;    Spin-glass theory;    Text document;    Threshold-value;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/699/1/012014/pdf
DOI  :  10.1088/1742-6596/699/1/012014

来源: IOP

【 摘 要 】

For a graph formed by vertices and weighted edges, a generalized minimum dominating set (MDS) is a vertex set of smallest cardinality such that the summed weight of edges from each outside vertex to vertices in this set is equal to or larger than certain threshold value. This generalized MDS problem reduces to the conventional MDS problem in the limiting case of all the edge weights being equal to the threshold value. We treat the generalized MDS problem in the present paper by a replica-symmetric spin glass theory and derive a set of belief-propagation equations. As a practical application we consider the problem of extracting a set of sentences that best summarize a given input text document. We carry out a preliminary test of the statistical physics-inspired method to this automatic text summarization problem.