基于louvain算法的《三國演義》文本人物社群劃分研究*

嚴祥偉 雒偉群

（西藏民族大學信息工程學院，陜西 咸陽 712082）

0 引言

隨著經濟的發展，網絡文字成為當前傳遞信息最常用的載體，尤其是文本信息。在當前計算機應用技術進一步成熟的趨勢下，計算機已經可以處理身邊的許多事情。其中之一便是對中文文本的分析和處理。本文將《三國演義》的人物視作圖的節點，對人物之間的關系抽象成圖的邊，建立了人物關系網絡圖，之后對網絡圖進行了社群結構劃分，將其大致劃分出了魏蜀吳三方勢力。

社群結構由Newman［1］提出，即在一個社交網絡圖中，存在子圖內個體關系緊密、子圖間個體關系稀疏。現階段復雜網絡社群結構劃分方法，主要分為兩種，一種是邊的分離，一種是節點的聚合。對于n個節點，最多可有條邊，故在大型復雜網絡中，邊分離算法由于其較高的時間復雜度，明顯不如節點聚合算法。鑒于此，節點聚合類算法接連取得進展，從Newman等［2］最初提出了一個模塊度概念。隨后，基于模塊度的社群劃分算法研究逐漸趨于成熟，FN(fast Newman)算法［3］和louvain算法［4］便是基于模塊度的經典算法。louvain算法在效率和維度上，是目前公認非重疊社區方法中最好的［5］，被廣泛應用于網絡的社群劃分。

自louvain算法誕生以來，與此相關的應用如雨后春筍般涌出，林定等［6］在提出一種圖的三維樹形可視化方法時，利用了louvain算法對其中復雜的網絡關系進行了層次聚類。徐進等［7］利用louvain 算法對鐵路旅客社會網絡進行社群劃分，提取出聯系緊密的的旅客出行團體。黃志宏等［8］為了在網絡威脅入侵日志中準確發現攻擊者，使用louvain算法對攻擊事件特征圖進行聚類，以構建網絡攻擊者畫像。生物學上，馮一城等［9］利用louvain 算法來分析社團演化和木聚糖酶耐熱性的關系。輿情分析上，韓珂珂等［10］在新冠肺炎期間，對新浪微博上的33 萬條數據利用louvain 算法，分析出不同區域的輿情特點與關注主題差異。醫學上，嚴明等［11］基于louvain 聚類方法，挖掘連花清瘟膠囊治療上呼吸道感染聯合用藥方案的規律。

以上已經取得的相關研究成果，給我們生活帶來了極大改變，但就目前而言，在文學上，利用louvain算法對文中人物的社群劃分卻鮮有研究。尤其是人物關系錯綜復雜的文學小說。本文對《三國演義》人物關系網絡進行了louvain 算法社群劃分。深度挖掘了文中人物關系，引導我們從不同角度進行思考，旨在幫助讀者深入理解小說。

1 louvain算法

louvain 算法由BLONDEL V D、GUILLAUME JL、LAMBIOTTE R、LEFEBVREE 四人提出，也稱BGLL 算法。它是一種基于模塊度（Modularity）Q 的社群劃分算法。模塊度Q 是經過某種特定劃分結果的聚合性與隨機劃分結果聚合性之間的差值［12］，常用來評價社群劃分結果的質量。模塊度Q 越大，表明社群劃分結果越好。

在一個有權的網絡中，模塊度的定義如公式1：

對(1)化簡得公式2：

Σin表示社群C 中所有邊的權值和，Σtot表示連接到社群C 的所有邊的權值和。（2）式可以看出社群C 的模塊度為其下各個社群模塊度之和。可分別進行計算。

Louvain 算法基于模塊度，可對社群進行高效劃分，主要分為兩個階段。

在第一階段初始時，我們將每一個節點視作一個獨立社群。

①按照一定次序遍歷整個網絡，對于每個節點，將其嘗試分配到任意鄰居節點所在的社群，計算其加入前后，目標社群模塊性增量?Q，如果?Q＞0，則將節點添加進使?Q最大的那個社群。

模塊性增量?Q如公式3：

公式(3)為節點a 移動到社群C，其模塊性增量。∑in與∑tot含義見公式（2）說明。Ka,in表示節點a到社群C所有邊的權值和。

②對所有節點，迭代執行上述步驟，直到沒有節點可移動。

例如：對于圖1 左邊所示網絡圖結構，圖1 右邊為第一階段結束狀態。

