Computer Science ›› 2021, Vol. 48 ›› Issue (11A): 236-243.doi: 10.11896/jsjkx.210300205

• Big Data & Data Science • Previous Articles     Next Articles

Community Mining Based on KL-Ball

LOU Zheng-zheng, WANG Guan-wei, LI Hui, WU Yun-peng   

  1. School of Information Engineering,Zhengzhou University,Zhengzhou 450001,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:LOU Zheng-zheng,born in 1984,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include machine learning,pattern recognition and compute.
    WU Yun-peng,born in 1987,Ph.D,lecturer.His main research interests include computer vision and pattern re-cognition.
  • Supported by:
    National Natural Science Foundation of China(62002330).

Abstract: This paper presents a new community mining method where each community is viewed as a KL-Ball,and the KL divergence is adopted to measure the distance between nodes in the sparse adjacency matrix.This paper defines the KL-Ball consisting of four aspects:center,radius,mutual information and density.The center determines the location of KL-Ball in the complex network,and the radius determines the region of KL-Ball.The mutual information is used to measure the consistency of objects in a community,and the density is adopted to measure the coherence of a community.Given a radius,we aim to find communities with lower-information and higher-density in the complex network.For this purpose,we define the community mining objective function based on KL-Ball.Then we propose an optimization algorithm to minimize the objective function and theoretically prove the convergence of it.The proposed algorithm adopts a flexible community mining framework,and can be applied to several kinds of community mining tasks based on different locations and regions of the KL-Balls,such as the traditional community mining,high precision community mining and overlapping community detection.The experiment results show that the proposed KL-Ball based method can effectively find the community structure in complex network,including non-overlapping and overlapping communities.

Key words: Community mining, KL divergence, Non-overlapping community, Overlapping community

CLC Number: 

  • TP391
