›› 2012, Vol. ›› Issue (2): 341-357.doi: 10.1007/s11390-012-1227-y

• Machine Learning and Data Mining • Previous Articles     Next Articles

A Dimensionality Reduction Framework for Detection of Multiscale Structure in Heterogeneous Networks

Hua-Wei Shen1 (沈华伟), Member, CCF, Xue-Qi Cheng1 (程学旗), Senior Member, CCF, Member, IEEE, Yuan-Zhuo Wang1 (王元卓), Senior Member, CCF, Member, ACM, IEEE, and Yixin Chen2 (陈一昕), Senior Member, IEEE   

  1. 1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;
    2. Computer Science Department, Washington University in St Louis, MO 63130, U.S.A.
  • Received:2011-09-04 Revised:2011-11-21 Online:2012-03-05 Published:2012-03-05
  • Supported by:

    This work was funded by the National Natural Science Foundation of China under Grant Nos. 60873245, 60933005, 60873243, 60903139 and 60803123. This work was also partly funded by the National High Technology Research and Development 863 Program of China under Grant No. 2010AA012503, and the Beijing Natural Science Foundation under Grant No. 4122077.

Graph clustering has been widely applied in exploring regularities emerging in relational data. Recently, the rapid development of network theory correlates graph clustering with the detection of community structure, a common and important topological characteristic of networks. Most existing methods investigate the community structure at a single topological scale. However, as shown by empirical studies, the community structure of real world networks often exhibits multiple topological descriptions, corresponding to the clustering at different resolutions. Furthermore, the detection of multiscale community structure is heavily affected by the heterogeneous distribution of node degree. It is very challenging to detect multiscale community structure in heterogeneous networks. In this paper, we propose a novel, unified framework for detecting community structure from the perspective of dimensionality reduction. Based on the framework, we first prove that the well-known Laplacian matrix for network partition and the widely-used modularity matrix for community detection are two kinds of covariance matrices used in dimensionality reduction. We then propose a novel method to detect communities at multiple topological scales within our framework. We further show that existing algorithms fail to deal with heterogeneous node degrees. We develop a novel method to handle heterogeneity of networks by introducing a rescaling transformation into the covariance matrices in our framework. Extensive tests on real world and artificial networks demonstrate that the proposed correlation matrices significantly outperform Laplacian and modularity matrices in terms of their ability to identify multiscale community structure in heterogeneous networks.

[1] Newman M E J. The structure and function of complex net-works. SIAM Rev., 2003, 45(2): 167-256.

[2] Boccaletti S, Latora V, Moreno Y, Chavez M, Hwang D U.Complex networks: Structure and dynamics. Phys. Rep.,2006, 424: 175-308.

[3] Flake G W, Lawrence S, Giles C L, Coetzee F M. Self-organization and identification of Web communities. Com-puter, 2002, 35(3): 66-71.

[4] Cheng X Q, Ren F X, Zhou S, Hu M B. Triangular clusteringin document networks. New J. Phys., 2009, 11(3): 033019.

[5] Cheng X Q, Ren F X, Shen H W, Zhang Z K, Zhou T. Bridge-ness: A local index on edge significance in maintaining globalconnectivity. J. Stat. Mech., 2010, P10011.

[6] Guimer?a R, Amaral L A N. Functional cartography of com-plex metabolic networks. Nature, 2005, 433: 895-900.

[7] Girvan M, Newman M E J. Community structure in socialand biological networks. Proc. Natl. Acad. Sci. U.S.A.,2002, 99(12): 7821-7826.

[8] Arenas A, D??az-Guilera A, P?erez-Vicente C J. Synchroniza-tion reveals topological scales in complex networks. Phys.Rev. Lett., 2006, 96(11): 114102.

[9] Lambiotte R, Delvenne J C, Barahona M. Laplacian dynamicsand multiscale modular structure in networks. e-print arXiv:0812.1770, 2008.

[10] Cheng X Q, Shen H W. Uncovering the community structureassociated with the diffusion dynamics on networks. J. Stat.Mech., 2010, P04024.

[11] Newman M E J, Girvan M. Finding and evaluating com-munity structure in networks. Phys. Rev. E, 2004, 69(2):026113.

[12] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D.Defining and identifying communities in networks. Proc.Natl. Acad. Sci. U.S.A., 2004, 101(9): 2658-2663.

[13] Palla G, Der?enyi I, Farkas I, Vicsek T. Uncovering the over-lapping community structure of complex networks in natureand society. Nature, 2005, 435: 814-818.

