TY - JOUR
T1 - Exploiting small world property for network clustering
AU - Qian, Tieyun
AU - Li, Qing
AU - Srivastava, Jaideep
AU - Peng, Zhiyong
AU - Yang, Yang
AU - Wang, Shuo
N1 - Publisher Copyright:
© 2013, Springer Science+Business Media New York.
PY - 2014/5/1
Y1 - 2014/5/1
N2 - 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 partitioning/clustering. Social networks differ from conventional graphs in that they exhibit some key properties like power-law and small-world property. Currently, these features are largely neglected in popular partitioning algorithms. In this paper, we present a novel framework which leverages the small-world property for finding clusters in social networks. The framework consists of several key features. Firstly, we define a total order, which combines the edge weight, the small-world weight, and the hub value, to better reflect the connection strength between two vertices. Secondly, we design a strategy using this ordered list, to greedily, yet effectively, refine existing partitioning algorithms for common objective functions. Thirdly, the proposed method is independent of the original approach, such that it could be integrated with any types of existing graph clustering algorithms. We conduct an extensive performance study on both real-life and synthetic datasets. The empirical results clearly demonstrate that our framework significantly improves the output of the state-of-the-art methods. Furthermore, we show that the proposed method returns clusters with both internal and external higher qualities.
AB - 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 partitioning/clustering. Social networks differ from conventional graphs in that they exhibit some key properties like power-law and small-world property. Currently, these features are largely neglected in popular partitioning algorithms. In this paper, we present a novel framework which leverages the small-world property for finding clusters in social networks. The framework consists of several key features. Firstly, we define a total order, which combines the edge weight, the small-world weight, and the hub value, to better reflect the connection strength between two vertices. Secondly, we design a strategy using this ordered list, to greedily, yet effectively, refine existing partitioning algorithms for common objective functions. Thirdly, the proposed method is independent of the original approach, such that it could be integrated with any types of existing graph clustering algorithms. We conduct an extensive performance study on both real-life and synthetic datasets. The empirical results clearly demonstrate that our framework significantly improves the output of the state-of-the-art methods. Furthermore, we show that the proposed method returns clusters with both internal and external higher qualities.
KW - graph partitioning
KW - network clustering
KW - small world property
UR - http://www.scopus.com/inward/record.url?scp=84919666068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84919666068&partnerID=8YFLogxK
U2 - 10.1007/s11280-013-0209-5
DO - 10.1007/s11280-013-0209-5
M3 - Article
AN - SCOPUS:84919666068
SN - 1386-145X
VL - 17
SP - 405
EP - 425
JO - World Wide Web
JF - World Wide Web
IS - 3
ER -