On Lagrangians Extreme Value Estimation And Correlation Clustering Algorithms Of Hypergraphs

In 1965,Motzkin and Straus introduced Lagrangians of graphs and established a connection between the clique number of a graph and it's Lagrangian,i.e.,the Lagrangian of a graph is equal to the Lagrangian of its maximum clique.Based on this connection,Motzkin and Straus gave a new proof of Turan's theorem.Motzkin-Straus theorem has also been successfully applied to the maximum clique problem,spectral graph theory and reltaed fields.These successful applications have aroused people's great interest in Lagrangians.Sos and Straus extended this concept to hypergraphs.The Lagrangian of a hypergraph has become a powerful tool for studying the extreme problems in hypergraphs.The Lagrangians of hypergraphs and their extensions are also widely used in the partition of hypergraphs,clustering and other fields.In many applications of Lagrangians of hypergraphs,the upper bound needs to be estimated.However,it is very challenging to estimate the upper bound of the Lagrangian of a hypergraph.Frankl and Furedi conjectured that the r-graph with m edges formed by taking the first m sets in the colex ordering of N(r)has the largest Lagrangian of all r-graphs with m edges.This paper focuses on Lagrangians of hypergraphs and their applications in clustering.The main results of this paper are shown as follows:(1)Frankl-Furedi conjecture holds for a class of 3-uniform hypergraphs with fewer edges is proved theoretically.That is to say,the following theorem is proved:Let m and t be intetirgers sasfying(?)and t?8,such that?([t-1](3)).(2)The study on Frankl-Furedi conjecture is mostly confined to 3-uniform hypergraphs.It is very challenging for the general r-uniform hypergraph(r?4).In this paper,we prove the following theorem of Frankl-Furedi conjecture on 4-uniform hypergraphs:Let m and t be intergers satisfying(?)H represtents a 4-uniform hypergraph with t vertexs and m edges,such that A(H)??([t-1](4)).It is proved that the Frankl-Fiiredi conjecture is established under the above conditions.These results provide support for the Frankl-Furedi conjecture.(3)The complement graphs structure is introduced into Lagrange extremum functions,and the definition of Lagrangians is modified,then,the concept of generalized Lagrange extremum is given.With these tools,some Mozkin-Straus type theorems of 3-uniform hypergraphs under broader conditions are proposed.Thus,we establish a connection between the generalized Lagrangian and the maximum clique of a hypergraph.On the one hand,this connection can provide heuristic for the maximum clique problem of the 3-graphs,and on the other hand it can also be used to the standard simplex optimization in Euclidean space to provide combination ideas for a class of cubic homogeneous polynomial optimization problems.At the same time,these results also provide support for the Frankl-Furedi conjecture.(4)A clustering algorithm and a dimensionality reduction method of hypergraphs are proposed.The clustering score function is constructed with the deformation of hypergraph Lagrange function.The algorithm is validated on the simulation point set and the real image data set Corel lk.The results show that this method not only has better classification effect,but also has faster convergence speed.On the image dataset Corel 1k,applying the hypergraph model to reduce the dimension of features can greatly shorten the classification time but lose less classification accuracy.