کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6895225 1445940 2018 31 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The bi-objective critical node detection problem
ترجمه فارسی عنوان
مسئله تشخیص گره حساس دو هدف
کلمات کلیدی
شبکه های، شناسایی گره انتقادی، چند هدفه، الگوریتمهای تکاملی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی
Identifying critical nodes in complex networks has become an important task across a variety of application domains. The Critical Node Detection Problem (CNDP) is an optimization problem that aims to minimize pairwise connectivity in a graph by removing a subset of K nodes. Despite the CNDP being recognized as a bi-objective problem, until now only single-objective problem formulations have been proposed. In this paper, we propose a bi-objective version of the problem that aims to maximize the number of connected components in a graph while simultaneously minimizing the variance of their cardinalities by removing a subset of K nodes. We prove that our bi-objective formulation is distinct from the CNDP, despite their common motivation. Finally, we give a brief comparison of six common multi-objective evolutionary algorithms using sixteen common benchmark problem instances, including for the node-weighted CNDP. We find that of the examined algorithms, NSGAII generally produces the most desirable approximation fronts.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 265, Issue 3, 16 March 2018, Pages 895-908
نویسندگان
, , ,