[14] Duch J, Arenas A. Community detection in complex networksusing extremal optimization. Phys. Rev. E, 2005, 72(2):027104.

[15] Newman M E J. Modularity and community structure in net-works. Proc. Natl. Acad. Sci. U.S.A., 2006, 103(23): 8577-8582.

[16] Newman M E J. Finding community structure in networks us-ing the eigenvectors of matrices. Phys. Rev. E, 2006, 74(3):036104.

[17] Yang B, Cheung W K, Liu J M. Community mining fromsigned social networks. IEEE Trans. Knowl. Data Eng., 2007, 19(10): 1333-1348.

[18] Rosvall M, Bergstrom C T. Maps of random walks on com-plex networks reveal community structure. Proc. Natl. Acad.Sci. U.S.A., 2008, 105(4): 1118-1123.

[19] Bagrow J P. Evaluating local community methods in net-works. J. Stat. Mech., 2008, P05001.

[20] Leskovec J, Lang K J, Dasgupta A, Mahoney M W. Statisticalproperties of community structure in large social and infor-mation networks. In Proc. the 17th Int. Conf. World WideWeb, April 2008, pp.695-704.

[21] Shen H W, Cheng X Q, Cai K, Hu M B. Detect overlappingand hierarchical community structure in networks. PhysicaA, 2009, 388(8): 1706-1712.

[22] Shen H W, Cheng X Q, Guo J F. Quantifying and identifyingthe overlapping community structure in networks. J. Stat.Mech., 2009, P07042.

[23] Shen H W, Cheng X Q. Spectral methods for the detectionof network community structure: A comparative analysis. J.Stat. Mech., 2010, P10020.

[24] Chen D B, Shang M S, Lv Z H, Fu Y. Detecting overlap-ping communities of weighted networks via a local algorithm.Physica A, 2010, 389(19): 4177-4187.

[25] Shen H W, Cheng X Q, Guo J F. Exploring the structralregularities in networks. Phys. Rev. E, 2011, 84(5): 056111.

[26] Danon L, D??az-Guilera A, Duch J, Arenas A. Comparing com-munity structure identification. J. Stat. Mech., 2005, P09008.

[27] Fortunato S. Community detection in graphs. Phys. Rep.,2010, 486(3-5): 75-174.

[28] Leskovec J, Lang K J, Mahoney M W. Empirical comparisonof algorithms for network community detection. In Proc. the19th Int. Conf. World Wide Web, April 2010, pp.631-640.

[29] Fortunato S, Barth?elemy M. Resolution limit in communitydetection. Proc. Natl. Acad. Sci. U.S.A., 2007, 104(1):36-41.

[30] Arenas A, Fernández A, G?omez S. Analysis of the structure ofcomplex networks at different resolution levels. New J. Phys.,2008, 10(5): 053039.

[31] Ronhovde P, Nussinov Z. Multiresolution community detec-tion for megascale networks by information-based replica cor-relations. Phys. Rev. E, 2009, 80(1): 016109.

[32] Delvenne J C, Yaliraki S N, Barahona M. Stability of graphcommunities across time scales. Proc. Natl. Acad. Sci.U.S.A., 2010, 107(29): 12755-12760.

[33] Mucha P J, Richardson T, Macon K, Porter M A, Onnela JP. Community structure in time-dependent, multiscale, andmultiplex networks. Science, 2010, 328(5980): 876-878.

[34] Ahn Y Y, Bagrow J P, Lehmann S. Link communities revealmultiscale complexity in networks. Nature, 2010, 466: 761-764.

[35] Arenas A, Borge-Holthoefer J, G?omez S, Zamora-L?opez G.Optimal map of the modular structure of complex networks.New J. Phys., 2010, 12(5): 053009.

[36] Shen H W, Cheng X Q, Fang B X. Covariance, correlationmatrix, and the multiscale community structure of networks.Phys. Rev. E, 2010, 82(1): 016114.

[37] Jolliffe I T. Principal Component Analysis. 2nd edition,Springer, NY, 2002.

[38] von Luxburg U. A tutorial on spectral clustering. Stat. Com-put., 2007, 17(4): 395-416.

[39] Fiedler M. Property of eigenvectors of nonnegative symmetricmatrices and its application to graph theory. Czech. Math.J., 1975, 25(4): 619-633.

[40] Chung F R K. Spectral Graph Theory. Amer. Math. Soc.,1997.

