ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Multi-strategy ant colony algorithm for solving the maximum clique problem based on Spark

  • 1.

    School of Artificial Intelligence, Hebei University of Technology, Tianjin 300401, China

  • 2.

    Hebei Province Key Laboratory of Big Data Computing, Tianjin 300401, China

  • 3.

    School of Information Engineering, Tianjin University of Commerce, Tianjin 300134, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2019.10.011
  • Received Date: 28 May 2018
  • Accepted Date: 18 September 2018
  • Rev Recd Date: 18 September 2018
  • Publish Date: 31 October 2019
    Abstract

  • Abstract

    Social network analysis has become one of the hotspots in data mining research. Aggregating subgroups are important indicators for measuring the structure of social networks. The maximum clique structure is the most compact condensed subgroup in social networks. The study of the maximum clique problem has also become an important angle of social network analysis. With the development of big data, the massiveness of the nodes and the complexity of the edge structure in the graph put forward a higher requirement for solving the maximum clique problem. Therefore, a multi-strategy ant colony algorithm is proposed for solving the maximum clique problem first, the algorithm uses a multi-conditional selection strategy to expand the search space, increases the diversity of feasible solutions, and avoids falling into the local optimal solution. At the same time, a local search strategy is adopted to improve the accuracy and convergence speed of the algorithm; Then, the algorithm is implemented in parallel on the Spark distributed platform, which verifies the parallelism of the algorithm and improves the efficiency of the algorithm in handling large-scale community networks.

    Abstract

    Social network analysis has become one of the hotspots in data mining research. Aggregating subgroups are important indicators for measuring the structure of social networks. The maximum clique structure is the most compact condensed subgroup in social networks. The study of the maximum clique problem has also become an important angle of social network analysis. With the development of big data, the massiveness of the nodes and the complexity of the edge structure in the graph put forward a higher requirement for solving the maximum clique problem. Therefore, a multi-strategy ant colony algorithm is proposed for solving the maximum clique problem first, the algorithm uses a multi-conditional selection strategy to expand the search space, increases the diversity of feasible solutions, and avoids falling into the local optimal solution. At the same time, a local search strategy is adopted to improve the accuracy and convergence speed of the algorithm; Then, the algorithm is implemented in parallel on the Spark distributed platform, which verifies the parallelism of the algorithm and improves the efficiency of the algorithm in handling large-scale community networks.
    • FullText(HTML)
  • loading
    • References(24)
  • [1]
    邵娜娜. 蚁群算法求解最大团问题研究与应用[D].河北工业大学,2015.
    SHAO Nana. Research and application of ant colony algorithm for the maximum clique problem[D]. Hebei university of technology, 2015.
    [2]
    WU D, SCHAEFER D, ROSEN D W. Cloud-based design and manufacturing systems: A social network analysis[C]// International Conference on Engineering Design. Seoul, Korea: ACM, 2013: 1-10.
    [3]
    FADIGAS I S, PEREIRA H B B. A network approach based on cliques[J]. Physica A: Statistical Mechanics & Its Applications, 2013, 392(10): 2576-2587.
    [4]
    ARULSELVAN A, BAOURAKIS G, BOGINSKI V, et al. Analysis of food industry market using network approaches[J]. British Food Journal, 2013, 110(9): 916-928.
    [5]
    WANG P, LIN H T, WANG T S. An improved ant colony system algorithm for solving the IP traceback problem[J]. Information Sciences, 2016, 326(1): 172-187.
    [6]
    XU B, MIN H. Solving minimum constraint removal (MCR) problem using a social-force-model-based ant colony algorithm[J]. Applied Soft Computing, 2016, 43(6): 553-560.
    [7]
    徐永成, 陈崚. 基于蚁群优化的二分网络社区挖掘[J]. 计算机科学与探索, 2014, 8(3): 296-304.
    XU Yongcheng, CHEN Ling. Community detection on bipartite networks based on ant colony optimization [J]. Journal of Frontiers of Computer Science & Technology, 2014, 8(3): 296-304.
    [8]
    WU Q, HAO J K. A review on algorithms for maximum clique problems[J]. European Journal of Operational Research, 2015, 242(3): 693-709.
    [9]
    支志兵, 宁爱兵, 陈吉珍, 等. 最大团问题的加权分治算法[J]. 计算机工程与应用, 2016, 52(2): 50-53.
    ZHI Zhibing, NING Aibing, CHEN Jizhen, et al. Measure and conquer approach for maximum clique problem[J]. Computer Engineering and Applications, 2016, 52(2): 50-53.
    [10]
    ARI A A A, DAMAKOA I, TITOUNA C, et al. Efficient and scalable ACO-based task scheduling for green cloud computing environment[C]// IEEE International Conference on Smart Cloud. New York, USA: IEEE, 2017: 66-71.
    [11]
    SITARZ P, POWAKA B. Modal parameters estimation using ant colony optimisation algorithm[J]. Mechanical Systems and Signal Processing, 2016, 76(8): 531-554.
    [12]
    王辉，王景良，朱龙彪，等.基于改进蚁群算法的泊车系统路径规划[J]. 控制工程，2018, 25(2): 53-58.
    WANG Hui, WANG Jingliang, ZHU Longbiao, et al. Path planning of parking system based on improved ant colony algorithm[J]. Control Engineering of China, 2018, 25(2): 53-58.
    [13]
    FENET S, SOLNON C. Searching for maximum cliques with ant colony optimization[J]. Applications of Evolutionary Computing Proceedings of Evoworkshops Evocop Evoiasp Evostim, 2003, 2611(4): 236-245.
    [14]
    SOLNON C, FENET S. A study of ACO capabilities for solving the maximum clique[J]. Journal of Heuristics, 2006, 12(3): 155-180.
    [15]
    XU X, MA J, LEI J. An improved ant colony optimization for the maximum clique problem[C]// Third International Conference on Natural Computation ICNC. Haikou, China: IEEE, 2007: 766-770.
    [16]
    王会颖, 耿家礼. 基于蚁群算法求解最大团问题[J]. 计算机应用与软件, 2010, 27(10): 107-113.
    WANG Huiying, GENG Jiali. Solving maximum clique problem on ant colony optimization[J]. Computer Application and Software, 2010, 27(10): 107-113.
    [17]
    LIU Lei, WANG Shaoqiang. An improved ant colony optimization algorithm using local pheromone and global pheromone updating rule[C]// International Conference on Intelligent Transportation, Big Data & Smart City.Changsha, China: IEEE Computer Society, 2016: 63-67.
    [18]
    SOLEIMANI-POURI M, REZVANIAN A, MEYBODI M R. Finding a maximum clique using ant colony optimization and particle swarm optimization in social networks[C]// Proceedings of the 2012 international conference on advances in social networks analysis and mining ASONAM. Washington, USA: IEEE Computer Society, 2012: 58-61.
    [19]
    夏卫雷, 王立松. 基于MapReduce的并行蚁群算法研究与实现[J]. 电子科技,2013, 26(2): 146-149.
    XIA Weilei, WANG Lisong. Research on and Implementation of parallel ant colony algorithm based on MapReduce[J]. Electronic Science and Technology, 2013, 26(2): 146-149.
    [20]
    王诏远, 李天瑞, 易修文. 基于MapReduce的蚁群优化算法实现方法[J]. 计算机科学, 2014, 41(7): 261-265.
    WANG Zhaoyuan, LI Tianrui, YI Xiuwen. Approach for development of ant colony optimization based on MapReduce[J]. Computer Science, 2014, 41(7): 261-265.
    [21]
    王诏远, 王宏杰, 邢焕来, 等. 基于Spark的蚁群优化算法[J]. 计算机应用, 2015, 35(10): 2777-2780, 2797.
    WANG Zhaoyuan, WANG Hongjie, XING Huanlai, et al. Ant colony optimization algorithm based on Spark[J]. Journal of Computer Applications, 2015, 35(10): 2777-2780, 2797.
    [22]
    DONG G, FU X, LI H, et al. Cooperative ant colony-genetic algorithm based on Spark[J]. Computers & Electrical Engineering, 2017, 60(C): 66-75.
    [23]
    LIU Tiantian, FANG Zhiyi, ZHAO Chen, et al. Parallelization of a series of extreme learning machine algorithms based on Spark[C]// 15th International Conference on Computer and Information Science. Okayama, Japan: IEEE, 2016: 1-5.
    [24]
    JING W, HUO S, MIAO Q, et al. A model of parallel mosaicking for massive remote sensing images based on Spark[J]. IEEE Access, 2017, 5(99): 18229-18237.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    Get Citation
    PDF
    XML
    [1]
    邵娜娜. 蚁群算法求解最大团问题研究与应用[D].河北工业大学,2015.
    SHAO Nana. Research and application of ant colony algorithm for the maximum clique problem[D]. Hebei university of technology, 2015.
    [2]
    WU D, SCHAEFER D, ROSEN D W. Cloud-based design and manufacturing systems: A social network analysis[C]// International Conference on Engineering Design. Seoul, Korea: ACM, 2013: 1-10.
    [3]
    FADIGAS I S, PEREIRA H B B. A network approach based on cliques[J]. Physica A: Statistical Mechanics & Its Applications, 2013, 392(10): 2576-2587.
    [4]
    ARULSELVAN A, BAOURAKIS G, BOGINSKI V, et al. Analysis of food industry market using network approaches[J]. British Food Journal, 2013, 110(9): 916-928.
    [5]
    WANG P, LIN H T, WANG T S. An improved ant colony system algorithm for solving the IP traceback problem[J]. Information Sciences, 2016, 326(1): 172-187.
    [6]
    XU B, MIN H. Solving minimum constraint removal (MCR) problem using a social-force-model-based ant colony algorithm[J]. Applied Soft Computing, 2016, 43(6): 553-560.
    [7]
    徐永成, 陈崚. 基于蚁群优化的二分网络社区挖掘[J]. 计算机科学与探索, 2014, 8(3): 296-304.
    XU Yongcheng, CHEN Ling. Community detection on bipartite networks based on ant colony optimization [J]. Journal of Frontiers of Computer Science & Technology, 2014, 8(3): 296-304.
    [8]
    WU Q, HAO J K. A review on algorithms for maximum clique problems[J]. European Journal of Operational Research, 2015, 242(3): 693-709.
    [9]
    支志兵, 宁爱兵, 陈吉珍, 等. 最大团问题的加权分治算法[J]. 计算机工程与应用, 2016, 52(2): 50-53.
    ZHI Zhibing, NING Aibing, CHEN Jizhen, et al. Measure and conquer approach for maximum clique problem[J]. Computer Engineering and Applications, 2016, 52(2): 50-53.
    [10]
    ARI A A A, DAMAKOA I, TITOUNA C, et al. Efficient and scalable ACO-based task scheduling for green cloud computing environment[C]// IEEE International Conference on Smart Cloud. New York, USA: IEEE, 2017: 66-71.
    [11]
    SITARZ P, POWAKA B. Modal parameters estimation using ant colony optimisation algorithm[J]. Mechanical Systems and Signal Processing, 2016, 76(8): 531-554.
    [12]
    王辉，王景良，朱龙彪，等.基于改进蚁群算法的泊车系统路径规划[J]. 控制工程，2018, 25(2): 53-58.
    WANG Hui, WANG Jingliang, ZHU Longbiao, et al. Path planning of parking system based on improved ant colony algorithm[J]. Control Engineering of China, 2018, 25(2): 53-58.
    [13]
    FENET S, SOLNON C. Searching for maximum cliques with ant colony optimization[J]. Applications of Evolutionary Computing Proceedings of Evoworkshops Evocop Evoiasp Evostim, 2003, 2611(4): 236-245.
    [14]
    SOLNON C, FENET S. A study of ACO capabilities for solving the maximum clique[J]. Journal of Heuristics, 2006, 12(3): 155-180.
    [15]
    XU X, MA J, LEI J. An improved ant colony optimization for the maximum clique problem[C]// Third International Conference on Natural Computation ICNC. Haikou, China: IEEE, 2007: 766-770.
    [16]
    王会颖, 耿家礼. 基于蚁群算法求解最大团问题[J]. 计算机应用与软件, 2010, 27(10): 107-113.
    WANG Huiying, GENG Jiali. Solving maximum clique problem on ant colony optimization[J]. Computer Application and Software, 2010, 27(10): 107-113.
    [17]
    LIU Lei, WANG Shaoqiang. An improved ant colony optimization algorithm using local pheromone and global pheromone updating rule[C]// International Conference on Intelligent Transportation, Big Data & Smart City.Changsha, China: IEEE Computer Society, 2016: 63-67.
    [18]
    SOLEIMANI-POURI M, REZVANIAN A, MEYBODI M R. Finding a maximum clique using ant colony optimization and particle swarm optimization in social networks[C]// Proceedings of the 2012 international conference on advances in social networks analysis and mining ASONAM. Washington, USA: IEEE Computer Society, 2012: 58-61.
    [19]
    夏卫雷, 王立松. 基于MapReduce的并行蚁群算法研究与实现[J]. 电子科技,2013, 26(2): 146-149.
    XIA Weilei, WANG Lisong. Research on and Implementation of parallel ant colony algorithm based on MapReduce[J]. Electronic Science and Technology, 2013, 26(2): 146-149.
    [20]
    王诏远, 李天瑞, 易修文. 基于MapReduce的蚁群优化算法实现方法[J]. 计算机科学, 2014, 41(7): 261-265.
    WANG Zhaoyuan, LI Tianrui, YI Xiuwen. Approach for development of ant colony optimization based on MapReduce[J]. Computer Science, 2014, 41(7): 261-265.
    [21]
    王诏远, 王宏杰, 邢焕来, 等. 基于Spark的蚁群优化算法[J]. 计算机应用, 2015, 35(10): 2777-2780, 2797.
    WANG Zhaoyuan, WANG Hongjie, XING Huanlai, et al. Ant colony optimization algorithm based on Spark[J]. Journal of Computer Applications, 2015, 35(10): 2777-2780, 2797.
    [22]
    DONG G, FU X, LI H, et al. Cooperative ant colony-genetic algorithm based on Spark[J]. Computers & Electrical Engineering, 2017, 60(C): 66-75.
    [23]
    LIU Tiantian, FANG Zhiyi, ZHAO Chen, et al. Parallelization of a series of extreme learning machine algorithms based on Spark[C]// 15th International Conference on Computer and Information Science. Okayama, Japan: IEEE, 2016: 1-5.
    [24]
    JING W, HUO S, MIAO Q, et al. A model of parallel mosaicking for massive remote sensing images based on Spark[J]. IEEE Access, 2017, 5(99): 18229-18237.
    Recommended articles
    TrendMD
    Volume 49 Issue 10 page: 851-860
    Cover

    Article Metrics

    Article views (36) PDF downloads(122)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return