Abstract
Antagonistic communities refer to groups of people with opposite tastes, opinions, and factions within a community. Given a set of interactions among people in a community, we develop a novel pattern mining approach to mine a set of antagonistic communities. In particular, based on a set of user-specified thresholds, we extract a set of pairs of communities that behave in opposite ways with one another. We focus on extracting a compact lossless representation based on the concept of closed patterns to prevent exploding the number of mined antagonistic communities. We also present a variation of the algorithm using a divide and conquer strategy to handle large datasets when main memory is inadequate. The scalability of our approach is tested on synthetic datasets of various sizes mined using various parameters. Case studies on Amazon, Epinions, and Slashdot datasets further show the efficiency and the utility of our approach in extracting antagonistic communities from social interactions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agrawal R, Srikant R (1994) Fast algorithms for mining association rules. In: Proceedings of international conference on very large data bases
Albert R, Jeong H, Barabasi AL (1999) The diameter of the world wide web. Nature 401: 130–131
Bonacich P, Lloyd P (2004) Calculating status with negative relationships. Social Networks, pp 331–338
Cai D, Shao Z, He X, Yan X, Han J (2005) Community mining from multi-relational networks. In: Proceedings of European conference on principles and practice of knowledge discovery in databases
Cartwright D, Harary F (1956) Structural balance: a generalization of heider’s theory. Psychol Rev 63(5): 277–293
Dasgupta I (in press) ‘living’ wage, class conflict and ethnic strife. J Econ Behav Organ 2009
Dasgupta I, Kanbur R (2007) Community and class antagonism. J Public Econ 91(9): 1816–1842
Denrell J (2005) Why most people disapprove of me: experience sampling in impression formation. Psychol Rev 112(4): 951–978
Ding B, Lo D, Han J, Khoo S-C (2009) Efficient mining of closed repetitive gapped subsequences from a sequence database. In: Proceedings of the IEEE international conference on data engineering
Downloaded Epinions Dataset-Trustlet. http://www.trustlet.org/wiki/Downloaded_Epinions_dataset/ratings_data.txt.bz2
Easley D, Kleinberg J (2010) Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, Cambridge
Flake G, Lawrence S, Giles C, Coetzee F (2002) Self-organization and identification of web commu- nities. Computer 35(3): 66–71
Gibson D, Kleinberg J, Raghavan P (1998) Inferring web communities from link topology. In: Proceed- ings of ACM conference on Hypertext and hypermedia
Giles M, Evans A (1986) The power approach to intergroup hostility. J Confl Resolut 30(3): 469–486
Girvan M, Newman MEJ (2002) Community structure in social and biological networks. Proc Natl Acade Sci USA 99(12): 7821–7826
González AYR, Trinidad JFM, Carrasco-Ochoa JA, Ruiz-Shulcloper J (2011) Rp-miner: a relaxed prune algorithm for frequent similar pattern mining. Knowl Inf Syst 27(3): 451–471
Harary F (1953) On the notion of balance of a signed graph. Mich Math J 2(2): 143–146
Jia Y, Zhang J, Huan J (2011) An efficient graph-mining method for complicated and noisy data with real-world applications. Knowl Inf Syst 28(2): 423–447
Labovitz S, Hagedorn R (1975) A structural-behavioral theory of intergroup antagonism. Soc Forces 53(3): 444–448
Leicht EA, Newman MEJ (2008) Community structure in directed networks. Phys Rev Lett 100(11): 118703
Leskovec J, Huttenlocher D, Kleinberg J (2010) Predicting positive and negative links in online social networks. In: Proceedings of international conference on world wide web, pp 641–650
Li H-F, Huang H-Y, Lee S-Y (2011) Fast and memory efficient mining of high-utility itemsets from data streams: with and without negative item profits. Knowl Inf Syst 28(3): 495–522
Liu H, Lin Y, Han J (2011) Methods for mining frequent items in data streams: an overview. Knowl Inf Syst 26(1): 1–30
Lo D, Khoo S-C, Li J (2008) Mining and ranking generators of sequential patterns. In: Proceedings of SIAM international conference on data mining
Lo D, Khoo S-C, Liu C (2008) Efficient mining of recurrent rules from a sequence database. In: DASFAA, pp 67–83
Lo D, Surian D, Zhang K, Lim E-P (2011) Mining direct antagonistic communities in explicit trust networks. In: Proceedings of ACM international conference on information and knowledge management
McPerson M, Smith-Lovin L, Cook J (2001) Birds of a feather: Homophily in social networks. Annu Rev Sociol 27(3): 415–444
Moerchen F, Thies M, Ultsch A (2011) Efficient mining of all margin-closed itemsets with applications in temporal knowledge discovery and classification by compression. Knowl Inf Syst 29(1): 55–80
Newman MEJ (2004) Fast algorithm for detecting community structure in networks. Phys Rev E 69(6):066133-1–066133-5. doi:10.1103/PhysRevE.69.066133. http://link.aps.org/doi/10.1103/PhysRevE.69.066133
Pasquier N, Bastide Y, Taouil R, Lakhal L (1999) Discovering frequent closed itemsets for association rules. In: Proceedings of international conference on database theory, pp 398–416
Strogatz SH (2001) Exploring complex networks. Nature 410(6825): 268–276
Stanford large network dataset collection. http://snap.stanford.edu/data/
Tolsma J, Graaf ND, Quillian L (2009) Does intergenerational social mobility affect antagonistic attitudes toward ethnic minorities. British J Sociol 60(2): 257–277
Traag VA, Bruggeman J (2009) Community detection in networks with positive and negative links. Phys Rev E 80(3): 036115
Wang J, Han J (2004) BIDE: efficient mining of frequent closed sequences. In: Proceedings of the IEEE international conference on data engineering
White DR, Harary F (2001) The cohesiveness of blocks in social networks: node connectivity and conditional density. Sociol Methodol 31(1):305–359. http://www.blackwell-synergy.com/links/doi/10.1111%2F0081-1750.00098
Yan X, Han J (2002) Gspan: graph-based substructure pattern mining. In: Proceedings of IEEE international conference on data mining
Yang B, Cheung W, Liu J (2007) Community mining from signed social networks. IEEE Trans Knowl Data Eng 19(10): 1333–1348
Zaki MJ, Hsiao C-J (2002) Charm: an efficient algorithm for closed itemset mining. In: SDM
Zhang K, Lo D, Lim E-P (2010) Mining antagonistic communities from social networks. In: Proceedings of Pacific-Asia conference on knowledge discovery and data mining
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, K., Lo, D., Lim, EP. et al. Mining indirect antagonistic communities from social interactions. Knowl Inf Syst 35, 553–583 (2013). https://doi.org/10.1007/s10115-012-0519-4
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10115-012-0519-4