Identifying Large Structural Balanced Cliques in Signed Graphs
- Publisher:
- Institute of Electrical and Electronics Engineers (IEEE)
- Publication Type:
- Journal Article
- Citation:
- IEEE Transactions on Knowledge and Data Engineering, 2024, 36, (3), pp. 1145-1160
- Issue Date:
- 2024-03
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Identifying_Large_Structural_Balanced_Cliques_in_Signed_Graphs.pdf | Published version | 2.52 MB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Signed graphs have been used to capture the polarity of relationships through positive negative edge signs In this paper we consider balanced cliques a clique is balanced if its vertex set C C can be partitioned into C L CL and C R CR such that all negative edges are between C L CL and C R CR and study the problems of maximum balanced clique computation and large balanced clique enumeration Our main idea is a novel graph reduction that transforms a balanced clique problem over a signed graph G G to problems over small subgraphs of G G Specifically for each vertex u u in G G we extract the subgraph G u Gu of G G induced by V L cup V R VL VR V L VL is u u and u u s positive neighbors while V R VR is u u s negative neighbors Then we remove from G u Gu all positive edges between V L VL and V R VR and all negative edges between vertices of the same set denote the resulting graph of discarding edge signs as g u gu We show that all balanced cliques containing u u in G G can be found by processing g u gu Due to the small size and no edge signs large cliques containing u u in g u gu can be efficiently identified Experimental results on real signed graphs demonstrated the advantages of our techniques
Please use this identifier to cite or link to this item: