Article: Overlapping communities in social networks Journal: International Journal of Social Computing and Cyber-Physical Systems (IJSCCPS) 2011 Vol.1 No.2 pp.135 - 159 Abstract: Traditionally, methods to identify community structure in networks have focused on partitioning the vertex set into a number of disjoint groups. However, recently proposed methods have included mechanisms to account for possible overlap between communities. These approaches have taken a wide variety of forms, resulting in a lack of consensus as to what characteristics overlapping communities should have. Additionally, the application of algorithms which account for community overlap are often justified via intuitive rather than empirical arguments. In this text, each of the issues mentioned above is examined. From previous literature, a minimal set of axioms which overlapping communities should satisfy is presented. Additionally, a modification of a previously published algorithm, iterative scan, is introduced to ensure that these properties are met. Finally, the overlap between communities discovered in a large, real world communication network is examined. The analysis offers empirical justification that the application of overlapping community detection methods capture relationships which cannot be identified via traditional disjoint methods. Inderscience Publishers - linking academia, business and industry through research

Title: Overlapping communities in social networks

Authors: Stephen Kelley; Mark K. Goldberg; Konstantin Mertsalov; Malik Magdon-Ismail; William Wallace

Addresses: Oak Ridge National Laboratory, 1 Bethel Valley Road, Oak Ridge, TN 37831, USA. ' Department of Computer Science, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA. ' IPMKS, Svobodi 3, Tula, Russia. ' Department of Computer Science, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA. ' Department of Industrial and Systems Engineering, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY 12180, USA

Abstract: Traditionally, methods to identify community structure in networks have focused on partitioning the vertex set into a number of disjoint groups. However, recently proposed methods have included mechanisms to account for possible overlap between communities. These approaches have taken a wide variety of forms, resulting in a lack of consensus as to what characteristics overlapping communities should have. Additionally, the application of algorithms which account for community overlap are often justified via intuitive rather than empirical arguments. In this text, each of the issues mentioned above is examined. From previous literature, a minimal set of axioms which overlapping communities should satisfy is presented. Additionally, a modification of a previously published algorithm, iterative scan, is introduced to ensure that these properties are met. Finally, the overlap between communities discovered in a large, real world communication network is examined. The analysis offers empirical justification that the application of overlapping community detection methods capture relationships which cannot be identified via traditional disjoint methods.

Keywords: community detection; social network analysis; overlapping groups; social networks; community structure; relationships.

DOI: 10.1504/IJSCCPS.2011.044171

International Journal of Social Computing and Cyber-Physical Systems, 2011 Vol.1 No.2, pp.135 - 159

Published online: 21 Feb 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article

Title: Overlapping communities in social networks

Keep up-to-date