Computer Science ›› 2021, Vol. 48 ›› Issue (12): 204-211.doi: 10.11896/jsjkx.210300060

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

Attributed Network Embedding Based on Matrix Factorization and Community Detection

XU Xin-li, XIAO Yun-yue, LONG Hai-xia, YANG Xu-hua, MAO Jian-fei   

  1. College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China
  • Received:2021-03-05 Revised:2021-06-08 Online:2021-12-15 Published:2021-11-26
  • About author:XU Xin-li,born in 1977,Ph.D,associate professor,is a member of China Computer Federation.Her main research interests include intelligent computing,network embedding and medical image computing.
    MAO Jian-fei,born in 1976,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include network visual media and mobile media technology,computer,vision and embedded system.
  • Supported by:
    National Natural Science Foundation of China(61773348),Zhejiang Public Welfare Science and Technology Plan Project(LGG20F020017) and Natural Science Foundation of Zhejiang Province(LQ18F030015).

Abstract: An attributed network contains not only the complex topological structure but also the nodes with rich attribute information.It can be used to more effectively model modern information systems than traditional networks.Community detection of the attributed network has important research value in hierarchical analysis of complex systems,control of information propagation in the network,and prediction of group behavior of network users.In order to make better use of topology information and attribute information for community discovery,an attributed network embedding based on matrix factorization and community detection(CDEMF) are proposed.First,an attributed network embedding method based on matrix factorization is proposed to model the attributed proximity and the similarity of adjacent nodes calculated in term of the local link information of the network,where the low-dimensional embedding vector corresponding to each node can be obtained by a distributed algorithm of matrix decomposition,that is,the network nodes can be mapped into a collection of data points represented by low-dimensional vectors.Then the community detection method based on curvature and modularity is developed to achieve attributed network community division by clustering the data point set,which can automatically determine the number of communities contained in the data point set.CDEMF is compared with the other 8 kinds of well-known approaches on public real network datasets.The experimental results demonstrate the effectiveness and superiority of CDEMF.

Key words: Attributed network embedding, Automatic clustering, Community detection, Curvature, Matrix factorization

CLC Number: 

  • TP391
