Important subgraph discovery using non-dominance criterion

Abstract

Методам аналізу графів приділяли багато уваги для виявлення важливих підграфів на основі певних критеріїв. Ці методи стають все більш важливими через зростання кількості програм, які використовують дані на основі графіків. Деякі приклади: (І) аналіз даних мікроматриць у біоінформатиці, (ІІ) аналіз транспортних мереж, (ІІІ) аналіз соціальних мереж. У цьому дослідженні пропонується алгоритм декомпозиції графа з використанням критерію недомінування для визначення важливих підграфів на основі двох характеристик: реберної зв’язності та діаметра. Запропонований метод використовує підхід багатоцільової оптимізації для максимізації зв’язності ребер і мінімізації діаметра. Подібно ідентифікація спільнот у мережі може покращити наше розуміння характеристик і властивостей мережі. Як наслідок, було детально вивчено виявлення структур спільноти в мережах. У статті подано інноваційний метод виявлення спільноти, заснований на запропонованому підході. Ефективність запропонованого метода перевіряється як на реальних, так і на синтетично згенерованих наборах даних.

Graph mining techniques have received a lot of attention to discover important subgraphs based on certain criteria. These techniques have become increasingly important due to the growing number of applications that rely on graph-based data. Some examples are: (I) microarray data analysis in bioinformatics, (III) transportation network analysis, (III) social network analysis. In this study, we propose a graph decomposition algorithm using the non-dominance criterion to identify important subgraphs based on two characteristics: edge connectivity and diameter. The proposed method uses a multi-objective optimization approach to maximize the edge connectivity and minimize the diameter. In a similar vein, identifying communities within a network can improve our comprehension of the network's characteristics and properties. Therefore, the detection of community structures in networks has been extensively studied. As a result, in this paper an innovative community detection method is presented based on our approach. The performance of the proposed technique is examined on both real-life and synthetically generated data sets.