向心路径结点定义的子图划分与聚类子图边交叉数计算

发布时间：2017-05-27 15:12

  本文关键词：向心路径结点定义的子图划分与聚类子图边交叉数计算，由笔耕文化传播整理发布。

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

• 摘要3-4
• ABSTRACT4-7
• 1. 引言7-11
• 1.1. 研究背景7-8
• 1.2. 网络分析8
• 1.3. 图结构分析8-9
• 1.4. 本文研究方向9-10
• 1.5. 本文结构安排10-11
• 2. 相关理论与方法11-24
• 2.1. 图论相关知识11-12
• 2.2. 复杂网络特性12
• 2.3. 复杂网络中心性12-14
• 2.4. 图划分算法14-17
• 2.5. 边交叉数计算17-19
• 2.6. 图布局算法19-24
• 2.6.1. 力导引布局算法20-22
• 2.6.2. 圆形布局算法22-24
• 3. 基于图论的图划分算法24-35
• 3.1. 子类中心节点计算24-28
• 3.2. 非中心节点子类划分28-30
• 3.3. 图划分算法实验30-33
• 3.3.1. 海豚网络社区划分30-31
• 3.3.2. 美国西部电力网络社区划分31-32
• 3.3.3. 算法比较32-33
• 3.4. 小结33-35
• 4. 聚类图的交叉数计算35-45
• 4.1. 人工分类图构造算法35-39
• 4.1.1. 分类子图生成算法36-37
• 4.1.2. 子图连接算法37-38
• 4.1.3. 算法归纳与实验38-39
• 4.2. 聚类图边交叉计算算法39-41
• 4.3. 实验41-44
• 4.3.1. 人工图边交叉数计算实验41-42
• 4.3.2. 真实网络聚类图边交叉数计算实验42-44
• 4.4. 小结44-45
• 5. 总结与展望45-46
• 5.1. 总结45
• 5.2. 展望45-46
• 参考文献46-50
• 个人简介50-51
• 导师简介51-52
• 获得成果目录52-53
• 致谢53

【相似文献】

中国期刊全文数据库 前10条

1 孙亮;叶淼林;;图的子图匹配数与图的标准化拉普拉斯谱[J];安庆师范学院学报(自然科学版);2011年04期

2 陈赐平;;带亏数的[1,n]-子图[J];北京农业工程大学学报;1987年03期

3 李学良;;有向1-因子图[J];新疆大学学报(自然科学版);1988年02期

4 李传湘;层次结构中封闭子图的映射[J];数学物理学报;1990年04期

5 郭思平;;立方图中一类具有极大边数子图的性质[J];云南师范大学学报(自然科学版);1991年04期

6 谢力同,范红兵;关于局部子图可重构性的一个新结果(英文)[J];数学进展;1997年05期

7 龙和平,谢力同,颜谨,刘桂真;边型带权核子图的边可重构性[J];山东大学学报(理学版);2002年02期

8 李慰萱;;图的结构多项式与子图恒等式[J];长沙铁道学院学报;1979年03期

9 郭知熠;关于完全k-边可染子图[J];华中工学院学报;1985年06期

10 辛林，，徐恭勤;子图个数的计算问题[J];教学与教材研究;1994年03期

中国重要会议论文全文数据库 前4条

1 徐以凡;;层分解和子图识别问题[A];2001年全国数学规划及运筹研讨会论文集[C];2001年

2 陶剑文;丁佩芬;赵杰煜;;csgIndex:一种可扩展的对比子图索引模型[A];第二十七届中国控制会议论文集[C];2008年

3 吴卫江;李国和;;Apriori算法思想在频繁子图挖掘中应用的研究[A];第六届全国信息获取与处理学术会议论文集（2）[C];2008年

4 吴颖华;周皓峰;袁晴晴;洪铭胜;汪卫;施伯乐;;Topology:一个快速的频繁连通子图的挖掘算法[A];第二十届全国数据库学术会议论文集（技术报告篇）[C];2003年

中国博士学位论文全文数据库 前4条

1 蔺厚元;禁用子图与图的哈密尔顿性[D];华中师范大学;2012年

2 毛玲;基于层次因子图的心电图自动诊断方法研究[D];国防科学技术大学;2009年

3 崔庆;Tutte子图方法及其应用[D];南开大学;2009年

4 吴云建;一致星因子图与笼的连通性[D];南开大学;2009年

中国硕士学位论文全文数据库 前10条

1 范淦;高效的庞大图的频繁子图挖掘方法研究[D];辽宁大学;2015年

2 魏真真;大规模不确定图紧密子图挖掘算法研究[D];燕山大学;2015年

3 齐宝雷;面向不确定图数据的子图模式挖掘算法的研究与实现[D];东北大学;2013年

4 王会会;精确子图数据库查询技术研究[D];哈尔滨工业大学;2014年

5 白杨;复杂网络图中高密度子图检测方法与实现[D];西安电子科技大学;2014年

6 王鹏;基于局部邻域的最大密度子图检测方法研究与实现[D];西安电子科技大学;2014年

7 赵路;图的Q-特征值与图结构[D];青海师范大学;2015年

8 王璐璐;不确定图上Top-k子图相似性查询技术研究[D];东北大学;2014年

9 张天明;大图上频繁子图挖掘算法的研究[D];东北大学;2014年

10 王峰;基于众核平台子图匹配算法研究[D];北京理工大学;2016年

  本文关键词：向心路径结点定义的子图划分与聚类子图边交叉数计算，由笔耕文化传播整理发布。

本文编号：400364