Weight-Discounted Symmetrization in Clustering Directed Graphs

Abstract:

An increasing attention has been recently devoted to uncovering community structure in directed graphs which widely exist in real-world complex networks such as social networks, citation networks, World Wide Web, email networks, etc. A two-stage framework for detecting clusters is an effective way for clustering directed graphs while the first stage is to symmetrize the directed graph using some similarity measures. Any state-of-the-art clustering algorithms for undirected graphs can be leveraged in the second stage. Hence, both stages are important to the effectiveness of the clustering result. However, existing symmetrization methods only consider about the direction of edges but ignore the weights of nodes. In this paper, we first attempt to connect link analysis in directed graph clustering. This connection not only takes into consideration the directionality of edges but also uses node ranking scores such as authority and hub score to explicitly capture in-link and out-link similarity. We also demonstrate the generality of our proposed method by showing that existing state-of-the-art symmetrization methods can be derived from our method. Empirical validation shows that our method can find communities effectively in real world networks.

• Periodical: Advanced Materials Research (Volumes 756-759)
• Pages: 2979-2987
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.756-759.2979
• Online since: September 2013
• Authors: Bin He, Hui Liu, Xiang Hui Zhao, Ze Feng Li
• Keywords: Clustering, Community Detection, Directed Graph, Graph Transformations

References

[1] Y. Kim, S. -W. Son, and H. Jeong, LinkRank: finding communities in directed networks, Phys. Rev. E, Vol. 81, 016103, (2010).

[2] V. Satuluri and S. Parthasarathy, Symmetrizations for clustering directed graphs, In Proceedings of EDBT, 2011, pp.343-354.

[3] M. Meila and W. Pentney, Clustering by weighted cuts in directed graphs, Proc. of the 7th SIAM International Conference on Data Mining, 2007, p.135–144.

DOI: 10.1137/1.9781611972771.13

[4] E. A. Leicht and M. E. J. Newman, Community structure in directed networks, Physical Review Letters, Vol. 100, 118703, (2008).

[5] S.E. Schaeffer, Graph clustering, Computer Science Review, Vol. 1, 2007, p.27–64.

[6] T. Yang, Y. Chi, S. Zhu, Y. Gong, R. Jin, Directed network community detection: A popularity and productivity link model, SIAM International Conference on Data Mining, 2010, p.742–753.

DOI: 10.1137/1.9781611972801.65

[7] U. von Luxburg, A tutorial on spectral clustering, Statistics and Computing, Vol. 17, p.395–416, (2006).

DOI: 10.1007/s11222-007-9033-z

[8] M. E. J. Newman, M. Girvan, Finding and evaluating community structure in networks, Physical Review E, Vol. 70, 066111, (2004).

[9] J. Shi and J. Malik, Normalized cuts and image segmentation, IEEE Conference on Computer Vision and Pattern Recognition, 1997, p.731–737.

DOI: 10.1109/cvpr.1997.609407