电子技术论文物理布局算法改进设计

　　随着互联网技术和计算机技术的发展，网络在人们生活当中的重要性日益显著。网络规模日益庞大且关系复杂，因此如何直观高效分析研究这些网络中复杂的数据成为人们密切关注的热点。通过网络可视化模型可以解决上述的问题，网络可视化是一种便利高效简洁的方法，但是网络规模日益增大，大量的节点和边出现在网络当中，将会导致可视化模型出现交叉拥塞的问题，大大影响到可视化的效果。通常可以靠改进网络拓扑结构的物理布局算法来优化可视化的效果，其核心思想就是进行物理类比。

　　摘要：随着互联网技术以及计算机技术的发展，网络安全越来越受到人们的重视。在现实当中，可以用复杂网络的思想解释和研究很多真实的网络，而社区结构正是复杂网络的一个很重要的特征。因此，提出一种基于社区结构的网络布局算法，利用附在网络社区发现算法划分网络当中的节点，并且抽象社区为一个节点，每个节点之间相互关联，形成一个网络。而社区中心点的位置采用物理类比的方法来确定，运用条件择优方式完成网络拓扑的布局优化。这种物理布局算法相比传统的布局算法而言更加安全高效，结构也更加清晰。

　　关键词：电子技术论文,复杂网络,安全,布局

　　The Improve of Physical Layout Design Algorithm in Complex Network

　　Abstract： With the development of Internet and computer technology， network security attracts people's attention. In reality， you can use the network to explain complex ideas and analyse the actual network， and complex network is a very important feature of community structure . Therefore， a network layout algorithm is proposed based on the community structure using the online communities attached to the network discovery algorithm dividing the nodes， and abstracts the community as a node ， and the correlation between each node form sa network.The algorithm uses physical analogy method to determine the community center point and the conditions merit accomplishinglayout optimization of the network topology. Compared with the traditional layout algorithm，this physical layout algorithm is better at security， efficiency and structure.

　　Key words： complex network;security;layout

　　1 传统的物理布局算法

　　物理布局算法概念第一次出现在1984年由Peter Eaders提出的弹力模型当中，该模型认为每个定点是一个钢圈，顶点间的边是钢圈之间的弹簧。起初，随机放置顶点的位置，弹力也会随机加在顶点之上，不断的迭代，一定的次数之后会终止。算法的收敛速度相对不同的网络而言也是不一样的。Kamada针对这种情况提出了KK模型，这是一种改进型的模型，这种模型的优势就是能够大大的提高收敛的速度，但是仍然有很大的上升的空间。在此之后Davidson又提出了改进型的DH模型，能量函数的思想第一次在该模型当中被提出。每个布局被赋予一个能量，用能量的大小表示布局的优化程度。DH模型能够获得比较好的布局，但是非常的消耗时间。

　　随后，Fruchteman在此基础上提出FR算法，这是一个比较经典的算法，它对弹力模型进行了优化设计。在提出的FR算法模型当中，节点被比作为原子或者天体。根据物理学的原理，原子或者天体之间具有相互作用，或者表现为斥力或者表现为引力。这些力会引起物体运动。和最初弹力模型不一样的是，节点之间不但具有引力的作用，同时也会有斥力的作用，最终引力和斥力会达到一个平衡的状态。FR算法具有布局效果好、易于实现，因此比较适用在结构比较简单、数目比较小的简单的网络。FR算法复杂度比较低，是现在比较常用的网络布局算法之一。后期提出的GEM算法和LinLog算法都在一定程度上参考了FR算法。力导布局算法以及快速多级力导布局算法等也都属于物理布局算法。

　　近些年来，人们对拓扑结构的物理算法的研究主要集中在对电子硬件元件的布局布线的算法比如FPGA或者芯片研究。随着人们对于复杂网络的研究取得一定的成功，这就给网络布局算法带来了新的研究思路，人们不再仅仅局限使用物理类比的方法来考虑布局的问题，利用复杂网络抽象一些复杂的系统，充分研究了复杂系统小世界性、无标度性、聚集性等等。现实生活当中的复杂的系统都可以表示成一些网络，其中有信息网络，生物网络，技术网络等等。研究分析表明，可以用一些节点划分这些网络，同一个节点组内的节点相对于不同的节点更加具有相互连接的效应。这样就能形成社区结构。这种结构能够很好的刻画出网络的局部聚集的性质。好的布局算法能够揭示复杂的数据的深刻含义，方便观察者了解内在的构成。因此，该文在布局的时候通过社区划分网络，能够更加细致刻画连边的局部性质，从而提高物理布局算法的效果。由于真实网络具有的社区结构特性，因此这种算法具有良好的普遍适用性。　　2 算法的设计实现

