Bridge Node Detection between Communities Based on GNN
In a complex network, some nodes are relatively concentrated in topological structure, thus forming a relatively independent node group, which we call a community. Usually, there are multiple communities on a network, and these communities are interconnected and exchange information with each other....
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-10-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/12/20/10337 |
| _version_ | 1827651845448794112 |
|---|---|
| author | Hairu Luo Peng Jia Anmin Zhou Yuying Liu Ziheng He |
| author_facet | Hairu Luo Peng Jia Anmin Zhou Yuying Liu Ziheng He |
| author_sort | Hairu Luo |
| collection | DOAJ |
| description | In a complex network, some nodes are relatively concentrated in topological structure, thus forming a relatively independent node group, which we call a community. Usually, there are multiple communities on a network, and these communities are interconnected and exchange information with each other. A node that plays an important role in the process of information exchange between communities is called an inter-community bridge node. Traditional methods of defining and detecting bridge nodes mostly quantify the bridging effect of nodes by collecting local structural information of nodes and defining index operations. However, on the one hand, it is often difficult to capture the deep topological information in complex networks based on a single indicator, resulting in inaccurate evaluation results; on the other hand, for networks without community structure, such methods may rely on community partitioning algorithms, which require significant computing power. In this paper, considering the multi-dimensional attributes and structural characteristics of nodes, a deep learning-based framework named BND is designed to quickly and accurately detect bridge nodes. Considering that the bridging function of nodes between communities is abstract and complex, and may be related to the multi-dimensional information of nodes, we construct an attribute graph on the basis of the original graph according to the features of the five dimensions of the node to meet our needs for extracting bridging-related attributes. In the deep learning model, we overlay graph neural network layers to process the input attribute graph and add fully connected layers to improve the final classification effect of the model. Graph neural network algorithms including GCN, GAT, and GraphSAGE are compatible with our proposed framework. To the best of our knowledge, our work is the first application of graph neural network techniques in the field of bridge node detection. Experiments show that our designed framework can effectively capture network topology information and accurately detect bridge nodes in the network. In the overall model effect evaluation results based on indicators such as Accuracy and F1 score, our proposed graph neural network model is generally better than baseline methods. In the best case, our model has an Accuracy of 0.9050 and an F1 score of 0.8728. |
| first_indexed | 2024-03-09T20:47:13Z |
| format | Article |
| id | doaj.art-0024f99c466442e982e8ea3e85ef89fe |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-09T20:47:13Z |
| publishDate | 2022-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-0024f99c466442e982e8ea3e85ef89fe2023-11-23T22:43:02ZengMDPI AGApplied Sciences2076-34172022-10-0112201033710.3390/app122010337Bridge Node Detection between Communities Based on GNNHairu Luo0Peng Jia1Anmin Zhou2Yuying Liu3Ziheng He4School of Cyber Science and Engineering, Sichuan University, Chengdu 610065, ChinaSchool of Cyber Science and Engineering, Sichuan University, Chengdu 610065, ChinaSchool of Cyber Science and Engineering, Sichuan University, Chengdu 610065, ChinaSchool of Cyber Science and Engineering, Sichuan University, Chengdu 610065, ChinaSchool of Cyber Science and Engineering, Sichuan University, Chengdu 610065, ChinaIn a complex network, some nodes are relatively concentrated in topological structure, thus forming a relatively independent node group, which we call a community. Usually, there are multiple communities on a network, and these communities are interconnected and exchange information with each other. A node that plays an important role in the process of information exchange between communities is called an inter-community bridge node. Traditional methods of defining and detecting bridge nodes mostly quantify the bridging effect of nodes by collecting local structural information of nodes and defining index operations. However, on the one hand, it is often difficult to capture the deep topological information in complex networks based on a single indicator, resulting in inaccurate evaluation results; on the other hand, for networks without community structure, such methods may rely on community partitioning algorithms, which require significant computing power. In this paper, considering the multi-dimensional attributes and structural characteristics of nodes, a deep learning-based framework named BND is designed to quickly and accurately detect bridge nodes. Considering that the bridging function of nodes between communities is abstract and complex, and may be related to the multi-dimensional information of nodes, we construct an attribute graph on the basis of the original graph according to the features of the five dimensions of the node to meet our needs for extracting bridging-related attributes. In the deep learning model, we overlay graph neural network layers to process the input attribute graph and add fully connected layers to improve the final classification effect of the model. Graph neural network algorithms including GCN, GAT, and GraphSAGE are compatible with our proposed framework. To the best of our knowledge, our work is the first application of graph neural network techniques in the field of bridge node detection. Experiments show that our designed framework can effectively capture network topology information and accurately detect bridge nodes in the network. In the overall model effect evaluation results based on indicators such as Accuracy and F1 score, our proposed graph neural network model is generally better than baseline methods. In the best case, our model has an Accuracy of 0.9050 and an F1 score of 0.8728.https://www.mdpi.com/2076-3417/12/20/10337social network analysisbridge node detectiongraph neural networkcommunity |
| spellingShingle | Hairu Luo Peng Jia Anmin Zhou Yuying Liu Ziheng He Bridge Node Detection between Communities Based on GNN Applied Sciences social network analysis bridge node detection graph neural network community |
| title | Bridge Node Detection between Communities Based on GNN |
| title_full | Bridge Node Detection between Communities Based on GNN |
| title_fullStr | Bridge Node Detection between Communities Based on GNN |
| title_full_unstemmed | Bridge Node Detection between Communities Based on GNN |
| title_short | Bridge Node Detection between Communities Based on GNN |
| title_sort | bridge node detection between communities based on gnn |
| topic | social network analysis bridge node detection graph neural network community |
| url | https://www.mdpi.com/2076-3417/12/20/10337 |
| work_keys_str_mv | AT hairuluo bridgenodedetectionbetweencommunitiesbasedongnn AT pengjia bridgenodedetectionbetweencommunitiesbasedongnn AT anminzhou bridgenodedetectionbetweencommunitiesbasedongnn AT yuyingliu bridgenodedetectionbetweencommunitiesbasedongnn AT zihenghe bridgenodedetectionbetweencommunitiesbasedongnn |