吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (5): 1616-1621.doi: 10.13229/j.cnki.jdxbgxb201605034

Previous Articles     Next Articles

Link clustering method based on maxima and minima non-neighbor link similarity

WANG Gui-shen1,2, HUANG Lan1,2, WANG Yan1,2, SONG Li-ming1,2, OU Ge1,2   

  1. 1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2.Key Laboratory of Symbol Computation and Knowledge Engineering,Ministry of Education, Changchun 130012, China
  • Received:2015-06-20 Online:2016-09-20 Published:2016-09-20

Abstract: Traditional clustering methods can be applied to the research of overlapping community detection directly with link similarity. However, Link Clustering (LC) method does not consider the relationship between non-neighbor links in the calculation of link similarity. In this paper, two link similarity strategies are proposed based on the maxima and minima non-neighbor (MLS) in order to overcome the shortcomings of the original link clustering. The two link similarity strategies consider the minimum and maximum conditions of link similarity relationships. Then, a link clustering method is put forward based on MLS strategies (MLC) with EQ evaluation. Experimental results on three real-world networks show that the proposed MLC method achieves better performance than the original LC method, classical CPM method and Extended Link Clustering (ELC) method under several evaluation criteria.

Key words: artificial intelligence, link clustering, link similarity, overlapping community detection, neighbor links, non-neighbor links

CLC Number: 

  • TP301
[1] Palla G, Derényi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society[J]. Nature, 2005,435(7043):814-818.
[2] Evans T S, Lambiotte R. Line graphs, link partitions, and overlapping communities[J]. Phys Rev E, 2009,80: 016105.
[3] Ahn Y Y, Bagrow J P, Lehmann S. Link communities reveal multi-scale complexity in networks[J]. Nature, 2010, 466(7307):761-764.
[4] Kalinka A T. The generation, visualization, and analysis of link communities in arbitrary networks with the R package linkcomm[J]. Bioinformatics, 2011, 27 (14):2011-2012.
[5] Xie J R, Kelley S, Szymanski B K. Overlapping community detection in networks: the state-of-the-art and comparative study[J]. ACM Comput Surv, 2013, 45(4): 43.
[6] Huang L, Wang G, Wang Y,et al. Link clustering with extended link similarity and EQ evaluation division[J]. PloS One, 2013, 8(6): e66005.
[7] Shi C, Cai Y, Fu D, et al. A link clustering based overlapping community detection algorithm[J]. Data & Knowledge Engineering, 2013, 87: 394-404.
[8] Lim S, Ryu S, Kwon S, et al. LinkSCAN * : overlapping community detection using the link-space transformation[C]∥2014 IEEE 30th International Conference on Data Engineering, Chicago, IL, 2014: 292-303.
[9] He D, Jin D, Baquero C, et al. Link community detection using generative model and nonnegative matrix factorization[J]. PloS One, 2014, 9(1): e86899.
[10] Shen Hua-wei, Cheng Xue-qi, Cai Kai, et al. Detect overlapping and hierarchical community structure in networks[J]. Physica A: Statistical Mechanics and its Applications, 2009, 388(8):1706-1712.
[11] Lancichinetti A, Fortunato S, Kertész J. Detecting the overlapping and hierarchical community structure in complex networks[J]. New Journal of Physics, 2009,11:033015.
[12] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research, 1977, 33(4): 452-473.
[13] Lusseau D, Schneider K, Boisseau O J, et al. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations[J]. Behavioral Ecology and Sociobiology, 2003, 54:396-405.
[14] Newman M E J. Modularity and community structure in networks[J]. Proc Natl Acad Sci, 2006, 103(23):8577-8582.
[15] Newman M. Network collection from Newman M[EB/OL].[2015-11-12]. http://www.cise.ufl.edu/research/sparse/matrices/Newman/polbooks.html.
[1] DONG Sa, LIU Da-you, OUYANG Ruo-chuan, ZHU Yun-gang, LI Li-na. Logistic regression classification in networked data with heterophily based on second-order Markov assumption [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1571-1577.
[2] GU Hai-jun, TIAN Ya-qian, CUI Ying. Intelligent interactive agent for home service [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1578-1585.
[3] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Measurement of graph similarity based on vertical dimension sequence dynamic time warping method [J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4] ZHANG Hao, ZHAN Meng-ping, GUO Liu-xiang, LI Zhi, LIU Yuan-ning, ZHANG Chun-he, CHANG Hao-wu, WANG Zhi-qiang. Human exogenous plant miRNA cross-kingdom regulatory modeling based on high-throughout data [J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5] HUANG Lan, JI Lin-ying, YAO Gang, ZHAI Rui-feng, BAI Tian. Construction of disease-symptom semantic net for misdiagnosis prompt [J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6] LI Xiong-fei, FENG Ting-ting, LUO Shi, ZHANG Xiao-li. Automatic music composition algorithm based on recurrent neural network [J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7] LIU Jie, ZHANG Ping, GAO Wan-fu. Feature selection method based on conditional relevance [J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity [J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[9] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework [J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[10] LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia. Quantum k-means algorithm [J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[11] QU Hui-yan, ZHAO Wei, QIN Ai-hong. A fast collision detection algorithm based on optimization operator [J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[12] LI Jia-fei, SUN Xiao-yu. Clustering method for uncertain data based on spectral decomposition [J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[13] SHAO Ke-yong, CHEN Feng, WANG Ting-ting, WANG Ji-chi, ZHOU Li-peng. Full state based adaptive control of fractional order chaotic system without equilibrium point [J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[14] WANG Sheng-sheng, WANG Chuang-feng, GU Fang-ming. Spatio-temporal reasoning for OPRA direction relation network [J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[15] MA Miao, LI Yi-bin. Multi-level image sequences and convolutional neural networks based human action recognition method [J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] ZHU Jian-feng, LIN Yi, CHEN Xiao-kai, SHI Guo-biao. Structural topology optimization based design of automotive transmission housing structure[J]. 吉林大学学报(工学版), 2013, 43(03): 584 -589 .
[5] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[6] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[7] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[8] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[9] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[10] XIAO Yun, LEI Jun-qing, ZHANG Kun, LI Zhong-san. Fatigue stiffness degradation of prestressed concrete beam under multilevel amplitude cycle loading[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .