Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking
Network dismantling is one of the important NP-hard problems in the field of social network analysis. It aims to break down networks into many small components of limited size by only removing a small group of nodes. One feasible way is to decycle (eliminating all the cycles) the network first and t...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9446072/ |
| _version_ | 1811273985274413056 |
|---|---|
| author | Xiaobin Rui Fanrong Meng Yahui Chai Zhixiao Wang Philip S. Yu |
| author_facet | Xiaobin Rui Fanrong Meng Yahui Chai Zhixiao Wang Philip S. Yu |
| author_sort | Xiaobin Rui |
| collection | DOAJ |
| description | Network dismantling is one of the important NP-hard problems in the field of social network analysis. It aims to break down networks into many small components of limited size by only removing a small group of nodes. One feasible way is to decycle (eliminating all the cycles) the network first and then break the acyclic graph. However, existing decycling-based algorithms mainly concentrate on the decycling step, ignoring the importance of the tree breaking process. Besides, none of the algorithms try to pre-process the network, which may bring improvement in both effectiveness and efficiency. In this paper, we fill these two gaps by proposing a novel network dismantling algorithm that combines skeleton extraction and greedy tree breaking (SEGTB). Network skeleton supports the whole network structure, whose removal would leave a much looser structure and serves as an effective pre-processing for the dismantling problem. The presented tree breaking method is provided with theoretical proofs on its lower bound. Experiments on ten real-world datasets show that our proposed SEGTB algorithm is both effective and efficient, outperforming the state-of-the-art. |
| first_indexed | 2024-04-12T23:09:25Z |
| format | Article |
| id | doaj.art-7451a5f09ffd4838814dd6eae5dd7a1c |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-12T23:09:25Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-7451a5f09ffd4838814dd6eae5dd7a1c2022-12-22T03:12:50ZengIEEEIEEE Access2169-35362021-01-019849228493110.1109/ACCESS.2021.30860999446072Dismantling Networks by Skeleton Extraction and Greedy Tree BreakingXiaobin Rui0Fanrong Meng1Yahui Chai2Zhixiao Wang3https://orcid.org/0000-0002-4256-1477Philip S. Yu4School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, ChinaSchool of Computer Science and Technology, China University of Mining and Technology, Xuzhou, ChinaSchool of Computer Science and Technology, China University of Mining and Technology, Xuzhou, ChinaSchool of Computer Science and Technology, China University of Mining and Technology, Xuzhou, ChinaDepartment of Computer Science, University of Illinois at Chicago, Chicago, IL, USANetwork dismantling is one of the important NP-hard problems in the field of social network analysis. It aims to break down networks into many small components of limited size by only removing a small group of nodes. One feasible way is to decycle (eliminating all the cycles) the network first and then break the acyclic graph. However, existing decycling-based algorithms mainly concentrate on the decycling step, ignoring the importance of the tree breaking process. Besides, none of the algorithms try to pre-process the network, which may bring improvement in both effectiveness and efficiency. In this paper, we fill these two gaps by proposing a novel network dismantling algorithm that combines skeleton extraction and greedy tree breaking (SEGTB). Network skeleton supports the whole network structure, whose removal would leave a much looser structure and serves as an effective pre-processing for the dismantling problem. The presented tree breaking method is provided with theoretical proofs on its lower bound. Experiments on ten real-world datasets show that our proposed SEGTB algorithm is both effective and efficient, outperforming the state-of-the-art.https://ieeexplore.ieee.org/document/9446072/Network dismantlingnetwork skeletonacyclic graphgreedy tree breakingapproximation algorithm |
| spellingShingle | Xiaobin Rui Fanrong Meng Yahui Chai Zhixiao Wang Philip S. Yu Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking IEEE Access Network dismantling network skeleton acyclic graph greedy tree breaking approximation algorithm |
| title | Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking |
| title_full | Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking |
| title_fullStr | Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking |
| title_full_unstemmed | Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking |
| title_short | Dismantling Networks by Skeleton Extraction and Greedy Tree Breaking |
| title_sort | dismantling networks by skeleton extraction and greedy tree breaking |
| topic | Network dismantling network skeleton acyclic graph greedy tree breaking approximation algorithm |
| url | https://ieeexplore.ieee.org/document/9446072/ |
| work_keys_str_mv | AT xiaobinrui dismantlingnetworksbyskeletonextractionandgreedytreebreaking AT fanrongmeng dismantlingnetworksbyskeletonextractionandgreedytreebreaking AT yahuichai dismantlingnetworksbyskeletonextractionandgreedytreebreaking AT zhixiaowang dismantlingnetworksbyskeletonextractionandgreedytreebreaking AT philipsyu dismantlingnetworksbyskeletonextractionandgreedytreebreaking |