第二階段時，我們將前述所得的劃分結果，重新視為一個網絡圖，網絡圖的節點為第一階段劃分出的社群，將其視為超節點。超節點的權值為社群內部邊的權值和，超節點之間邊的權值為社群外部邊的權值和。

對超節點構成的新圖，迭代執行①②步驟，直到沒有超節點可移動。如圖2所示為第二階段結束狀態。

2 實驗及結果分析

以四大名著之一《三國演義》為例，將其作為實驗對象，對其中人物建立網絡圖，使用三種不同方式可視化，并用louvain算法進行社群劃分。

實驗概要設計：

（1）實驗前期準備，列出了實驗環境及設備。

（2）數據及預處理，一是說明了研究所用文本數據及其來源；二是考慮到中文不存在天然的詞語劃分標志，對《三國演義》文本進行了分詞，并對其中需要分析的人物建立了實體，為后續數據分析做準備。

（3）關系網絡圖生成，依照鄰近共現規則建立人物關系網絡圖。

（4）人物關系網絡圖可視化，使用三種不同方式對建立的人物關系網絡圖進行了可視化。

（5）人物關系網絡圖社群劃分，對人物網絡圖節點進行了基于louvain 算法社群劃分，劃分出人物社群。

2.1 實驗前期準備

實驗環境及設備如表1：

表1 實驗環境及設備

2.2 實驗數據及預處理

2.2.1 獲取文本數據。本文所用數據為《三國演義》全文文本，來源于“古詩文網”（https://so.gushiwen.cn/guwen/ book_46653FD803893E4F7F702BCF1F7CCE17.aspx）。它的獲取得益于python爬蟲技術，對其進行逐章爬取。

網絡爬蟲通俗來講是一段在網絡上自動抓取信息的程序，在法律允許的范圍內，可以方便快捷的實現數據的搜索和下載。它可以為搜索引擎從萬維網上下載網頁，是搜索引擎的重要組成［13］。傳統網絡爬蟲從一個初始網頁的URL開始，首先需要獲得初始網頁上的URL，并響應其中內容，從當前頁面不斷抽取所需要的信息，或者新的URL 繼續迭代，直到爬取完所需信息。在python 中有許多可以用于數據爬取的第三方庫，方便快捷易于編寫。

本文使用了python 中兩個功能強大的爬蟲相關庫，requests 和lxml。requests 庫作為一種HTTP 庫，在urllib 基礎上進一步封裝，用來進行網頁下載，獲取響應內容。在爬蟲中，發揮主要作用的是lxml網頁解析庫，采用了該庫支持的XPath 解析方式對網頁的各個標簽進行解析，找到所需文本數據后，爬取到txt 文檔即可。將爬取下來的文本數據經過簡單預處理后，以json格式存儲。

2.2.2 中文分詞。中文分詞是指將中文文本基于某種需求劃分為“詞”的過程［14］。目前常用的分詞方法為基于統計的分詞方法。即是根據字和詞的統計信息，把相鄰字間的信息、詞頻及相應的共現信息等應用于分詞。

Jieba分詞是Python環境中常用的分詞工具，它屬于基于統計詞典的分詞方法。有三個主要特點，一是支持3 種分詞模式，分別是精確模式、全模式、搜索引擎模式；二是支持繁體分詞；三是支持自定義詞典［15］。

于本文來說，由于Jieba 分詞支持自定義詞典，帶給本文了極大便捷。除了自定義詞典，它本身就具有一個名為dict.txt 的詞典，擁有2000 多個中文字詞，由人民日報等語料數據訓練。其大致工作流程為先將載入的dict 詞典生成Trie 樹，再利用dict 詞典對輸入句子進行切分，生成分詞的有向無環圖（DAG）。從DAG圖中可以得出該句子的多種分詞路徑，找出其最短路徑。對于未登陸詞典的詞，采用隱馬爾可夫模型（Hidden Markov Model）來預測分詞，實現新詞發現。使用維特比（Viterbi）算法動態規劃來得到分詞和標注。最后基于TF-IDF 和textrank 模型來提取關鍵詞。隨著大規模語料庫建立，jieba 分詞的實用性較好，能夠對文本進行高效處理。它與python 中相關工具庫的結合，在文本分析、識別上具有廣闊的應用前景。

本文使用內置了jieba 的harvesttext 庫，對全文文本進行切分，實際操作中分為以下兩個步驟：

（1）登錄新詞

文本切分時，如果直接使用常規分詞，可能將文中的不可分割的名詞分開，故應先指定出專有名詞，將其作為新詞登錄到詞典中。以下展示了是否登陸新詞的不同分詞結果：

