Research On Balanced Hypergraph Partitioning Algorithm Based On Generating Subgraphs

Minimizing the query cost among multiple hosts is of great significance for data processing in large data applications.Hypergraphs are good at modeling data and data relationships in complex networks(typical large data applications)by representing multipath relationships or interactions as networks.Hypergraph partitioning helps to partition query loads on multiple hosts,thus achieving horizontal scaling of large-scale networks.Finding a good division of communication tasks among available processing units is essential to shorten execution time,reduce energy consumption,and make better use of computing and communication resources.Therefore,this paper improves the existing hypergraph partitioning algorithm of cutting network based on generating subgraph theory,which can process online information communication tasks with a large number of users more efficiently and in parallel.Existing heuristic hypergraph partitioning algorithms are generally divided into two types:vertex partitioning and edge(network)partitioning.The aim is to minimize the number of cutting networks while satisfying the balance requirement of partition weight on vertices.However,since the workload is mainly generated by group operation(network),it is more reasonable to consider network partitioning in order to reduce the total query cost and balance the workload in the whole communication network in horizontal expansion.Therefore,we propose a heuristic hypergraph partitioning algorithm for networks.Specifically,first,determine the average number of edges per partition.Then,according to the reverse thinking,the hyperedge is regarded as a node,and the search algorithm of minimal generating subgraph is used to find the minimum node that can contain the mean of hyperedges.Then,the current partition is optimized based on the definition of excess moving gain in the classical hypergraph partitioning algorithm HEPart.Finally,the hypergraph partition satisfying the weight balance constraints of the network is obtained.In two complex network datasets modeled by undirected hypergraphs,the performance of the proposed algorithm is evaluated at different cutset scales.Compared with the existing hyper-edge partitioning algorithm HEPart,the partitioning quality and performance are compared.The experimental results show that the proposed algorithm has lower computational cost and better partition quality.