Identifying Large Structural Balanced Cliques in Signed Graphs

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 <inline-formula><tex-math notation="LaTeX">$C$</tex-math><alternatives><mml:math><mml:mi>C</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq1-3295803.gif"/></alternatives></inline-formula> can be partitioned into <inline-formula><tex-math notation="LaTeX">$C_{L}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>C</mml:mi><mml:mi>L</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq2-3295803.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$C_{R}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>C</mml:mi><mml:mi>R</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq3-3295803.gif"/></alternatives></inline-formula> such that all negative edges are between <inline-formula><tex-math notation="LaTeX">$C_{L}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>C</mml:mi><mml:mi>L</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq4-3295803.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$C_{R}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>C</mml:mi><mml:mi>R</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq5-3295803.gif"/></alternatives></inline-formula> — 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 <inline-formula><tex-math notation="LaTeX">$G$</tex-math><alternatives><mml:math><mml:mi>G</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq6-3295803.gif"/></alternatives></inline-formula> to problems over small subgraphs of <inline-formula><tex-math notation="LaTeX">$G$</tex-math><alternatives><mml:math><mml:mi>G</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq7-3295803.gif"/></alternatives></inline-formula>. Specifically, for each vertex <inline-formula><tex-math notation="LaTeX">$u$</tex-math><alternatives><mml:math><mml:mi>u</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq8-3295803.gif"/></alternatives></inline-formula> in <inline-formula><tex-math notation="LaTeX">$G$</tex-math><alternatives><mml:math><mml:mi>G</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq9-3295803.gif"/></alternatives></inline-formula>, we extract the subgraph <inline-formula><tex-math notation="LaTeX">$G_{u}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>G</mml:mi><mml:mi>u</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq10-3295803.gif"/></alternatives></inline-formula> of <inline-formula><tex-math notation="LaTeX">$G$</tex-math><alternatives><mml:math><mml:mi>G</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq11-3295803.gif"/></alternatives></inline-formula> induced by <inline-formula><tex-math notation="LaTeX">$V_{L} \cup V_{R}$</tex-math><alternatives><mml:math><mml:mrow><mml:msub><mml:mi>V</mml:mi><mml:mi>L</mml:mi></mml:msub><mml:mo>∪</mml:mo><mml:msub><mml:mi>V</mml:mi><mml:mi>R</mml:mi></mml:msub></mml:mrow></mml:math><inline-graphic xlink:href="yao-ieq12-3295803.gif"/></alternatives></inline-formula>; <inline-formula><tex-math notation="LaTeX">$V_{L}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>V</mml:mi><mml:mi>L</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq13-3295803.gif"/></alternatives></inline-formula> is <inline-formula><tex-math notation="LaTeX">$u$</tex-math><alternatives><mml:math><mml:mi>u</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq14-3295803.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$u$</tex-math><alternatives><mml:math><mml:mi>u</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq15-3295803.gif"/></alternatives></inline-formula>'s positive neighbors while <inline-formula><tex-math notation="LaTeX">$V_{R}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>V</mml:mi><mml:mi>R</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq16-3295803.gif"/></alternatives></inline-formula> is <inline-formula><tex-math notation="LaTeX">$u$</tex-math><alternatives><mml:math><mml:mi>u</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq17-3295803.gif"/></alternatives></inline-formula>'s negative neighbors. Then, we remove from <inline-formula><tex-math notation="LaTeX">$G_{u}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>G</mml:mi><mml:mi>u</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq18-3295803.gif"/></alternatives></inline-formula> all positive edges between <inline-formula><tex-math notation="LaTeX">$V_{L}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>V</mml:mi><mml:mi>L</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq19-3295803.gif"/></alternatives></inline-formula> and <inline-formula><tex-math notation="LaTeX">$V_{R}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>V</mml:mi><mml:mi>R</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq20-3295803.gif"/></alternatives></inline-formula> and all negative edges between vertices of the same set; denote the resulting graph of discarding edge signs as <inline-formula><tex-math notation="LaTeX">$g_{u}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>g</mml:mi><mml:mi>u</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq21-3295803.gif"/></alternatives></inline-formula>. We show that all balanced cliques containing <inline-formula><tex-math notation="LaTeX">$u$</tex-math><alternatives><mml:math><mml:mi>u</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq22-3295803.gif"/></alternatives></inline-formula> in <inline-formula><tex-math notation="LaTeX">$G$</tex-math><alternatives><mml:math><mml:mi>G</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq23-3295803.gif"/></alternatives></inline-formula> can be found by processing <inline-formula><tex-math notation="LaTeX">$g_{u}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>g</mml:mi><mml:mi>u</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq24-3295803.gif"/></alternatives></inline-formula>. Due to the small size and no edge signs, large cliques containing <inline-formula><tex-math notation="LaTeX">$u$</tex-math><alternatives><mml:math><mml:mi>u</mml:mi></mml:math><inline-graphic xlink:href="yao-ieq25-3295803.gif"/></alternatives></inline-formula> in <inline-formula><tex-math notation="LaTeX">$g_{u}$</tex-math><alternatives><mml:math><mml:msub><mml:mi>g</mml:mi><mml:mi>u</mml:mi></mml:msub></mml:math><inline-graphic xlink:href="yao-ieq26-3295803.gif"/></alternatives></inline-formula> can be efficiently identified. Experimental results on real signed graphs demonstrated the advantages of our techniques.