常規分詞:武鄉侯/七擒/南蠻/王

登陸“南蠻王”后:武鄉侯/七擒/南蠻王

（2）實體鏈接

《三國演義》中許多人物有不同的別稱，如南蠻王即是孟獲的別稱，武鄉侯指的是諸葛亮。此外諸葛亮還有臥龍、孔明等別稱，此時需要將別稱統一處理，即文中所有地方出現的“臥龍”“孔明”“武鄉侯”，都將其視作“諸葛亮”。為達到這一目的，我們將專有名詞諸葛亮建成一個實體，并指定人名類型，對實體的抽取調用了harvesttext庫。在本實驗中建立了1064個人物實體。

建成實體，指定類型格式如下：

對于建成的實體在分詞時優先切分出來，而后內置的jieba庫再對句子進行常規切分，選擇將別稱替換為對應實體名，如下：

“武鄉侯/七擒/南蠻王”

“諸葛亮/七擒/孟獲”

2.3 關系網絡圖的生成

網絡的構建分為節點和邊的構建。提取文中實體，將其作為網絡節點。網絡邊則定義為實體之間的聯系。采用鄰近共現關系，即兩個實體在相鄰兩句話內同時出現，則視之存在聯系，其間繪制這條邊，由此得到共現網絡。實體間聯系的次數則以邊的權重表示，這種共現關系每出現一次，則邊的權重加1。

本文的具體操作先將文本切分為單句，形成單句列表［1,2,3,...］，進而構造成二連句列表，形如［12,23,34,...］，逐個提取二連句使用harvesttext 庫處理，該庫利用鄰近共現規則，將二連句中實體和實體之間的關系識別出來，識別實體的過程稱作命名實體識別。最后使用其內置的networkx 庫繪制節點和邊，形成人物關系網絡圖。

如以下二連句示例，及其對應的網絡如圖3：

①程遠志大怒，遣副將鄧茂出戰。

②張飛挺丈八蛇矛直出，手起處，刺中鄧茂心窩，翻身落馬。

以上二連句中出現了三個人物：程遠志、鄧茂、張飛，則繪制出三個節點。由于張飛、程遠志在相鄰兩句話中只出現了一次，則他們之間加一條邊。由于鄧茂在相鄰兩句話中出現了兩次，則在鄧茂-張飛、鄧茂-程遠志之間加兩條邊。

在后續處理其他二連句時，繼續向其中加入節點和邊，逐漸形成全文人物關系網絡圖。

2.4 人物關系網絡圖的可視化

對于數據的可視化，有多種選擇，最常用的是基于標簽云、基于樹圖以及基于關聯的文本可視化。由于本文是人物之間的共現關系建立的人物關系網絡圖，在可視化時，應充分凸顯人物實體之間的聯系。為了達到這一要求，采用基于實體關聯的文本可視化，這種可視化更好的給讀者反映了實體之間的多層面信息，也更便于社群的劃分及展示。以下使用不同的方式對建立的網絡圖進行可視化：

2.4.1 matplotlib 庫可視化網絡圖。對于networkx 構建的網絡圖，可直接使用matplotlib庫進行可視化。只需將節點的度對應為節點的大小，邊的權重對應為邊的寬度，調用pyplot.show（）即可顯示之。這里使用FR（Fruchterman-Reingold）布局算法布局網絡圖，FR算法基于粒子物理理論，將節點模擬成原子，模擬原子間的力場來計算節點間的位置關系，反映了網絡圖人物之間的“遠近”。通過考慮原子間引力和斥力的互相作用，計算得到節點的速度和加速度，最終進入一種動態平衡狀態。

以每個章節作為建圖最小單位，即可研究任意章節范圍的人物關系。對第49 章（赤壁之戰）建立的人物關系網絡圖有40 個節點，篩選出節點度大于等于5的人物節點如圖4。圖中有23 個主要人物，其中黃蓋、周瑜、諸葛亮、曹操節點較大，連線較寬，視為赤壁之戰的主角，符合史實。

分別建立120 個章節的人物網絡圖，然后將其合并成一個總的網絡圖，總圖表現了三國演義中1064個人物實體的關系。取總圖最大連通分量，并篩選出度大于等于50 的人物節點。得到全文的85 個主要人物網絡如圖5所示，處于全圖中心位置，節點大的視為全文的核心人物。

