The identification of important nodes with strong propagation capabilities in road networks is a vital topic in urban planning. Existing methods for evaluating the importance of nodes in traffic ...networks only consider topological information and traffic volumes, the diversity of the traffic characteristics in road networks, such as the number of lanes and average speed of road segments, is ignored, thus limiting their performance. To solve this problem, we propose a graph learning-based framework (MGL2Rank) that integrates the rich characteristics of road networks to rank the importance of nodes. This framework comprises an embedding module containing a sampling algorithm (MGWalk) and an encoder network to learn the latent representations for each road segment. MGWalk utilizes multi-graph fusion to capture the topology of road networks and establish associations between road segments based on their attributes. The obtained node representation is then used to learn the importance ranking of the road segments. Finally, a synthetic dataset is constructed for ranking tasks based on the regional road network of Shenyang City, and the ranking results on this dataset demonstrate the effectiveness of our method. The data and source code for MGL2Rank are available at https://github.com/ZJ726.
The measurement of node importance in complex networks has an important impact on the stability and robustness of networks, such as stopping the spread of disease and rumors and preventing power ...grids from being powered off. A variety of network centricity criteria are used to evaluate the importance of nodes, while each of them accompanied by a single criterion has its own shortcomings and limitations. A novel method is therefore proposed to rank node importance based on combining the existing centrality criteria. This paper considers degree centrality, closeness centrality, and betweenness centrality and raises an integrated measuring method to evaluate node importance in complex networks. In our method, the weight of each criterion is calculated by entropy weighting method which overcomes the impact of the subjective factor, and the Vlsekriterijumska Optimizacija I Kompromisno Resenje (VIKOR) method is used for ranking nodes’ importance. Finally, four experiments are conducted based on four actual networks to verify the feasibility and effectiveness of the proposed method. The experimental results demonstrate that the performance of ranking node importance of the proposed method is better than a single centrality criterion.
•Entropy weighting method and VIKOR are combined to rank importance of nodes.•Weight of criterion is obtained using entropy weighting method.•Experiments show that the proposed method outperforms a single centrality criterion.•The proposed method can reduce the frequency of nodes with the same ranking.
Although graph neural networks (GNNs) work well on graph data, they are black-box models that lack of reliable explanations for their predictions. We propose a multi-granularity subgraph aggregation ...method based on graph topology to explain GNNs. Specifically, given a trained GNN model and an input graph, our method constructs a subgraph by heuristics from fine-grained to coarse-grained and sorts the subgraph nodes to obtain subgraph and node-level explain. Furthermore, we propose an improved Shapley value as a heuristic function for the search algorithm, which strikes a balance between the time complexity and accuracy. Finally, experimental results on both synthetic and real datasets demonstrate that our method achieves best performance on seven datasets, quantifying the influence of individual nodes on prediction results and providing more reliable explanations.
•We propose a multi-granularity subgraph aggregation method with graph's topology.•We propose an improved Shapley value for balancing time complexity and performance.•We propose a node ranking and verification method utilizing perturbation.•We propose a new metric to evaluate the explainability algorithm.
With the development of complex networks in urban rail transit (URT), the topological structure changes accordingly and node importance also redistributes dynamically. However, many deficiencies ...exist in the single measure or unweighted network or static network when ranking node importance. Most importantly, the evolution mechanism of node importance with the network development is seldom studied. In view of this, in this paper, six unweighted and weighted complex networks are firstly modeled in the evolution of URT networks. One of Multiple Attribute Decision Making (MADM) methods is proposed, that is WTOPSIS (The Weighted Technique for Order of Preference by Similarity to Ideal Solution) algorithm combining Coefficient of Variation method and TOPSIS. Then four local and global centralities are aggregated and utilized in WTOPSIS to rank the node importance in those six networks. On the basis, the intersection degrees among the ranking sets are calculated to evaluate the similarities of ranking results. Furthermore, the factors contributing to the evolution of node importance are discussed quantitatively and qualitatively with examples. Finally, the feasibility of the method is verified by the Shenzhen Metro system in 2016. Results show that WTOPSIS algorithm outperforms the single attribute in ranking node importance, which makes up for the shortcomings in existing studies. Besides, for different stations in URT network development, node importance evolution is affected differently by the changes of topological structure and passenger flow. It is necessary to combine with the actual situations for the specific analysis. This study reveals the evolution mechanism of the node importance in the development of URT networks and it also has great theoretical and practical significance.
•Four centralities are measured in six unweighted and weighted complex networks with the evolution of URT.•The WTOPSIS algorithm is proposed to rank node importance.•Case study shows that the proposed algorithm outperforms the single attribute.•The evolution mechanism of node importance in the URT networks is revealed.
Evaluating the importance of nodes for complex networks is of great significance to the research of survivability and robusticity of networks. This paper proposes an effective ranking method based on ...degree value and the importance of lines. It can well identify the importance of bridge nodes with lower computational complexity. Firstly, the properties of nodes that are connected to a line are used to compute the importance of the line. Then, the contribution of nodes to the importance of lines is calculated. Finally, degree of nodes and the contribution of nodes to the importance of lines are considered to rank the importance of nodes. Five real networks are used as test data. The experimental results show that our method can effectively evaluate the importance of nodes for complex networks.
•A Node Importance ranking method (DIL) is proposed based on local information.•The importance of line is considered to evaluate the importance of node.•DIL can well identify the importance of nodes especially the bridge nodes.•DIL can be used in large-scale networks with lower computational complexity.
Recently, the detection of high-quality community has become a hot spot in the research of social network. Label propagation algorithm (LPA) has been widely concerned since it has the advantages of ...linear time complexity and is unnecessary to define objective function and the number of community in advance. However, LPA has the shortcomings of uncertainty and randomness in the label propagation process, which affects the accuracy and stability of the community. For large-scale social network, this paper proposes a novel label propagation algorithm for community detection based on node importance and label influence (LPA_NI). The experiments with comparative algorithms on real-world networks and synthetic networks have shown that LPA_NI can significantly improve the quality of community detection and shorten the iteration period. Also, it has better accuracy and stability in the case of similar complexity.
•Label propagation algorithm based on node importance and label influence is proposed.•The algorithm uses a novel method for node importance evaluation.•The algorithm updates the nodes in the descending order of the node importance.•The algorithm has better accuracy and stability in the case of similar complexity.
In Cyber–Physical–Social Systems (CPSS), the interactions among various entities form complex graphs. Many tasks can be formulated as instances of node classification. Node classification on graphs ...has attracted increasing research interest. However, the performance of existing graph neural networks for few-shot node classification has not achieved satisfactory results due to the limitation of the number of labeled instances. Therefore, we propose a graph-weighted prototype scaling network (GWPSN) based on deep metric learning for addressing the graph few-shot node classification problem. Specifically, we first extract node representations for the attributed graph via the simplifying graph convolutional network. At the same time, learning the importance of each node in the attributed graph is used to aggregate class prototypes. Finally, the class of the test node can be predicted by comparing the scaled metric distance between the test node and the class prototype. Experiments indicate that GWPSN can achieve superior performance on three real-world datasets and thus can provide enhanced few-shot classification services for CPSS.
•Extracting node representations by the simplifying graph convolutional network•A new approach to aggregating class prototypes by using a few samples of each class•First introduction of metric scaling parameters in graph few-shot node classification•Proving the effectiveness of the proposed method on three real-world datasets
Label propagation algorithm (LPA) has attracted much attention due to its linear time complexity. However, there are disadvantages of uncertainty and randomness in the label propagation process, ...which may affect the stability and accuracy of community detection. In order to solve this problem, this paper proposes a novel label propagation algorithm based on node importance (NI-LPA). In the algorithm, a new index of node importance is presented which integrates the signal propagation of nodes, ks value of nodes themselves and Jaccard distance between adjacent nodes. The signal propagation considers the node importance from the perspective of network locality, the index reflects the position of nodes in the entire network, and Jaccard distance embodies the connection between nodes. The proposed index can fully reflect the node importance in the entire network. In the label propagation process, when the nodes with the maximum number of neighboring nodes are not unique, their labels are updated in terms of node importance. The proposed algorithm can avoid the instability caused by random selection in LPA algorithm. Experiments on real and synthetic networks show that NI-LPA can significantly improve the modularity of community and reduce the number of iterations. NI-LPA has better stability and accuracy than LPA.
•Jaccard distance is defined to measure the potential influence between two nodes.•A new index is proposed based on signal propagation, ks value and Jaccard distance.•We propose a new label propagation algorithm to detect community structures.
Vessel Traffic Services (VTS) aims to improve the safety and efficiency of water transportation, yet its operation relies heavily on the work of Vessel Traffic Services Operators (VTSOs). Enhancing ...VTSO's situational awareness help improve VTS performance while relieving the workload of VTSOs. However, an effective method of analysing the water traffic from a systemic perspective to improve situational awareness among VTSOs is lacking. Therefore, we propose a method to evaluate the node importance of ships based on the marine traffic situation complex network (MTSCN) to enhance the situational awareness of VTSO. The node importance of ships reflects the conflicting risk and the complexity of the traffic structure. Several case studies were conducted to demonstrate the feasibility of applying this proposed method to promote the performance of VTS. The promising results show that the identification of key ships with high node importance can help VTSOs identify targeted ships in need of traffic service and control and determine the priority in which these targeted vessels are to be supervised. The application of this proposed method supports the construction of intelligent VTS to improve its efficiency and automation in controlling and serving water traffic.
•A new method is proposed towards enhancing Vessel Traffic Services.•Marine Traffic Situation Complex Network (MTSCN) is constructed.•Ship node importance reflects conflict risk and traffic structure complexity.•The identification of key ships enhances the situational awareness of VTSO.
PDF
