A Swap-Based Heuristic Algorithm for the Maximum k-Plex Problem

Sun Yuan Hsieh; Shih Shun Kao; Yu Sheng Lin

doi:10.1109/ACCESS.2019.2934470

A Swap-Based Heuristic Algorithm for the Maximum k-Plex Problem

Sun Yuan Hsieh, Shih Shun Kao, Yu Sheng Lin

Research output: Contribution to journal › Article › peer-review

Abstract

The maximum k-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 k-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.

Original language	English
Article number	8794502
Pages (from-to)	110267-110278
Number of pages	12
Journal	IEEE Access
Volume	7
DOIs	https://doi.org/10.1109/ACCESS.2019.2934470
Publication status	Published - 2019

All Science Journal Classification (ASJC) codes

Computer Science(all)
Materials Science(all)
Engineering(all)

Access to Document

10.1109/ACCESS.2019.2934470

Fingerprint Dive into the research topics of 'A Swap-Based Heuristic Algorithm for the Maximum k-Plex Problem'. Together they form a unique fingerprint.

Cite this

@article{d3f1e78d0ea14a68afce682c9fbe8031,

title = "A Swap-Based Heuristic Algorithm for the Maximum k-Plex Problem",

abstract = "The maximum k-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 k-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. ",

author = "Hsieh, {Sun Yuan} and Kao, {Shih Shun} and Lin, {Yu Sheng}",

year = "2019",

doi = "10.1109/ACCESS.2019.2934470",

language = "English",

volume = "7",

pages = "110267--110278",

journal = "IEEE Access",

issn = "2169-3536",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A Swap-Based Heuristic Algorithm for the Maximum k-Plex Problem

AU - Hsieh, Sun Yuan

AU - Kao, Shih Shun

AU - Lin, Yu Sheng

PY - 2019

Y1 - 2019

N2 - The maximum k-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 k-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.

AB - The maximum k-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 k-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.

UR - http://www.scopus.com/inward/record.url?scp=85097371482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85097371482&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2019.2934470

DO - 10.1109/ACCESS.2019.2934470

M3 - Article

AN - SCOPUS:85097371482

VL - 7

SP - 110267

EP - 110278

JO - IEEE Access

JF - IEEE Access

SN - 2169-3536

M1 - 8794502

ER -