Graph_Generator

Python语言设计与实践 第一次项目

需求

• 一键生成一个图，并把相应的连接矩阵构建出来，并把连接矩阵存进Excel表中

• 解决最短路算法问题，解决 PageRank 算法问题，并做出相应的排序

• 解决爬虫问题，红楼梦的知识图谱问题和词云，论文引用的知识图谱问题，以及论文引用的 PageRank 算法问题

分析

• 我们组本项目采用了无向图和有向图两种方式供用户选择，用 networkx 和 matplotlib 两个库来创建图，同时采用 xlsxwriter 将连接矩阵导出为Excel

• 同时采用目前最新 PySide6 库来创建UI界面，并使用 qt_material 中的配置文件来美化界面，使用 scipy 库来做改进所支持的结点数

• 在解决第二次需求的过程中，处理最短路算法和 PageRank 算法，用到 plotly.graph_objects 和 plotly_express 来分别绘制柱状图和散点图 由于这两个库生成的图片会自动生成 html文件用以展示图片，所以在 Frame 的最后调用析构函数来删除冗余的 html 文件

• 在实现第三个需求的过程中

  • 首先对于爬虫问题，是针对一个红楼梦网址设计的爬虫，并且用上了三个反爬措施

  • 对于红楼梦和论文引用的知识图谱，采用抽取出来的三元组，即 .csv 数据集，采用 neo4j 图数据库来构建知识图谱，并 用到爬虫所爬取到的红楼梦全文来创建词云

  • 对于论文引用的 PageRank 问题，则是调用第二个需求中实现的 PageRank 算法来解决

环境

python 版本:3.11

项目框架的说明

• CharactersImages 存的是20个重要人物的知识图谱，用于选择展示

• images 文件夹中存放生成的图片，以有向图和无向图进行分类存放

• Kernel 文件夹中为核心功能的 Python 文件

• KnowledgeGraph 文件夹中为实现红楼梦和论文引用知识图谱的核心文件

• Spider 文件夹中为实现爬虫的核心文件

• Thesis 文件夹中为处理50篇论文引用的核心文件

• WordClouds 文件夹中为处理红楼梦词云的核心文件

• xlsx 文件夹中存放生成的Excel文件，同样是以有向图和无向图进行分类存放

• config.txt 中为本项目需要的所有配置，配置环境时可采用以下命令行安装库

pip install -r config.txt

• Frame.py 为本项目的整体架构文件

• generator_ui.py 为 generator_ui.ui 转成的 Python 文件，里面是UI界面的代码，通过以下命令转换：

pyside6-uic generator_ui.ui -o generator_ui.py

• main.py 文件运行 Frame.py 中的 run 函数，以此执行项目

• temp 文件夹保存生成的 html 文件，等待后续的删除；同时利用 dat.dat 文件来占位

• version 文件夹保存的是上一版本的相关代码

• 由于参考代码中生成的图片会覆盖原先生成的图片，所以本项目对这部分进行优化，引入时间 time 模块，用时间戳命名图片和Excel文件，这样可以保证名字永远唯一而不被覆盖

• HLMLauncher.py 文件为红楼梦相关功能的一起创建

• PaperLauncher.py 文件为论文引用相关功能的一起创建

• neochecker.py 主要是检测图数据库是否连接上，初次使用需要设为 False ，后续可以设置为 True ，加快速度

• neochecker.bat 为登录 neo4j 图数据库的命令行，被内部代码调用执行，不必手动调用和写命令行

• struct.png 为整体项目的框架视图

改进

• 由于一开始原本的库只能支持最多200多个结点，临时改进，下载一个 scipy 库，就可以支持到1000个结点

• 下来查阅资料发现是 networkx 底层处理大数据的时候会用到 scipy 库，所以加上这个库才可以处理更大的数据

• 同时这次版本的UI界面相对于上一版本也有一定的改进和升级

关于算法的一些说明

本项目主要包括两个算法，分别是 最短路算法 和 PageRank 算法

• 对于最短路算法，整体包含两种，分别是 单源最短路 和 多源最短路 ，多源最短路的典型代表是 Floyd ，而单源最短路 的典型代表是 Dijkstra 而由于 Dijkstra 不能处理负权的情况，所以这里采用了能处理负权的 Bellman-Ford 和 SPFA 算法，其中后者是前者加了队列优化

• 然后对于 Floyd ，我们不仅调用了相关库函数，也自己实现了这个算法，并且给出相应运行效率的对比图；而对于单源最短路算法， 我们也自己实现了 SPFA 算法并与库函数的 Bellman-Ford 作比较

• 最后对于 PageRank 算法，我们也同样给出了自己模拟的过程，并与库函数的原生方法做对比

关于知识图谱

• 采用抽取出来的三元组形成的csv文件来构建知识图谱，用到 neo4j 图数据库的社区版，并且分别包含两张不同后缀名的知识图谱全图

• 包括此文件夹在内以 Test_ 开头的 Python 文件为单元测试所用，对项目的运行无影响，后续便不再赘述

• 由于该图数据库仅为社区版本，无法分离红楼梦和论文引用关系两张知识图谱，所以每次创建之前都把原先的先删掉

• 补充：

  若需要查找某个人物的所有关系，可采用 MATCH (p:Person {name: '贾宝玉'})-[r]-(other) RETURN p,r,other

  若需要找到某个人物与某个特定关系的结点，可采用 MATCH (p: Person {name:"贾宝玉"})-[k:丫鬟]-(r) RETURN p,k,r

  若需要找到一个人物与另一个人物之间的所有的结点，可采用 MATCH (p1:Person {name:"贾宝玉"}),(p2:Person{name:"香菱"}),p=shortestpath((p1)-[*..10]-(p2)) RETURN p

关于爬虫

• 大致思路 爬取网页源码 筛选所有章节的跳转链接 依次访问每个链接 得到每篇文章的内容

• 实现三个反爬措施

  • 添加 headers 字段，模拟浏览器的访问而非编译器的直接访问

  • 添加 time.sleep(1) 字段，使每次的访问存在1秒的时间间隔 避免短时间内大量访问

  • 添加 proxies 字段 模拟用户IP，避免访问过多次被封

• timeout 字段 在服务器长时间无应答时主动退出，避免死循环

关于论文引用部分

• 主要的核心文件包括两个， Matrix.py 和 PaperGraph.py

• 前者是生成连接矩阵供别的部分调用，后者是生成有向图供别的部分调用

• resources 文件夹中包含的是50篇原始没经过处理的论文，在其他 .py 文件中处理

关于词云

• 采用 jieba 库进行中文分词，采用 wordcloud 来创建词云

• 根据爬虫爬取的红楼梦全文来统计词频和创建词云

小组成员

Lin Xiaoyi, Tang Jiajun, Wang Zhen, Chen Guanrui, Wang Jing

此项目仅供学习交流使用，转载请注明出处！