Discovering overlapping communities more easily and precisely from social networks

KAIST researchers developed a novel framework for overlapping community detection in social networks as well as an algorithm based on the framework.

Article  |  Fall 2014

The advent of online social networks has been one of the most exciting events in this decade. Numerous online social networks such as Twitter, Facebook, and LinkedIn have become increasingly popular. A social network is typically modeled as a graph, where a vertex represents a user and an edge represents a relationship between users. Community detection is an analytical method for finding the sets of users closely related with each other and has been extensively studied by many researchers.

Prof. Lee’s team advanced this field by proposing a novel framework for overlapping community detection. This research result was published at the IEEE ICDE 2014 conference, which is the premiere conference on data engineering [1].

A strong point of the framework is the capability of dealing with “overlapping” communities. In overlapping community detection, a user can belong to multiple communities; on the other hand, in disjointed community detection, a user can belong to at most one community. Overlapping community detection is considered to fit better in the real world than disjointed community detection because there are many instances of overlapping communities. For example, a user belongs to a community with his/her classmates and at the same time to another community with his/her work colleagues. However, supporting the overlap of communities has made community detection algorithms much more complicated than ever before.

Prof. Lee’s team suggested a simple yet effective strategy to remove this complication, proposing the link-space transformation. It systematically converts an original graph into a link-space graph, which is another representation of the original graph in a different space. The benefits of the transformation are two-fold. First, finding “disjointed” communities in the link-space graph is equivalent to finding “overlapping” communities in the original graph. Second, the original structure is preserved well in the link-space graph because similarity properly reflects the structure of the original graph. Thus, there is no reason to be bothered with the overlap of communities anymore. Any conventional algorithms for disjointed community detection can be applied to overlapping community detection once the original graph is transformed to the link-space graph. Moreover, Prof. Lee’s team designed a community detection algorithm LinkSCAN* that takes advantage of the link-space transformation. Through extensive experiments, LinkSCAN* is shown to produce more accurate results (by up to 200%), especially for graphs with many highly overlapping vertices and those with various internal structures, than the state-of-the-art community detection algorithms.

[1] Lim, S., Ryu, S., Kwon, S., Jung, K., and Lee, J., “LinkSCAN*: Overlapping Community Detection Using the Link-Space Transformation,” In Proc. 30th Int’l Conf. on Data Engineering (IEEE ICDE), Chicago, Illinois, pp. 292~303, Apr. 2014.