A memetic algorithm for finding multiple subgraphs that optimally cover an input network.
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 f...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2023-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://doi.org/10.1371/journal.pone.0280506 |
| _version_ | 1797942900125859840 |
|---|---|
| author | Xiaochen He Yang Wang Haifeng Du Marcus W Feldman |
| author_facet | Xiaochen He Yang Wang Haifeng Du Marcus W Feldman |
| author_sort | Xiaochen He |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T20:15:57Z |
| format | Article |
| id | doaj.art-bc35be80602742a6a11e26339d5def25 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-04-10T20:15:57Z |
| publishDate | 2023-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-bc35be80602742a6a11e26339d5def252023-01-26T05:32:16ZengPublic Library of Science (PLoS)PLoS ONE1932-62032023-01-01181e028050610.1371/journal.pone.0280506A memetic algorithm for finding multiple subgraphs that optimally cover an input network.Xiaochen HeYang WangHaifeng DuMarcus W FeldmanFinding 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.https://doi.org/10.1371/journal.pone.0280506 |
| spellingShingle | Xiaochen He Yang Wang Haifeng Du Marcus W Feldman A memetic algorithm for finding multiple subgraphs that optimally cover an input network. PLoS ONE |
| title | A memetic algorithm for finding multiple subgraphs that optimally cover an input network. |
| title_full | A memetic algorithm for finding multiple subgraphs that optimally cover an input network. |
| title_fullStr | A memetic algorithm for finding multiple subgraphs that optimally cover an input network. |
| title_full_unstemmed | A memetic algorithm for finding multiple subgraphs that optimally cover an input network. |
| title_short | A memetic algorithm for finding multiple subgraphs that optimally cover an input network. |
| title_sort | memetic algorithm for finding multiple subgraphs that optimally cover an input network |
| url | https://doi.org/10.1371/journal.pone.0280506 |
| work_keys_str_mv | AT xiaochenhe amemeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork AT yangwang amemeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork AT haifengdu amemeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork AT marcuswfeldman amemeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork AT xiaochenhe memeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork AT yangwang memeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork AT haifengdu memeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork AT marcuswfeldman memeticalgorithmforfindingmultiplesubgraphsthatoptimallycoveraninputnetwork |