We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Link community detection by non-negative matrix factorization with multi-step similarities.
- Authors
Tang, Xianchao; Yang, Guoqing; Xu, Tao; Feng, Xia; Wang, Xiao; Li, Qiannan; Liu, Yanbei
- Abstract
Uncovering community structures is a fundamental and important problem in analyzing the complex networks. While most of the methods focus on identifying node communities, recent works show the intuitions and advantages of detecting link communities in networks. In this paper, we propose a non-negative matrix factorization (NMF) based method to detect the link community structures. Traditional NMF-based methods mainly consider the adjacency matrix as the representation of network topology, while the adjacency matrix only shows the relationship between immediate neighbor nodes, which does not take the relationship between non-neighbor nodes into consideration. This may greatly reduce the information contained in the network topology, and thus leads to unsatisfactory results. Here, we address this by introducing multi-step similarities using the graph random walk approach so that the similarities between non-neighbor nodes can be captured. Meanwhile, in order to reduce impact caused by self-similarities (similarities between nodes themselves) and increase importance gained from similarities between other different nodes, we add a penalty term to our objective function. Then an efficient optimization scheme for the objective function is derived. Finally, we test the proposed method on both synthetic and real networks. Experimental results demonstrate the effectiveness of the proposed approach.
- Subjects
NONNEGATIVE matrices; FACTORIZATION; RANDOM walks; MATHEMATICAL functions; ELECTRIC network topology; COMMUNITY organization
- Publication
Modern Physics Letters B, 2016, Vol 30, Issue 32/33, p-1
- ISSN
0217-9849
- Publication type
Article
- DOI
10.1142/S021798491650370X