Skip to main content
Article
On detecting maximal quasi antagonistic communities in signed graphs
Data Mining and Knowledge Discovery
  • Ming GAO, East China Normal University
  • Ee-Peng LIM, Singapore Management University
  • David LO, Singapore Management University
  • Philips Kokoh PRASETYO, Singapore Management University
Publication Type
Journal Article
Version
acceptedVersion
Publication Date
1-2016
Abstract

Many networks can be modeled as signed graphs. These include social networks, and relationships/interactions networks. Detecting sub-structures in such networks helps us understand user behavior, predict links, and recommend products. In this paper, we detect dense sub-structures from a signed graph, called quasi antagonistic communities (QACs). An antagonistic community consists of two groups of users expressing positive relationships within each group but negative relationships across groups. Instead of requiring complete set of negative links across its groups, a QAC allows a small number of inter-group negative links to be missing. We propose an algorithm, Mascot, to find all maximal quasi antagonistic communities (MQACs). Mascot consists of two stages: pruning and enumeration stages. Based on the properties of QAC, we propose four pruning rules to reduce the size of candidate graphs in the pruning stage. We use an enumeration tree to enumerate all strongly connected subgraphs in a top-down fashion in the second stage before they are used to construct MQACs. We have conducted extensive experiments using synthetic signed graphs and two real networks to demonstrate the efficiency and accuracy of the Mascot algorithm. We have also found that detecting MQACs helps us to predict the signs of links.

Keywords
  • Bi-clique,
  • Enumeration tree,
  • Power law distribution,
  • Quasi antagonistic community,
  • Signed graph
Identifier
10.1007/s10618-015-0405-2
Publisher
Springer
Copyright Owner and License
Authors
Creative Commons License
Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International
Additional URL
https://doi.org/10.1007/s10618-015-0405-2
Citation Information
Ming GAO, Ee-Peng LIM, David LO and Philips Kokoh PRASETYO. "On detecting maximal quasi antagonistic communities in signed graphs" Data Mining and Knowledge Discovery Vol. 30 Iss. 1 (2016) p. 99 - 146 ISSN: 1384-5810
Available at: http://works.bepress.com/david_lo/300/