Approximation Algorithms And Heuristics For The Max K-Uncut Problem

With the deep study of the physical and mathematical characteristics of networks,researchers have found that many networks in the real world have a property in common,namely community structure.In other words,the whole network is composed of several"communities" or "groups".The connections between nodes in each communit0y are relatively dense,while the connections between different communities are sparse.Revealing the community structure of the network is very important for us to understand the network structure and analyze network characteristics.The corresponding community partition problem in network science can be modeled as dividing a topological graph structure into k parts.The Max k-Uncut problem provides a new measure for network partition.Given an undirected graph G with n vertices,where each edge has a non-negative weight assigned to it,and a positive integer k,the Max k-Uncut problem is to find a k-partition of the G so that the sum of the weight of edges not cut by the partition is maximized.This problem is the complement of the Min k-Cut problem,and is closely related to many combinatorial optimization problems,including the Densest k-Subgraph problem.Therefore,the Max kUncut problem is significant for both real-world applications and theory research.Note that Max k-Uncut is not intended to replace the existing measures for partitioning and classifying networks,such as k-Cut,k-Center,k-Means,etc,but to provide a new choice.In this paper,we explore the solution of the Max k-Uncut problem using three different types of algorithms,namely,deterministic algorithm,approximation algorithm and heuristic algorithm.In terms of deterministic algorithm,we view the Max k-Uncut problem from two perspectives with one from the perspective of subset,and the other from the perspective of vertex.We provide detailed description of the algorithms and their complexity analysis.It is proved that the time complexities of the two algorithms are O((n+m)2kn)and O((n+m)kn)respectively.As for the approximation algorithm,we propose an algorithm named Multiple Greed(MG).MG is a simple algorithm with intuitive greedy strategy.The algorithm evolves calculating the minimum cuts for k-1 times and cut the "weakest" part of the generated subgraph in each iteration.We give a detailed description of the algorithm.And it is strictly proved that MG has an approximation ratio of 1-2k-1/n,which is the same as the best approximation ratio known for the Max k-Uncut problem,compared with the existing algorithms,MG can give a more natural solution for the Max k-Uncut problem,which is more in line with the reality.In addition,we improved the running time of the algorithm using minimum heap,taking the vertex subset as the value and the weight of the minimum cut of the subset as the key.The improved algorithm has 0(kn2)time complexity.About the heuristic algorithms,we propose two heuristic algorithms,namely,the Binary Partition Algorithm(BP)and the Max Adjacency Search Algorithm(MAS).BP is a variant of MG,and the way of generating partition is different from MG.MAS uses greedy strategy.This paper gives the descriptions of the two algorithms,improves the running time of the two algorithms,and analyzes their time complexity respectively.At last,these algorithms are tested and verified by experiments.Three graph generating models are used to generate test sets.These three models are G[n,p]model,configuration model and preference model.By fixing the number of partition parts k and the number of vertices n,graph generating models are used to generate 12 test sets,and the approximation algorithm and the heuristic algorithms in this paper are tested on the test sets.Compared with the existing algorithms,MG has achieved the best experimental results in terms of the solution value and winning times.Two heuristic algorithms,MAS and BP,have also achieved good results.