Nature Inspired Algorithms to Solve the Motif-Densest-k-Subgraph Problem

Abstract

Abstract Motif detection is an essential device in the toolbox of researchers who work with interlinked data in the form of graphs. During network analysis, one can look at multiple points of interest, one of which would be a high concentration of certain properties in one part of the graph. Firstly, this paper defines the motif-densest-k-subgraph problem, which consists of finding a subgraph of k nodes that has the maximum number of motifs present. Secondly, it proposes a nature inspired algorithm, namely a genetic algorithm to solve the problem. Numerical experiments were conducted on a wide variety of graphs, and the results are presented to underline the effectiveness of the algorithm.