Graph convolution networks (GCN) have emerged as the leading method to classify node classes in networks, and have reached the highest accuracy in multiple node classification tasks. In the absence of available tagged samples, active learning methods have been developed to obtain the highest accuracy using the minimal number of queries to an oracle. The current best active learning methods use the sample class uncertainty as selection criteria. However, in graph based classification, the class of each node is often related to the class of its neighbors. As such, the uncertainty in the class of a node's neighbor may be a more appropriate selection criterion. We here propose two such criteria, one extending the classical uncertainty measure, and the other extending the page-rank algorithm. We show that the latter is optimal when the fraction of tagged nodes is low, and when this fraction grows to one over the average degree, the regional uncertainty performs better than all existing methods. While we have tested this methods on graphs, such methods can be extended to any classification problem, where a distance metrics can be defined between the input samples. All the code used can be accessed at : this https URL All the datasets used can be accessed at : this https URL
Centrality based approaches focus on nodes which are more central (e.g. higher degree). The assumption is that the central nodes will have a major impact on the unknown labels, as used by Macskassy in the ERM algorithm, where he showed that betweenness centrality is a good measure for centrality @cite_33 . Cai and Chang proposed to calculate a node representativeness score based on graph centrality. They tested several centrality measures: degree centrality, betweenness centrality, harmonic centrality, closeness centrality, and page-rank centrality. They conclude that the Page-Rank centrality is superior, and suggest using it when the prediction model is not informative enough @cite_9 .
@cite_9 @cite_33
1992250165 2963957156 2171137858 1981000476
Identifying influential nodes that lead to faster and wider spreading in complex networks is of theoretical and practical significance. The degree centrality method is very simple but of little relevance. Global metrics such as betweenness centrality and closeness centrality can better identify influential nodes, but are incapable to be applied in large-scale networks due to the computational complexity. In order to design an effective ranking method, we proposed a semi-local centrality measure as a tradeoff between the low-relevant degree centrality and other time-consuming measures. We use the Susceptible–Infected–Recovered (SIR) model to evaluate the performance by using the spreading rate and the number of infected nodes. Simulations on four real networks show that our method can well identify influential nodes. Betweenness centrality ranks the importance of nodes by their participation in all shortest paths of the network. Therefore computing exact betweenness values is impractical in large networks. For static networks, approximation based on randomly sampled paths has been shown to be significantly faster in practice. However, for dynamic networks, no approximation algorithm for betweenness centrality is known that improves on static recomputation. We address this deficit by proposing two incremental approximation algorithms (for weighted and unweighted connected graphs) which provide a provable guarantee on the absolute approximation error. Processing batches of edge insertions, our algorithms yield significant speedups up to a factor of 104 compared to restarting the approximation. This is enabled by investing memory to store and efficiently update shortest paths. As a building block, we also propose an asymptotically faster algorithm for updating the SSSP problem in unweighted graphs. Our experimental study shows that our algorithms are the first to make in-memory computation of a betweenness ranking practical for million-edge semi-dynamic networks. Moreover, our results show that the accuracy is even better than the theoretical guarantees in terms of absolute errors and the rank of nodes is well preserved, in particular for those with high betweenness. Centrality measures are used in network science to rank the relative importance of nodes and edges of a graph. Here we define new measures of centrality for power grid structure that are based on its functionality. We show that the relative importance analysis based on centrality in graph theory can be generalized to power grid network with its electrical parameters taken into account. In the paper we experiment with the proposed electrical centrality measures on the NYISO-2935 system and the IEEE 300-bus system. We analyze the centrality distribution in order to identify important nodes or branches in the system which are of essential importance in terms of system vulnerability. We also present and discuss a number of interesting discoveries regarding the importance rank of power grid nodes and branches. This paper proposes an alternative way to identify nodes with high betweenness centrality. It introduces a new metric, κ-path centrality, and a randomized algorithm for estimating it, and shows empirically that nodes with high κ-path centrality have high node betweenness centrality. The randomized algorithm runs in time O(κ3n2−2αlog n) and outputs, for each vertex v, an estimate of its κ-path centrality up to additive error of ±n1 2+α with probability 1 − 1 n2. Experimental evaluations on real and synthetic social networks show improved accuracy in detecting high betweenness centrality nodes and significantly reduced execution time when compared with existing randomized algorithms.