基于稀疏子空间聚类的多层网络社团检测

doi:10.19678/j.issn.1000-3428.0059629

摘要/Abstract

摘要： 现有的子空间聚类方法大多只适用于单层网络，或者仅对多层网络中每层的聚类结果简单地进行平均，未考虑每层网络中包含信息量不同的特点，致使聚类性能受限。针对该问题，提出一种面向多层网络的稀疏子空间聚类方法。将距离正则项和非负约束条件集成到稀疏子空间聚类框架中，从而在聚类时能够同时利用数据的全局信息和局部信息进行图学习。此外，通过引入稀疏约束使学习到的图具有更清晰的聚类结构，并设计迭代算法进行优化求解。在多个真实数据集上的实验结果表明，该方法能够挖掘网络不同层的互补信息，得到准确的一致性联合稀疏表示，有效提高社团聚类性能。

关键词: 高维数据, 子空间聚类, 稀疏表示, 社团检测, 复杂网络

Abstract: The existing subspace clustering methods are only applicable to single-layer networks, or just average the clustering results of each layer in the multi-layer network.They fail to consider the different amounts of information contained in each layer, which causes a reduction in the subspace clustering performance.To address the problem, a sparse subspace clustering method for multi-layer networks is proposed.Firstly, a distance regularization term and a non-negative constraint are jointly integrated into the framework of sparse subspace clustering, which enables the method to simultaneously exploit the global and local information of data for graph learning during clustering.In addition, the sparse constraint is introduced to provide the learned graph with a clear clustering structure, and an iterative algorithm is designed to optimize the solution.Experimental results on multiple real datasets show that the proposed method can mine the complementary information of different layers of the network, obtain an accurate consistent joint sparse representation, and effectively improve the community clustering performance of multi-layer networks.

Key words: high-dimensional data, subspace clustering, sparse representation, community detection, complex network

中图分类号:

TP18

孙登第, 凌媛, 丁转莲, 罗斌. 基于稀疏子空间聚类的多层网络社团检测[J]. 计算机工程, 2021, 47(10): 52-60.

SUN Dengdi, LING Yuan, DING Zhuanlian, LUO Bin. Multi-Layer Network Community Detection Based on Sparse Subspace Clustering[J]. Computer Engineering, 2021, 47(10): 52-60.

http://www.ecice06.com/CN/Y2021/V47/I10/52

图/表 9

20211015190223

20211015190226

20211015190229

20211015190233

20211015190236

20211015190239

20211015190243

20211015190247

20211015190250

参考文献

