Journal Article

Finding a Friendly Community in Social Networks Considering Bad Relationships

Sang-Yeon Kim, Dong-Wan Choi and Chin-Wan Chung

in The Computer Journal

Volume 58, issue 6, pages 1469-1481
Published in print June 2015 | ISSN: 0010-4620
Published online September 2014 | e-ISSN: 1460-2067 | DOI: https://dx.doi.org/10.1093/comjnl/bxu092

Show Summary Details

Preview

Community detection in social networks is one of the most active problems with lots of applications. Most of the existing works on the problem have focused on detecting the community considering only the closeness between community members. In the real world, however, it is also important to consider bad relationships between members. In this paper, we propose a new variant of the community detection problem, called friendly community search. In the proposed problem, for a given graph, we aim to not only find a densely connected subgraph that contains a given set of query nodes but also minimizes the number of nodes involved in bad relationships in the subgraph. We prove that is Non-deterministic Polynomial-time hard (NP-hard), and develop two novel algorithms, called Greedy and SteinerSwap that return the near optimal solutions. Experimental results show that two proposed algorithms outperform the algorithm adapted from an existing algorithm for the optimal quasi-clique problem.

Keywords: community detection; social network; graph algorithm

Journal Article.  0 words. 

Subjects: Computer Science