IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v536y2019ics037843711931235x.html
   My bibliography  Save this article

A hybrid iterated carousel greedy algorithm for community detection in complex networks

Author

Listed:
  • Kong, Hanzhang
  • Kang, Qinma
  • Li, Wenquan
  • Liu, Chao
  • Kang, Yunfan
  • He, Hong

Abstract

Community detection remains up to this date a challenging combinatorial optimization problem which has received much attention from various scientific fields in recent years. Since the problem for community detection with modularity maximization is known to be NP-complete, many metaheuristics for finding best-possible solutions within an acceptable computational time have been exploited to tackle this problem. In this paper, a hybrid metaheuristic called iterated carousel greedy (ICG) algorithm is presented for solving community detection problem with modularity maximization. The proposed ICG algorithm generates a sequence of solutions by iterating over a greedy construction heuristic using destruction, carousel and reconstruction phases. A local search procedure with strong intensification is applied to search for a better solution in each iteration. Compared with the traditional iterated greedy (IG) metaheuristic, the improved method employs the carousel greedy procedure between destruction and reconstruction to direct the search towards the better solution space. The experimental results on synthetic and real-world networks show the effectiveness and robustness of the proposed method over the existing methods in the literature.

Suggested Citation

  • Kong, Hanzhang & Kang, Qinma & Li, Wenquan & Liu, Chao & Kang, Yunfan & He, Hong, 2019. "A hybrid iterated carousel greedy algorithm for community detection in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 536(C).
    • Handle: RePEc:eee:phsmap:v:536:y:2019:i:c:s037843711931235x
    DOI: 10.1016/j.physa.2019.122124
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037843711931235X
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2019.122124?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Pan, Quan-Ke & Ruiz, Rubén, 2012. "Local search methods for the flowshop scheduling problem with flowtime minimization," European Journal of Operational Research, Elsevier, vol. 222(1), pages 31-43.
    2. Li, Mingming & Liu, Jing, 2018. "A link clustering based memetic algorithm for overlapping community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 503(C), pages 410-423.
    3. Lozano, M. & Molina, D. & GarcI´a-MartI´nez, C., 2011. "Iterated greedy for the maximum diversity problem," European Journal of Operational Research, Elsevier, vol. 214(1), pages 31-38, October.
    4. Zhang, Weitong & Zhang, Rui & Shang, Ronghua & Li, Juanfei & Jiao, Licheng, 2019. "Application of natural computation inspired method in community detection," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 130-150.
    5. Sun, Hong-liang & Ch’ng, Eugene & Yong, Xi & Garibaldi, Jonathan M. & See, Simon & Chen, Duan-bing, 2018. "A fast community detection method in bipartite networks by distance dynamics," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 496(C), pages 108-120.
    6. Pahwa, S. & Youssef, M. & Schumm, P. & Scoglio, C. & Schulz, N., 2013. "Optimal intentional islanding to enhance the robustness of power grid networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(17), pages 3741-3754.
    7. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    8. Ruiz, Ruben & Stutzle, Thomas, 2008. "An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1143-1159, June.
    9. Pablo M. Gleiser & Leon Danon, 2003. "Community Structure In Jazz," Advances in Complex Systems (ACS), World Scientific Publishing Co. Pte. Ltd., vol. 6(04), pages 565-573.
    10. Hong-Liang Sun & Eugene Ch’ng & Xi Yong & Jonathan M. Garibaldi & Simon See & Duan-Bing Chen, 2017. "An improved game-theoretic approach to uncover overlapping communities," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 28(09), pages 1-17, September.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. García-Martínez, C. & Rodriguez, F.J. & Lozano, M., 2014. "Tabu-enhanced iterated greedy algorithm: A case study in the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 454-463.
    2. Pan, Quan-Ke & Gao, Liang & Li, Xin-Yu & Gao, Kai-Zhou, 2017. "Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times," Applied Mathematics and Computation, Elsevier, vol. 303(C), pages 89-112.
    3. Huerta-Muñoz, Diana L. & Ríos-Mercado, Roger Z. & Ruiz, Rubén, 2017. "An iterated greedy heuristic for a market segmentation problem with multiple attributes," European Journal of Operational Research, Elsevier, vol. 261(1), pages 75-87.
    4. Hatami, Sara & Ruiz, Rubén & Andrés-Romano, Carlos, 2015. "Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times," International Journal of Production Economics, Elsevier, vol. 169(C), pages 76-88.
    5. Brammer, Janis & Lutz, Bernhard & Neumann, Dirk, 2022. "Permutation flow shop scheduling with multiple lines and demand plans using reinforcement learning," European Journal of Operational Research, Elsevier, vol. 299(1), pages 75-86.
    6. Pan, Quan-Ke & Ruiz, Rubén, 2012. "Local search methods for the flowshop scheduling problem with flowtime minimization," European Journal of Operational Research, Elsevier, vol. 222(1), pages 31-43.
    7. Pessoa, Luciana S. & Andrade, Carlos E., 2018. "Heuristics for a flowshop scheduling problem with stepwise job objective function," European Journal of Operational Research, Elsevier, vol. 266(3), pages 950-962.
    8. Marco Pranzo & Dario Pacciarelli, 2016. "An iterated greedy metaheuristic for the blocking job shop scheduling problem," Journal of Heuristics, Springer, vol. 22(4), pages 587-611, August.
    9. Pagnozzi, Federico & Stützle, Thomas, 2019. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 276(2), pages 409-421.
    10. Shirvani, Nargess & Ruiz, Rubén & Shadrokh, Shahram, 2014. "Cyclic scheduling of perishable products in parallel machine with release dates, due dates and deadlines," International Journal of Production Economics, Elsevier, vol. 156(C), pages 1-12.
    11. Sioud, A. & Gagné, C., 2018. "Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 264(1), pages 66-73.
    12. Hesamipour, Sajjad & Balafar, Mohammad Ali, 2019. "A new method for detecting communities and their centers using the Adamic/Adar Index and game theory," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 535(C).
    13. Libralesso, Luc & Focke, Pablo Andres & Secardin, Aurélien & Jost, Vincent, 2022. "Iterative beam search algorithms for the permutation flowshop," European Journal of Operational Research, Elsevier, vol. 301(1), pages 217-234.
    14. Ciavotta, Michele & Minella, Gerardo & Ruiz, Rubén, 2013. "Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study," European Journal of Operational Research, Elsevier, vol. 227(2), pages 301-313.
    15. Pan, Quan-Ke & Ruiz, Rubén, 2014. "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem," Omega, Elsevier, vol. 44(C), pages 41-50.
    16. Xiong, Fuli & Xing, Keyi & Wang, Feng, 2015. "Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time," European Journal of Operational Research, Elsevier, vol. 240(2), pages 338-354.
    17. Sun, Hong-liang & Chen, Duan-bing & He, Jia-lin & Ch’ng, Eugene, 2019. "A voting approach to uncover multiple influential spreaders on weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 519(C), pages 303-312.
    18. Pagnozzi, Federico & Stützle, Thomas, 2021. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems with additional constraints," Operations Research Perspectives, Elsevier, vol. 8(C).
    19. Lin, Shih-Wei & Ying, Kuo-Ching, 2014. "Minimizing shifts for personnel task scheduling problems: A three-phase algorithm," European Journal of Operational Research, Elsevier, vol. 237(1), pages 323-334.
    20. Urlings, Thijs & Ruiz, Rubén & Stützle, Thomas, 2010. "Shifting representation search for hybrid flexible flowline problems," European Journal of Operational Research, Elsevier, vol. 207(2), pages 1086-1095, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:536:y:2019:i:c:s037843711931235x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.