基于圖正則化非負(fù)矩陣分解的二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)算法
doi: 10.11999/JEIT141649
-
解放軍信息工程大學(xué)信息系統(tǒng)工程學(xué)院 鄭州 450002
基金項目:
國家863計劃項目(2011AA013603)和國家重大科技專項(2013ZX 03006002)
Identifying Community in Bipartite Networks Using Graph Regularized-based Non-negative Matrix Factorization
-
摘要: 現(xiàn)實(shí)世界存在大量二分網(wǎng)絡(luò)，研究其社區(qū)結(jié)構(gòu)有助于從新角度認(rèn)識和理解異質(zhì)復(fù)雜網(wǎng)絡(luò)。非負(fù)矩陣分解模型能夠克服二分結(jié)構(gòu)的限制，有效地挖掘二分網(wǎng)絡(luò)的潛在結(jié)構(gòu)，但也存在著時間復(fù)雜度高、收斂慢等問題。該文提出一種基于圖正則化的三重非負(fù)矩陣分解(NMTF)算法應(yīng)用于二分網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)，通過圖正則化將用戶子空間和目標(biāo)子空間的內(nèi)部連接關(guān)系作為約束項引入到三重非負(fù)矩陣分解模型中；同時將NMTF分解為兩個最小化近似誤差的子問題，并給出了乘性迭代算法以交替更新因子矩陣，從而簡化矩陣分解迭代，加快收斂速度。實(shí)驗(yàn)和分析證明：對于計算機(jī)生成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)，該文提出的社區(qū)劃分方法均表現(xiàn)出較高的準(zhǔn)確率和穩(wěn)定性，能夠快速準(zhǔn)確地挖掘二分網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)。
-
關(guān)鍵詞:
- 二分網(wǎng)絡(luò) /
- 社區(qū)發(fā)現(xiàn) /
- 圖正則化 /
- 非負(fù)矩陣分解
Abstract: There are many bipartite networks composed of two types of nodes in the real world, studying the community structure of them is helpful to understand the complex network from a new point of view. Non- negative matrix factorization can overcome the limitation of the two-mode structure of bipartite networks, but it is also subject to several problems such as slow convergence and large computation. In this paper, a novel algorithm using graph regularized-based non-negative matrix factorization is presented for community detection in bipartite networks. It respectively introduces the internal connecting information of two-kinds of nodes into the Non- negative Matrix Tri-Factorization (NMTF) model as the graph regularizations. Moreover, this paper divides NMTF into two sub problems of minimizing the approximation error, and presents an alternative iterative algorithm to update the factor matrices, thus the iterations of matrix factorization can be simplified and accelerated. Through the experiments on both computer-generated and real-world networks, the results and analysis show that the proposed method has superior performances than the typical community algorithms in terms of the accuracy and stability, and can effectively discover the meaningful community structures in bipartite networks. -
全佳妮. 基于二分網(wǎng)絡(luò)的協(xié)同推薦研究[D]. [碩士論文], 蘇州大學(xué), 2012. Quan Jia-ni. Research on collaborative recommendation based on bipartite network[D]. [Master dissertation], Suzhou University, 2012. 熊湘云. 基于二分網(wǎng)絡(luò)的多維度推薦技術(shù)研究[D]. [碩士論文], 蘇州大學(xué), 2013. Xiong Xiang-yun. Research on multi-dimensional recommendation based on bipartite network[D]. [Master dissertation], Suzhou University, 2013. Liu X and Murata T. How does label propagation algorithm work in bipartite networks[C]. Proceedings of the IEEE International Joint Conference on Web Intelligence and Intelligent Agent Technology, Milano, Italy, 2009: 5-8. Barber M J. Modularity and community detection in bipartite networks[J]. Physical Review E, 2007, 76(6): 066102. Murata T. Detecting communities from bipartite networks based on bipartite modularities[C]. Proceedings of the Computational Science and Engineering, Vancouver, Canada, 2009, 4: 50-57. Suzuki K and Wakita K. Extracting multi-facet community structure from bipartite networks[C]. Proceedings of the Computational Science and Engineering, Vancouver, Canada, 2009, 4: 312-319. Roger Guimera, Marta Sales Pardo, Luis A, et al.. Module identification in bipartite and directed networks[J]. Physical Review E, 2007, 76(3): 036102. Tang L, Wang X, and Liu H. Community detection via heterogeneous interaction analysis[J]. Data Mining and Knowledge Discovery, 2012, 25(1): 1-33. Sun Y, Tang J, Han J, et al.. Community evolution detection in dynamic heterogeneous information networks[C]. Proceedings of the 8th Workshop on Mining and Learning with Graphs, Washington DC, USA, 2010: 137-146. Wang H, Nie F, Huang H, et al.. Nonnegative matrix tri- factorization based high-order co-clustering and its fast implementation[C]. Proceedings of 11th International Conference on Data Mining, Vancouver, Canada, 2011: 774-783. Nguyen N P, Dinh T N, Tokala S, et al.. Overlapping communities in dynamic networks: their detection and mobile applications[C]. Proceedings of the 17th Annual International Conference on Mobile Computing and Networking, Las Vegas, USA, 2011: 85-96. Zhang Z Y, Wang Y, and Ahn Y Y. Overlapping community detection in complex networks using symmetric binary matrix factorization[J]. Physical Review E, 2013, 87(6): 062803. Li Ping, Bu Jia-jun, Chen Chun, et al.. Relational multimanifold coclustering[J]. IEEE Transactions on Cybernetics, 2013, 43(6): 1871-1881. Cai D, He X, Han J, et al.. Graph regularization non-negative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560. Wang F, Li T, Wang X, et al.. Community discovery using nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery, 2011, 22(3): 493-521. Zhang Yu and Yeung Dit-Yan. Overlapping community detection via bounded nonnegative matrix tri-factorization [C]. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, 2012: 606-614. Shang Fan-hua, Jiao L C, and Wang Fei. Graph dual regularization non-negative matrix factorization for co- clustering[J]. Pattern Recognition, 2012, 45(6): 2237-2250. Scott J and Hughes M. The Anatomy of Scottish Capital: Scottish Companies and Scottish Capital[M]. London: Croom Helm, 1980: 291. Opsahl T. Triadic closure in two-mode networks: redefining the global and local clustering coefficients[J]. Social Networks, 2013, 35(2): 159-167. -
計量
- 文章訪問數(shù): 1062
- HTML全文瀏覽量: 91
- PDF下載量: 997
- 被引次數(shù): 0
下載:
