.png){kind=icon}
.png){kind=icon}
Return
Identifying Large Structural Balanced Cliques in Signed Graphs
.png){kind=icon}
PRE
AI
DOI：10.1109/TKDE.2023.3295803.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 can be partitioned into C-L and C-R such that all negative edges are between C-L and C-R - 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 to problems over small subgraphs of G . Specifically, for each vertex u in G , we extract the subgraph G(u) of G induced by V-L boolean OR V-R ; V-L is u and u 's positive neighbors while V-R is u 's negative neighbors. Then, we remove from G(u) all positive edges between V-L and V-R and all negative edges between vertices of the same set; denote the resulting graph of discarding edge signs as g(u) . We show that all balanced cliques containing u in G can be found by processing g(u) . Due to the small size and no edge signs, large cliques containing u in gu can be efficiently identified. Experimental results on real signed graphs demonstrated the advantages of our techniques.
Keywords:
Proteins
Social networking (online)
Image edge detection
Transforms
Australia
Toy manufacturing industry
Computer science
Graph algorithms
signed graphs
structural balanced cliques
Journal
IF:
10.4
Papers:
6.8K
Citations:
3.2W