Title

Mining Direct Antagonistic Communities in Signed Social Networks

Publication Type

Journal Article

Publication Date

2013

Abstract

Social networks provide a wealth of data to study relationship dynamics among people. Most social networks such as Epinions and Facebook allow users to declare trusts or friendships with other users. Some of them also allow users to declare distrusts or negative relationships. When both positive and negative links co-exist in a network, some interesting community structures can be studied. In this work, we mine Direct Antagonistic Communities (DACs) within such signed networks. Each DAC consists of two sub-communities with positive relationships among members of each sub-community, and negative relationships among members of the other sub-community. Identifying direct antagonistic communities is an important step to understand the nature of the formation, dissolution, and evolution of such communities. Knowledge about antagonistic communities allows us to better understand and explain behaviors of users in the communities. Identifying DACs from a large signed network is however challenging as various combinations of user sets, which is very large in number, need to be checked. We propose an efficient data mining solution that leverages the properties of DACs, and combines the identification of strongest connected components and bi-clique mining. We have experimented our approach on synthetic, myGamma, and Epinions datasets to showcase the efficiency and utility of our proposed approach. We show that we can mine DACs in less than 15 min from a signed network of myGamma, which is a mobile social networking site, consisting of 600,000 members and 8 million links. An investigation on the behavior of users participating in DACs shows that antagonism significantly affects the way people behave and interact with one another.

Keywords

Direct antagonistic community, Mining maximal bi-cliques, Signed social network

Discipline

Software Engineering

Research Areas

Software Systems

Publication

Information Processing and Management

Volume

49

Issue

4

First Page

773–791

Last Page

791

ISSN

0306-4573

Identifier

10.1016/j.ipm.2012.12.009

Publisher

Elsevier

Additional URL

http://dx.doi.org/10.1016/j.ipm.2012.12.009