# Solving Multi-Document Summarization as an Orienteering Problem
## 5 The Proposed Solution
### Computing the Content Scores  
In this stage, the score of each word in the text is computed to get the content scores of the sentences. The content score for each sentence is based on the scores of the words it contains. The proposed algorithm to compute the scores of the words follows the iterative reinforcement approach proposed by [PERSON] et al. [38]. It combines ideas similar to PageRank [39] and the HITS [40] graph-ranking algorithms. First, three graphs are built: (1) a sentence-to sentence graph to represent the relationship among the sentences, (2) a word-to-word graph to represent the relationship among the words, and (3) a sentence-to-word bipartite graph that connects each sentence with the words it contains. To compute the scores of the words, the algorithm applies a PageRank-based method to the sentence-to-sentence and word-to-word graphs, and an HITS-based method to the sentence-to-word graph, where hubs represent the sentences, and authorities represent the words.  
The proposed algorithm computes the arcs weights of the sentence-to-sentence and the sentence-to-word graphs based on the TF-ISF scores and cosine similarity measure. For the word-to-word graph, the arc weights are equal to the longest common substring between the two connected words. The weights of the arcs in sentence-to-sentence, sentence-to-word, and word-to-word graphs are represented by three matrices: \(U\), \(W\), and \(V\), respectively. The scores of the words (represented by matrix \(V\)) and sentences (represented by matrix \(U\)) are computed by applying the following two equations, which are calculated repeatedly until a convergence state is reached.  
\[U^{(n)}=\alpha\widetilde{U}^{T}U^{(n-1)}+\beta\widetilde{W}^{T}V^{(n-1)} \tag{11}\]  
\[V^{(n)}=\alpha\widetilde{V}^{T}V^{(n-1)}+\beta\widetilde{W}^{T}U^{(n-1)} \tag{12}\]  
where \(\widetilde{U}\), \(\widetilde{W}\), and \(\widetilde{V}\) are the normalized version of the matrices \(U\), \(W\), and \(V\), respectively. The normalized transposed of the matrix \(W\) is \(\widehat{W}\). The values of the vector \(u^{(n)}\) and vector \(u^{(n-1)}\) represent the values of the vector \(U\) at the iterations \(n\) and \(n-1\), respectively. Similarly, the values of the vector \(v^{(n)}\) and vector \(v^{(n-1)}\) represent the values of the vector \(V\) at the iterations \(n\) and \(n-1\), respectively. After each calculation of \(u^{(n)}\) and \(v^{(n)}\), the two vectors are normalized. In addition, to emphasize the importance of the first sentences, the proposed algorithm gives more weight to the words of these sentences.  
Figure 2: An example of the intermediate representation of an input text with four sentences. The length of Sentence 1 (\(s_{1}\)), Sentence 2 (\(s_{2}\)), Sentence 3 (\(s_{3}\)), and Sentence 4 (\(s_{4}\)) are \(l_{1}\), \(l_{2}\), \(l_{3}\), and \(l_{4}\), respectively.  
Several differences exist between the reinforcement approach of [PERSON] et al. (2018) and the proposed algorithm. The proposed algorithm generates multi-document summaries instead of single-document summaries. It uses the scores of the words to maximize the overall information coverage score of the resulting summary, whereas the reinforcement approach uses the scores of the sentences to generate the summaries. Moreover, it computes the similarities among the words in the word-to-word graph based on the longest common substring to keep the proposed solution language independent, instead of using knowledge-based or corpus-based measures.