　　2.1 算法的主要思想

　　若是存在这样一个N网络，网络N可以用N(V，E)来表示，其中V(N)是顶点的集合，E(N)为边的集合，那么网络布局可能获得一个层次清楚的拓扑图，用如下的指标衡量该拓扑图：

　　1) 拥挤度。局部的边过多会造成拥挤，合理的网络拓扑结构应该尽可能的减少拥堵。社区算法使用了估计函数来合理的分析网络布局的拥挤的程度。这种方法能够方便高效的检测到所有的拥挤的区域。

　　2) 边交叉树目。拓扑图的交叉的数据应该尽量的少，这样图的布局就会更加的清晰，布局更加的合理。

　　3) 节点的分布情况。节点的分布应该尽可能的利用空间，应该是划分的区域内节点数目的均方差值尽可能的小。

　　4) 具有连边的节点之间的相对的位置：如果一个节点的附近有m个节点和它邻近，那么这m个节点设置应该尽可能的和它靠近，这样才能清晰的表达出节点之间的关系，减小交叉的边。

　　研究表明，可以用复杂网络的方式对网络进行建模，即采用复杂网络解释真实网络的性质。在使用社区算法分析研究网络性质的时候，应该先抽象社区为节点，使用社区间关联构建社区的网络，然后采用物理类比方法完成对社区的布局。因为网络划分为社区，节点数目较少，这就避免节点过多造成的收敛速度慢的问题。最后使用择优算法填充节点，完成布局。

　　2.2 算法的设计

　　算法的设计主要分为4个步骤：

　　1) 建立节点社区网络

　　为了得到优秀的物理布局，FR算法会受到条件的约束，首先节点位置邻近，其次要避免相互靠近。由于众多的节点连边，基于上述的约束条件，需要将社区看成一个节点来布局网络，在布局的基础上确定社区区域来填充内部相互邻近的节点，这样做不仅符合布局的规范，也能够简化一些布局的步骤。

　　2) 社区网络布局引入物理类比算法

　　依据FR的思想，根据动量守恒定律，系统在受到平衡力或者不受到外力作用的情况下，系统如果只具有内部的力的作用，系统的动量是守恒的。系统的初始的动量是为0的，那么经过一段的时间的内力作用后，系统内部的节点要么趋于静止要么保持震荡，利用这个性质可以完成对社区的中心位置的布局。设R(x，y)表示节点x，y之间的斥力，网络中的第i个和第j个社区分别用Ci和Cj表示，存在常量f和g，抽象后的斥力可以用下列式子表示：

　　其中d为节点间的欧几里德距离，m为社区内节点的质量。

　　张力可以用如下的式子表示：

　　3) 确定社区的范围

　　新网络当中每个节点的坐标对应着节点所代表社区的中心点的坐标，在确定了社区中心点的方位之后，分配一个区域来填充每个社区的内部的节点。可以采用以中心节点为圆心画圆的方法。为了使节点均匀的布置，圆的半径要根据社区的规模来确定。

　　4) 填充社区的内部节点

　　在确定社区中心节点和半径之后，开始进行社区节点的填充，社区节点可以分为非边缘节点和边缘节点，非边缘节点指的是一个节点和具有相同边的节点都属于一个社区，而边缘节点就是它们跨社区了。填充需要受到下面3个条件约束：1) 边缘节点尽量在社区共有区域之间。2) 度数较大的节点应该尽量的靠近所属的社区的中心位置。3) 边缘节点应该尽可能的和它有连边的非边缘的节点靠近。

　　3 总结

　　根据物理布局算法的要求，该文提出了划分网络社区的拓扑布局算法思想，由于大多数网络具有复杂网络的性质，比如说聚类性质以及社区性质，因此使用社区算法进行物理布局不仅仅反映了网络的社区结构，同时也减小了计算的规模，从而提高了运算的速度。

　　参考文献：

　　[1]李卓远，吴为民，洪先龙.优化线长和拥挤度的增量式布局算法[J].计算机辅助设计与图形学学报，2003，15(6)： 651-655

　　[2]程学旗，沈华伟.复杂网络中的社区结构[J].复杂系统与复杂性科学，2011，8(1)：58.

　　[3]戴晖，周强，边计年，等.层次式FPGA快速布局算法[J].计算机辅助设计与图形学学报，2010，22(9)： 1455-1462.

　　[4]吕亮，卢泽新，俪苏丹，等.基于扩展力学模型的网络拓扑图布局算法[J].计算机应用研究，2010，27(7)： 2713-2715.