计算机科学 ›› 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, Spectral clustering, Similarity matrix

中图分类号: 

  • 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] 周波. 融合语义模型的二分网络推荐算法[J]. 计算机科学, 2020, 47(11A): 482-485.
[2] 周波. 二分网络推荐算法与协同过滤算法的关系研究[J]. 计算机科学, 2019, 46(11A): 163-166.
[3] 刘树栋, 魏嘉敏. 基于谱聚类和成对数据表示的多层感知机分类算法[J]. 计算机科学, 2019, 46(11A): 194-198.
[4] 戴彩艳, 陈崚, 胡孔法. 基于模块度增量的二分网络社区挖掘算法[J]. 计算机科学, 2018, 45(6A): 442-446.
[5] 胡庆成, 张勇, 邢春晓. 基于有重叠社区划分的社会网络影响最大化方法研究[J]. 计算机科学, 2018, 45(6): 32-35.
[6] 王颖,杨余旺. 基于堆和邻域共存信息的KNN相似图算法[J]. 计算机科学, 2018, 45(5): 196-200.
[7] 王亮,田萱. 单幅散焦图像的局部特征模糊分割算法[J]. 计算机科学, 2018, 45(2): 318-321.
[8] 常家伟, 戴牡红. 基于PageRank和谱方法的个性化推荐算法[J]. 计算机科学, 2018, 45(11A): 398-401.
[9] 李鹏清, 李扬定, 邓雪莲, 李永钢, 方月. 一种基于SimRank得分的谱聚类算法[J]. 计算机科学, 2018, 45(11A): 458-461.
[10] 陈俊芬, 张明, 何强. 基于启发式确定类数的NJW谱聚类算法[J]. 计算机科学, 2018, 45(11A): 474-479.
[11] 王平心,刘强,杨习贝,米据生. 基于动态邻域的三支聚类分析[J]. 计算机科学, 2018, 45(1): 62-66.
[12] 李金泽,徐喜荣,潘子琦,李晓杰. 改进的自适应谱聚类NJW算法[J]. 计算机科学, 2017, 44(Z6): 424-427.
[13] 邹凌君,陈崚,戴彩艳. 基于广义后缀树的二分网络社区挖掘算法[J]. 计算机科学, 2017, 44(7): 221-226.
[14] 李效伦,丁志军. LBSNs中的群体行程推荐方法[J]. 计算机科学, 2017, 44(6): 199-205.
[15] 柯祖福,易本顺,谢秋莹. 基于非局部自相似性的谱聚类图像去噪算法[J]. 计算机科学, 2017, 44(5): 299-303.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .