Frequent Itemset-Driven Search for Finding Minimal Node Separators and its Application to Air Transportation Network Analysis

Yangming Zhou, Xiaze Zhang, Na Geng, Zhibin Jiang, Shouguang Wang, Mengchu Zhou

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

The α-separator problem ( α-SP) consists of finding the minimum set of vertices whose removal separates the network into multiple different connected components with fewer than a limited number of vertices in each component, which belongs to the family of critical node detection problems. The α-SP problem is an important NP-hard problem with various real-world applications. In this paper, we propose a frequent itemset-driven search (FIS) algorithm to solve α-SP, which integrates the concept of frequent itemset into the well-known memetic search framework. Starting from a high-quality population built by population construction and population repair, FIS then iteratively employs a frequent itemset recombination operator (to generate promising offspring solution), a tabu-based simulated annealing (to find local optima), a population repair procedure, and a population management strategy (to guarantee healthy/diverse population). Extensive evaluations on 50 benchmark instances show that FIS significantly outperforms the state-of-the-art algorithms. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds. Finally, we experimentally analyze the importance of each key algorithmic component, and perform a case study on an air transportation network for understanding its network structure and identifying its influential airports.

Original languageEnglish (US)
Pages (from-to)8348-8360
Number of pages13
JournalIEEE Transactions on Intelligent Transportation Systems
Volume24
Issue number8
DOIs
StatePublished - Aug 1 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Automotive Engineering
  • Mechanical Engineering
  • Computer Science Applications

Keywords

  • Memetic search
  • critical node detection
  • frequent itemset
  • transportation network
  • α-separator problem

Fingerprint

Dive into the research topics of 'Frequent Itemset-Driven Search for Finding Minimal Node Separators and its Application to Air Transportation Network Analysis'. Together they form a unique fingerprint.

Cite this