[1] AGRAWAL R, GEHRKE J, GUNOPULOS D, et al.Automatic subspace clustering of high dimensional data[J].Data Mining and Knowledge Discovery, 2005, 11(1):5-33.
[2] LU L, VIDAL R.Combined central and subspace clustering for computer vision applications[C]//Proceedings of the 23rd International Conference on Machine Learning.New York, USA:ACM Press, 2006:593-600.
[3] HONG W, WRIGHT J, HUANG K, et al.Multiscale hybrid linear models for lossy image representation[J].IEEE Transactions on Image Processing, 2006, 15(12):3655-3671.
[4] YANG A Y, WRIGHT J, MA Y, et al.Unsupervised segmentation of natural images via lossy data compression[J].Computer Vision and Image Understanding, 2008, 110(2):212-225.
[5] 刘宇廷, 毕海滨, 郭强, 等.基于网络拓扑与节点元数据的社团检测算法[J].计算机工程, 2018, 44(11):178-183. LIU Y T, BI H B, GUO Q, et al.Community detection algorithm based on network topology and node metadata[J].Computer Engineering, 2018, 44(11):178-183.(in Chinese)
[6] 彭焱, 溪利亚.局部优先的动态网络重叠社团及其演变模式检测[J].计算机工程, 2016, 42(12):188-195, 203. PENG Y, XI L Y.Local-first detection of overlapping community and its evolution pattern in dynamic networks[J].Computer Engineering, 2016, 42(12):188-195, 203.(in Chinese)
[7] 蒋盛益, 吴美玲, 杨博泓.基于网络社团检测的电信客户细分[J].计算机工程, 2014, 40(7):312-316. JIANG S Y, WU M L, YANG B H.Telecom customer segmentation based on network community detection[J].Computer Engineering, 2014, 40(7):312-316.(in Chinese)
[8] 尹欣红, 赵世燕, 陈晓云.带偏置的信号传播的随机游走的社团检测算法[J].计算机科学, 2019, 46(12):45-55. YIN X H, ZHAO S Y, CHEN X Y.Random walk community detection algorithm with biased signal propagation[J].Computer Science, 2019, 46(12):45-55.(in Chinese)
[9] DOMENICO M, SOLÉ-RIBALTA A, COZZO E, et al.Mathematical formulation of multi-layer networks[J].Physical Review X, 2014, 3(4):4192-4195.
[10] 贾郑磊, 谷林, 高智勇, 等.基于节点相似性的加权复杂网络BGLL社团检测方法[J].计算机系统应用, 2019, 28(2):201-206. JIA Z L, GU L, GAO Z Y, et al.Weighted complex network BGLL community detection method based on node similarity[J].Computer System Applications, 2019, 28(2):201-206.(in Chinese)
[11] 刘迪洋, 张震, 张进.基于社区结构的复杂网络鲁棒性优化策略[J].计算机工程, 2021, 47(8):84-92. LIU D Y, ZHANG Z, ZHANG J.Robust optimization strategy for complex networks based on community structure[J].Computer Engineering, 2021, 47(8):84-92.(in Chinese)
[12] ELHAMIFAR E, VIDAL R.Sparse subspace clustering:algorithm, theory, and applications[J].IEEE Transactions on Pattern Analysis & Machine Intelligence, 2013, 35(11):2765-2781.
[13] LIU G, LIN Z, YU Y.Robust subspace segmentation by low-rank representation[C]//Proceedings of International Conference on Machine Learning.New York, USA:ACM Press, 2010:663-670.
[14] FANG X Z, HAN N, WU J G, et al.Approximate low-rank projection learning for feature extraction[J].IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(11):5228-5241.
[15] WANG Q, HE X, LI X D.Locality and structure regularized low rank representation for hyperspectral image classification[J].IEEE Transactions on Geoscience and Remote Sensing, 2018, 57(2):911-923.
[16] 陶洋, 鲍灵浪, 胡昊.结构约束的对称低秩表示子空间聚类方法[J].计算机工程, 2021, 47(4):56-61, 67. TAO Y, BAO L L, HU H.Structure-constrained symmetric low-rank representation subspace clustering method[J].Computer Engineering, 2021, 47(4):56-61, 67.(in Chinese)
[17] BOYD S, PARIKH N, CHU E, et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends in Machine Learning, 2011, 3(1):1-122.
[18] ZHANG S, ZHAO H, NG M K.Functional module analysis for Gene coexpression networks with network integration[J].IEEE/ACM Transactions on Computational Biology & Bioinformatics, 2015, 12(5):1146-1160.
[19] YAN S, WANG H.Semi-supervised learning by sparse representation[C]//Proceedings of 2009 SIAM International Conference on Data Mining.[S.l.]:DBLP, 2009:1-5.
[20] GUO X.Robust subspace segmentation by simultaneously learning data representations and their affinity matrix[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence.Washington D.C., USA:IEEE Press, 2015:1-5.
[21] XU Y, YIN W.A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion[J].SIAM Journal on Imaging Sciences, 2015, 6(3):1758-1789.
[22] MAHMOOD A, SMALL M.Subspace based network community detection using sparse linear coding[J].IEEE Transactions on Knowledge & Data Engineering, 2016, 28(3):801-812.
[23] SHI J B, MALIK J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence, 2000, 22(8):888-905.
[24] GLIGORIJEVIĆ V, PANAGAKIS Y, ZAFEIRIOU S.Non-negative matrix factorizations for multiplex network analysis[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 41(4):928-940.
[25] TANG W, LU Z, DHILLON I S.Clustering with multiple graphs[C]//Proceedings of 2009 IEEE International Conference on Data Mining.Washington D.C., USA:IEEE Press, 2009:1016-1021.
[26] WANG B, MEZLINI A M, DEMIR F, et al.Similarity network fusion for aggregating data types on a genomic scale[J].Nature Methods, 2014, 11(3):333.
[27] DONG X, FROSSARD P, VANDERGHEYNST P, et al.Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds[J].IEEE Transactions on Signal Processing, 2013, 62(4):905-918.
[28] ZHAO Y, KARYPIS G.Empirical and theoretical comparisons of selected criterion functions for document clustering[J].Machine Learning, 2004, 55(3):311-331.
[29] MANNING C D, RAGHAVAN P, SCHÜTZE H.Text classification and naive Bayes[J].Introduction to Information Retrieval, 2008, 1(6):1-5.
[30] LIU H, WU Z, LI X, et al.Constrained nonnegative matrix factorization for image representation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 34(7):1299-1311.

选择文件类型/文献管理软件名称

选择包含的内容