A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex Problem
The maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-plex problem is intended to relax the clique definition with maximum cardinality. It helps people understand the structures of networks by considering them a problem of graph cl...
Main Authors: | , , |
---|---|
Format: | Article |
Language: | English |
Published: |
IEEE
2019-01-01
|
Series: | IEEE Access |
Subjects: | |
Online Access: | https://ieeexplore.ieee.org/document/8794502/ |
_version_ | 1818479658066247680 |
---|---|
author | Sun-Yuan Hsieh Shih-Shun Kao Yu-Sheng Lin |
author_facet | Sun-Yuan Hsieh Shih-Shun Kao Yu-Sheng Lin |
author_sort | Sun-Yuan Hsieh |
collection | DOAJ |
description | The maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-plex problem is intended to relax the clique definition with maximum cardinality. It helps people understand the structures of networks by considering them a problem of graph clustering; therefore, it is a useful model for social network analysis. In this paper, we propose a swap-based heuristic algorithm for the maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-plex problem. Starting with a randomly selected solution, we use three types of swap operators to enlarge our current solution in different situations. The results of experiments conducted on various graphs from two benchmarks demonstrated that our proposed algorithm achieved desirable performance on specific graphs compared with other algorithms. |
first_indexed | 2024-12-10T11:13:40Z |
format | Article |
id | doaj.art-841f9ea1535a4b8ba483cb2d4598adea |
institution | Directory Open Access Journal |
issn | 2169-3536 |
language | English |
last_indexed | 2024-12-10T11:13:40Z |
publishDate | 2019-01-01 |
publisher | IEEE |
record_format | Article |
series | IEEE Access |
spelling | doaj.art-841f9ea1535a4b8ba483cb2d4598adea2022-12-22T01:51:18ZengIEEEIEEE Access2169-35362019-01-01711026711027810.1109/ACCESS.2019.29344708794502A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex ProblemSun-Yuan Hsieh0https://orcid.org/0000-0003-4746-3179Shih-Shun Kao1Yu-Sheng Lin2Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, TaiwanDepartment of Computer Science and Information Engineering, National Cheng Kung University, Tainan, TaiwanDepartment of Computer Science and Information Engineering, National Cheng Kung University, Tainan, TaiwanThe maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-plex problem is intended to relax the clique definition with maximum cardinality. It helps people understand the structures of networks by considering them a problem of graph clustering; therefore, it is a useful model for social network analysis. In this paper, we propose a swap-based heuristic algorithm for the maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-plex problem. Starting with a randomly selected solution, we use three types of swap operators to enlarge our current solution in different situations. The results of experiments conducted on various graphs from two benchmarks demonstrated that our proposed algorithm achieved desirable performance on specific graphs compared with other algorithms.https://ieeexplore.ieee.org/document/8794502/Clique relaxationheuristic algorithmsgraph algorithmssocial networksNP-complete |
spellingShingle | Sun-Yuan Hsieh Shih-Shun Kao Yu-Sheng Lin A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex Problem IEEE Access Clique relaxation heuristic algorithms graph algorithms social networks NP-complete |
title | A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex Problem |
title_full | A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex Problem |
title_fullStr | A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex Problem |
title_full_unstemmed | A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex Problem |
title_short | A Swap-Based Heuristic Algorithm for the Maximum <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-Plex Problem |
title_sort | swap based heuristic algorithm for the maximum inline formula tex math notation latex k tex math inline formula plex problem |
topic | Clique relaxation heuristic algorithms graph algorithms social networks NP-complete |
url | https://ieeexplore.ieee.org/document/8794502/ |
work_keys_str_mv | AT sunyuanhsieh aswapbasedheuristicalgorithmforthemaximuminlineformulatexmathnotationlatexktexmathinlineformulaplexproblem AT shihshunkao aswapbasedheuristicalgorithmforthemaximuminlineformulatexmathnotationlatexktexmathinlineformulaplexproblem AT yushenglin aswapbasedheuristicalgorithmforthemaximuminlineformulatexmathnotationlatexktexmathinlineformulaplexproblem AT sunyuanhsieh swapbasedheuristicalgorithmforthemaximuminlineformulatexmathnotationlatexktexmathinlineformulaplexproblem AT shihshunkao swapbasedheuristicalgorithmforthemaximuminlineformulatexmathnotationlatexktexmathinlineformulaplexproblem AT yushenglin swapbasedheuristicalgorithmforthemaximuminlineformulatexmathnotationlatexktexmathinlineformulaplexproblem |