计算机科学 ›› 2019, Vol. 46 ›› Issue (4): 216-221.doi: 10.11896/j.issn.1002-137X.2019.04.034

• 人工智能 • 上一篇    下一篇

基于谱聚类的二分网络社区发现算法

张晓琴1, 安晓丹1, 曹付元2   

  1. 山西大学数学科学学院 太原0300061
    山西大学计算机与信息技术学院 太原0300062
  • 收稿日期:2018-03-01 出版日期:2019-04-15 发布日期:2019-04-23
  • 通讯作者: 张晓琴(1975-),女,博士,硕士生导师,主要研究方向为统计机器学习,E-mail:zhangxiaoqin@sxu.edu.cn(通信作者)
  • 作者简介:安晓丹(1991-),女,硕士生,主要研究方向为统计机器学习;曹付元(1974-),男,教授,博士生导师,主要研究方向为数据挖掘与机器学习。
  • 基金资助:
    本文受国家自然科学基金(61573229),山西省回国留学人员科研资助项目(2017-020),山西省基础研究计划项目(201701D121004),山西省高等学校教学改革创新项目(J2017002)资助。

Detecting Community from Bipartite Network Based on Spectral Clustering

ZHANG Xiao-qin1, AN Xiao-dan1, CAO Fu-yuan2   

  1. School of Mathematics Sciences,Shanxi University,Taiyuan 030006,China1
    School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China2
  • Received:2018-03-01 Online:2019-04-15 Published:2019-04-23

摘要: 二分网络是一类特殊的网络,在探索网络深层结构上具有重要作用。针对二分网络社区划分方法仍存在划分精度不高的问题,应用标准化谱聚类,提出了二分网络社区发现算法——谱聚类交互算法(SPCI)。首先,根据二分网络中两类节点之间的连边关系,构建相似性矩阵;然后,利用谱聚类算法将其中一类节点聚类;最后,利用交互度指标实现二分网络的社区划分。在人工数据和真实数据上的验证表明,SPCI不仅拥有比资源分布矩阵算法、边集聚系数算法和联合谱聚类算法更高的准确性和模块度,而且可以较为准确地确定社区划分个数。

关键词: 二分网络, 谱聚类, 社区划分, 相似性矩阵

Abstract: Bipartite network is a special kind of network,which plays an important role in exploring the deep structure of the network.However,themethods of dividing the bipartite network community still have some problems,such as low precision of division.Through the application of normalized spectral clustering algorithm,an algorithm of detecting community- spectral clustering interaction (SPCI) was proposed.First,a similarity matrix is constructed based on the relationship between two kinds of nodes.Then,a cluster is clustered by spectral clustering algorithm.Finally,the community partition of two points network is realized by using two kinds of node’s interaction index.Through the verification on artificial data and real data,the result shows that SPCI not only has higher accuracy and modularity than the algorithm based on resource distribution matrix,edge clustering coefficient and spectral co-clustering,but also can accurately determine the number of community partition.

Key words: Bipartite network, Community partition, Similarity matrix, Spectral clustering

中图分类号: 

  • TP391
[1]SHANG M,LU L,ZHANG Y C,et al.Empirical analysis of web-based user-object bipartite networks[J].Epl,2012,90(4):1303-1324.
[2]YANG Z,ZHANG Z K,ZHOU T.Anchoring bias in online vo- ting[J].Computer Science,2012,100(6):1-6.
[3]JEONG H,TOMBOR B,ALBERT R,et al.The large-scale organization of metabolic networks [J].Nature,2000,407(6804):651-654.
[4]JUAN,SHENG,ZHANG,et al.Traffic characteristics based dynamic radio resource management in heterogeneous wireless networks [J].China Communications,2014,11(1):1-11.
[5]CHEN D,YAN Y,WANG D,et al.Community detection algorithm based on structural similarity for bipartite networks[C]∥IEEE International Conference on Software Engineering and Service Science.IEEE,2017:98-102.
[6]MELAMED D.Community structures in bipartite networks:a dual-projection approach[J].Plos One,2014,9(5):1-5.
[7]MURATA T.Detecting communities from bipartite networks based on bipartite modularities[C]∥ International Conference on Computational Science and Engineering.IEEE Computer Society,2009:50-57.
[8]GAO M,CHEN L,XU Y C.Projection based algorithm for link prediction in bipartite network [J].Computer Science,2016,43(2):118-123.(in Chinese) 高曼,陈崚,徐永成.基于投影的二分网络链接预测[J].计算机科学,2016,43(2):118-123.
[9]BARBER M J.Modularity and community detection in bipartite networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2007,76(2):1-9.
[10]LEHMANN S,SCHWARTZ M,HANSEN L K.Biclique communities[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2008,78(2):1-9.
[11]GREGORI E,LENZINI L,MAINARDIS.Parallel k-clique community detection on large-scale networks[J].IEEE Transa-ctions on Parallel & Distributed Systems,2013,24(8):1651-1660.
[12]LIU X,MURATA T.Community detection in large-scale bipartite networks[C]∥IEEE /WIC /ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies,2009.WI-LAT:IEEE,2009:50-57.
[13]CHEN B L,CHEN L,ZOU S R,et al.Detecting community structure in bipartite networks based on matrix factorization[J].Computer Science,2014,41(2):55-58.(in Chinese) 陈伯伦,陈崚,邹盛荣,等.基于矩阵分解的二分网络社区挖掘算法[J].计算机科学,2014,41(2):55-58.
[14]GUIMERA R,SALESPARDO M,Amaral L A N.Module identification in bipartite and directed networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2007,76(3 Pt 2):1-8.
[15]NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks [J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,69(2):1-15.
[16]LI Z,ZHANG S,ZHANG X.Modularity and community detection in bipartite networks[J].American Journal of Operations Research,2015,5(5):421-434.
[17]DORMANN C F,STRAUSS R.A method for detecting modules in quantitative bipartite networks[J].Methods in Ecology & Evolution,2014,5(1):90-98.
[18]GUO G G,QIAN Y H,ZHANG X Q,et al.Algorithm of detecting community in bipartite network with autonomous determination of the number of communities[J].PR & AI,2015,28(11):969-975.(in Chinese) 郭改改,钱宇华,张晓琴,等.自主确定社区个数的二模网络社区发现算法[J].模式识别与人工智能,2015,28(11):969-975.
[19]TANG L,LIU H.社会计算:社区发现和社会媒体挖掘.文益民,闭应洲,译.机械工业出版社,2013:78-83.
[20]ZHOU Y,SUN G,XING Y,et al.Local community detection algorithm based on minimal cluster[J].Applied Computational Intelligence and Soft Computing,2016,2016(2):1-11.
[21]LUXBURG U V.A Tutorial on spectral clustering[J].Statistics & Computing,2007,17(4):395-416.
[22]YAN D,HUANG L,JORDAN M I.Fast approximate spectral clustering[C]∥ACM Sigkdd International Conference on Knowledge Discovery and Data Mining.ACM,2009:907-916.
[23]ZHANG P,WANG J,LI X,et al.Clustering coefficient and community structure of bipartite networks[J].Physica A Statistical Mechanics & Its Applications,2008,387(27):6869- 6875.
[24]WU Y J.A Clustering algorithm for bipartite network based on distribution matrix of resources[J].Journal of Beijing Normal University,2010,46(5):643-646.(in Chinese) 吴亚晶,狄增如,樊瑛.基于资源分布矩阵的二分网聚类方法.北京师范大学学报(自然科学版),2010,46(5):643-646.
[25]DAVIS A,GARDNER B B,GARDER M R.Deep South;a social anthropological study of caste and class[J].American Journal of Sociology,1941,2(3):117-118.
[26]SCOTT J,HUGHES M,MACKENZIE J.The anatomy of Scottish capital:Scottish companies and Scottish Capital,1900-1979[J].Economic History Review,1980,33(4):271-275.
[27]WASSERMAN S,FAUST K.Social network analysis:methods and applications[J].Contemporary Sociology,1994,91(435):219-220.
[1] 郭奕杉, 刘漫丹.
基于时空轨迹数据的异常检测
Anomaly Detection Based on Spatial-temporal Trajectory Data
计算机科学, 2021, 48(6A): 213-219. https://doi.org/10.11896/jsjkx.201100193
[2] 李鹏, 刘力军, 黄永东.
基于地标表示的联合谱嵌入和谱旋转的谱聚类算法
Landmark-based Spectral Clustering by Joint Spectral Embedding and Spectral Rotation
计算机科学, 2021, 48(6A): 220-225. https://doi.org/10.11896/jsjkx.210100167
[3] 杨旭华, 王晨.
基于网络嵌入与局部合力的复杂网络社区划分算法
Community Detection Algorithm in Complex Network Based on Network Embedding and Local Resultant Force
计算机科学, 2021, 48(4): 229-236. https://doi.org/10.11896/jsjkx.200200102
[4] 周波.
融合语义模型的二分网络推荐算法
Bipartite Network Recommendation Algorithm Based on Semantic Model
计算机科学, 2020, 47(11A): 482-485. https://doi.org/10.11896/jsjkx.200400028
[5] 周波.
二分网络推荐算法与协同过滤算法的关系研究
Research on Relationship Between Bipartite Network Recommendation Algorithm and Collaborative Filtering Algorithm
计算机科学, 2019, 46(11A): 163-166.
[6] 刘树栋, 魏嘉敏.
基于谱聚类和成对数据表示的多层感知机分类算法
Multilayer Perceptron Classification Algorithm Based on Spectral Clusteringand Simultaneous Two Sample Representation
计算机科学, 2019, 46(11A): 194-198.
[7] 戴彩艳, 陈崚, 胡孔法.
基于模块度增量的二分网络社区挖掘算法
Algorithm for Mining Bipartite Network Based on Incremental Modularity
计算机科学, 2018, 45(6A): 442-446.
[8] 胡庆成, 张勇, 邢春晓.
基于有重叠社区划分的社会网络影响最大化方法研究
K-clique Heuristic Algorithm for Influence Maximization in Social Network
计算机科学, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005
[9] 王颖,杨余旺.
基于堆和邻域共存信息的KNN相似图算法
KNN Similarity Graph Algorithm Based on Heap and Neighborhood Coexistence
计算机科学, 2018, 45(5): 196-200. https://doi.org/10.11896/j.issn.1002-137X.2018.05.033
[10] 王亮,田萱.
单幅散焦图像的局部特征模糊分割算法
Local Feature Fuzzy Segmentation Algorithm for Single Defocused Image
计算机科学, 2018, 45(2): 318-321. https://doi.org/10.11896/j.issn.1002-137X.2018.02.055
[11] 常家伟, 戴牡红.
基于PageRank和谱方法的个性化推荐算法
Personalized Recommendation Algorithm Based on PageRank and Spectral Method
计算机科学, 2018, 45(11A): 398-401.
[12] 李鹏清, 李扬定, 邓雪莲, 李永钢, 方月.
一种基于SimRank得分的谱聚类算法
Spectral Clustering Algorithm Based on SimRank Score
计算机科学, 2018, 45(11A): 458-461.
[13] 陈俊芬, 张明, 何强.
基于启发式确定类数的NJW谱聚类算法
Heuristically Determining Cluster Numbers Based NJW Spectral Clustering Algorithm
计算机科学, 2018, 45(11A): 474-479.
[14] 王平心,刘强,杨习贝,米据生.
基于动态邻域的三支聚类分析
Three-way Clustering Analysis Based on Dynamic Neighborhood
计算机科学, 2018, 45(1): 62-66. https://doi.org/10.11896/j.issn.1002-137X.2018.01.009
[15] 李金泽,徐喜荣,潘子琦,李晓杰.
改进的自适应谱聚类NJW算法
Improved Adaptive Spectral Clustering NJW Algorithm
计算机科学, 2017, 44(Z6): 424-427. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.095
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!