Research On Graph Partitioning Algorithms Of Network Topology

Many researches of Internet management and cognitive network are involved in using high-speed parallel cluster computer to simulate or process large-scale network.The network topology partitioning is an effective technical method to deal with the corresponding computing task allocation.Since the graph partitioning is widely used in many application and to ensure the partitioning quality,the network topology graph partitioning algorithm is studied.Our researches are focus on 4 sides:the network topology graph partitioning scheme,the network simulation graph partitioning algorithms,graph partitioning algorithm for CDN cache server placement and an evaluation method for the network topology graph partitioning quality.The concrete research contents are as follows:First,in order to standardize the solving process of network topology graph partitioning problem,from the internal mechanisms to achieve assurance of partitioning quality,A solving scheme with loop optimization to regulate the network topology partitioning algorithm is constructed.The scheme consists of three parts:one is the pretreatment of the graph,i.e.the weight estimation,constraint condition and the determination of the optimization goal;another include three stages which are the graph partitioning,including the graph coarsen,the initial partitioning and refinement,the third is the evaluation of partitioning quality and loop optimization adjustment of operation parameters.Meanwhile,in order to meet the needs of the expanding application field of the graph partitioning,on the basis of the general definition of network topology graph partitioning,the concept of maximizing the cutting edge is put forward,four extended definitions of network topology graph partitioning are given.The bondage which traditional graph partitioning can only for the minimized edge cutting,but not for the maximized.Second,depending on the solving scheme of the network topology graph partitioning,a network simulation graph partitioning algorithm with loop optimization is constructed.On the basis of the traditional algorithm,the pretreatment link is increased,weight estimation is carried,according to task requirement and the actual data,optimization objectives and constraint conditions is determined.The SLVM in the compression phase is expounded,and not consider some of the problems in the original designare of the LVM are solved.in initial partitioning phase,a selected graph growing partitioning algorithm and selected greedy graph growing partitioning algorithm are proposed.It is resolved that sensitive issues of original algorithm due to the different initial node affects the number of edges cutting.In refinement phase the improved algorithm is discussed,including greedy refinement algorithm and global KL refinement algorithm In the partitioning process,partitioning quality evaluation and adjustment mechanism of the cycle optimization of operating parameters are achieved.Using SLVM,comparing LVM and SHEM,Internet simulation partitioning experiments are carried out.The experimental data proved that SLVM is better than contrast algorithm in edges cutting and equilibrium degree both,and more suitable for Internet simulation partitioning.Third,a new method is proposed for partitioning CDN graph using the maximum edge cutting algorithm to solve the problem for CDN cache server placement..The conditions to be met for CDN graph partitioning is described,the definition of CDN graph partition is given,pointing out that CDN graph partitioning algorithm is to solve the graph partitioning to maximized the cutting edges under the condition of ensuring the overall balance and the node connectivity within a partition.Weight abstract rules of CDN graph are discussed;once one edge compression algorithm and selective light vertex compression algorithm for CDN graph partitioning coarsening compression are proposed;a once one light edge compression k-way partitioning algorithm for CDN graph initial partitioning is proposed.Improving KL/FM refinement algorithm for CDN graph partitioning.CDN graph partitioning experimental data confirm SLVC and OOLEC are the effective methods to solve the problem of CDN graph partitioning.Finally,to compare the performance of different partitioning algorithm,network topology graph partitioning quality comprehensive evaluation method is proposed.Many basic evaluation parameters for network topology graph partitioning are defined.The basic method for network topology graph partitioning quality evaluation is constructed including the concept of cutting-balance product Q,network simulation graph partitioning quality relative evaluation index J and dimensionless evaluation index C and so on.Network simulation graph partitioning quality comprehensive evaluation methods is proposed and constructed.Using J value method and C value method,examples are given for network simulation graph partitioning quality comprehensive evaluation,and comparative experimental data show that:evaluation results show the diffrent indexes can reflect the partition effect and J-value method and the C-value method have practical application value.CDN graph partitioning quality evaluation indexes are built,including the concept of cutting-balance quotient R and CDN graph partitioning relative evaluation index L.With the L value evaluation in CDN graph partitioning quality,the experimental data of the SLVC,OOLEC and LEM algorithm are comparatively analyzed,and it shows that SLVC and OOLEC method have obvious advantages,the effect is better than others.