Advertisement
Published in:
2010 | OriginalPaper | Chapter
Refining Graph Partitioning for Social Network Clustering
Authors : Tieyun Qian, Yang Yang, Shuo Wang
Published in: Web Information Systems Engineering – WISE 2010
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Graph partitioning is a traditional problem with many applications and a number of high-quality algorithms have been developed. Recently, demand for social network analysis arouses the new research interest on graph clustering. Social networks differ from conventional graphs in that they exhibit some key properties which are largely neglected in popular partitioning algorithms. In this paper, we propose a novel framework for finding clusters in real social networks. The framework consists of several key features. Firstly, we define a new metric which measures the small world strength between two vertices. Secondly, we design a strategy using this metric to greedily, yet effectively, refine existing partitioning algorithms for common objective functions. We conduct an extensive performance study. The empirical results clearly show that the proposed framework significantly improve the results of state-of-the-art methods.