[1]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics:Theory and Experiment,2008(10):P10008.
[2]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E,2007,76(3):036106.
[3]ROZEMBERCZKI B,DAVIES R,SARKAR R,et al.GEMSEC:Graph embedding with self clustering[C]//Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.2019:65-72.
[4]SUN F Y,QU M,HOFFMANN J,et al.vGRAPH:A generative model for joint community detection and node representation learning[C]//Advances in Neural Information Processing Systems.2019:514-524.
[5]YANG J,MCAULEY J,LESKOVEC J.Community detection in networks with node attributes[C]//2013 IEEE 13th International Conference on Data Mining.IEEE,2013:1151-1156.
[6]JIN D,LIU Z Y,HE R F,et al.A Robust and Strong Explanation Community Detection Method for Attributed Networks[J].Chinese Journal of Computers,2018,41(7):1476-1489.
[7]HUANG X,LI J,HU X.Accelerated attributed network embedding[C]//Proceedings of the 2017 SIAM International Confe-rence on Data Mining.Society for Industrial and Applied Mathematics,2017:633-641.
[8]HUANG X,LI J,ZOU N,et al.A general embedding framework for heterogeneous information learning in large-scale networks[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2018,12(6):1-24.
[9]LI J,HU X,WU L,et al.Robust unsupervised feature selection on networked data[C]//Proceedings of the 2016 SIAM International Conference on Data Mining.Society for Industrial and Applied Mathematics,2016:387-395.
[10]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.2014:701-710.
[11]TANG J,QU M,WANG M,et al.Line:Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web.2015:1067-1077.
[12]WANG H,YANG Y,LIU B.GMC:Graph-based multi-view clustering[J].IEEE Transactions on Knowledge and Data Engineering,2019,32(6):1116-1129.
[13]SUN H,HE F,HUANG J,et al.Network embedding for community detection in attributed networks[J].ACM Transactions on Knowledge Discovery from Data(TKDD),2020,14(3):1-25.
[14]YE Z L,ZHAO H X,ZHANG K,et al.Network representation learning algorithm based on multi-view integration[J].Compu-ter Science,2019,46(1):124-132.
[15]ZHANG B,YU Z,ZHANG W.Community-Centric Graph Convolutional Network for Unsupervised Community Detection[C]//IJCAI.2020.
[16]ESTER M,KRIEGEL H P,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//KDD-96 Proceedings.AAAI,1996:226-231.
[17]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.
[18]CHEN J F,ZHANG M,HE Q.NJW spectral clustering algorithm based on heuristics to determine the number of classes[J].Computer Science,2018,45(2):474-479.
[19]TIBSHIRANI R,WALTHER G,HASTIE T.Estimating the number of clusters in a data set via the gap statistic[J].Journal of the Royal Statistical Society:Series B(Statistical Methodology),2001,63(2):411-423.
[20]SUGAR C A,JAMES G M.Finding the number of clusters in a dataset:An information-theoretic approach[J].Journal of the American Statistical Association,2003,98(463):750-763.
[21]ZHANG Y,MAHDZIUK J,QUEK C H,et al.Curvature-based method for determining the number of clusters[J].Information Sciences,2017,415-416:414-428.
[22]YANG Y,LIU H,GUAN Z,et al.CoHomo:A cluster-attribute correlation aware graph clustering framework[J].Neurocomputing,2020,412:327-338.
[23]KUANG D,DING C,PARK H.Symmetric nonnegative matrix factorization for graph clustering[C]//Proceedings of the 2012 SIAM international conference on data mining.Society for Industrial and Applied Mathematics,2012:106-117.
[24]CALINSKI T,HARABASZ J.A dendrite method for cluster analysis[J].Communications in Statistics-theory and Methods,1974,3(1):1-27.
[25]KRZANOWSKI W J,LAI Y T.A criterion for determining the number of groups in a data set using sum-of-squares clustering[J].Biometrics,1988,44(1):23-34.
[26]NEWMAN M E J.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):066133.
[27]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.
[28]HUANG X,LI J,HU X.Label informed attributed network embedding[C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining.2017:731-739.
[29]HUANG Z,ZHONG X,WANG Q,et al.Detecting community in attributed networks by dynamically exploring node attributes and topological structure[J].Knowledge-Based Systems,2020,196:105760.
[30]PAN Y,HU G,QIU J,et al.FLGAI:a unified network embedding framework integrating multi-scale network structures and node attribute information[J].Applied Intelligence,2020,50(11):3976-3989.
[31]GAO Y,GONG M,XIE Y,et al.Community-oriented attributed network embedding[J].Knowledge-Based Systems,2020,193:105418.
[32]YOU X,MA Y,LIU Z.A three-stage algorithm on community detection in social networks[J].Knowledge-Based Systems,2020,187:104822.
[1] YANG Wen-kun, YUAN Xiao-pei, CHEN Xiao-feng, GUO Rui. Spatial Multi-feature Segmentation of 3D Lidar Point Cloud [J]. Computer Science, 2022, 49(8): 143-149.
[2] HE Xi, HE Ke-tai, WANG Jin-shan, LIN Shen-wen, YANG Jing-lin, FENG Yu-chao. Analysis of Bitcoin Entity Transaction Patterns [J]. Computer Science, 2022, 49(6A): 502-507.
[3] HE Yi-chen, MAO Yi-jun, XIE Xian-fen, GU Wan-rong. Matrix Transformation and Factorization Based on Graph Partitioning by Vertex Separator for Recommendation [J]. Computer Science, 2022, 49(6A): 272-279.
[4] WANG Ben-yu, GU Yi-jun, PENG Shu-fan, ZHENG Di-wen. Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning [J]. Computer Science, 2022, 49(5): 170-178.
[5] 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.
[6] PU Shi, ZHAO Wei-dong. Community Detection Algorithm for Dynamic Academic Network [J]. Computer Science, 2022, 49(1): 89-94.
[7] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[8] ZHAN Wan-jiang, HONG Zhi-lin, FANG Lu-ping, WU Zhe-fu, LYU Yue-hua. Collaborative Filtering Recommendation Algorithm Based on Adversarial Learning [J]. Computer Science, 2021, 48(7): 172-177.
[9] SHAO Chao, SONG Shu-mi. Collaborative Filtering Recommendation Algorithm Based on User Preference Under Trust Relationship [J]. Computer Science, 2021, 48(6A): 240-245.
[10] DUAN Fei, WANG Hui-min, ZHANG Chao. Cauchy Non-negative Matrix Factorization for Data Representation [J]. Computer Science, 2021, 48(6): 96-102.
[11] YANG Xu-hua, WANG Chen. Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force [J]. Computer Science, 2021, 48(4): 229-236.
[12] PAN Yu, ZOU Jun-hua, WANG Shuai-hui, HU Gu-yu, PAN Zhi-song. Deep Community Detection Algorithm Based on Network Representation Learning [J]. Computer Science, 2021, 48(11A): 198-203.
[13] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[14] LI Yu-rong, LIU Jie, LIU Ya-lin, GONG Chun-ye, WANG Yong. Parallel Algorithm of Deep Transductive Non-negative Matrix Factorization for Speech Separation [J]. Computer Science, 2020, 47(8): 49-55.
[15] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!