• Publication year

  2024

• Venue

  IEEE Transactions on Knowledge and Data Engineering

• Publication date

  2024-03-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TKDE.2023.3295803
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computing Maximum Structural Balanced Cliques in Signed Graphs

  2022influential reference
• Signed heterogeneous network embedding in social media

  2020cited by this paper
• Extending DeGroot Opinion Formation for Signed Graphs and Minimizing Polarization

  2020cited by this paper
• Efficient Maximal Balanced Clique Enumeration in Signed Networks

  2020influential reference
• Searching for polarization in signed graphs: a local spectral approach

  2020cited by this paper
• Efficient maximum clique computation and enumeration over large sparse graphs

  2020cited by this paper
• Discovering Polarized Communities in Signed Networks

  2019cited by this paper
• Efficient Maximum Clique Computation over Large Sparse Graphs

  2019influential reference
• Cohesive Subgraph Computation Over Large Sparse Graphs

  2019cited by this paper
• Relevance Measurements in Online Signed Social Networks

  2018cited by this paper
• Annotating activation/inhibition relationships to protein-protein interactions using gene ontology relations

  2018cited by this paper
• Community Interaction and Conflict on the Web

  2018cited by this paper
• Leveraging semantic resources in diversified query expansion

  2017cited by this paper
• An algorithm based on positive and negative links for community detection in signed networks

  2017cited by this paper
• Recommendations in Signed Social Networks

  2016cited by this paper
• Finding Gangs in War from Signed Networks

  2016cited by this paper
• Detecting Protein Complexes from Signed Protein-Protein Interaction Networks

  2015cited by this paper
• A Survey of Signed Network Mining in Social Media

  2015cited by this paper
• Characterizing Protein Interactions Employing a Genome-Wide siRNA Cellular Phenotyping Screen

  2014cited by this paper
• Detecting k-Balanced Trusted Cliques in Signed Social Networks

  2014cited by this paper
• The maximum balanced subgraph of a signed graph: Applications and solution approaches

  2014cited by this paper
• Quantifying trust dynamics in signed graphs, the S-Cores approach

  2014cited by this paper
• Predicting positive and negative links in signed social networks by transfer learning

  2013cited by this paper
• An effective recommendation method for cold start new users using trust and distrust networks

  2013cited by this paper
• Predicting positive and negative links in online social networks

  2010cited by this paper
• WordNet: A Lexical Database for English

  1995cited by this paper
• Smallest-last ordering and clustering and graph coloring algorithms

  1983cited by this paper
• Finding All Cliques of an Undirected Graph (Algorithm 457)

  1973influential reference
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• On the notion of balance of a signed graph.

  1953influential reference

• An Adaptive Structural Balance Method Based on Reinforcement Learning for Signed Social Networks

  2026cites this paper
• Detecting Structural Balanced Near-Cliques in Large Signed Graphs

  2026cites this paper
• Efficient Antagonistic <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="li-ieq1-3552335.gif"/></alternatives></inline-formula>-Plex Enumeration in Signed Graphs

  2025cites this paper
• Monitoring Political Polarization Based on Multi-Layer Signed Network Analysis

  2025cites this paper