Scalable Community Discovery of Large Networks
Over the past decade, community structure, a statistical property of networked systems such as social network and world wide web, has attracted considerable attention in data mining field because it enables description and prediction of complex networks. Many highly sensitive graph clustering algorithms were developed for identification of communities having dense connections internally and loose connections with others. In this context, Newman and Girvan 1 proposed modularity Q score for quantifying the strength of community structure and measuring the fitness of a division. The Q function has become an important standard recently. In this paper, combining the strengths of the Q score and multilevel paradigm 2 first developed for graph partitioning, we introduced a scalable algorithm MOME (i.e. Modularity-based Multilevel Graph Clustering) to efficiently discover communities from a network. The experimental results indicated that MOME ran extremely faster and finally achieved a division with a slightly higher Q score against the latest modularity-based method and its variant 3, 4, particularly when the network was of a large-scale.
Zhemin Zhu Chen Wang Li Ma Yue Pan Zhiming Ding
National Engineering Research Center of Fundamental Software Institute of Software,Chinese Academy o IBM China Research Academy of Sciences,Beijing,China
国际会议
The Ninth International Conference on Web-Age Information Management(第九届web时代信息管理国际会议)(WAIM 2008)
张家界
英文
2008-07-20（万方平台首次上网日期，不代表论文的发表时间）