Bridge Node Detection between Communities Based on GNN

Abstract

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.

Keywords

• social network analysis
• bridge node detection
• graph neural network
• community