计算机科学 ›› 2019, Vol. 46 ›› Issue (4): 216-221.doi: 10.11896/j.issn.1002-137X.2019.04.034
张晓琴1, 安晓丹1, 曹付元2
ZHANG Xiao-qin1, AN Xiao-dan1, CAO Fu-yuan2
摘要: 二分网络是一类特殊的网络,在探索网络深层结构上具有重要作用。针对二分网络社区划分方法仍存在划分精度不高的问题,应用标准化谱聚类,提出了二分网络社区发现算法——谱聚类交互算法(SPCI)。首先,根据二分网络中两类节点之间的连边关系,构建相似性矩阵;然后,利用谱聚类算法将其中一类节点聚类;最后,利用交互度指标实现二分网络的社区划分。在人工数据和真实数据上的验证表明,SPCI不仅拥有比资源分布矩阵算法、边集聚系数算法和联合谱聚类算法更高的准确性和模块度,而且可以较为准确地确定社区划分个数。
中图分类号:
[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 |
|