计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (11): 107-113.doi: 10.11896/jsjkx.221000226

• 数据库&大数据&数据科学 • 上一篇    下一篇

基于二部图表示的属性网络社区发现算法

赵兴旺1,2, 薛晋芳1   

  1. 1 山西大学计算机与信息技术学院 太原 030006
    2 山西大学计算智能与中文信息处理教育部重点实验室 太原 030006
  • 收稿日期:2022-10-26 修回日期:2023-03-04 出版日期:2023-11-15 发布日期:2023-11-06
  • 通讯作者: 赵兴旺(zhaoxw84@163.com)
  • 基金资助:
    国家自然科学基金(62072293,62272285)

Community Discovery Algorithm for Attributed Networks Based on Bipartite Graph Representation

ZHAO Xingwang1,2, XUE Jinfang1   

  1. 1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
    2 Key Laboratory of Computational Intelligence and Chinese Information Processing,Ministry of Education,Shanxi University,Taiyuan 030006,China
  • Received:2022-10-26 Revised:2023-03-04 Online:2023-11-15 Published:2023-11-06
  • About author:ZHAO Xingwang,born in 1984,Ph.D,associate professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include data mining and machine learning.
  • Supported by:
    National Natural Science Foundation of China(62072293,62272285).

PDF (PC)

2396

摘要： 属性网络社区发现是网络数据分析中的一项重要研究内容。为了提高社区发现的准确性,现有算法大多通过融合拓扑信息和属性信息对属性网络进行低维表示,然后基于低维特征进行社区发现。然而,这类算法通常基于深度模型进行表示学习,缺乏一定的可解释性。因此,文中提出了一种基于二部图表示的属性网络社区发现算法,以提高社区发现结果的准确性和可解释性。首先,分别基于属性网络的拓扑信息和属性信息计算网络中各个节点作为代表点的概率,通过两类信息融合选出一定比例的节点作为代表点;其次,基于拓扑结构和节点属性计算各个节点到代表点的距离,构建二部图;最后,基于二部图利用谱聚类算法进行社区发现,得到最终结果。在人造属性网络和真实属性网络上与已有的属性网络社区发现算法进行实验比较分析。实验结果表明,所提算法在标准化互信息、调整兰德指数等评价指标上均优于已有算法。

关键词: 属性网络, 社区发现, 二部图, 融合

Abstract: Community discovery in attributed networks is an important research content in network data analysis.To improve the accuracy of community discovery,most existing algorithms perform low-dimensional representation of attributed networks by fusing topological and attributed information,and then perform community discovery based on low-dimensional features.Such algorithms,however,are typically based on deep learning models for representation learning,which lack interpretability.Therefore,in order to improve the accuracy and interpretability of community discovery results,this paper proposes a community discovery algorithm for attributed networks based on bipartite graph representation.Firstly,the topological and attributed information of the attributed networks are used to calculate the probability of each node serving as a representative point in the network,and a certain proportion of nodes are chosen as representative points.Secondly,based on the topological structure and node attributes,the distances of each node to the representative points are calculated to construct a bipartite graph.Finally,based on the bipartite graph,the result is obtained by using the spectral clustering algorithm for community discovery.Experiments are carried out on artificial and real attributed networks to compare and analyze the proposed algorithm and the existing algorithms.In terms of evaluation indices such as normalized mutual information and adjusted rand index,experimental results show that the proposed algorithm outperforms the existing algorithms.

Key words: Attributed networks, Community discovery, Bipartite graph, Fusion

中图分类号: 

  • TP391
