ABCDE: Approximating Betweenness-Centrality ranking with progressive-DropEdge
Betweenness-centrality is a popular measure in network analysis that aims to describe the importance of nodes in a graph. It accounts for the fraction of shortest paths passing through that node and is a key measure in many applications including community detection and network dismantling. The computation of betweenness-centrality for each node in a graph requires an excessive amount of computing power, especially for large graphs. On the other hand, in many applications, the main interest lies in finding the top-k most important nodes in the graph. Therefore, several approximation algorithms were proposed to solve the problem faster. Some recent approaches propose to use shallow graph convolutional networks to approximate the top-k nodes with the highest betweenness-centrality scores. This work presents a deep graph convolutional neural network that outputs a rank score for each node in a given graph. With careful optimization and regularization tricks, including an extended version of DropEdge which is named Progressive-DropEdge, the system achieves better results than the current approaches. Experiments on both real-world and synthetic datasets show that the presented algorithm is an order of magnitude faster in inference and requires several times fewer resources and time to train.
Code (1)
Tasks
Approximating Betweenness-Centrality rankingCommunity DetectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Graph Neural Networks for Scalable and Transferable Node Centrality Approximation
Graph Neural Networks (GNNs) provide a learning-based framework for approximating graph quantities that are expensive to compute exactly. This paper investigates GNNs for scalable approximation of betweenness and closene…
Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks
Computing the importance of nodes in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality,…
Graph Neural NetworkTemporal Walk Centrality: Ranking Nodes in Evolving Networks
We propose the Temporal Walk Centrality, which quantifies the importance of a node by measuring its ability to obtain and distribute information in a temporal network. In contrast to the widely-used betweenness centralit…
ONBRA: Rigorous Estimation of the Temporal Betweenness Centrality in Temporal Networks
In network analysis, the betweenness centrality of a node informally captures the fraction of shortest paths visiting that node. The computation of the betweenness centrality measure is a fundamental task in the analysis…
Graph Centrality Measures for Boosting Popularity-Based Entity Linking
Many Entity Linking systems use collective graph-based methods to disambiguate the entity mentions within a document. Most of them have focused on graph construction and initial weighting of the candidate entities, less …
Entity Linkinggraph constructionGraph Ranking