On detecting maximal quasi antagonistic communities in signed graphs

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...

Full description

Saved in:
Bibliographic Details
Main Authors: GAO, Ming, LIM, Ee-Peng, LO, David, PRASETYO, Philips Kokoh
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2016
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/2858
https://ink.library.smu.edu.sg/context/sis_research/article/3858/viewcontent/Detecting_maximal_quasi_antagonistic_communities_in_signed_graphs_afv.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-3858
record_format dspace
spelling sg-smu-ink.sis_research-38582020-03-25T08:44:46Z On detecting maximal quasi antagonistic communities in signed graphs GAO, Ming LIM, Ee-Peng LO, David PRASETYO, Philips Kokoh 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. 2016-01-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/2858 info:doi/10.1007/s10618-015-0405-2 https://ink.library.smu.edu.sg/context/sis_research/article/3858/viewcontent/Detecting_maximal_quasi_antagonistic_communities_in_signed_graphs_afv.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Bi-clique Enumeration tree Power law distribution Quasi antagonistic community Signed graph Computer Sciences Databases and Information Systems Theory and Algorithms
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Bi-clique
Enumeration tree
Power law distribution
Quasi antagonistic community
Signed graph
Computer Sciences
Databases and Information Systems
Theory and Algorithms
spellingShingle Bi-clique
Enumeration tree
Power law distribution
Quasi antagonistic community
Signed graph
Computer Sciences
Databases and Information Systems
Theory and Algorithms
GAO, Ming
LIM, Ee-Peng
LO, David
PRASETYO, Philips Kokoh
On detecting maximal quasi antagonistic communities in signed graphs
description 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.
format text
author GAO, Ming
LIM, Ee-Peng
LO, David
PRASETYO, Philips Kokoh
author_facet GAO, Ming
LIM, Ee-Peng
LO, David
PRASETYO, Philips Kokoh
author_sort GAO, Ming
title On detecting maximal quasi antagonistic communities in signed graphs
title_short On detecting maximal quasi antagonistic communities in signed graphs
title_full On detecting maximal quasi antagonistic communities in signed graphs
title_fullStr On detecting maximal quasi antagonistic communities in signed graphs
title_full_unstemmed On detecting maximal quasi antagonistic communities in signed graphs
title_sort on detecting maximal quasi antagonistic communities in signed graphs
publisher Institutional Knowledge at Singapore Management University
publishDate 2016
url https://ink.library.smu.edu.sg/sis_research/2858
https://ink.library.smu.edu.sg/context/sis_research/article/3858/viewcontent/Detecting_maximal_quasi_antagonistic_communities_in_signed_graphs_afv.pdf
_version_ 1770572643235266560