[1]BOTHOREL C,CRUZ J D,MAGNANI M,et al.Clustering attributed graphs:Models,measures and methods [J].Network Science,2015,3(3):408-444.
[2]FORTUNATO S,NEWMAN M E J.20 years of network community detection [J].Nature Physics,2022,18(8):848-850.
[3]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks [J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.
[4]CHUNAEV P.Community detection in node-attributed social networks:A survey [J].Computer Science Review,2020,37:100286.
[5]STEINHAEUSER K,CHAWLA N V.Community detection in a large real-world social network [J].Social Computing,Beha-vioral Modeling,and Prediction,2008,7:168-175.
[6]COMBE D,LARGERON C,EGYED-ZSIGMOD E,et al.Combining relations and text in scientific network clustering [C]//Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.IEEE,2012:1248-1253.
[7]HUANG B Y,WANG C K,WANG B B.NMLPA:Uncoveringoverlapping communities in attributed networks via a multi-label propagation approach [J].Sensors,2019,19(2):260-275.
[8]ALINEZHAD E,TEIMOURPOUR B,SEPEHRI M M,et al.Community detection in attributed networks considering both structural and attribute similarities:Two mathematical programming approaches [J].Neural Computing and Applications,2020,32(8):3203-3320.
[9]WANG X,JIN D,CAO X C,et al.Semantic community identification in large attribute networks [C]//Proceedings of the 13th AAAI Conference on Artificial Intelligence.Phoenix.AAAI Press,2016:265-271.
[10]QIN M,JIN D,HE D X,et al.Adaptive community detection incorporating topology and content in social networks[C]//Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining.IEEE,2017:675-682.
[11]PEI Y L,CHAKRABORTY N,SYCARA K.Nonnegative matrix tri-factorization with graph regularization for community detection in social networks[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence.AAAI Press,2015:2083-2089.
[12]XU Z Q,KE Y P,WANG Y,et al.A model-based approach to attributed graph clustering [C]//Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data.ACM,2012:505-516.
[13]YANG J,MCAULEY J,LESKOVEC J.Com munity detection in networks with node attributes [C]//Proceedings of the IEEE International Conference on Data Mining.IEEE,2013:1151-1156.
[14]XU Z Q,KE Y P,WANG Y,et al.GBAGC:A general Bayesian framework for attributed graph clustering [J].ACM Transactions on Knowledge Discovery from Data,2014,9(1):5.1-5.43.
[15]GAO H C,HUANG H.Deep attributed network embedding[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence.AAAI Press,2018:3364-3370.
[16]LIAO L Z,HE X N,ZHANG H W,et al.Attributed social network embedding [J].IEEE Transactions on Knowledge and Data Engineering,2018,30(12):2257-2270.
[17]WANG C,PAN S R,LONG G D,et al.MGAE:Marginalized graph autoencoder for graph clustering [C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Ma-nagement.ACM,2017:889-898.
[18]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks [J].Science,2014,344(6191):1492-1496.
[19]LUXBURG U V.A tutorial on spectral clustering [J].Statistics and Computing,2004,17(4):395-416.
[20]BRIN S,PAGE L.The anatomy of a large-scale hypertextualweb search engine [J].Computer Networks and ISDN Systems,1998,30(1-7):107-117.
[21]BONACICH P.Power and centrality:A family of measures [J].American Journal of Sociology,1987,92(5):1170-1182.
[22]YU S X,SHI J B.Multiclass spectral clustering [C]//Procee-dings of the 9th IEEE International Conference on Computer Vison.IEEE,2003,2:313-319.
[23]ELHADI H,AGAM G.Structure and attributes community de-tection:Comparative analysis of composite,ensemble and selection methods [C]//Proceedings of the 7th Workshop on Social Network Mining and Analysis.ACM,2013,10:1-7.
[24]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms [J].Physical Review E,2008,78(4):046110.
[25]BERAHMAND K,HAGHANI S,ROSTAMI M,et al.A new attributed graph clustering by using label propagation in complex network [J].Journal of King Saud University－Computer and Information Sciences,2022,34(5):1869-1883.
[26]LIU L Y,XU L L,WANG Z,et al.Community detection based on structure and content:A content propagation perspective [C]//Proceedings of the 2015 IEEE International Conference on Data Mining.IEEE Computer Society,2015:271-280.
[27]ZHANG X T,LIU H,LI Q M,et al.Attributed graph clustering via adaptive graph convolution [C]//Proceedings of the 28th International Joint Conference on Artificial Intelligence.AAAI Press,2019:4327-4333.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发