2.4.2 pyecharts 庫可視化網絡圖。對于已經構建好的networkx 型Graph 圖，還可以進一步重構節點和邊的數據，將其改造成pyecharts 庫可識別的結構，并調用pyecharts庫進行可視化，生成一個Echarts圖表。

Echarts 是一個使用JavaScrit 實現的開源可視化庫，在python 環境下需通過PyEcharts 庫對接口進行調用，生成的Echarts 圖表，可流暢地運行在PC 和移動設備上，兼容當前絕大部分瀏覽器［16］，圖表作為一個獨立網頁存在。使用Pyecharts 生成的網絡圖如圖6，相比matplotlib 生成的人物網絡，具有的一定的可交互性。

2.4.3 Gephi 軟件可視化網絡圖。生成網絡圖時，不僅可以在python 環境下調用第三方庫，還可以借助分析網絡圖更專業的Gephi軟件。Gephi基于JVM開發，可用于多種網絡和復雜系統的可視化，它在應對復雜網絡系統上，能進行更強大的人機交互性分析［17］。在構建pyecharts 型人物網絡圖時，可將節點和邊的信息連帶輸出，生成一個csv 文件，使用Gephi 軟件打開該csv 文件，即可得到人物網絡如圖7 所示，在Gephi 軟件中可以對圖進行更多的交互性操作。

2.5 人物關系網絡圖社群劃分

對于建立的人物關系網絡圖，我們采用louvain算法對其進行社群劃分。

由于《三國演義》全文時間跨度較長，到第98 回，孫權最后一個稱帝時，三國鼎立完全建立。我們取前98個章節，建立全網絡圖。同樣篩選出節點度大于等于50的人物，計72個主要人物，進行基于louvain算法的社群劃分。使用louvain 算法將前98 個章節人物關系圖劃分結果如圖8～10。

在圖中大致劃分出了魏蜀吳三方勢力：

魏勢力中人物多而雜，不僅有曹魏將領，也有曹操早期敵對人物，這是由于曹操發跡于北方，從起兵征伐董卓開始，歷經數十年征戰，消滅呂布、袁術、袁紹等，驅逐馬超、馬岱，一統北方。使曹魏政權有了在北方大片地區建立的基礎。故這些早期敵對人物也都出現在了曹魏北方集團里。

蜀勢力中，人物節點較多較大，主要因為作者羅貫中，較為傾向蜀漢正統。從《三國演義》開篇從桃園三結義講起，以劉關張、諸葛亮等作為主線，詳細敘述了他們的經歷。故蜀漢集團人物出場次數較多。值得注意的是，司馬懿也赫然在列，這是由于司馬懿本身出場比較晚，加上曹操在世時，未重用司馬懿，導致他出場率不是很高。直到諸葛亮北伐時，曹睿才被迫啟用司馬懿，他的大多數出場都與諸葛亮鄰近共現。在建立網絡圖時，系統并不知道司馬懿和諸葛亮作為對手而存在，只是按照鄰近共現的規則將他們一同提取出來，所以二者的聯系相對緊密，甚至超過了在各自集團中與其他人的聯系程度。所以司馬懿被系統錯誤的劃進了蜀集團。

吳勢力中，出現人物較少，這是由于在《三國演義》中，許多篇幅描寫的都是蜀漢正統和曹魏篡漢政權的爭斗，東吳集團從孫堅父子三人開始，便處于割據勢力，很少主動參與中原爭斗，在三足鼎立中作為平衡的杠桿，相比其他兩方，人物出場次數較少。

3 結束語

本文結合python 數據處理技術對《三國演義》文本人物進行了社群劃分。在爬取全文文本數據后，使用中文分詞技術對其進行處理，并將《三國演義》的人物依據鄰近共現關系建立人物關系網絡圖。對網絡圖分別使用matplotlib 庫、pyecharts 庫、gephi 軟件進行可視化。實驗結果對人物進行了基于louvain 算法的社群劃分，劃分結果有一定的趣味性，在激發讀者興趣、提供專業讀者以不同角度的思考方面，有一定的應用價值。

但本文的不足之處也顯而易見：一是使用鄰近共現規則建圖，只能識別人物在文中物理位置的“鄰近”，無法識別文章作者真正想表達的“親疏”關系；二是在社群劃分時，只是單純使用louvain 算法進行劃分。并未對算法加以改進或融合適宜文本人物關系劃分的某種方法，以致劃分結果并不十分精確。

后續研究可圍繞這兩個問題，以期將文本人物的親疏遠近精確的劃分出來，從《三國演義》文本推而廣之到其他文本。