# Coword and Cluster Analysis for the Romance of the Three Kingdoms

Authors: Chao Fan; Yu Li
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

TheRomance of the Three Kingdoms (RTK) is a classical Chinese historical novel by Luo Guanzhong. This paper establishes a research framework of analyzing the novel by utilizing coword and cluster analysis technology. At the beginning, we segment the full text of the novel, extracting the names of historical figures in the RTK novel. Based on the coword analysis, a social network of historical figures is constructed. We calculate several network features and enforce the cluster analysis. In addition, a modified clustering method using edge betweenness is proposed to improve the effect of clustering. Finally, both quantified and visualized results are displayed to confirm our approach.


---

## Body

## 1. Introduction

TheRomance of the Three Kingdoms, written by Luo Guanzhong, is generally considered to be one of the four great classical novels in Chinese literature. It describes the turbulent years from the end of the Han dynasty to the Three Kingdoms (Wei, Shu, and Wu) era in Chinese history. More than 1000 personalities are vividly portrayed in the historical novel.In this research, text of original novel is divided into a number of sentences. According to coword analysis, there is a certain intrinsic relationship between the two words when they appear in the same document. Thus, we calculated the frequency of cooccurrences for two names in a sentence. The character name is reckoned as the node and the cooccurrence as the link, so that an undirected network can be established. Furthermore, various network features are computed to analyze relationships of characters in the novel. Cluster analysis is employed to explore the hierarchical structure of RTK. Finally, an improved clustering algorithm by cutting high-betweenness edges is proposed, which performs better than the common approach in clustering effect.This manuscript is organized as follows. Section2 gives related work of this paper. Data preparation is discussed in Section 3. Sections 4 and 5 express the network feature analysis, cluster analysis, experiments, and the analysis of results. Conclusions are drawn in Section 6.


## 2. Related Work

Early research about the RTK concentrates on qualitative analysis, such as the writing style, genealogy, and characters. Later, a quantitative approach was adopted to analyze the novel. Coword analysis is such a method of importance, which was first devised by French scholars and introduced into the information science field by Callon [1]. According to the theory of coword analysis, there is a close connection between two words when they appear in a sentence. More cooccurrences of the two words indicate the closer relationship between them. In this paper, we consider the cooccurrence of character names in a sentence of the RTK novel.Numerous researches on literature analysis have been done based on the technologies of coword analysis. Ravikumar et al. [2] inspect 959 articles in scientometrics based on the coword analysis approach and find that the topics in publication are changing to new themes. As for the medical literature, there is a study utilizing this tool to process them over a span of thirty years [3]. Another work focuses on past themes and future trends in medical tourism research [4]. Employing the coword analysis, some researchers attempt to identify the themes and trends of main knowledge areas including engineering, health, public administration, and management [5]. Moreover, a coword network is established to analyze the relationship of characters in the Dream of the Red Chamber [6]. Wang et al. build a similar network for the Romance of the Three Kingdoms [7].After creating a social network based on coword analysis, the cluster analysis is carried out by performing a hierarchical clustering algorithm. Two types of algorithm are often implemented when moving up the hierarchy. The divisive approach of clustering reckons all data as one cluster and performs splits, which is used in many research [8]. Nevertheless, the agglomerative hierarchical clustering is a bottom-up method with many variants [9]. It merges the two most similar clusters at each time. The agglomerative method is exploited in this work because it can provide a visual expression of the clustering results.


## 3. Data Preparation

### 3.1. Building RTK Corpus and Preprocessing

