论文部分内容阅读
在数据时代,伴随着信息量的骤增,图作为重要的信息载体,日益受到研究者的重视。如何更好地呈现与分析图数据业已成为研究的热点。为了更好地理解图的结构和衡量图布局的优劣,本文采用图论中的路径分析、计算几何中的线段求交和计算机仿真等方法,主要研究子图划分和图的边交叉数计算问题。其中,子图划分为边的交叉数计算提供了基础。主要结论和创新点体现在下面三个方面：(1)子图划分研究。依据子类中心节点对于同一个类别中其它节点具有更强的控制力的思想,提出了子类中心点的概念及其确定方法,进一步给出上通路和向心路径的定义。在子类中心节点基础上通过计算向心路径数量,实现网络节点的快速聚类算法,即向心路径节点聚类算法(Toward to Subheart Roads Defining NetworkClustering Algorithm)。相比于传统算法,TSRDNCA算法具有较高的网络社区判断的准确性。(2)分类图的边交叉数计算研究。充分利用分类(子)图自身已有的节点分类信息,将分类图中的边划分为两类分别进行交叉数计算,即类内边交叉数计算与类间边交叉数计算,在类间边数较少的情况下,提高了计算时间效率。(3)人工图的生成研究。依据节点的无尺度特性与图结构分析理论,将人工图的生成过程分为子图构建与子图联接两部分。在子图构建阶段,主要研究边的构建思路,即节点倾向于与高节点度相连。在子图联接阶段,我们采用两个概率优先原则：连接两个子图的顶点有较大概率选择在边缘处的点；在后续增加子图之间的边时,有较大概率选择已经处于连接子图关系的顶点。我们的人工图生成算法可依据用户需求生成相应规格的分类图,构造的图具有较好的仿真效果。此外,生成的人工图为边交叉数计算提供了各种例子。