[41] Shi J, Malik J. Normalized cuts and image segmentation.IEEE Trans. Pattern Anal. Mach. Intell., 2000, 8(8): 888-905.

[42] Ding C H Q, He X, Zha H, Gu M, Simon H D. A Min-maxcut algorithm for graph partitioning and data clustering. InProc. IEEE Int. Conf. Data Mining, Nov.29-Dec.2, 2001,pp.107-114.

[43] Scott J. Social Network Analysis: A Handbook, 2nd edition.Sage Publications, 2000.

[44] Brandes U, Delling D, Gaertler M, G?orke R, Hoefer M,Nikoloski Z, Wagner D. On modularity clustering. IEEETrans. Knowl. Data Eng., 2008, 30(2): 172-188.

[45] Newman M E J. Fast algorithm for detecting communitystructure in networks. Phys. Rev. E, 2004, 69(6): 066133.

[46] Blondel V D, Guillaume J L, Lambiotte R, Lefebvre E. Fastunfolding of communities in large networks. J. Stat. Mech.,2008, 10: P10008.

[47] Agarwal G, Kempe D. Modularity-maximizing graph com-munities via mathematical programming. Eur. Phys. J. B,2008, 66(3): 409-418.

[48] Zachary W W. An information flow model for conflict and fis-sion in small groups. J. Anthropol. Res., 1977, 33: 452-473.

[49] Newman M E J. Assortative mixing in networks. Phys. Rev.Lett., 2002, 89(20): 208701.

[50] Chauhan S, Girvan M, Ott E. Spectral properties of net-works with community structure. Phys. Rev. E, 2009, 80(5):056114.

[51] Capocci C, Servedio V D P, Caldarelli G, Colaiori F. Detect-ing communities in large networks. Physica A, 2005, 352(2-4):669-676.

[52] Lancichinetti A, Fortunato S, Radicchi F. Benchmark graphsfor testing community detection algorithms. Phys. Rev. E,2008, 78(4): 046110.

[53] Rosvall M, Bergstrom C T. An information-theoretic frame-work for resolving community structure in complex networks.Proc. Natl. Acad. Sci. U.S.A., 2007, 104(18): 7327-7331.

[54] Muff S, Rao F, Caflisch A. Local modularity measure for net-work clusterizations. Phys. Rev. E, 2005, 72(5): 056107.

[55] Gleiser P, Danon L. Community structure in jazz. Adv. Com-plex Syst., 2003, 6(4): 565-573.

[56] Guimer?a R, Danon L, D??az-Guilera A, Giralt F, Arenas A.Self-similar community structure in a network of human in-teractions. Phys. Rev. E, 2003, 68(6): 065103.
No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] Andrew I. Adamatzky;. Identification of Nonstationary Cellular Automata[J]. , 1992, 7(4): 379 -382 .
[2] Xu Dianxiang; Zheng Guoliang;. Towards a Declarative Semantics of Inheritance with Exceptions[J]. , 1996, 11(1): 61 -71 .
[3] Ju Jiubin; Wang Yong; Yin Yu;. Scheduling PVM Tasks[J]. , 1997, 12(2): 167 -176 .
[4] Chen Yangjun;. Counting and Topological Order[J]. , 1997, 12(6): 497 -509 .
[5] Hu Weiwu; Xia Peisu;. Out-of-Order Execution in Sequentially Consistent Shared-Memory Systems:Theory and Experiments[J]. , 1998, 13(2): 125 -140 .
[6] PENG wei; LU Xicheng;. An Approach to Support IP Multicasting in Networks with Mobile Hosts[J]. , 1999, 14(6): 529 -538 .
[7] Hai Zhuge and Xiang-Feng Luo. Knowledge Map: Mathematical Model and Dynamic Behaviors[J]. , 2005, 20(3): 289 -295 .
[8] Yang-Li Wang and Cheng-Ke Wu. Complete Multiple Description Mesh-Based Video Coding Scheme and Its Performance[J]. , 2005, 20(3): 426 -431 .
[9] Katerina Asdre and Stavros D. Nikolopoulos. P-Tree Structures and Event Horizon: Efficient Event-Set Implementations[J]. , 2006, 21(1): 19 -26 .
[10] Yan-Li Liu, Jin Wang, Xi Chen, Yan-Wen Guo, and Qun-Sheng Peng. A Robust and Fast Non-Local Means Algorithm for Image Denoising[J]. , 2008, 23(2): 270 -279 .

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved