A memetic algorithm for finding multiple subgraphs that optimally cover an input network.

Abstract

Finding dense subgraphs is a central problem in graph mining, with a variety of real-world application domains including biological analysis, financial market evaluation, and sociological surveys. While a series of studies have been devoted to finding subgraphs with maximum density, the problem of finding multiple subgraphs that best cover an input network has not been systematically explored. The present study discusses a variant of the densest subgraph problem and presents a mathematical model for optimizing the total coverage of an input network by extracting multiple subgraphs. A memetic algorithm that maximizes coverage is proposed and shown to be both effective and efficient. The method is applied to real-world networks. The empirical meaning of the optimal sampling method is discussed.