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...

Full description

Bibliographic Details
Main Authors: Sun-Yuan Hsieh, Shih-Shun Kao, Yu-Sheng Lin
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