图谱理论与复杂网络相关算法

作者简介

《图谱理论与复杂网络相关算法》通过对图的邻接矩阵、Laplacian矩阵、signless Laplacian矩阵及关联矩阵性质的研究，证明了一些图类的谱确定性，发现并证明了几类不能由谱确定的同谱图类，拓宽了谱确定图类的范围；对复杂网络的社团结构提取算法进行了研究。全书共分6章，第1章给出了相关概念及符号表示，列举了已有的谱确定图类及图谱理论在计算机科学中的应用；第2章归类了图的谱性质，给出了后面证明中要用到的基本引理；第3章证明了似双星树的谱确定性；第4章证明了几类单圈图的谱确定性；第5章证明了几类双圈图的谱确定性；第6章研究了复杂网络社团发现算法。

书籍目录

第1章 绪论 1.1 图谱问题的研究背景及应用 1.2 基本概念与记号 1.3 谱确定问题的研究现状 1.3.1 邻接谱确定的图形 1.3.2 Laplacian谱确定的图形 1.3.3 signless Laplacian谱确定的图形 1.4 图谱理论在计算机科学方面的若干应用 第2章 基本概念与引理 2.1 基本概念 2.2 基本引理 2.3 本章小结 第3章 树图的谱刻画 3.1 一类邻接同谱双星树 3.2 所有似双星树由Laplacian谱刻画 3.2.1 似双星树的谱特征 3.2.2 似双星树H（p，n，q）由Laplacian谱确定 3.3 本章小结 第4章 几类单圈图的谱刻画 4.1 一类偶圈图由Laplacian谱刻画 4.1.1 一类偶圈图的谱特征 4.1.2 偶圈图H（n；q，n1，n2，n3）由Laplacian谱确定 4.2 单圈图H（n；q；n1；n2；n3）由Laplacian谱刻画 4.3 章鱼图由Laplacian谱刻画 4.3.1 章鱼图的谱特征 4.3.2 图H（Cn，q）由Laplacian谱确定 4.4 长须章鱼图由Laplacian谱刻画 4.4.1 长须章鱼图的谱特征 4.4.2 图Hn（Cp，s，q）由Laplacian谱确定 4.5 一类Laplacian同谱单圈图 4.6 一类邻接同谱单圈图 4.7 本章小结 第5章 双圈图的谱刻画 5.1 沙漏图 5.1.1 沙漏图的谱特征 5.1.2 沙漏图由邻接谱确定 5.1.3 沙漏图由Laplacian谱确定 5.2 几类同谱的双圈图 5.3 一类奇双圈图由邻接谱刻画 5.3.1 图H（Cp，Cp，r）的谱特征 5.3.2 图H（Cp，Cp，r）由邻接谱确定 5.4 同Laplacian谱的哑铃图必同构 5.4.1 哑铃图 5.4.2 没有两个不同构的哑铃图同Laplacian谱 5.5 本章小结 第6章 图谱在复杂网络中的应用 6.1 复杂网络基本概念 6.2 常见社团划分算法 6.3 局部社团发现算法 6.3.1 一种局部社团发现算法 6.3.2 局部社团发现算法实验及分析 6.4 一种改进的CPM社团发现算法 6.4.1 结合CPM的中心度发现社团算法 6.4.2 改进的CPM社团发现算法实验及分析 6.5 本章小结 参考文献

编辑推荐

《图谱理论与复杂网络相关算法》系统全面介绍了图谱理论与复杂网络相关算法，《图谱理论与复杂网络相关算法》是一本专著，也可以作为高等学校计算机、数学及其他相关专业研究生和本科高年级图论及相关算法的教材，还可以供从事图谱理论方面的科技工作者参考。

章节摘录

版权页：   插图：    该方法的缺点在于它每次只能将网络节点平分，如果当网络的社团结构大于两个时，就必须要多次重复该算法，而且第一次社团结构划分的正确性直接影响到最终的结果。另外，当网络的社团结构不明显时，即网络的Laplacian矩阵的第二小特征值λ2不能很快从其它特征值中分离出来时，算法的速度就可能在一定程度上变慢。换句话说，如果网络的社团结构非常明显，那么该算法的速度和效果会非常理想；否则该算法就未必有效。 3.分裂方法 划分网络社团结构的一种简单的方法是将连通社团之间的边移除，这就是分裂方法的基本思想。而这个方法的主要难点就在于如何正确地找到社团之间的边。在分裂方法中，从整个网络出发，试图找到已连接的相似性最低的节点对，然后移除它们之间的边，在某些极端情况下也有可能将节点也移除（由于连接该点的边都被移除）。分裂方法利用树状图来表示其分裂的流程，可以更好地描述整个网络逐步分裂成若干个越来越小的社团的过程。底部的各个圆代表了网络中的各个节点，当水平虚线从顶部逐步向底部移动时，即表示整个网络逐渐分成若干个社团结构，在虚线移动到底部时，整个网络的节点就退化成独立的社团。在分裂方法中GN算法和快速分裂算法是比较有代表性的。 1）GN算法 由Girvan和Newman提出的GN算法在近几年已成为社团结构分析的一种标准算法，它的基本思想是从网络的整体出发，不断地从网络中移除介数最大的边，从而获得最佳的社团结构。边介数定义为网络中经过每条边的最短路径的数目（139）。

---

 图谱理论与复杂网络相关算法下载

---