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

Xiaochen He; Yang Wang; Haifeng Du; Marcus W Feldman

doi:10.1371/journal.pone.0280506

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

PLoS One. 2023 Jan 20;18(1):e0280506. doi: 10.1371/journal.pone.0280506. eCollection 2023.

Authors

Xiaochen He¹, Yang Wang¹, Haifeng Du¹, Marcus W Feldman²

Affiliations

¹ Center for Administration and Complexity Science of Xi'an Jiaotong University, Xi'an, Shaanxi Province, China.
² Morrison Institute for Population and Resource Studies, Stanford University, Stanford, CA, United States of America.

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.

Copyright: © 2023 He et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Algorithms*
Models, Theoretical*

Grants and funding

This work was supported by the National Natural Science Foundation of China (grant numbers: 72104194 (XH) and 72004177 (YW), https://www.nsfc.gov.cn/), by the Key Project of the National Social Science Foundation of China (HD) (Grant no. 21AGL028, http://www.nopss.gov.cn/), and by the Fundamental Research Funds for the Central Universities (XH) (grant number: SK2021003, http://skc.xjtu.edu.cn/index.htm). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript. There was no additional external funding received for this study.