Computer Science ›› 2019, Vol. 46 ›› Issue (4): 216-221.doi: 10.11896/j.issn.1002-137X.2019.04.034

• Artificial Intelligence • Previous Articles     Next Articles

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

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

CLC Number: 

  • 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] LI Bin, WAN Yuan. Unsupervised Multi-view Feature Selection Based on Similarity Matrix Learning and Matrix Alignment [J]. Computer Science, 2022, 49(8): 86-96.
[2] GUO Yi-shan, LIU Man-dan. Anomaly Detection Based on Spatial-temporal Trajectory Data [J]. Computer Science, 2021, 48(6A): 213-219.
[3] LI Peng, LIU Li-jun, HUANG Yong-dong. Landmark-based Spectral Clustering by Joint Spectral Embedding and Spectral Rotation [J]. Computer Science, 2021, 48(6A): 220-225.
[4] ZHOU Bo. Bipartite Network Recommendation Algorithm Based on Semantic Model [J]. Computer Science, 2020, 47(11A): 482-485.
[5] LIU Shu-dong, WEI Jia-min. Multilayer Perceptron Classification Algorithm Based on Spectral Clusteringand Simultaneous Two Sample Representation [J]. Computer Science, 2019, 46(11A): 194-198.
[6] ZHOU Bo. Research on Relationship Between Bipartite Network Recommendation Algorithm and Collaborative Filtering Algorithm [J]. Computer Science, 2019, 46(11A): 163-166.
[7] DAI Cai-yan, CHEN Ling, HU Kong-fa. Algorithm for Mining Bipartite Network Based on Incremental Modularity [J]. Computer Science, 2018, 45(6A): 442-446.
[8] WANG Ying and YANG Yu-wang. KNN Similarity Graph Algorithm Based on Heap and Neighborhood Coexistence [J]. Computer Science, 2018, 45(5): 196-200.
[9] CHANG Jia-wei, DAI Mu-hong. Personalized Recommendation Algorithm Based on PageRank and Spectral Method [J]. Computer Science, 2018, 45(11A): 398-401.
[10] LI Peng-qing, LI Yang-ding, DENG Xue-lian, LI Yong-gang, FANG Yue. Spectral Clustering Algorithm Based on SimRank Score [J]. Computer Science, 2018, 45(11A): 458-461.
[11] CHEN Jun-fen, ZHANG Ming, HE Qiang. Heuristically Determining Cluster Numbers Based NJW Spectral Clustering Algorithm [J]. Computer Science, 2018, 45(11A): 474-479.
[12] WANG Ping-xin, LIU Qiang, YANG Xi-bei and MI Ju-sheng. Three-way Clustering Analysis Based on Dynamic Neighborhood [J]. Computer Science, 2018, 45(1): 62-66.
[13] LI Jin-ze, XU Xi-rong, PAN Zi-qi and LI Xiao-jie. Improved Adaptive Spectral Clustering NJW Algorithm [J]. Computer Science, 2017, 44(Z6): 424-427.
[14] ZOU Ling-jun, CHEN Ling and DAI Cai-yan. Detecting Community from Bipartite Network Based on Generalized Suffix Tree [J]. Computer Science, 2017, 44(7): 221-226.
[15] LI Xiao-lun and DING Zhi-jun. Group Travel Trip Recommendation Method in LBSNs [J]. Computer Science, 2017, 44(6): 199-205.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!