Maximum Signed θ-Clique Identification In Large Signed Graphs

The maximum clique problem is finding the clique with the largest size,where every vertex in the clique is adjacent.The problem finds many practical applications and is notable for its ability to model many combinatorial problems.However,most existing research focuses on dealing with unsigned graphs,i.e.,treating each connection equally.In practical applications,the edges of a graph are usually associated with signed information,i.e.,positive or negative edges.Due to its unique properties,signed graph analysis has attracted significant attention in recent years.This paper first analyzes the shortcomings of existing signed models and then propose a new clique model named the maximum signedθclique.Given a signed graph G and a subgraph S,let the number of positive neighbors of vertex u in S be d_S~+(u),and the number of antagonistic neighbors of vertex u in S be d_S~-(u).This paper says that a subgraph S is a signedθclique if(4)4))S is a clique,(4)4)4)4))every vertex u in S satisfies d_S~+(u)-d_S~-(u)≥,(4)4)4)4)4)4))is the largest.This paper shows that the problem of identifying the largest signedθclique is NP-hard.This paper proposes new pruning techniques to reduce the search space.Furthermore,efficient search strategies are developed to scale large graphs.This paper conducts extensive experiments on eight real-world datasets to demonstrate the effectiveness and efficiency of the proposed method.In large datasets,our baseline method can not return result in 24 hours,but our optimized algorithm for finding maximum signedθclique can return in 100 seconds.Based on the definition of maximum signedθclique,this paper also proposes a signed(6)6),)-truss on signed graphs,building on ideas from this paper.A subgraph is a signed(6)6),)-truss if(4)4))each edge is contained in at least6)6)balanced triangles,(4)4)4)4))each edge is included in at mostunbalanced triangles,and(4)4)4)4)4)4))it is the largest,that is,its hypergraph does not satisfy the previous constraints.Unlike the traditional6)6)truss model in unsigned graphs,there may be multiple(6)6),)-trusses in signed graphs.Due to the NP-hardness of the problem,this paper first proposes a framework of greedy algorithms.This paper develops novel pruning techniques and search algorithms to speed up the search.Finally,this paper conducts experiments on real world signed graphs to demonstrate the advantages of the proposed models and methods.Experiments prove that our algorithm designed in this paper takes less than100 seconds to return the result even in large symbolic networks.Finally,this paper puts forward some areas that need to be improved based on the existing research.These directions will also become the research goals of future scientific research.Generally speaking,these aspects mainly include signed bipartite graph analysis and efficient algorithm design.