Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (11): 77-87.doi: 10.11896/jsjkx.230600003

• Database & Big Data & Data Science • Previous Articles     Next Articles

Graph Clustering Algorithm Based on Node Clustering Complexity

ZHENG Wenping1,2,3, WANG Fumin1, LIU Meilin1, YANG Gui1   

  1. 1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
    2 Key Laboratory of Computation Intelligence and Chinese Information Processing of Ministry of Education,Shanxi University,Taiyuan 030006,China
    3 Institute of Intelligent Information Processing,Shanxi University,Taiyuan 030006,China
  • Received:2023-05-31 Revised:2023-08-24 Online:2023-11-15 Published:2023-11-06
  • About author:ZHENG Wenping,born in 1979,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.Her main research interests include graph theory algorithms and bioinformatics.
  • Supported by:
    National Natural Science Foundation of China(62072292) and 1331 Engineering Project of Shanxi Province,China.

PDF (PC)

2468

Abstract: Graph clustering is an important task in the analysis of complex networks,which can reveal the community structure within a network.However,clustering complexity of nodes varies throughout the network.To address this issue,a graph clustering algorithm based on node clustering complexity(GCNCC)is proposed.It calculates the clustering complexity of nodes and assigns pseudo-labels to nodes with low clustering complexity.Then it uses these pseudo-labels as supervised information to lower the clustering complexity of other nodes to obtain the community structure of the network.The GCNCC algorithm consists of three main modules:node representation,node clustering complexity assessment,and graph clustering.The node representation module represents nodes in a low-dimensional space to maintain the clustering of nodes,the node clustering complexity assessment module identifies low clustering complexity nodes,and assigns them pseudo-labels,which can be used to update the clustering complexity of other nodes.The graph clustering module uses label propagation to spread the pseudo-labels from nodes with low clustering complexity to those with high clustering complexity.Compared with 9 classic algorithms on 3 real citation networks and 3 biological datasets,the proposed GCNCC performed well in terms of ACC,NMI,ARI,and F1.

Key words: Graph clustering, Node clustering complexity, Network embedding, Self-supervised

CLC Number: 

  • TP391