[1]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.
[2]LIU D Y,JIN D,HE D X,et al.Community Mining in ComplexNetworks[J].Journal of Computer Research and Development,2013,50(10):2140-2154.
[3]COSCIA M,GIANNOTTI F,PEDRESCHI D.A classificationfor community discovery methods in complex networks[J].Statistical Analysis and Data Mining:The ASA Data Science Journal,2011,4(5):512-546.
[4]RADICCHI F,CASTELLANO C,CECCONI F,et al.Defining and identifying communities in networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(9):2658-2663.
[5]FORTUNATO S.Community detection in graphs[J].PhysicsReports,2010,486(3/4/5):75-174.
[6]YANG B,CHEUNG W,LIU J.Community mining from signed social networks[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(10):1333-1348.
[7]LIBEN-NOWELLY D,KLEINBERG J.The link predictionproblem for social networks[C]//Proceedings of the Twelfth International Conference on Information and Knowledge Mana-gement(CIKM).2004,556-559.
[8]YANG N,GONG D Z,LI X,et al.Survey of Web Communities Identification[J].Journal of Computer Research and Development,2005(3):439-447.
[9]SRIVASTAVA J,COOLEY R,DESHPANDE M,et al.Web usage mining:Discovery and applications of usage patterns from web data[J].Acm Sigkdd Explorations Newsletter,2000,1(2):12-23.
[10]BENSON A R,GLEICH D F,LESKOVEC J.Higher-order or-ganization of complex networks[J].Science,2016,353(6295):163.
[11]YIN D W,HONG L J,XIONG X,et al.Link formation analysisin microblogs[C]//Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval (SIGIR 11).Beijing,China:ACM Press,2011:1235-126.
[12]NEWMAN M E J.Communities,modules and large-scale structure in networks[J].Nature Physics,2012(8):225-31.
[13]NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E,2004,69(6):066133.
[14]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical Review E,2004,70(6):066111.
[15]NEWMAN M E J.The structure and function of complex net-works[J].SIAM Review,2003,45(2):167-256.
[16]PALLA G,DERENYI L,FARKAS L,et al.Uncovering theoverlapping community structure of complex networks in nature and society[J].Nature,2005,435(9):814-818.
[17]BAUMES J.Efficient identification of overlapping communities[C]//Proc of IEEE International Conference on Intelligence and Security Informations.2005:27-36.
[18]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detecting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015.
[19]COVER T M,THOMAS J A.Elements of information theory [M].John Wiley & Sons.2012.
[20]TELGARSKY M,VATTANI A.Hartigan's Method:k-means clustering without voronoi[C]//International Conference on Artificial Intelligence and Statistics.2010:820-827.
[21]SLONIM N,AHARONI E,CRAMMER K.Hartigan's k-means versus Lloyd's k-means:is it time for a change?[C]//Proceedings of the International Joint Conference on Artificial Intelligence.2013:1677-1684.
[22]ZACHARY W W.An information flow model for conflict andfission in small groups[J].Journal of Anthropological Research,1977,33:452-473.
[23]NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E,2004,69 (6):066133.
[24]NEWMAN M E J.Modularity and community structure in networks[J].Proceedings of the national academy of sciences,2006,103(23):8577-8582.
[25]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics,2008,2008(10):155-168.
[26]RAGHAVAN U N,ALBERT R,KUMARA S.Near LinearTime Algorithm to Detect Community Structures in Large-scale Networks[J].Phys Rev E,2007,76(3):036106.
[27]LEE C,REID F,MCDAID A,et al.Detecting highly overlapping community structure by greedy clique expansion[C]//Proceedings Of the 4th SNA-KDD Workshop on Social Network Mining and Analysis.Washington,DC,USA,2010:33-42.
[28]EVANS T,LAMBIOTTE R.Line Graphs,Link Partitions and Overlapping Communities[J].Physical Review E,2009,80(1):16105.
[29]WHANG J J,DHILLON I S,GLEICH D F.Non-exhaustive,overlapping k-means[C]//Proceedings of the 2015 SIAM International Conference on Data Mining,Society for Industrial and Applied Mathematics.2015:936-944.
[30]KOUNI I B E,KAROUI W,ROMDHANE L B.Node Importance based Label Propagation Algorithm for overlapping community detection in networks[J].Expert Systems with Applications,2019,162:113020.
[31]ZHANG Q,CHEN H M,FENG Y F.Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model[J].Computer Science,2020,47(10):75-82.
[32]XUE L,TANG X Q.Algorithm for Detecting Overlapping Communities Based on Centered Cliques[J].Computer Science,2020,47(8):157-163.
[33]WANG Y,BU Z,YANG H,et al.An effective and scalable overlapping community detection approach:Integrating social identity model and game theory[J].Applied Mathematics and Computation,2021,390:125601.
[34]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms[J].Physical Review E,2008,78(4):46-61.
[35]LUSSEAU D,NEWMAN M E J.Identifying the role that animals play in their social networks[J].Proceedings of the Royal Society of London.Series B:Biological Sciences,2004,271(suppl_6):S477-S481.
[36]NEWMAN M E J.Network Data[EB/OL].[2013-04-19].http://www-personal.umich.edu/~mejn/netdata/.
[37]MCDAID A F,GREENE D,HURLEY N.Normalized mutual information to evaluate overlapping community finding algorithms[J].arXiv:1110.2515,2011.
[38]COSCIA M,ROSSETTI G,GIANNOTTI F,et al.Demon:a local-first discovery method for overlapping communities[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2012:615-623.
[1] CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure [J]. Computer Science, 2021, 48(9): 244-250.
[2] NING Yi-xin, XIE Hui, JIANG Huo-wen. Survey of Graph Neural Network in Community Detection [J]. Computer Science, 2021, 48(11A): 11-16.
[3] XUE Lei, TANG Xu-qing. Algorithm for Detecting Overlapping Communities Based on Centered Cliques [J]. Computer Science, 2020, 47(8): 157-163.
[4] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Density Peaks [J]. Computer Science, 2020, 47(5): 72-78.
[5] WANG Shuai-hui, HU Gu-yu, PAN Yu, ZHANG Zhi-yue, ZHANG Hai-feng, PAN Zhi-song. Community Detection in Signed Networks with Game Theory [J]. Computer Science, 2020, 47(11A): 449-453.
[6] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model [J]. Computer Science, 2020, 47(10): 75-82.
[7] LIU Chun, ZHANG Guo-liang. Software Feature Extraction Method Based on Overlapping Community Detection [J]. Computer Science, 2019, 46(12): 201-207.
[8] FU Li-dong, LI Dan, LI Zhan-li. Following-degree Tree Algorithm to Detect Overlapping Communities in Complex Networks [J]. Computer Science, 2019, 46(12): 322-326.
[9] FENG Yun-fei, CHEN Hong-mei. Topological Structure Based Density Peak Algorithm for Overlapping Community Detection [J]. Computer Science, 2019, 46(10): 39-48.
[10] ZHANG Zhong-zheng and LI Jian-wu. Parallelizable Overlapping Community Detection Algorithm Based on Local Expansion [J]. Computer Science, 2016, 43(9): 61-65.
[11] CHAI Xu-qing and DONG Yong-liang. Efficient k-Clique Mining Algorithm in Large-scale Networks [J]. Computer Science, 2016, 43(5): 265-268.
[12] LIU Bing-yu, WANG Cui-rong, WANG Cong and YUAN Ying. Overlapping Community Recognition Algorithm of Weighted Networks Based on Gravity Factor [J]. Computer Science, 2016, 43(12): 153-157.
[13] YANG Xu-hua and ZHOU Shi-jie. Double Layers Routing Algorithm on Large Road Networks Based on Overlapping Communities Detecting [J]. Computer Science, 2015, 42(Z6): 285-289.
[14] NI Han and BAI Qing-yuan. Research of Post-processing of FN Algorithm Results in Social Networking [J]. Computer Science, 2015, 42(6): 256-261.
[15] LI Li-jie,CHEN Duan-bing and WANG Guan-nan. Fast Algorithm for Overlapping Community Detection in Directed Networks [J]. Computer Science, 2014, 41(Z6): 258-261.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!