Semi-supervised clustering algorithm for community structure detection in complex networks

被引:112
作者
Ma, Xiaoke [1 ]
Gao, Lin [1 ]
Yong, Xuerong [2 ]
Fu, Lidong [1 ]
机构
[1] Xidian Univ, Sch Comp Sci & Technol, Xian 710071, Shaanxi, Peoples R China
[2] Univ Puerto Rico, Dept Math Sci, Mayaguez, PR 00681 USA
关键词
Semi-supervised clustering; Complex networks; Community structure; Nonnegative matrix factorization; MODULARITY;
D O I
10.1016/j.physa.2009.09.018
中图分类号
O4 [物理学];
学科分类号
070305 [高分子化学与物理];
摘要
Discovering a community structure is fundamental for uncovering the links between structure and function in complex networks In this paper, we discuss an equivalence of the objective functions of the symmetric nonnegative matrix factorization (SNMF) and the maximum optimization of modularity density. Based on this equivalence. we develop a new algorithm. named the so-called SNMF-SS, by combining SNMF and a semi-supervised clustering approach, Previous NMF-based algorithms often suffer from the restriction of measuring network topology from only one perspective, but our algorithm uses a semi-supervised mechanism to get rid of the restriction. The algorithm is illustrated and compared with spectral clustering and NMF by using artificial examples and other classic real world networks. Experimental results show the significance of the proposed approach. particularly, in the cases when Community structure is obscure. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码:187 / 197
页数:11
相关论文
共 35 条
[1]
BERRY JW, 2009, 09031072 ARXIV, P61901
[2]
On modularity clustering [J].
Brandes, Ulrik ;
Delling, Daniel ;
Gaertler, Marco ;
Goerke, Robert ;
Hoefer, Martin ;
Nikoloski, Zoran ;
Wagner, Dorothea .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2008, 20 (02) :172-188
[3]
Cristianini Nello, 2000, An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, DOI DOI 10.1017/CB09780511801389
[4]
Comparing community structure identification -: art. no. P09008 [J].
Danon, L ;
Díaz-Guilera, A ;
Duch, J ;
Arenas, A .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2005, :219-228
[5]
Ding C, 2005, SIAM PROC S, P606
[6]
Community detection in complex networks using extremal optimization [J].
Duch, J ;
Arenas, A .
PHYSICAL REVIEW E, 2005, 72 (02)
[7]
Resolution limit in community detection [J].
Fortunato, Santo ;
Barthelemy, Marc .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (01) :36-41
[8]
Gibson D., 1998, Hypertext 98: Ninth ACM Conference on Hypertext and Hypermedia, P225, DOI 10.1145/276627.276652
[9]
Community structure in social and biological networks [J].
Girvan, M ;
Newman, MEJ .
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (12) :7821-7826
[10]
Comparison and validation of community structures in complex networks [J].
Gustafsson, Mika ;
Hornquist, Michael ;
Lombardi, Anna .
PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2006, 367 :559-576