As many data of the novel can be downloaded from the Internet, we selected a high-quality text document (https://72k.us/file/22215238-408791478) in Chinese character, establishing the RTK corpus by cleaning the original data. Some words with errors were modified, and the wrong punctuations were removed manually.The raw text is preprocessed using the natural language processing toolkit ICTCLAS (http://ictclas.nlpir.org/). We acquired a name list of RTK characters through the Internet and added it to the dictionary of ICTCLAS. Then, the lexical analysis is executed to segment Chinese sentences into words where names of characters can be found.


### 3.2. Creation of Character Name Network

Based on coword analysis, an undirected network of character names can be created by counting the cooccurrences of two names in sentences. We treated full name, its courtesy name, and abbreviated name as one name. For example, “Cao Cao” is equal to “Cao Mengde” and “Mengde,” which means the three names refer to a single person of “Cao Cao.”The final constructed network of character names has 1,133 nodes and 5,844 links. As depicted in Figure1, the size of a node indicates the count of the character name in the novel and the thickness of a link corresponds to the frequency of two characters that appear together.Figure 1
A network of character names (top 80 in node frequency).


## 3.1. Building RTK Corpus and Preprocessing

As many data of the novel can be downloaded from the Internet, we selected a high-quality text document (https://72k.us/file/22215238-408791478) in Chinese character, establishing the RTK corpus by cleaning the original data. Some words with errors were modified, and the wrong punctuations were removed manually.The raw text is preprocessed using the natural language processing toolkit ICTCLAS (http://ictclas.nlpir.org/). We acquired a name list of RTK characters through the Internet and added it to the dictionary of ICTCLAS. Then, the lexical analysis is executed to segment Chinese sentences into words where names of characters can be found.


## 3.2. Creation of Character Name Network

Based on coword analysis, an undirected network of character names can be created by counting the cooccurrences of two names in sentences. We treated full name, its courtesy name, and abbreviated name as one name. For example, “Cao Cao” is equal to “Cao Mengde” and “Mengde,” which means the three names refer to a single person of “Cao Cao.”The final constructed network of character names has 1,133 nodes and 5,844 links. As depicted in Figure1, the size of a node indicates the count of the character name in the novel and the thickness of a link corresponds to the frequency of two characters that appear together.Figure 1
A network of character names (top 80 in node frequency).


## 4. Network Feature Analysis

### 4.1. Degree Distribution

As the degree of a node is the number of links adjacent to it, the degree distribution is the probability distribution of these degrees. A power indexγ can be used to describe the curve if the network’s degree distribution follows a power-law distribution.For the network of RTK characters, the top ten characters of the highest degree are Cao Cao, Liu Bei, Zhuge Liang, Sun Quan, Zhao Yun, Guan Yu, Yuan Shao, Sima Yi, Lv Bu, and Wei Yan. The average degree of the network is 10.31, and the degree distribution can be illustrated in Figure2. It emerges to be a heavy-tailed distribution (see Figure 2(a)). As the data can be approximated with a linear function y=−1.2864x+2.5654 on a log-log scale in Figure 2(b), we conclude that the degree distribution follows a power-law distribution.Figure 2
Degree distribution and power-law degree distribution on a log-log scale.
(a)(b)


### 4.2. Average Shortest-Path Length

The shortest path between two nodes is a path where the number of links is minimized. Accordingly, the length of the shortest path is the number of links that the path contains. A sum of all shortest-path length divided by the number of links is the average shortest-path length.The average shortest-path length of the RTK network is 3.1743. Hence, one character can be connected to others in three steps on average, which means any two characters are “three-degree separation.”The distance of the largest shortest path in the network is called diameter. In this paper, the RTK network’s diameter is 9. One path of the diameter is from Liu Ai to Zhang Shang: Liu Ai, Wang Li, Dong Zhao, Cao Hong, Cao Cao, Sima Yan, Yang Hu, Du Yu, Lu Jing, and Zhang Shang. The distribution of the shortest-path length between any two characters can be illuminated in Figure3. According to the figure, 47.63% of the shortest-path length in the RTK network is 3 and about 92.15% is between length 2 and length 4.Figure 3
Distribution of shortest-path length.


### 4.3. Clustering Coefficient

A clustering coefficient [10, 11] measures the extent to which a network’s nodes tend to cluster together. The clustering coefficient of node x can be given by
(1)Cx=2Exkxkx−1.Ex is the existing links among neighbors of node x. As kx is a degree of node x, 1/2kxkx−1 represents the number of potential links for node x’s neighbors. Therefore, the average value for all Cx is the clustering coefficient of the whole network.
(2)C=1N∑xCx.A random network is produced by an Erdős-Rényi (ER) model utilizing the same number of nodes and links as the RTK network. The comparison between random network and RTK network is shown in Table1. The RTK network is a small-world network because it has a larger clustering coefficient as well as a smaller average shortest-path length compared with a random network.Table 1
Comparison between RTK and random network.
Number of nodesNumber of linksAverage degreeAverage shortest-path lengthClustering coefficientRTK network1,1335,84410.31593.17430.5306Random network1,1335,84410.31593.27020.0082We choose the characters who clearly belong to the three groups of Wei, Shu, and Wu and calculate the network features of the three kingdoms, respectively. The results are summarized in Table2.Table 2
Comparison of three subnetworks and the whole network.
DensityClustering coefficientAverage shortest-path lengthDiameterShu0.16520.66352.05634Wu0.10990.58452.30545Wei0.08030.62172.59536The whole network0.00910.53063.17439The character relationship networks within three groups have high clustering coefficients and small average shortest-path lengths. Consequently, all of the three subnetworks are “small-world” networks. From the Shu to Wu and Wei, the density and clustering coefficient of the subnetworks decrease sequentially except for the clustering coefficient of Wu. On the contrary, the average shortest-path length and diameter increase successively. This reflects a decrease in the closeness of the connections among the groups. In other words, the connections among characters in Wei are less closely than Wu and Shu.


### 4.4. Density

The density of a network shows the ratio of links, which can be simply calculated by formula (3). N and E are the number of nodes and links. It describes the portion of all possible links in a network that are actual connections. The value is a fraction between 0 and 1. As the density of the RTK network is 0.0091, it is a sparse network.
(3)d=2ENN−1.


### 4.5. Centrality

The centrality measures the importance of nodes, containing degree centrality, betweenness centrality, and closeness centrality.Degree centrality is a measure of centrality based on degree. A high-degree node is a local center within the network. Betweenness centrality expresses the extent that the node falls on the shortest path between other pairs of nodes. A node with a high betweenness is capable of controlling the interactions between two nonadjacent nodes [5]. Closeness centrality is a measure of the average shortest distance from each node to each other node. It evaluates the closeness that a node is to all the other nodes [3].Three centralities of characters in the RTK network are calculated, respectively. Table3 gives the top ten characters of the highest centrality. The value of centrality is listed in parentheses. From Table 3, we can find eight names listed in three centralities: Cao Cao, Liu Bei, Zhuge Liang, Sun Quan, Zhao Yun, Guan Yu, Yuan Shao, and Sima Yi. They are in a significant position in the character network.Table 3
Top 10 characters in rank with the highest centrality.
RankingDegree centralityBetweenness centralityCloseness centrality1Cao Cao (0.2094)Cao Cao (0.1751)Cao Cao (0.4528)2Liu Bei (0.2085)Liu Bei (0.1304)Liu Bei (0.4442)3Zhuge Liang (0.1714)Zhuge Liang (0.1093)Zhuge Liang (0.4313)4Sun Quan (0.1060)Sun Quan (0.0695)Sun Quan (0.4073)5Zhao Yun (0.0998)Sima Yi (0.0430)Guan Yu (0.3969)6Guan Yu (0.0972)Zhao Yun (0.0413)Zhao Yun (0.3963)7Yuan Shao (0.0813)Liu Shan (0.0402)Sima Yi (0.3924)8Sima Yi (0.0742)Guan Yu (0.0375)Wei Yan (0.3856)9Lv Bu (0.0716)Yuan Shao (0.0369)Yuan Shao (0.3842)10Wei Yan (0.0707)Jiang Wei (0.0357)Cao Ren (0.3824)


## 4.1. Degree Distribution

As the degree of a node is the number of links adjacent to it, the degree distribution is the probability distribution of these degrees. A power indexγ can be used to describe the curve if the network’s degree distribution follows a power-law distribution.For the network of RTK characters, the top ten characters of the highest degree are Cao Cao, Liu Bei, Zhuge Liang, Sun Quan, Zhao Yun, Guan Yu, Yuan Shao, Sima Yi, Lv Bu, and Wei Yan. The average degree of the network is 10.31, and the degree distribution can be illustrated in Figure2. It emerges to be a heavy-tailed distribution (see Figure 2(a)). As the data can be approximated with a linear function y=−1.2864x+2.5654 on a log-log scale in Figure 2(b), we conclude that the degree distribution follows a power-law distribution.Figure 2
Degree distribution and power-law degree distribution on a log-log scale.
(a)(b)


## 4.2. Average Shortest-Path Length

The shortest path between two nodes is a path where the number of links is minimized. Accordingly, the length of the shortest path is the number of links that the path contains. A sum of all shortest-path length divided by the number of links is the average shortest-path length.The average shortest-path length of the RTK network is 3.1743. Hence, one character can be connected to others in three steps on average, which means any two characters are “three-degree separation.”The distance of the largest shortest path in the network is called diameter. In this paper, the RTK network’s diameter is 9. One path of the diameter is from Liu Ai to Zhang Shang: Liu Ai, Wang Li, Dong Zhao, Cao Hong, Cao Cao, Sima Yan, Yang Hu, Du Yu, Lu Jing, and Zhang Shang. The distribution of the shortest-path length between any two characters can be illuminated in Figure3. According to the figure, 47.63% of the shortest-path length in the RTK network is 3 and about 92.15% is between length 2 and length 4.Figure 3
Distribution of shortest-path length.


## 4.3. Clustering Coefficient

A clustering coefficient [10, 11] measures the extent to which a network’s nodes tend to cluster together. The clustering coefficient of node x can be given by
(1)Cx=2Exkxkx−1.Ex is the existing links among neighbors of node x. As kx is a degree of node x, 1/2kxkx−1 represents the number of potential links for node x’s neighbors. Therefore, the average value for all Cx is the clustering coefficient of the whole network.
(2)C=1N∑xCx.A random network is produced by an Erdős-Rényi (ER) model utilizing the same number of nodes and links as the RTK network. The comparison between random network and RTK network is shown in Table1. The RTK network is a small-world network because it has a larger clustering coefficient as well as a smaller average shortest-path length compared with a random network.Table 1
Comparison between RTK and random network.
Number of nodesNumber of linksAverage degreeAverage shortest-path lengthClustering coefficientRTK network1,1335,84410.31593.17430.5306Random network1,1335,84410.31593.27020.0082We choose the characters who clearly belong to the three groups of Wei, Shu, and Wu and calculate the network features of the three kingdoms, respectively. The results are summarized in Table2.Table 2
Comparison of three subnetworks and the whole network.
DensityClustering coefficientAverage shortest-path lengthDiameterShu0.16520.66352.05634Wu0.10990.58452.30545Wei0.08030.62172.59536The whole network0.00910.53063.17439The character relationship networks within three groups have high clustering coefficients and small average shortest-path lengths. Consequently, all of the three subnetworks are “small-world” networks. From the Shu to Wu and Wei, the density and clustering coefficient of the subnetworks decrease sequentially except for the clustering coefficient of Wu. On the contrary, the average shortest-path length and diameter increase successively. This reflects a decrease in the closeness of the connections among the groups. In other words, the connections among characters in Wei are less closely than Wu and Shu.


## 4.4. Density

The density of a network shows the ratio of links, which can be simply calculated by formula (3). N and E are the number of nodes and links. It describes the portion of all possible links in a network that are actual connections. The value is a fraction between 0 and 1. As the density of the RTK network is 0.0091, it is a sparse network.
(3)d=2ENN−1.


## 4.5. Centrality

The centrality measures the importance of nodes, containing degree centrality, betweenness centrality, and closeness centrality.Degree centrality is a measure of centrality based on degree. A high-degree node is a local center within the network. Betweenness centrality expresses the extent that the node falls on the shortest path between other pairs of nodes. A node with a high betweenness is capable of controlling the interactions between two nonadjacent nodes [5]. Closeness centrality is a measure of the average shortest distance from each node to each other node. It evaluates the closeness that a node is to all the other nodes [3].Three centralities of characters in the RTK network are calculated, respectively. Table3 gives the top ten characters of the highest centrality. The value of centrality is listed in parentheses. From Table 3, we can find eight names listed in three centralities: Cao Cao, Liu Bei, Zhuge Liang, Sun Quan, Zhao Yun, Guan Yu, Yuan Shao, and Sima Yi. They are in a significant position in the character network.Table 3
Top 10 characters in rank with the highest centrality.
RankingDegree centralityBetweenness centralityCloseness centrality1Cao Cao (0.2094)Cao Cao (0.1751)Cao Cao (0.4528)2Liu Bei (0.2085)Liu Bei (0.1304)Liu Bei (0.4442)3Zhuge Liang (0.1714)Zhuge Liang (0.1093)Zhuge Liang (0.4313)4Sun Quan (0.1060)Sun Quan (0.0695)Sun Quan (0.4073)5Zhao Yun (0.0998)Sima Yi (0.0430)Guan Yu (0.3969)6Guan Yu (0.0972)Zhao Yun (0.0413)Zhao Yun (0.3963)7Yuan Shao (0.0813)Liu Shan (0.0402)Sima Yi (0.3924)8Sima Yi (0.0742)Guan Yu (0.0375)Wei Yan (0.3856)9Lv Bu (0.0716)Yuan Shao (0.0369)Yuan Shao (0.3842)10Wei Yan (0.0707)Jiang Wei (0.0357)Cao Ren (0.3824)


## 5. Cluster Analysis

### 5.1. Cooccurrence and Similarity Matrix

The cooccurrence matrix measures the frequency that two characters appear together. A cooccurrence matrix of main characters in the RTK network is presented in Table4. It is a symmetric matrix, and data on the diagonal show the frequencies of characters that appear in text.Table 4
Cooccurrence matrix of main characters.
CooccurrenceLiu BeiCao CaoSun QuanZhuge LiangGuan YuZhang FeiLiu Bei5411125819010675Cao Cao11227539505816Sun Quan583914528182Zhuge Liang19050283364325Guan Yu10658184327247Zhang Fei751622547165The cooccurrence of two characters cannot be used as the similarity because it is greatly affected by frequency. We normalize the cooccurrence matrix utilizing the Ochiai coefficient [12] and obtain the similarity matrix. Ochiai coefficient is defined by
(4)K=nA∩BnA×nB.AsA and B are sets, nA is the number of elements in A and nA∩B is the number of cooccurrence. The similarity matrix calculated by the Ochiai coefficient is described in Table 5.Table 5
Ochiai similarity matrix of main characters.
CooccurrenceLiu BeiCao CaoSun QuanZhuge LiangGuan YuZhang FeiLiu Bei10.2903710.2070830.4456410.2763270.251027Cao Cao0.29037110.1953050.1644880.2120690.075112Sun Quan0.2070830.19530510.1268540.0906370.01293Zhuge Liang0.4456410.1644880.12685410.1422380.106176Guan Yu0.2763270.2120690.0906370.14223810.221856Zhang Fei0.2510270.0751120.012930.1061760.2218561


### 5.2. Hierarchical Clustering

#### 5.2.1. Clustering Algorithm

An agglomerative hierarchical clustering algorithm utilizing the Ochiai similarity matrix is implemented to complete the task of cluster analysis. It is a bottom-up approach. Initially, each node is treated as a single cluster. Two clusters with the largest Ochiai similarity are combined into a new bigger cluster. The clustering algorithm stops when it achieves a setting threshold or there is only one cluster left. The similarity between two clusters is defined as the average similarity between each of their nodes.


#### 5.2.2. Evaluation

The P-IP scores [13] are adopted to measure the clustering result. There are m character names and n clusters. Suppose Cij is the number of character names marked with label j for character name i, where j=argkmaxk=1,2,⋯,nCik. The precision and recall of character name i can be given by
(5)Pi=Cij∑l=1mClj,Ri=Cij∑k=1nCik.Thus, theF score is calculated by
(6)Fi=2PiRiPi+Ri.The overall precision, recall, andF score are the averages of corresponding values. Moreover, the gold standard is built by marking the character name with a specific kingdom tag. For example, Cao Cao is tagged with “Wei” and Liu Bei is tagged with “Shu.” Finally, 308 character names with definite kingdom tags are secured for cluster analysis.


#### 5.2.3. Clustering Result

The result of hierarchical clustering is illustrated in Table6. The F score achieves the best value of 79.89% when the number of clusters k is 15.Table 6
The clustering result of the RTK network (k is the final number of hierarchical clusters).
kPrecisionRecallF score…………1143.83%78.90%56.35%1247.08%78.90%58.97%1371.10%75.00%73.00%1471.10%75.00%73.00%1587.66%73.38%79.89%1687.66%62.99%73.30%1787.66%59.09%70.60%1887.66%50.97%64.46%…………


### 5.3. Improved Clustering Algorithm

In the RTK network, some characters play a vital role in interconnections of different kingdoms, like “Lu Su” between Wu and Shu, “Huang Gai” between Wu and Wei. These characters have a high betweenness according to the definition of betweenness (see Section4.5). Further, the node betweenness can be extended to “edge betweenness” [14]. The link with a high edge betweenness is often a bridge between different clusters (see red link in Figure 4). Therefore, removing these high-betweenness links by setting a similarity of 0 will reduce the intercluster similarity and improve the clustering result eventually. The removal operation can be introduced as preprocessing before conducting the cluster analysis.Figure 4
A link with a high edge betweenness.The improved clustering algorithm using edge betweenness is executed, and the result is displayed in Table7. When the number of removals is zero, it is the baseline of the original algorithm. With an adequate removing operation, the F score reaches a peak of 80.87%. Nevertheless, removing too many links will destroy the whole network and make the F score decline dramatically (see Figure 5).Table 7
The clustering result of the RTK network (k is the final number of hierarchical clusters).
Number of removalsPrecisionRecallF score087.66%73.38%79.89%587.66%73.38%79.89%1088.31%73.38%80.15%1588.64%74.35%80.87%2088.64%74.35%80.87%2588.64%74.35%80.87%3088.64%74.35%80.87%3588.64%74.35%80.87%4088.96%73.70%80.62%4588.96%73.38%80.42%5089.94%73.05%80.62%5589.94%72.08%80.02%6047.73%90.58%62.52%…………Figure 5
The change ofF score according to the number of removals.


### 5.4. Analysis

Data visualization is also given to display the characteristics of historical figures in the RTK network. As hierarchical clustering can be depicted as a tree-based visual dendrogram, we visualize the character relationship in the RTK novel from Chapter 43 to 50, which is a period describing “the battle of Red Cliffs” (see Figure6).Figure 6
Dendrogram of clustering result for the period of “the battle of Red Cliffs.”As can be seen from Figure6, six parts can be divided manually. H1 and H3 are groups containing characters from “Wu,” like Sun Quan and Sun Ce. H2 encompasses main characters from “Shu” and “Wu” in the battle of Red Cliffs: Liu Bei, Guan Yu, Zhuge Liang, Zhou Yu, Lu Su, etc. However, there are two exceptions: Cao Cao and Cheng Yu, because they are highly connected with other main characters in the battle of Red Cliffs. Further, H1, H3, and H2 merge into a bigger cluster in the hierarchical clustering because these characters are from the alliance of “Wu” and “Shu” against Cao’s army.On the other hand, H5 is composed of characters from a large group “Wei,” including Xiahou Dun, Xiahou Yuan, Cao Ren, and Cao Hong. H6 includes few characters from “Shu” or “Wu.” H4 is not a cluster, and it contains a number of characters from different kingdoms.


## 5.1. Cooccurrence and Similarity Matrix

The cooccurrence matrix measures the frequency that two characters appear together. A cooccurrence matrix of main characters in the RTK network is presented in Table4. It is a symmetric matrix, and data on the diagonal show the frequencies of characters that appear in text.Table 4
Cooccurrence matrix of main characters.
CooccurrenceLiu BeiCao CaoSun QuanZhuge LiangGuan YuZhang FeiLiu Bei5411125819010675Cao Cao11227539505816Sun Quan583914528182Zhuge Liang19050283364325Guan Yu10658184327247Zhang Fei751622547165The cooccurrence of two characters cannot be used as the similarity because it is greatly affected by frequency. We normalize the cooccurrence matrix utilizing the Ochiai coefficient [12] and obtain the similarity matrix. Ochiai coefficient is defined by
(4)K=nA∩BnA×nB.AsA and B are sets, nA is the number of elements in A and nA∩B is the number of cooccurrence. The similarity matrix calculated by the Ochiai coefficient is described in Table 5.Table 5
Ochiai similarity matrix of main characters.
CooccurrenceLiu BeiCao CaoSun QuanZhuge LiangGuan YuZhang FeiLiu Bei10.2903710.2070830.4456410.2763270.251027Cao Cao0.29037110.1953050.1644880.2120690.075112Sun Quan0.2070830.19530510.1268540.0906370.01293Zhuge Liang0.4456410.1644880.12685410.1422380.106176Guan Yu0.2763270.2120690.0906370.14223810.221856Zhang Fei0.2510270.0751120.012930.1061760.2218561


## 5.2. Hierarchical Clustering

### 5.2.1. Clustering Algorithm

An agglomerative hierarchical clustering algorithm utilizing the Ochiai similarity matrix is implemented to complete the task of cluster analysis. It is a bottom-up approach. Initially, each node is treated as a single cluster. Two clusters with the largest Ochiai similarity are combined into a new bigger cluster. The clustering algorithm stops when it achieves a setting threshold or there is only one cluster left. The similarity between two clusters is defined as the average similarity between each of their nodes.


### 5.2.2. Evaluation

The P-IP scores [13] are adopted to measure the clustering result. There are m character names and n clusters. Suppose Cij is the number of character names marked with label j for character name i, where j=argkmaxk=1,2,⋯,nCik. The precision and recall of character name i can be given by
(5)Pi=Cij∑l=1mClj,Ri=Cij∑k=1nCik.Thus, theF score is calculated by
(6)Fi=2PiRiPi+Ri.The overall precision, recall, andF score are the averages of corresponding values. Moreover, the gold standard is built by marking the character name with a specific kingdom tag. For example, Cao Cao is tagged with “Wei” and Liu Bei is tagged with “Shu.” Finally, 308 character names with definite kingdom tags are secured for cluster analysis.


### 5.2.3. Clustering Result

The result of hierarchical clustering is illustrated in Table6. The F score achieves the best value of 79.89% when the number of clusters k is 15.Table 6
The clustering result of the RTK network (k is the final number of hierarchical clusters).
kPrecisionRecallF score…………1143.83%78.90%56.35%1247.08%78.90%58.97%1371.10%75.00%73.00%1471.10%75.00%73.00%1587.66%73.38%79.89%1687.66%62.99%73.30%1787.66%59.09%70.60%1887.66%50.97%64.46%…………


## 5.2.1. Clustering Algorithm

An agglomerative hierarchical clustering algorithm utilizing the Ochiai similarity matrix is implemented to complete the task of cluster analysis. It is a bottom-up approach. Initially, each node is treated as a single cluster. Two clusters with the largest Ochiai similarity are combined into a new bigger cluster. The clustering algorithm stops when it achieves a setting threshold or there is only one cluster left. The similarity between two clusters is defined as the average similarity between each of their nodes.


## 5.2.2. Evaluation

The P-IP scores [13] are adopted to measure the clustering result. There are m character names and n clusters. Suppose Cij is the number of character names marked with label j for character name i, where j=argkmaxk=1,2,⋯,nCik. The precision and recall of character name i can be given by
(5)Pi=Cij∑l=1mClj,Ri=Cij∑k=1nCik.Thus, theF score is calculated by
(6)Fi=2PiRiPi+Ri.The overall precision, recall, andF score are the averages of corresponding values. Moreover, the gold standard is built by marking the character name with a specific kingdom tag. For example, Cao Cao is tagged with “Wei” and Liu Bei is tagged with “Shu.” Finally, 308 character names with definite kingdom tags are secured for cluster analysis.


## 5.2.3. Clustering Result

The result of hierarchical clustering is illustrated in Table6. The F score achieves the best value of 79.89% when the number of clusters k is 15.Table 6
The clustering result of the RTK network (k is the final number of hierarchical clusters).
kPrecisionRecallF score…………1143.83%78.90%56.35%1247.08%78.90%58.97%1371.10%75.00%73.00%1471.10%75.00%73.00%1587.66%73.38%79.89%1687.66%62.99%73.30%1787.66%59.09%70.60%1887.66%50.97%64.46%…………


## 5.3. Improved Clustering Algorithm

In the RTK network, some characters play a vital role in interconnections of different kingdoms, like “Lu Su” between Wu and Shu, “Huang Gai” between Wu and Wei. These characters have a high betweenness according to the definition of betweenness (see Section4.5). Further, the node betweenness can be extended to “edge betweenness” [14]. The link with a high edge betweenness is often a bridge between different clusters (see red link in Figure 4). Therefore, removing these high-betweenness links by setting a similarity of 0 will reduce the intercluster similarity and improve the clustering result eventually. The removal operation can be introduced as preprocessing before conducting the cluster analysis.Figure 4
A link with a high edge betweenness.The improved clustering algorithm using edge betweenness is executed, and the result is displayed in Table7. When the number of removals is zero, it is the baseline of the original algorithm. With an adequate removing operation, the F score reaches a peak of 80.87%. Nevertheless, removing too many links will destroy the whole network and make the F score decline dramatically (see Figure 5).Table 7
The clustering result of the RTK network (k is the final number of hierarchical clusters).
Number of removalsPrecisionRecallF score087.66%73.38%79.89%587.66%73.38%79.89%1088.31%73.38%80.15%1588.64%74.35%80.87%2088.64%74.35%80.87%2588.64%74.35%80.87%3088.64%74.35%80.87%3588.64%74.35%80.87%4088.96%73.70%80.62%4588.96%73.38%80.42%5089.94%73.05%80.62%5589.94%72.08%80.02%6047.73%90.58%62.52%…………Figure 5
The change ofF score according to the number of removals.


## 5.4. Analysis

Data visualization is also given to display the characteristics of historical figures in the RTK network. As hierarchical clustering can be depicted as a tree-based visual dendrogram, we visualize the character relationship in the RTK novel from Chapter 43 to 50, which is a period describing “the battle of Red Cliffs” (see Figure6).Figure 6
Dendrogram of clustering result for the period of “the battle of Red Cliffs.”As can be seen from Figure6, six parts can be divided manually. H1 and H3 are groups containing characters from “Wu,” like Sun Quan and Sun Ce. H2 encompasses main characters from “Shu” and “Wu” in the battle of Red Cliffs: Liu Bei, Guan Yu, Zhuge Liang, Zhou Yu, Lu Su, etc. However, there are two exceptions: Cao Cao and Cheng Yu, because they are highly connected with other main characters in the battle of Red Cliffs. Further, H1, H3, and H2 merge into a bigger cluster in the hierarchical clustering because these characters are from the alliance of “Wu” and “Shu” against Cao’s army.On the other hand, H5 is composed of characters from a large group “Wei,” including Xiahou Dun, Xiahou Yuan, Cao Ren, and Cao Hong. H6 includes few characters from “Shu” or “Wu.” H4 is not a cluster, and it contains a number of characters from different kingdoms.


## 6. Conclusions

This paper developed a general framework for analyzing the character relationship in the novel. TheRomance of the Three Kingdoms is taken as the object of analysis. At first, the raw text of the RTK novel is processed with NLP tools and character names are recognized by lexical analysis. Then, a character name network is created based on coword analysis. After building the network, several network features are calculated such as degree distribution, average shortest-path length, and clustering coefficient. Besides, cluster analysis is conducted and it helps to better understanding of the hierarchical structure for characters in the RTK novel. A modified clustering algorithm using edge betweenness is proposed to improve the effect of clustering. Finally, visualization of results is completed to analyze the hierarchical clustering.There are some limitations of the proposed method since coword analysis does not necessarily reflect the true meaning of character relationship. However, our approach can study the main characters quantitatively and comprehend character relationship from another perspective. Hence, it is a valuable research direction.Subsequent work will study the meaning of pronouns because they represent different characters in different situations. Further, place names and institutions will be taken into consideration in the future.



---

*Source: 5553635-2021-04-01.xml*