Computer Science ›› 2016, Vol. 43 ›› Issue (5): 265-268.doi: 10.11896/j.issn.1002-137X.2016.05.050

Previous Articles     Next Articles

Efficient k-Clique Mining Algorithm in Large-scale Networks

CHAI Xu-qing and DONG Yong-liang   

  • Online:2018-12-01 Published:2018-12-01

Abstract: k-clique mining in networks is a basis for most network-based applications.Concerning the problem of low efficiency for mining k-cliques,this paper proposed an efficient k-clique mining algorithm for large-scale networks.Firstly,the problem of finding k-clique with maximal density is transformed to the problem of finding a k-clique whose density is larger than a given density value.Next,a bipartite network,whose left nodes are nodes in the original network and right nodes are k-1 cliques,is constructed,and the k-cliques problem can be solved within polynomial time applying it.In sparse networks,the time and space complexities of the proposed algorithm are O(c2k) and O(ck) respectively.The experiments show that,the proposed algorithm is more accurate and efficient than the best algorithm at present.Moreover,the proposed algorithm can be also applied to mine k-cliques in incomplete networks.

Key words: Community mining,Social networks,k-clique,Incomplete network

[1] Xu Ke,Zhang Sai,Chen Hao,et al.Measurement and analysis of online social network [J].Chinese Journal of Computers,2014,7(1):165-188(in Chinese) 徐恪,张赛,陈昊,等.在线社会网络的测量与分析[J].计算机学报,2014,37(1):165-188
[2] Wang Li,Cheng Su-qi,Shen Hua-wei,et al.Structure inference and prediction in the co-evolution of social network [J].Chinese Journal of Computer Research and Development,2015,0(12):2492-2503(in Chinese) 王莉,程苏琦,沈华伟,等.在线社会网络共演化的结构推断与预测[J].计算机研究与发展,2015,50(12):2492-2503
[3] Lin You-fang,Wang Tian-yu,Tang Rui,et al.An effective mo-del and algorithm community detection in social networks[J].Chinese Journal of Computer Research and Development,2015,9(2):337-345(in Chinese) 林友芳,王天宇,唐锐,等.一种有效的社会网络社区发现模型和算法[J].计算机研究与发展,2015,49(2):337-345
[4] Wang Li,Cheng Xue-qi.Dynamic community in online social net-works[J].Chinese Journal of Computers,2015,8(2):219-237(in Chinese) 王莉,程学旗.在线社会网络的动态社区发现及演化[J].计算机学报,2015,38(2):219-237
[5] Gao Quan-li,Gao Ling,Yang Jian-feng,et al.A preference Eli-citation method based on users’ cognitive behavior for Context-aware recommender system[J].Chinese Journal of Computers,2015,8(9):1767-1776(in Chinese) 高全力,高岭,杨建锋,等.上下文感知推荐系统中基于用户认知行为的偏好获取方法[J].计算机学报,2015,38(9):1767-1776
[6] Wang Li-cai,Meng Xiang-wu,Zhang Yu-jie.Context-aware re-commender systems[J].Journal of Software,2012,3(1):1-20(in Chinese) 王立才,孟祥武,张玉洁.上下文感知推荐系统[J].软件学报,2012,23(1):1-20
[7] Sun Ji-gui,Liu Jie,Zhao Lian-yu.Research on clustering algorithm[J].Journal of Software,2008,9(1):48-61(in Chinese) 孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008,19(1):48-61
[8] Yang Bo,Liu Da-you,Jin Di,et al.Complex network clustering method[J].Journal of Software,2009,0(1):54-66(in Chinese) 杨博,刘大有,金弟,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-66
[9] Chen Ke-han,Han Pan-pan,Wu Jian.User clustering based social network recommendation[J].Chinese Journal of Compu-ters,2013,6(2):349-359(in Chinese) 陈克寒,韩盼盼,吴健.基于用户聚类的异构社交网络推荐算法[J].计算机学报,2013,36(2):349-359
[10] Chiang K Y,Hsieh C J,Natarajan N,et al.Prediction and clustering in signed networks:a local to global perspective[J].The Journal of Machine Learning Research,2014,15(1):1177-1213
[11] Tsourakakis C.The K-clique Densest Subgraph Problem[C]∥Proceedings of the 24th International Conference on World Wide Web.International World Wide Web Conferences Steering Committee.2015:1122-1132
[12] Rossman B.The monotone complexity of k-clique on randomgraphs[J].SIAM Journal on Computing,2014,43(1):256-279
[13] Bahmani B,Kumar R,Vassilvitskii S.Densest subgraph in st-reaming and mapreduce[J].Proceedings of the VLDB Endowment,2012,5(5):454-465
[14] Bhawalkar K,Kleinberg J,Lewi K,et al.Preventing unraveling in social networks:the anchored k-core problem[M]∥Automata,Languages,and Programming.Springer Berlin Heidelberg,2012:440-451
[15] Khuller S,Saha B.On finding dense subgraphs[M]∥Automata,Languages and Programming.Springer Berlin Heidelberg,2009:597-608
[16] Andersen R,Chellapilla K.Finding dense subgraphs with sizebounds[M]∥Algorithms and Models for the Web-Graph.Springer Berlin Heidelberg,2009:25-37
[17] Chiba N,Nishizeki T.Arboricity and subgraph listing algori-thms[J].SIAM Journal on Computing,1985,14(1):210-223
[18] Lee Y T,Sidford A.Path finding methods for linear programming:Solving linear programs in o(vrank) iterations and faster algorithms for maximum flow[C]∥FOCS.2014:424-433

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!