随着人工智能、大数据及自媒体的快速进步，网络科学的计算思维与分析方法在人们生活、工作等方面得到了广泛应用与发展，同时也催生了各种对网络科学的理论计算方法和分析技术。本书主要围绕网络科学与计算展开，主要内容包括图论、网络模型、网络度分布及其度量、网络相似性度量、网络科学中的特征计算、网络谱度量、基于熵理论的网络科学分析、图计算重要算法、网络科学应用、网络科学计算分析。本书可读性强，内容丰富，涉及计算机科学、数学、新闻与传播学、社会学、管理学等多个学科领域。

网络科学是研究复杂网络与复杂系统如社交网络、生物网络、交通网络、认知和语义网络等的科学，主要由节点表示不同的元素或参与者，由连边表示元素或参与者之间的联系。网络科学借鉴了数学中的图论、物理学中的统计力学、计算机科学中的数据挖掘和信息可视化、统计学中的推断建模以及社会学中的社会结构等理论与方法。在现实生活中，我们应以网络的思维来思考问题。本书致力于研究网络科学及其计算方法，分析开放的网络科学与复杂系统，结合数学、物理学、控制论、信息论、传播学等交叉科学的相关技术与方法，重点介绍图论、网络模型、网络度分布及其度量、网络相似性度量、网络科学中的特征计算、网络谱度量、基于熵理论的网络科学分析、图计算重要算法、网络科学应用、网络科学计算分析等。 全书共 11 章。第1 章首先分析网络科学的相关定义，介绍什么是网络科学及网络科学的发展历程；接着描述网络科学中的一些基本概念，并对网络科学的性质进行简单阐述；然后介绍网络科学中影响较大的两种模型，并使用图例说明它们的重要性；最后讨论网络科学的前沿研究方向，聚焦于研究热点。 第 2 章介绍图的基本概念。首先介绍图的基本结构，接着介绍图的相关性质和四种广为人知的技术（邻接矩阵、邻接表、关联矩阵和边列表），然后介绍各种类型的图（零图和空图、有向图/无向图/混合图、简单图/多重图和带权图），最后讨论图的连通性及其相关概念、强连通分支和弱连通分支、两种特殊的树（生成树和斯坦纳树）等。 第 3 章首先简单介绍规则网络和随机网络，然后详细介绍与分析网络模型小世界网络，最后介绍无标度网络及其应用。 第 4 章首先介绍节点的度的概念，接着介绍度分布的概念及其在概率分布上的具体表现形式，然后介绍刻画网络的度相关性的几种不同方法，最后简要介绍度分布在实际场景中的具体应用。 第 5 章首先介绍图相似性问题的起源及其在相关领域中的应用，然后介绍图同构问题和图编辑距离问题，最后结合图神经网络（GNN）提出一种新型的图匹配模型。 第 6 章首先使用网络特征描述不同网络模型之间的区别与特点，接着分析网络科学中基于网络拓扑结构的特征，最后结合网络特征进行应用分析。 第 7 章首先给出谱的定义，接着介绍网络模型邻接矩阵的特征谱及其在网络中心性和二分性中的应用，最后介绍随机图的谱。 第 8 章介绍网络熵的概念，分析熵的衡量指标，并针对社交网络的研究提出许多关于节点重要度的评估算法。 第9 章首先分析图计算算法，如社区发现、链路预测与信息扩散，并且分别进行数学建模与仿真分析。在社区发现的研究过程中，对提出的社区发现算法进行应用分析；在链路预测算法中，结合不同数据集和传统模型进行对比分析，以验证所提出的链路预测算法的合理性与有效性；在信息扩散的研究过程中，结合用户感知影响激励分配机制提出并论证信息扩散影响力最大化模型。 第 10 章基于网络科学中网络信息级联预测、推荐系统、情感分析、复杂网络分层抽样、网络关键节点识别五个方向上的最新工作，介绍网络科学的应用。例如，在网络信息级联预测方面，结合生成方法和深度学习方法的GHawkes 模型来实现信息级联预测，表明激励点过程的图卷积级联预测GHawkes 模型的预测精度高于先前的方法，还表明在信息传播过程中用户影响力、网路拓扑结构、自激励机制和衰减机制是影响级联预测的重要因素；在推荐系统方向，提出一种融合社交关系的图卷积协同过滤推荐方法；在情感分析方向，提出一种基于中间融合的多模态情感分析模型。 第 11 章结合自然语言处理、社交网络分析和小说《人民的名义》，首先应用共词分析技术对小说进行关键人物提取，对小说进行人物重要性、相关性等分析，运用层次聚类方法对小说进行人物聚类，并运用词云绘制、社区划分进行直观可视化，最后运用Gephi 软件从不同角度绘制人物关系图谱，观察不同方法下人物的重要性。 本书的研究成果既可为相关管理部门提供决策参考和理论指导，又可帮助相关企事业单位优化产品与服务，并且依据网络科学中个体的不同特点，为用户提供精准的个性化推荐。 感谢为本书的完整性做出贡献的课题组成员：张子扬、付晓杨、高绿苑、肖伟、吴玉蝶、王浩田、李慧、丁楠、李祥、吴松阳、代尚宏、叶舒、马敏、张梦瑶等；感谢自己对网络科学与计算研究方向的热爱。 本书既适合作为高等学校计算机科学和人工智能等相关专业研究生的教材，也可供相关领域的研究人员参考。本书的出版得到了重庆理工大学研究生教育高质量发展行动计划资助（项目号gzljc202211）。由于作者水平有限，加之网络科学与计算技术的快速发展，书中不足之处在所难免，望读者不吝赐教。关于本书的宝贵建议，请读者发至邮箱lxy3103@163.com。 刘小洋

