Key nodes identification in complex networks based on subnetwork feature extraction
The problem of detecting key nodes in a network (i.e. nodes with the greatest ability to spread an infection) has been studied extensively in the past. Some approaches to key node detection compute node centrality, but there is no formal proof that central nodes also have the greatest spreading capa...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2023-07-01
|
| Series: | Journal of King Saud University: Computer and Information Sciences |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S1319157823001854 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849304537470337024 |
|---|---|
| author | Luyuan Gao Xiaoyang Liu Chao Liu Yihao Zhang Giacomo Fiumara Pasquale De Meo |
| author_facet | Luyuan Gao Xiaoyang Liu Chao Liu Yihao Zhang Giacomo Fiumara Pasquale De Meo |
| author_sort | Luyuan Gao |
| collection | DOAJ |
| description | The problem of detecting key nodes in a network (i.e. nodes with the greatest ability to spread an infection) has been studied extensively in the past. Some approaches to key node detection compute node centrality, but there is no formal proof that central nodes also have the greatest spreading capacity. Other methods use epidemiological models (e.g., the SIR model) to describe the spread of an infection and rely on numerical simulations to find out key nodes; these methods are highly accurate but computationally expensive. To efficiently but accurately detect key nodes, we propose a novel deep learning method called Rank by Graph Convolutional Network, RGCN. Our method constructs a subnetwork around each node to estimate its spreading power; then RGCN applies a graph convolutional network to each subnetwork and the adjacency matrix of the network to learn node embeddings. Finally, a neural network is applied to the node embeddings to detect key nodes. Our RGCN method outperforms state-of-the-art approaches such as RCNN and MRCNN by 11.84% and 13.99%, respectively, when we compare the Kendall’s τ coefficient between the node ranking produced by each method with the true ranking obtained by SIR simulations. |
| format | Article |
| id | doaj-art-3bcdb86ea1d24037a766b0adf36cf2cd |
| institution | Kabale University |
| issn | 1319-1578 |
| language | English |
| publishDate | 2023-07-01 |
| publisher | Springer |
| record_format | Article |
| series | Journal of King Saud University: Computer and Information Sciences |
| spelling | doaj-art-3bcdb86ea1d24037a766b0adf36cf2cd2025-08-20T03:55:41ZengSpringerJournal of King Saud University: Computer and Information Sciences1319-15782023-07-0135710163110.1016/j.jksuci.2023.101631Key nodes identification in complex networks based on subnetwork feature extractionLuyuan Gao0Xiaoyang Liu1Chao Liu2Yihao Zhang3Giacomo Fiumara4Pasquale De Meo5School of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, ChinaSchool of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, China; Corresponding author.School of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, ChinaSchool of Artificial Intelligence, Chongqing University of Technology, Chongqing 401135, ChinaMIFT Department, University of Messina, V.le F. Stagno D’Alcontres, 31, 98166 Messina, ItalyDepartment of Computer Science, University of Messina, V.le F. Stagno D’Alcontres, 31, 98166 Messina, ItalyThe problem of detecting key nodes in a network (i.e. nodes with the greatest ability to spread an infection) has been studied extensively in the past. Some approaches to key node detection compute node centrality, but there is no formal proof that central nodes also have the greatest spreading capacity. Other methods use epidemiological models (e.g., the SIR model) to describe the spread of an infection and rely on numerical simulations to find out key nodes; these methods are highly accurate but computationally expensive. To efficiently but accurately detect key nodes, we propose a novel deep learning method called Rank by Graph Convolutional Network, RGCN. Our method constructs a subnetwork around each node to estimate its spreading power; then RGCN applies a graph convolutional network to each subnetwork and the adjacency matrix of the network to learn node embeddings. Finally, a neural network is applied to the node embeddings to detect key nodes. Our RGCN method outperforms state-of-the-art approaches such as RCNN and MRCNN by 11.84% and 13.99%, respectively, when we compare the Kendall’s τ coefficient between the node ranking produced by each method with the true ranking obtained by SIR simulations.http://www.sciencedirect.com/science/article/pii/S1319157823001854Key nodes identificationComplex networkSubnetwork feature extractionGraph convolutional networks |
| spellingShingle | Luyuan Gao Xiaoyang Liu Chao Liu Yihao Zhang Giacomo Fiumara Pasquale De Meo Key nodes identification in complex networks based on subnetwork feature extraction Journal of King Saud University: Computer and Information Sciences Key nodes identification Complex network Subnetwork feature extraction Graph convolutional networks |
| title | Key nodes identification in complex networks based on subnetwork feature extraction |
| title_full | Key nodes identification in complex networks based on subnetwork feature extraction |
| title_fullStr | Key nodes identification in complex networks based on subnetwork feature extraction |
| title_full_unstemmed | Key nodes identification in complex networks based on subnetwork feature extraction |
| title_short | Key nodes identification in complex networks based on subnetwork feature extraction |
| title_sort | key nodes identification in complex networks based on subnetwork feature extraction |
| topic | Key nodes identification Complex network Subnetwork feature extraction Graph convolutional networks |
| url | http://www.sciencedirect.com/science/article/pii/S1319157823001854 |
| work_keys_str_mv | AT luyuangao keynodesidentificationincomplexnetworksbasedonsubnetworkfeatureextraction AT xiaoyangliu keynodesidentificationincomplexnetworksbasedonsubnetworkfeatureextraction AT chaoliu keynodesidentificationincomplexnetworksbasedonsubnetworkfeatureextraction AT yihaozhang keynodesidentificationincomplexnetworksbasedonsubnetworkfeatureextraction AT giacomofiumara keynodesidentificationincomplexnetworksbasedonsubnetworkfeatureextraction AT pasqualedemeo keynodesidentificationincomplexnetworksbasedonsubnetworkfeatureextraction |