《复杂网络图的可视化技术研究毕业设计.doc》由会员分享，可在线阅读，更多相关《复杂网络图的可视化技术研究毕业设计.doc（70页珍藏版）》请在三一办公上搜索。
1、毕业设计论文复杂网络图的可视化技术研究Research On Visualization Technique For Complex Networks Graph摘 要可视化技术已经成为计算机应用科学的一个重要研究领域，通过对图进行可视化的展示，人们不仅能够对图的整体结构以及各节点之间的联系获得直观清晰的认识，并且通过可视化展示效果的处理以及用户的交互，能够对用户所关心的图的某一个部分进行有针对性的观察和分析，从而使用户能够获取更多有价值的信息，对用户的工作产生有意义的指导作用。但是随着需要被处理的网络图的规模的不断扩大，其内部的联系日益复杂，如何对复杂的网络图进行快速并且清晰有效的展示成为图
2、的可视化技术的研究的重点内容。本文从复杂网络图的可视化布局的流程出发，阐述了课题研究所涉及到的相关基础知识。论文针对课题所研究的对象和相关常用的概念的符号约定进行了说明；对FDA、FR两种图布局算法的理论依据和实现过程进行了描述，分析了各自的优势和不足之处；介绍了GN、NF两种网络图的社区结构发现算法，描述了算法的设计思路和实现流程，并指出了其各自的特点和缺陷。为了能够规避基于模块度最优的社区发现算法出现的的分辨率限制问题，论文引入了边密度的概念。基于GN算法的边分裂思路和NF算法的节点凝聚思路，论文提出了一个基于边密度的社区结构发现算法ECAA（EdgeDensity CastEdge Al
3、l Algorithm），对复杂网络图先依据边密度先进行边的分裂，然后再进行节点的凝聚，未利用模块度最优从而避免了分辨率限制的问题，算法的时间复杂度是（其中为网络中的边数，为网络中节点的最大节点度），小于GN和NF算法，从而提高了算法的执行效率。基于FR算法的思路，论文引入了改进的FR算法NWFR（Node Weighted FR），通过调整初始化布局以加快算法的收敛速度；重新定义受力模型以适应带权节点网络图的处理；修改节点越界的处理方式，使布局结果更加美观。利用上述理论的研究成果，论文设计并实现了一个复杂网络图可视化系统。系统定义了通用的操作接口和统一的内部数据格式；在展示交互模块采用WPF
4、技术MVVM架构，实现了展示界面和业务逻辑的分离，提高了程序的复用性并提供了丰富的辅助操作以获得更好的用户体验。将层次化网络图算法和图布局算法封装在两个模块中，在每个模块中利用工厂模式以提供统一的调用接口，并且每个模块可以集成多个算法，提高了系统的可扩展性和可维护性。关键词：复杂网络，社区结构，分辨率限制，边密度，自动探测，力导引，数据可视化ABSTRACTVisualization technology has become an important research field of the computational applied science. Through the visual
5、 display of the graph, People can not only obtain a visualized and clear understanding about the whole structure and the relationship between each node, but also get targeted observation and analysis about the part of the graph that users care about by processing the effect of the visual display and
6、 users interaction which enables users to get more valuable information and significant guidance. But with the rapid development of information technology, the scale of the graph which needs to be processing is unceasingly expanding, while the internal relation becoming increasingly complex. How to
7、make a clear and effective display of a complicated network diagram has become the key content of the research of the graphs visualization technology.Starting from the process of the visual layout of complex network diagram，the paper gives a presentation of the relevant basic knowledge of the projec
8、t research. It gives an illustration of the object and the agreed symbols; gives an introduction of the theoretical basis and implementation process of two map layout algorithms FDA, FR, analyzing their advantages and disadvantages respectively; gives an introduction of two community structure disco
9、very s GN, NF, describes the design ideas and implementation process of algorithms, and points out their characteristics and defects respectively.To avoid the problem of resolution limit of the community discovery algorithm based on the maximization of the value of Q, the paper introduces the concep
10、t of the density of edges. Based on the thought of edge splitting of GN and the thought of node aggregating of NF ,a community structure discovery algorithm - ECAA（Edge Density Cast Edge All Algorithm）based on the density of edges has been put forwarded. To complex network diagrams, the algorithm fi
11、rst splits the edges according to the density of edge, and then aggregates the nodes, not using the maximization of the value of Q so as to avoid the problem of resolution limit. The time complexity of the algorithm is O (k.m) (m is the number of edge in the network, k is the largest degree of node
12、in the network) which is less than that of GN and NF , so as to improve the efficiency of the algorithm.Based on the thought of FR algorithm, the improved FR algorithm-NWFR （Node Weighted FR）has been introduced. It accelerates the speed of convergence of the algorithm by adjusting the initial layout
13、; redefines the force model so as to adjust the process of weighted node network graph; modifies the treatment of transgression at the same time to make layout more artistic.Making use of the research results of the theories above, a visualization system of a complicated network graph has been desig
14、ned and implemented. The system defines the general operational interface and unified format of internal data. Technology of WPF and structure of MVVM are used in the display of interactive module, which realizes the separation of the display interface and business logic, improving the reusability o
15、f the program and providing a variety of auxiliary operation to get a better user experience. To package the hierarchical network diagram and the visualization graph algorithms in two modules, and to use factory model in each module to provide unified call interface. Each module can integrate severa
16、l algorithms. All of them improve the scalability and maintainability of the system.Keywords: Complex networks, Community structure, Resolution limit, Edge density, Automatic detect, Force-Directed, Data visualization目 录摘 要IABSTRACTIII目 录V第一章 绪论11.1 课题研究背景及意义11.2 课题研究现状21.2.1 网络图的布局算法21.2.2 社区结构发现算法
17、31.3 论文研究内容41.4 论文组织结构4第二章 复杂网络图可视化技术基础62.1 概述62.2 研究对象和相关符号约定62.3 网络图的布局算法72.3.1 FDA算法72.3.2 FR算法92.4 复杂网络图的化简112.4.1 网络图的层次化模型112.4.2 网络图的社区结构发现算法112.5 本章小结15第三章 基于边密度的复杂网络社区结构发现算法163.1 概述163.2 社区结构的基本概念163.3 模块度的基本概念173.4 社区结构发现算法ECAA193.4.1 边密度计算193.4.2 去边策略213.4.3 模块合并233.4.4 中间点处理253.4.5 算法描述2
18、63.5 案例应用263.5.1 Zachary空手道俱乐部263.5.2 橄榄球队网络273.5.3 分辨率限制反例273.5.4 总结293.6 本章小结29第四章 复杂网络图的布局算法304.1 概述304.2 复杂网络图可视化的难点304.3 布点算法NWFR324.3.1 限定布局范围324.3.2 初始化布局节点354.3.3 受力模型定义374.3.4 节点越界处理394.3.5 终止条件394.3.6 算法描述404.4 本章小结41第五章 复杂网络图可视化系统的设计与实现425.1 概述425.2 系统功能目标425.3 系统总体设计425.4 开发平台及工具435.5 系统
19、模块设计与实现445.5.1 系统数据处理模块445.5.2 网络分层模块465.5.3 可视化布点模块465.5.4 展示交互模块475.6 系统展示495.6.1 分层功能505.6.2 按层次展示功能505.6.3 逐级勘探功能505.6.4 辅助功能515.7 本章小结53第六章 总结与展望556.1 工作总结556.2 研究展望56参考文献58致谢62攻读硕士学位期间发表的论文63第一章 绪论1.1 课题研究背景及意义随着信息技术的飞速发展，数据的可视化技术已经成为计算机应用科学的一个重要研究领域，它被广泛应用于生物学1，信息科学1,2，社会学2等领域。大脑内70%的接受器和超过40
20、%的皮质都是为视觉服务的，人们应该充分地利用大脑的这项功能3。相反，如果试图使用文字或者表格的方式来发现数据之间的内在联系，则需要研究人员进行大量的记忆和推理。当成功地对数据进行可视化的处理并呈现以后，人们可以很直观地从处理结果中就获取数据之间的有效信息和一些隐晦的内在联系，从而可以从繁重的分析任务中解放出来，进而从事更高层次的认知活动。因此，数据的可视化技术的研究是非常有必要的。在数据的可视化技术中一般使用图结构来存储数据。从网络的角度可以刻画许多实际系统,例如：万维网4,5、食物链6、人际交往关系7,8等等。在使用网络来对实际系统进行抽象时，往往将系统中的个体对应至网络中的顶点 ，个体间的
21、相互联系对应成网络中的边 ,从而可以将这些系统看成由节点和节点之间的连接边构成的图。在规模较小的网络图的可视化布局的问题上，已经取的了较为令人满意的效果。1984年，P.Eades首先提出了力导引（Force-Directed）算法，该算法对于不同的图有不同的收敛速度。为此，Kamada和Kawai在1989年基于力导引算法进行了改进，尽管KK算法使力导引算法的收敛速度有了明显的增加，但是仍然有提高的余地。1991年，T.M.J.Fruchterman和E.M.ReingoId在前人工作的基础上，将网络图的布局总结出两条布局准则，并提出了FR算法，FR算法能够布局出优美的图形，但是其时间复杂度
22、仍然比较高，达到了，在进行规模较大的网络图进行布局的时候非常耗时。随着处理的网络图的规模的不断增大，直接使用布局算法进行布局，一方面导致处理时间大大超过用户的忍耐甚至造成内存溢出，另一方面造成节点大量堆积在画布上以至于用户无法从中获取有用的信息，失去了可视化的原有意义。因此，面对网络图规模过大的困境，要想快速地为用户呈现出他需要的美观的图形，就要采取一定的处理方式，包括改进原有的布局算法，将原网络图进行层次化的分割，并在此基础上进行分层展示。能够快速并可靠地降低复杂网络的规模、高效且美观地可视化呈现网络图、有良好设计的可视化系统是复杂网络图可视化技术研究的三个相互依赖的重要环节。本课题根据这三
23、个环节对复杂网络图的可视化技术进行了研究。提出了具有更高性能的社区结构发现算法并改进了FR算法，基于WPF技术MVVM架构设计并实现了一个复杂网络图可视化系统，对实际开发有一定的指导作用。1.2 课题研究现状1.2.1 网络图的布局算法1984年，P.Eades发表了A heuristics for graph drawing9一文，Eades开创性地将图形模拟成为一个物理系统，把节点比作钢环，把边比作弹簧。在初始化的时候，钢环会随机地被放置在待显示的区域上，然后让钢环在弹簧弹力的作用下进行移动，不断减少系统的能量，直到系统的总能量达到最小值时，钢环停止移动，此时会得到一个布局结构，从而完成图
24、形的布局过程。该算法称为 Force-Directed算法(FDA)。FDA算法对于不同的图，有不同的收敛速度。为此，基于FDA算法通过模拟弹簧系统的自适应来降低系统的能量，Kamada和Kawai在1989年对网络图中的任意两个节点定义了一个理想距离，并给出了系统的能量函数，运用微积分的知识计算能量函数的极小值来获取网络图中节点的最佳布局坐标，尽管KK算法使FDA算法的收敛速度有了明显的增加，但是仍然有提高的余地。1991年，T.M.J.Fruchterman和E.M.ReingoId提出了FR 算法10。FR算法将图的布局抽象出两个基本的原则：1.通过边相连的节点应该彼此靠近；2.节点之间
25、不能靠的太近。算法将图中的节点看成成原子，并假定原子间存在两种力：通过边连接的节点之间存在的吸引力和所有节点相互之间存在的排斥力。通过吸引力和排斥力的合力来计算节点的理想坐标。在理想状态下，每个节点最后所受的吸引力和排斥力会相等，算法停止。为了进一步提高力导引算法的效率11，各国学者又提出了高维嵌入（Hight-Dimensional Embedding）算法12、GEM（Graph Embedder）算法13以及多尺度（Multi-Scale）算法14。所提出的这些算法力求降低算法执行的时间复杂度，却为此付出了代价，这些算法在图形的布局质量上很多都不能够满足需求，如高维嵌入算法对部分真实网络
26、节点存在交叠问题，多尺度算法存在网络直径退化问题，GEM算法的健壮性较差的问题。1.2.2 社区结构发现算法对复杂网络图进行社区结构的发现能够在明显降低图规模的基础上保留图的整体结构。使用聚类算法进行社区结构的发现的过程中，可以建立起层次化的树形结构图，方便复杂网络图的可视化展示。聚类方法一般通过凝聚过程和分裂过程来进行实现。GN算法15是凝聚算法的典型代表，由Girvan和Newman在2002提出。GN算法是一种基于模块度最优的算法。一般使用社区内部的节点之间的联系是否要比社区之间的联系要多得多这一原则来评价一个聚类结果的好坏。模块度可以从数学上衡量一个聚类好坏的程度。该方法计算合并两个节
27、点对总的模块度的贡献，每次选择贡献度最大的两个点进行合并，属于贪心算法的思想。该算法最终一般都能够得到非常优秀的聚类结构，但是算法的时间复杂度很高，不适合在大规模网络中使用。NF算法16是分裂算法的典型代表，由Newman在2004年提出。NF算法同样是一种基于模块度最优的算法。该方法计算每条边的边介数，每次选择边介数最小的边移除，直到所有的边都被移除，然后选择除边过程中使得模块度最优的一步形成的划分作为算法执行的结果。算法的执行效率比GN算法要高一个数量级，为。1.3 论文研究内容本课题针对复杂网络图的可视化技术进行了研究。在参考了国内外大量优秀的文献的基础上，吸收了前人的成果并分析了现有技
28、术在复杂网络图处理方面的不足，分别对复杂网络图社区结构的发现算法、图的布局算法和可视化系统的架构三个方面做出了研究。论文的具体工作可分为以下几个方面：（1） 给出了复杂网络可视化图布局中的常见定义以及本文中使用的相关符号；介绍了知名的网络图的布局算法和复杂网络图社区结构的发现算法，并对各算法的特点和不足进行了分析。（2） 通过引入边密度的概念，综合凝聚过程和分裂过程思想，提出了一种新的用于复杂网络图的社区结构的发现算法ECAA，通过实验对比，相对于GN和NF算法，提高了算法执行结果的准确性和运行效率。（3） 基于FR算法思路，通过改善初始化布局算法、重新定义节点的受力、改进节点的越界处理三个方
29、面，提出了一个能够进行带权节点的网络图布局的NWFR算法，提高了FR算法的适用范围和性能。（4） 设计并且实现了一个复杂网络图的可视化系统，系统采用WPF技术MVVM架构进行构建，集成了ECAA算法和NWFR算法，利用ECAA算法处理原始图形，生成层次化的简化图结构，在每一个层次的简化图上使用NWFR算法对简化图进行可视化的布局。1.4 论文组织结构本论文分六章阐述所做的工作，各部分组织如下：第一章：绪论。对课题的研究背景及意义进行了介绍，简单给出了研究所涉及领域的研究现状，并给出了本课题的主要研究内容以及论文的组织结构。第二章：复杂网络图的可视化技术基础。介绍了复杂网络图的规模化简算法和图的
30、布局算法，给出了复杂网络可视化图布局中的常见定义以及本文中使用的相关符号。第三章：基于边密度的复杂网络社团结构发现算法。针对现有基于模块度最优算法会产生分辨率限制问题和时间复杂度过高的问题，而引入边密度的概念，提出了一种新的用于复杂网络图的社区结构的发现算法ECAA，描述了算法的详细过程，并通过实验和其它聚类算法在性能方面进行了比较。第四章：复杂网络图的布局算法。针对在层次可视化的过程中会涉及到处理带权节点图，通过改进FR算法，提出了NWFR算法，并描述了算法的详细过程。第五章：复杂网络图的可视化系统的设计与实现。详细介绍了系统的总体设计思路，并逐个介绍了各个模块的实现细节和功能展示。第六章：
31、总结与展望。对课题研究和开发工作进行了系统地总结，并给出下一步需要研究的内容。第二章 复杂网络图可视化技术基础2.1 概述相对于使用表格或者文字来描述网络图，可视化技术通过将数据化的网络图通过图形的形式展示在界面上，能够更加形象、直观地显示各个元素之间的联系以及网络图的结构特征。复杂网络图规模的化简算法和其布局算法是复杂网络可视化技术研究的核心。本章作为整个课题研究的基础，给出了课题的研究对象和相关符号约定，介绍了常用的可视化布局算法和用于化简数据规模的社团结构发现算法。2.2 研究对象和相关符号约定本课题主要研究对象是复杂网络图。目的是要架构一个针对复杂网络图进行可视化布局的系统。对研究的图
32、应满足以下几点要求：1. 研究的图使用符号表示，其中表示所有节点的集合，表示所有边的集合；2. 研究的图中的节点和边都是非带权的；3. 研究的图属于连通图，非连通图可以使用多个连通图进行表示；4. 研究的图是无向图。本文接下来所讨论的图如非特殊指定，都是表示满足上述要求的图。针对图中的一些常用属性，使用下列符号约定： 对于节点在画布上的坐标使用表示，其中； 表示节点和节点之间的欧式距离； 节点和节点的单位向量使用表示，其中； 对于从节点到节点的最短路径使用表示； 表示图中所有节点的个数； 表示图中所有边的个数； 表示画布的长，表示画布的高。2.3 网络图的布局算法图的布局算法用来计算图中的节点
33、在画布中的位置坐标。从美学的角度来考虑，判断一个图的布局算法的质量的好坏使用以下几点要求：171. 能够反映出原图内在的对称性2. 避免边的交叉和弯曲3. 保持边长统一4. 节点分布均匀长期以来，各国学者已经给出了许多图的布局算法，文献18针对各种图的布局算法作了一个相当全面的描述。由 P. Eades 提出的力导引算法（FDA，Force-Directed Algorithm）9 在图的布局领域有开创性意义，随后发展出了很多基于力导引算法思想的改进算法。由于FDA算法的模型来自于日常生活，思路直观、形象且易于实现。另一方面，在使用的过程中，算法能够获得满足审美标准的图形布局，并能够充分展现出
34、图的整体结构及其自同构特征，使得FDA 被广泛采用并发展。本节接下来将介绍FDA、FR算法，其中FR算法都是基于FDA的改进算法。2.3.1 FDA算法Eades 将节点抽象成小球，边抽象成连接小球的弹簧，在随机的初始布局下，通过引力和斥力来使得小球进行运动，通过运动可以不断减少作用在每个节点上的力，使得系统达到一个稳定的状态。在给定的图中，斥力和引力定义如下： 斥力： (2.1) 引力： (2.2)公式（2.1）中，是常量，称为排斥常数；斥力存在于任何两个不相邻节点（无边连接）之间，用来控制不相邻的节点能够均匀的分散开来。公式（2.2）中，是常数，称为弹力常数；表示弹簧的自然长度；引力用来模
35、拟弹簧的作用力，即该力存在于所有有边相连的节点中，用来控制相邻的节点不至于离的太远。根据公式（2.1）和公式（2.2），对于，在时刻，节点受到的作用力可以表示为在图中所有和节点不相邻的节点上的斥力和在图中所有和节点有边连接的节点之间的引力，公式如下： （2.3）根据时刻作用在节点上的力可以来计算节点在下一个时刻在画布中所处的位置，公式如下： （2.4）这样，可以通过计算各个时刻图中所有节点受到的作用力来调整其在下一个时刻中在画布上所处的位置，如此循环反复，最终会不断降低作用在每个节点上的作用力，从而使图的布局达到一个稳定的状态。图 2.1 就是一个利用弹簧模型进行图的可视化布局的一个例子。 图
36、 2.1 FDA算法演示，初始混乱状态下，经过引力和斥力的作用，达到一个相对稳定和美观的状态。2.3.2 FR算法T.M.J.Fruchterman和E.M.ReingoId以Eades 提出的FDA算法思想为基础在文献10中提出了FR 算法。该算法针对图的布局遵循两个简单的原则：1. 有边连接的节点应该互相靠近；2. 节点间不能离得太近。FR算法在图中任意两个节点之间定义斥力，使图中的节点产生距离，在图中有边连接的节点之间定义引力，从而能够让有边相连接的节点能够互相靠近，节点在力的作用下运动，最终达到平衡状态。力的定义如下： 斥力： (2.10) 引力： (2.11)其中，表示理想状态下图中
37、两个节点之间的距离，理想状态下，节点应该是均匀地分布在整个画布上，而每个节点周围都应该有半径为的一个空白区域。FR算法首先定义一个迭代次数。在每一次的迭代过程中，先计算每一个节点和图中其它节点之间的排斥力，然后再通过遍历每一条边计算构成边的两个顶点之间的吸引力，所有的力都不直接更新节点坐标而是记录于节点的临时变量中；最后遍历每一个节点计算其合力，再进行节点坐标的更新。算法伪代码见图 2.2：图 2.2 FR算法伪代码FR算法得益于出色的模型选择，所以能够画出相当优美的图形。算法的时间复杂度是。2.4 复杂网络图的化简2.4.1 网络图的层次化模型直接使用传统的布局算法对图直接运算产生布局结果的
38、做法已不适应图的规模的不断增大：其一，布局大量节点耗时过长，超过了用户的忍耐极限；其二，大量的节点和连边直接展示在有限的布局画板上，使得用户无法从其中获得有效的信息，失去了图可视化的原有目的。为了克服数据规模过大带来的问题，学者们提出了使用层次化的方式对图进行布局，也就是说将原有的图分割成多个层次，每一个层次都是对原图的一种精简，层次越往上精简程度越高，节点个数越少。针对某一层进行可视化布局一方面加快了处理速度，另一方面减少了画布上展示的节点数目，而且用户可以通过上钻和下钻操作对感兴趣的某一部分进行更高精度的观察和分析。图 2.3展示了图的层次化模型：图 2.3 图的层次化抽象2.4.2 网络
39、图的社区结构发现算法网络中的社区结构，是近年来众多研究人员对各种实际网络进行研究时所发现的网络中普遍存在的一个共同特征。它是指网络中的顶点可以分成组 ,组内顶点间的连接比较稠密 ,组间顶点的连接比较稀疏15-22。目前广泛被用来评估社区划分优劣的量化测度是由Grivan和Newman提出的模块度23： （2.12）其中是划分出社区的个数，是第个社区内部的边数，是第个社区中节点的度数和，是网络中的总边数。模块度函数的值越大，表示社区结构越明显，在实际网络中，该值一般在0.3到0.7之间。图 2.4是一个具有社区结构的网络示意图。图 2.4 社区网络结构示意图社区探测是社会网络研究工作中的一项重要
40、课题。随着越来越多的科研工作者投入到网络的社区结构的问题中，网络中的社区结构的探测问题已经得到了充分的研究并且提出了许多知名的社区探测算法。在通过凝聚节点和移除边两种方式来进行社区结构发现的时候可以建立起一个层次化的树结构，这类算法的特点在于关注网络连通形成的拓扑结构，并应用拓扑结构的特性刻画顶点和连边，划分网络中的社团。应用这类算法时往往并不需要额外的信息。接下来将介绍其中一部分最有名的社区结构探测方法。2.4.2.1 GN算法Girvan和Newman去边算法基本思想是按照一定标准将边从网络中移除，以达到社区的划分效果。GN算法由Girvan和Newman在2002年在文献15中被提出。该
41、算法是探索网络图中的社区结构的经典算法。根据网络图中对于社区结构的定义知道，社区内部的节点之间连接紧密，而社区之间的节点之间连接稀疏15,19。这就说明了社区与社区之间的边相对于社区内部之间的边要少。如果能够找到标识出社区之间连边的这种特性的标准，那就可以通过这个标准，找出所有的这些边，并将其移除，那么网络图中剩下的部分就是被分割出来的社区了。Girvan和Newman提出了边介数的概念。对于网络图中的某条边，该边的边介数指的是网络图中任意两点的最短距离所通过该边的次数。通过这个定义，就可以发现，连接社区之间的边的边介数相对于社区内部边的边介数要来的大。通过连接社区之间的边的边介数一般性来讲要
42、比社区之内的边的边介数要高的原因，GN算法采取每次去掉网络中边介数最高的边，直到网络中所有的边全部移除，然后再取去边过程中使模块度函数的值达到最大时的划分作为社区划分。该算法的具体过程如下：1. 计算网络图中所有边的边介数；2. 在最新层次中移除边介数最大的边；生成一个新的层次网络，并将该层次网络作为最新的层次；3. 重新计算网络图中剩下的边的边介数；4. 如果最新层次中边的个数大于1，返回步骤25. 选择使模块度函数值达到最大时的层次作为对原网络的社区划分。算法中包含的重新计算网络图中剩下边的边介数这个步骤是非常有必要的。由于当从网络图中进行移除边的操作时，网络图的结构也就随即发生了变化，原
43、来计算的边的边介数的值已经无法代表移除边以后的网络结构，需要重新计算剩下边的边介数。以一个例子来说：假设有一个包含两个社区结构的网络图，并且只有两条边进行连接。刚开始，其中一条边的边介数是最大的，所以，这一条边则首先被移除出网络图。这个时候，如果不重新计算各个边的边介数，那么，剩下的这条边根据其上一次计算的边介数数值可能不会被立即从网络图中移除。而如果重新计算网络图中剩余边的边介数，那么这条边的边介数很有可能是最大的，会被立即移除出网络图。这样，对于网络图中社区结构的划分显然会产生很重要的影响。树状图可以直观的表现出GN算法对网络进行社区结构划分的整个过程，如图2.5。图 2.5 GN算法得到
44、的空手道俱乐部社团结构划分的树状图及对应的模块化函数值19GN算法有着非常好的社区发现性能19，但是它的时间复杂度是，因此无法将其用于规模较大的复杂网络。2.4.2.2 NF算法NF算法由Newman在2004年在文献16中被提出，也被称为Newman贪婪算法。该算法过程如下：1. 初始时，将网络中每一个节点都看成一个独立的社区，此时，每一个社区内只有一个节点。即对于有个节点的网络图来说，便被初始化为个社区；2. 在最新划分的社区层次中合并使Q函数变化最大的两个社区，生成一个层次网络，并将该层次网络作为最新的层次；3. 重复步骤2的操作，不断地对社区进行两两合并，直到所有的节点都被合并到了同一
45、个社区中为止。最多能够进行次这样的操作；4. 选择使Q函数值达到最大时的层次作为对原网络的社区划分。NF算法有着非常好的社区发现性能，并且其时间复杂度为。在文献16中指出该算法在42分钟内处理了含有56 276个节点的网络，而使用GN算法需要花费3到5年的时间，说明NF算法是一个性能很优秀的社区发现算法，但其时间复杂度仍然有提升的空间。所有这些讨论的方法的目的就是在于探测出一个标准的划分，通过使用简单图，将每个节点都指定到一个特定的划分中。不幸的是，在现实中的网络中的图一般都不是简单图。首先第一个事实就是图中的边很有可能是带权的，我们不能将每条边都等同视之。举个例子，文献22中的模型为在线社会
46、网络用户评论（HTML格式）萃取出的语义信息构建了一个带权语义网络。这些权值反映出网络中各个边的重要性。为了降低研究的时间复杂度，该语义网络中的边通过用户指定的一个阀值来进行修剪。因此，经过这种修剪处理，社区探测算法可以把注意力集中在线社会网络的大件上面。其次，第二个事实是现实图中的节点通常不会只属于某一个社区。这种现象被称为重叠社区。2.5 本章小结本章对复杂网络图的可视化技术涉及到的相关概念进行了介绍。首先给出了本文研究的对象和相关符号约定，方便了下文中符号的重复声明。接下来介绍了FDA和FR两种用于网络图布局的力导引算法。然后从网络图的规模不断扩大，现有处理方式无法满足实际需求的现状出发
47、，列举了由于网络图规模的增大，对可视化技术带来的影响，随之，介绍了网络图的层次化模型和网络图的社区结构发现算法。并对现有算法的不足之处进行了相应的分析。力导引算法和社区结构发现算法是理解后面章节的基础，后两章还会对这两个问题进行更深入的探讨。第三章 基于边密度的复杂网络社区结构发现算法3.1 概述GN算法和NF算法是经典的网络社区结构发现算法，在网络社区结构的发现质量上有着不俗的表现，但是对于复杂网络来说，其性能仍然不能满足系统的要求，其中GN算法的时间复杂度是，NF算法的时间复杂度是。因此，研究一种能够更加快速并且有效地将网络中存在的社区结构探测出来，对于复杂网络的可视化布局是至关重要的。本章首先介绍了社区结构的基本概念和经典社区结构发现算法的社区结构划分优劣的评判准则模块度的概念。并指出了将模块度作为社区结构划分优劣的评判准则的不足之处。接下来详细地分析了新的社区结构发现算法ECAA的具体步骤。
