大图结构特征对划分效果的影响

摘要

针对大图结构特征如何影响划分效果这一问题,提出一种通过顶点度分布特征来描述大图结构特征的方法.首先,基于真实的图数据产生若干顶点数和边数相同、但结构特征不同的仿真数据集,通过实验计算真实图与仿真图之间的相似度,证明该方法对描述真实大图结构特征的有效性.然后,通过Hash和点对交换划分算法,验证图结构特征与划分效果之间的关系.当点对交换划分算法执行到5万次时,划分一个有6301个顶点和20777条边的真实图其交叉边数比Hash划分算法降低了54.32％,划分仿真图数据集中结构特征差异明显的两个图时,交叉边数分别为6233和316.实验结果表明,点对交换划分算法能够减少交叉边数,图的顶点度分布差异越大,划分后交叉边数越少,划分效果越好,因此大图结构特征影响其划分效果,这为建立图的结构特征与划分效果之间的关系模型研究奠定了基础.%Focusing on how the large-scale graphs' structural features affect the partitioning quality,through the structural features of vertex degree,a method of describing large-scale graphs' structural features was proposed.Firstly,based on the real graph data,a several simulation datasets with the same numbers of vertices and edges but different structural features were generated.Through the similarity between the real graph and the simulation graph calculated by the proposed algorithm,the validity of the method for describing the structural features of the real large-scale graphs was verified.Secondly,the relationship between the structural features of the graph and the quality of partitioning was verified by the Hash algorithm and point-to-point exchange algorithm.When the point-to-point algorithm was performed for 50000 times,the number of crossed edges of a real graph with 6 301 vertexes and 20 777 edges was reduced by 54.32％ compared with the Hash partitioning algorithm.When the two graphs with entirely different structural features in the simulation data were partitioned,the number of crossed edges were 6233 and 316 respectively.The experimental results show that the point-to-point algorithm can reduce the number of crossed edges.The larger the difference of the vertex degree distribution and the smaller the number of crossed edges are,the better the partitioning quality is.Therefore,the structural features of large graphs affect the partitioning effect,which lays the foundation for the model investigation of the relationship between structural features and partitioning quality.