第1 章网络科学概论 ????????????????????????????????????????????????????????????????????????? 1 1.1 网络科学?????????????????????????????????????????????????????????????????????????????? 1 1.1.1 网络科学的相关定义?????????????????????????????????????????????????????? 1 1.1.2 网络科学的发展历程?????????????????????????????????????????????????????? 1 1.2 网络科学的基本概念??????????????????????????????????????????????????????????????? 4 1.2.1 连通性???????????????????????????????????????????????????????????????????????? 4 1.2.2 度与稀疏性?????????????????????????????????????????????????????????????????? 5 1.2.3 度分布???????????????????????????????????????????????????????????????????????? 5 1.3 网络科学的性质????????????????????????????????????????????????????????????????????? 5 1.3.1 大小??????????????????????????????????????????????????????????????????????????? 6 1.3.2 密度??????????????????????????????????????????????????????????????????????????? 6 1.3.3 网络直径????????????????????????????????????????????????????????????????????? 6 1.4 网络科学的主要模型??????????????????????????????????????????????????????????????? 7 1.4.1 艾狄胥-雷尼模型??????????????????????????????????????????????????????????? 7 1.4.2 瓦茨-斯特罗加茨模型????????????????????????????????????????????????????? 7 1.5 网络科学的分支领域??????????????????????????????????????????????????????????????? 8 1.5.1 生物神经网络??????????????????????????????????????????????????????????????? 8 1.5.2 人工神经网络??????????????????????????????????????????????????????????????? 8 1.5.3 经济网络????????????????????????????????????????????????????????????????????10 1.6 网络科学的前沿方向??????????????????????????????????????????????????????????????10 1.6.1 时序网络????????????????????????????????????????????????????????????????????10 1.6.2 网络上的动力学过程?????????????????????????????????????????????????????11 1.6.3 自适应网络?????????????????????????????????????????????????????????????????11 1.6.4 高阶网络????????????????????????????????????????????????????????????????????12 1.7 本章小结?????????????????????????????????????????????????????????????????????????????12 思考题???????????????????????????????????????????????????????????????????????????????????????12 参考文献????????????????????????????????????????????????????????????????????????????????????12 第2 章图论 ????????????????????????????????????????????????????????????????????????????????????14 2.1 图的基本要素???????????????????????????????????????????????????????????????????????14 2.1.1 节点和边????????????????????????????????????????????????????????????????????14 2.1.2 度和度分布?????????????????????????????????????????????????????????????????15 2.2 图的表示?????????????????????????????????????????????????????????????????????????????16 2.2.1 邻接矩阵????????????????????????????????????????????????????????????????????16 2.2.2 邻接表???????????????????????????????????????????????????????????????????????17 2.2.3 关联矩阵表示法???????????????????????????????????????????????????????????17 2.2.4 边列表???????????????????????????????????????????????????????????????????????17 2.3 图的类型?????????????????????????????????????????????????????????????????????????????18 2.4 图的连通性??????????????????????????????????????????????????????????????????????????19 2.5 特殊图????????????????????????????????????????????????????????????????????????????????21 2.5.1 完全图???????????????????????????????????????????????????????????????????????21 2.5.2 平面图???????????????????????????????????????????????????????????????????????22 2.5.3 二分图???????????????????????????????????????????????????????????????????????22 2.5.4 树?????????????????????????????????????????????????????????????????????????????23 2.5.5 桥?????????????????????????????????????????????????????????????????????????????23 2.5.6 特殊子图????????????????????????????????????????????????????????????????????23 2.6 图的应用分析???????????????????????????????????????????????????????????????????????25 2.6.1 图/树的遍历?????????????????????????????????????????????????????????????????25 2.6.2 最短路径算法??????????????????????????????????????????????????????????????26 2.6.3 最小生成树?????????????????????????????????????????????????????????????????28 2.6.4 网络流算法?????????????????????????????????????????????????????????????????28 2.7 本章小结?????????????????????????????????????????????????????????????????????????????31 思考题???????????????????????????????????????????????????????????????????????????????????????31 参考文献????????????????????????????????????????????????????????????????????????????????????31 第3 章网络模型 ??????????????????????????????????????????????????????????????????????????????33 3.1 规则网络与随机网络??????????????????????????????????????????????????????????????33 3.1.1 规则网络????????????????????????????????????????????????????????????????????33 3.1.2 随机网络????????????????????????????????????????????????????????????????????33 3.1.3 对比分析????????????????????????????????????????????????????????????????????34 3.2 小世界网络??????????????????????????????????????????????????????????????????????????35 3.2.1 小世界网络?????????????????????????????????????????????????????????????????35 3.2.2 应用分析????????????????????????????????????????????????????????????????????35 3.3 无标度网络??????????????????????????????????????????????????????????????????????????36 3.3.1 无标度网络?????????????????????????????????????????????????????????????????36 3.3.2 应用分析????????????????????????????????????????????????????????????????????36 3.4 本章小结?????????????????????????????????????????????????????????????????????????????39 思考题???????????????????????????????????????????????????????????????????????????????????????39 参考文献????????????????????????????????????????????????????????????????????????????????????39 第4 章网络度分布及其度量 ???????????????????????????????????????????????????????????????41 4.1 节点度????????????????????????????????????????????????????????????????????????????????41 4.1.1 度与平均度?????????????????????????????????????????????????????????????????41 4.1.2 出度与入度?????????????????????????????????????????????????????????????????41 4.2 度分布????????????????????????????????????????????????????????????????????????????????42 4.2.1 度分布的概念??????????????????????????????????????????????????????????????42 4.2.2 钟形曲线到长尾分布?????????????????????????????????????????????????????43 4.2.3 幂律分布????????????????????????????????????????????????????????????????????44 4.3 度相关性及其度量?????????????????????????????????????????????????????????????????46 4.3.1 高阶度分布的引入????????????????????????????????????????????????????????46 4.3.2 联合概率分布??????????????????????????????????????????????????????????????47 4.3.3 条件概率和余平均度?????????????????????????????????????????????????????48 4.3.4 同配系数????????????????????????????????????????????????????????????????????49 4.4 应用分析?????????????????????????????????????????????????????????????????????????????50 4.4.1 蛋白组演化网络???????????????????????????????????????????????????????????50 4.4.2 预测流感病毒发生????????????????????????????????????????????????????????50 4.4.3 区域创新系统??????????????????????????????????????????????????????????????50 4.5 本章小结?????????????????????????????????????????????????????????????????????????????51 思考题???????????????????????????????????????????????????????????????????????????????????????51 参考文献????????????????????????????????????????????????????????????????????????????????????51 第5 章网络相似性度量 ?????????????????????????????????????????????????????????????????????53 5.1 图相似简介??????????????????????????????????????????????????????????????????????????53 5.2 结构相似性??????????????????????????????????????????????????????????????????????????54 5.3 图同构与图相似????????????????????????????????????????????????????????????????????55 5.3.1 图同构???????????????????????????????????????????????????????????????????????55 5.3.2 图编辑距离?????????????????????????????????????????????????????????????????56 5.3.3 不同类型的图同构????????????????????????????????????????????????????????57 5.4 相似性度量指标????????????????????????????????????????????????????????????????????58 5.4.1 基于路径的度量方法?????????????????????????????????????????????????????59 5.4.2 基于树的度量方法????????????????????????????????????????????????????????61 5.4.3 图编辑距离度量方法?????????????????????????????????????????????????????64 5.5 应用分析?????????????????????????????????????????????????????????????????????????????65 5.5.1 图嵌入模型?????????????????????????????????????????????????????????????????65 5.5.2 图匹配网络?????????????????????????????????????????????????????????????????66 5.5.3 实验分析????????????????????????????????????????????????????????????????????67 5.6 本章小结?????????????????????????????????????????????????????????????????????????????69 思考题???????????????????????????????????????????????????????????????????????????????????????69 参考文献????????????????????????????????????????????????????????????????????????????????????70 第6 章网络科学中的特征计算 ????????????????????????????????????????????????????????????72 6.1 图的距离?????????????????????????????????????????????????????????????????????????????72 6.2 平均距离?????????????????????????????????????????????????????????????????????????????73 6.3 集聚系数?????????????????????????????????????????????????????????????????????????????74 6.4 圈系数????????????????????????????????????????????????????????????????????????????????77 6.5 无标度随机图的集聚系数????????????????????????????????????????????????????????79 6.6 应用分析?????????????????????????????????????????????????????????????????????????????80 6.7 本章小结?????????????????????????????????????????????????????????????????????????????82 思考题???????????????????????????????????????????????????????????????????????????????????????82 参考文献????????????????????????????????????????????????????????????????????????????????????82 第7 章网络谱度量分析 ?????????????????????????????????????????????????????????????????????84 7.1 网络特征值??????????????????????????????????????????????????????????????????????????84 7.2 谱半径????????????????????????????????????????????????????????????????????????????????85 7.3 特征谱及其在网络科学中的应用???????????????????????????????????????????????87 7.4 网络谱密度分析????????????????????????????????????????????????????????????????????88 7.5 随机图的谱??????????????????????????????????????????????????????????????????????????93 7.6 本章小结?????????????????????????????????????????????????????????????????????????????93 思考题???????????????????????????????????????????????????????????????????????????????????????93 参考文献????????????????????????????????????????????????????????????????????????????????????94 第8 章网络熵 ?????????????????????????????????????????????????????????????????????????????????95 8.1 网络熵????????????????????????????????????????????????????????????????????????????????95 8.1.1 熵在网络模型中的表示??????????????????????????????????????????????????95 8.1.2 网络结构熵?????????????????????????????????????????????????????????????????96 8.2 基于度的熵??????????????????????????????????????????????????????????????????????????97 8.3 基于距离的熵???????????????????????????????????????????????????????????????????????98 8.4 基于特征向量及特征值的熵?????????????????????????????????????????????????????98 8.5 基于图论的网络熵分析???????????????????????????????????????????????????????????99 8.5.1 引言??????????????????????????????????????????????????????????????????????????99 8.5.2 局部连通性??????????????????????????????????????????????????????????????? 100 8.5.3 全局中心性??????????????????????????????????????????????????????????????? 100 8.6 基于子图的熵????????????????????????????????????????????????????????????????????? 102 8.6.1 密集子图和稠密子图??????????????????????????????????????????????????? 103 8.6.2 频繁子图?????????????????????????????????????????????????????????????????? 104 8.6.3 连通子图?????????????????????????????????????????????????????????????????? 104 8.7 基于随机图的熵?????????????????????????????????????????????????????????????????? 106 8.7.1 随机网络?????????????????????????????????????????????????????????????????? 106 8.8 应用分析??????????????????????????????????????????????????????????????????????????? 107 8.8.1 基于网络熵的重要节点发现?????????????????????????????????????????? 107 8.8.2 EnD 节点重要性排序算法????????????????????????????????????????????? 108 8.9 本章小结??????????????????????????????????????????????????????????????????????????? 109 思考题????????????????????????????????????????????????????????????????????????????????????? 110 参考文献?????????????????????????????????????????????????????????????????????????????????? 110 第9 章图计算重要算法 ??????????????????????????????????????????????????????????????????? 111 9.1 社区发现??????????????????????????????????????????????????????????????????????????? 111 9.1.1 相关模型?????????????????????????????????????????????????????????????????? 112 9.1.2 提出的社区发现方法??????????????????????????????????????????????????? 114 9.1.3 时间复杂度和实验结果分析?????????????????????????????????????????? 118 9.1.4 应用分析?????????????????????????????????????????????????????????????????? 122 9.2 链路预测??????????????????????????????????????????????????????????????????????????? 124 9.2.1 模型框架?????????????????????????????????????????????????????????????????? 124 9.2.2 算法描述?????????????????????????????????????????????????????????????????? 126 9.2.3 实验设置?????????????????????????????????????????????????????????????????? 128 9.2.4 实验结果与分析????????????????????????????????????????????????????????? 129 9.3 网络影响力扩散算法???????????????????????????????????????????????????????????? 138 9.3.1 引言???????????????????????????????????????????????????????????????????????? 138 9.3.2 问题描述与分析????????????????????????????????????????????????????????? 138 9.3.3 基于目标感知的分配激励模型??????????????????????????????????????? 143 9.3.4 实验结果与分析????????????????????????????????????????????????????????? 148 9.4 本章小结??????????????????????????????????????????????????????????????????????????? 155 思考题????????????????????????????????????????????????????????????????????????????????????? 155 参考文献?????????????????????????????????????????????????????????????????????????????????? 155 第10 章网络科学应用????????????????????????????????????????????????????????????????????? 157 10.1 网络信息级联预测?????????????????????????????????????????????????????????????? 157 10.1.1 引言??????????????????????????????????????????????????????????????????????? 157 10.1.2 自激励点过程??????????????????????????????????????????????????????????? 157 10.1.3 数据预处理?????????????????????????????????????????????????????????????? 158 10.1.4 自激励点过程的图卷积级联预测??????????????????????????????????? 160 10.1.5 实验结果与分析???????????????????????????????????????????????????????? 163 10.1.6 模型收敛性?????????????????????????????????????????????????????????????? 169 10.2 推荐系统?????????????????????????????????????????????????????????????????????????? 170 10.2.1 引言??????????????????????????????????????????????????????????????????????? 170 10.2.2 相关工作????????????????????????????????????????????????????????????????? 171 10.2.3 问题定义????????????????????????????????????????????????????????????????? 175 10.3 情感分析?????????????????????????????????????????????????????????????????????????? 177 10.3.1 引言??????????????????????????????????????????????????????????????????????? 177 10.3.2 相关工作????????????????????????????????????????????????????????????????? 178 10.3.3 基于多模态的舆情情感分类????????????????????????????????????????? 180 10.3.4 实验结果与分析???????????????????????????????????????????????????????? 185 10.4 复杂网络分层抽样?????????????????????????????????????????????????????????????? 190 10.4.1 引言??????????????????????????????????????????????????????????????????????? 190 10.4.2 相关工作????????????????????????????????????????????????????????????????? 191 10.5 网络关键节点识别?????????????????????????????????????????????????????????????? 194 10.5.1 引言??????????????????????????????????????????????????????????????????????? 194 10.5.2 相关工作????????????????????????????????????????????????????????????????? 196 10.5.3 准备工作????????????????????????????????????????????????????????????????? 198 10.6 本章小结?????????????????????????????????????????????????????????????????????????? 201 思考题????????????????????????????????????????????????????????????????????????????????????? 202 参考文献?????????????????????????????????????????????????????????????????????????????????? 202 第11 章网络科学计算分析??????????????????????????????????????????????????????????????? 204 11.1 引言???????????????????????????????????????????????????????????????????????????????? 204 11.2 相关工作?????????????????????????????????????????????????????????????????????????? 205 11.3 分析方法?????????????????????????????????????????????????????????????????????????? 205 11.3.1 共词分析????????????????????????????????????????????????????????????????? 205 11.3.2 节点中心性算法???????????????????????????????????????????????????????? 206 11.3.3 特征向量中心性???????????????????????????????????????????????????????? 210 11.4 实验数据分析???????????????????????????????????????????????????????????????????? 212 11.4.1 人物共词分析??????????????????????????????????????????????????????????? 212 11.4.2 小世界性分析??????????????????????????????????????????????????????????? 215 11.5 实验和结果??????????????????????????????????????????????????????????????????????? 216 11.5.1 关键人物重要性分析?????????????????????????????????????????????????? 216 11.5.2 SIR 模型评估中心性??????????????????????????????????????????????????? 220 11.5.3 人物相关性分析???????????????????????????????????????????????????????? 223 11.5.4 人物聚类分析??????????????????????????????????????????????????????????? 224 11.5.5 小说人物关系图谱????????????????????????????????????????????????????? 226 11.5.6 舆情分析????????????????????????????????????????????????????????????????? 227 11.6 本章小结?????????????????????????????????????????????????????????????????????????? 228 思考题????????????????????????????????????????????????????????????????????????????????????? 228 参考文献?????????????????????????????????????????????????????????????????????????????????? 229