基于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 算法进行划分。并未对算法加以改进或融合适宜文本人物关系划分的某种方法，以致划分结果并不十分精确。

后续研究可围绕这两个问题，以期将文本人物的亲疏远近精确的划分出来，从《三国演义》文本推而广之到其他文本。