[1]NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review.E,2004,69(6):026113.
[2]BLONDEL V D,GUILLAUME J,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J/OL].Journal of Statistical Mechanics:Theory and Experiment,2008,(10):P10008.https://iopscience.iop.org/article/10.1088/1742-5468/2008/10/P10008/meta#artAbst.
[3]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detec-ting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[4]WHANG J J,GLEICH D F,DHILLON I S.Overlapping community detection using neighborhood-inflated seed expansion[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(5):1272-1284.
[5]RAGHAVAN U N,ALBERT R,SOUNDAR K.Near lineartime algorithm to detect community structures in large-scale networks[J].PHYSICAL REVIEW E,2007,76(3):036106.
[6]LI W,HUANG C,WANG M,et al.Stepping community detection algorithm based on label propagation and similarity[J].Physica A－Statistical Mechanics and Its Applications,2017,472:145-155.
[7]DING J J,HE X X,YUAN J Q,et al.Community detection by propagating the label of center[J].Physica A:Statistical Mechanics and its Applications,2018,503:675-686.
[8]LI C W,CHEN H M,LI T R,et al.A stable community detection approach for complex network based on density peak clustering and label propagation[J].Applied Intelligence,2021,52(2):1188-1208.
[9]LEE D D,SEUNG H.S.Learning the parts of objects by non-negative matrix factorization[J].Nature,1999(401):788-791.
[10]ROWEIS S T,SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000(290):2323-2326.
[11]BELKIN M,NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering[J].Advances in Neural Information Processing Systems,2001,14(6):585-591.
[12]CAO S S,LU W,XU Q K.GraRep:Learning graph representa-tions with global structural information.[C]//Proceedings of the 24th ACM International on Conference on Information and Knowledge.Managemen New York,USA:ACM,2015:891-900.
[13]WANG X,CUI P,WANG J,et al.Community preserving network embedding[C]//Proceedings of the 32th AAAI Confe-rence on Artificial Intelligence.Palo Alto,USA:AAAI,2017:203-209.
[14]YANG C,LIU Z Y,ZHAO D L,et al.Network representation learning with rich text information[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence.Palo Alto,USA:AAAI,2015:2111-2117.
[15]HUANG X,LI J D,HU X.Accelerated attributed network embedding[C]//Proceedings of the 2017 SIAM International Conference on Data Mining.Philadelphia,USA:SIAM,2017:633-641.
[16]PEROZZI B,AL-RFOU R,SKIENA S.DeepWalk:Online lear-ning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Disco-very and Data Mining.New York,USA:ACM,2014:701-710.
[17]GROVER A,LESKOVEC J.Node2vec:Scalable feature learning for networks[C]//Proceedings of the 22th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.New York,USA:ACM,2016:855-864.
[18]HUANG X,SONG Q Q,LI Y N,et al.Graph recurrent networks with attributed random walks.[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2019:732-740.
[19]HONG R C,HE Y,WU L,et al.Deep attributed network embedding by preserving structure and attribute information[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2021,51(3):1434-1445.
[20]KIPF T,WELLING M.Semi-Supervised classification withgraph convolutional networks[C]//Proceedings of the International Conference on Learning Representations.2016.
[21]KIPF T,WELLING M.Variational graph auto-encoders[C]//Proceedings of the NIPS Workshop on Bayesian Deep Learning.2016.
[22]VELICKOVIC P,CUCURULL G,CASANOVA A,et al.Graph attention networks[C]//Proceedings of the International Conference on Learning Representations.2018.
[23]GASTEIGER J,BOJCHEVSKI A,GÜNNEMANN S.Predictthen propagate:graph neural networks meet personalized pageRank[C]//Proceedings of the International Conference on Learning Representations.2018.
[24]WANG X,ZHU M Q,BO D Y,et al.AM-GCN:Adaptive multi-channel graph convolutional networks[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2020:1243-1253.
[25]XIE J Y,GIRSHICK R,FARHADI A.Unsupervised deep embedding for clustering analysis[C]//Proceedings of the 33nd International Conference on Machine Learning.Cambridge,USA:MIT Press,2016:478-487.
[26]WANG C,PAN S R,HU R Q,et al.Attributed graph clustering:A deep attentional embedding approach[C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence.San Francisco,USA:Morgan Kaufmann,2019:3670-3676.
[27]BO D Y,WANG X,SHI C,et al.Structural deep clustering network[C]//Proceedings of the 29th International World Wide Web Conference.New York,USA:ACM,2020:1400-1410.
[28]PAN S R,HU R Q,FUNG S F,et al.Learning graph embedding with adversarial training methods[J].IEEE Transactions on Cybernetics,2019,50(6):2475-2487.
[29]CUI G Q,ZHOU J,YANG C et al.Adaptive graph encoder for attributed graph embedding[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discoveryand Data Mining.New York,USA:ACM,2020:976-985.
[30]JI J Z,LIANG Y LEI M L.Deep attributed graph clustering with self-separation regularization and parameter-free cluster estimation[J].Neural networks,2021,142:522-533.
[31]CHEN D L,LIN Y K,LI W,et al.Measuring and relieving the over-smoothing problem for graph neural networks from the topological View[C]//Proceedings of the 35th AAAI Conference on Artificial Intelligence.Palo Alto,USA:AAAI,2020:3438-3445.
[32]XIE Y Q,LI S,YANG C,et al.When do GNNs work:Understanding and improving neighborhood aggregation[C]//Proceedings of the 29th International Joint Conference on Artificial Intelligence.San Francisco,USA:Morgan Kaufmann,2020:1303-1309.
[33]HE D X,GUO R,WANG X B,et al.Inflation improves graph neural networks[C]//Proceedings of the 31th International World Wide Web Conference.New York,USA:ACM,2022:1466-1474.
[34]DUAN L,AGGARWAL C,MA S,et al.Improving spectralclustering with deep embedding and cluster estimation[C]//Proceedings of the International Conference on Data Mining.Washington,USA:IEEE,2019:170-179.
[35]LEIBER C,BAUER L G M,SCHELLINGB,et al.Dip-baseddeep embedded clustering with k-estimation[C]//Proceedings of the 27th ACM SIGKDD International Conference on Know-ledge Discovery and Data Mining.New York,USA:ACM,2021:903-913.
[1] LI Xiang, FAN Zhiguang, LIN Nan, CAO Yangjie, LI Xuexiang. Self-supervised Learning for 3D Real-scenes Question Answering [J]. Computer Science, 2023, 50(9): 220-226.
[2] ZENG Wu, MAO Guojun. Few-shot Learning Method Based on Multi-graph Feature Aggregation [J]. Computer Science, 2023, 50(6A): 220400029-10.
[3] ZENG Xiangyu, LONG Haixia, YANG Xuhua. Community Detection Based on Markov Similarity Enhancement and Network Embedding [J]. Computer Science, 2023, 50(4): 56-62.
[4] WANG Pengyu, TAI Wenxin, LIU Fang, ZHONG Ting, LUO Xucheng, ZHOU Fan. Self-supervised Flight Trajectory Prediction Based on Data Augmentation [J]. Computer Science, 2023, 50(2): 130-137.
[5] ZHU Lei, WANG Shanmin, LIU Qingshan. Self-supervised 3D Face Reconstruction Based on Detailed Face Mask [J]. Computer Science, 2023, 50(2): 214-220.
[6] DU Hang-yuan, LI Duo, WANG Wen-jian. Method for Abnormal Users Detection Oriented to E-commerce Network [J]. Computer Science, 2022, 49(7): 170-178.
[7] CHEN Shi-cong, YUAN De-yu, HUANG Shu-hua, YANG Ming. Node Label Classification Algorithm Based on Structural Depth Network Embedding Model [J]. Computer Science, 2022, 49(3): 105-112.
[8] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[9] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[10] TANG Qi-you, ZHANG Feng-li, WANG Rui-jin, WANG Xue-ting, ZHOU Zhi-yuan, HAN Ying-jun. Method of Attributed Heterogeneous Network Embedding with Multiple Features [J]. Computer Science, 2022, 49(12): 146-154.
[11] MIAO Zhuang, WANG Ya-peng, LI Yang, WANG Jia-bao, ZHANG Rui, ZHAO Xin-xin. Robust Hash Learning Method Based on Dual-teacher Self-supervised Distillation [J]. Computer Science, 2022, 49(10): 159-168.
[12] ZHENG Su-su, GUAN Dong-hai, YUAN Wei-wei. Heterogeneous Information Network Embedding with Incomplete Multi-view Fusion [J]. Computer Science, 2021, 48(9): 68-76.
[13] TIAN Song-wang, LIN Su-zhen, YANG Bo. Multi-band Image Self-supervised Fusion Method Based on Multi-discriminator [J]. Computer Science, 2021, 48(8): 185-190.
[14] WU Lan, WANG Han, LI Bin-quan. Unsupervised Domain Adaptive Method Based on Optimal Selection of Self-supervised Tasks [J]. Computer Science, 2021, 48(6A): 357-363.
[15] HU Xin-tong, SHA Chao-feng, LIU Yan-jun. Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis [J]. Computer Science, 2021, 48(5): 124-129.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.