RECORD
An Efficient Heuristic for Betweenness-Ordering
Social and Information Networks · Submitted 23 Sep 2014
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We compare our method with the available techniques in the literature and show that our method produces more efficient ordering than the currently known methods.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen broad and increasing applications across several disciplines of late. Amongst a plethora of application specific definitions available in the literature to rank the vertices, closeness centrality, betweenness centrality and eigenvector centrality (page-rank) have been the most important and widely applied ones. Networks where information, signal or commodities are flowing on the edges, surrounds us. Betweenness centrality comes as a handy tool to analyze such systems, but betweenness computation is a daunting task in large size networks. In this paper, we propose an efficient heuristic to determine the betweenness-ordering of $k$ vertices (where $k$ is very less than the total number of vertices) without computing their exact betweenness indices. The algorithm is based on a non-uniform node sampling model which is developed based on the analysis of Erdos-Renyi graphs. We apply our approach to find the betweenness-ordering of vertices in several synthetic and real-world graphs. The proposed heuristic results very efficient ordering even when runs for a linear time in the terms of the number of edges. We compare our method with the available techniques in the literature and show that our method produces more efficient ordering than the currently known methods.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen broad and increasing applications across several disciplines of late. | background 1.00 | 0.03 | 0.01 | asserted 1.00 |
| s1 | Amongst a plethora of application specific definitions available in the literature to rank the vertices, closeness centrality, betweenness centrality and eigenvector centrality (page-rank) have been the most important and widely applied ones. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s2 | Networks where information, signal or commodities are flowing on the edges, surrounds us. | background 1.00 | 0.04 | 0.01 | asserted 0.99 |
| s3 | Betweenness centrality comes as a handy tool to analyze such systems, but betweenness computation is a daunting task in large size networks. | background 0.75 | 0.06 | 0.03 | asserted 1.00 |
| s4 | In this paper, we propose an efficient heuristic to determine the betweenness-ordering of $k$ vertices (where $k$ is very less than the total number of vertices) without computing their exact betweenness indices. | contribution 0.99 | 0.93 | 0.40 | asserted 1.00 |
| s5 | The algorithm is based on a non-uniform node sampling model which is developed based on the analysis of Erdos-Renyi graphs. | method 0.99 | 0.89 | 0.04 | asserted 1.00 |
| s6 | We apply our approach to find the betweenness-ordering of vertices in several synthetic and real-world graphs. | method 0.73 | 0.96 | 0.05 | asserted 0.97 |
| s7 | The proposed heuristic results very efficient ordering even when runs for a linear time in the terms of the number of edges. | result 1.00 | 0.93 | 0.38 | asserted 1.00 |
| s8 | We compare our method with the available techniques in the literature and show that our method produces more efficient ordering than the currently known methods. | result 0.98 | 0.94 | 0.57 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v3
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Centrality measures, erstwhile popular amongst the sociologists and psychologists, have seen broad and increasing applications across several disciplines of late. Amongst a plethora of application specific definitions available in the literature to rank the vertices, closeness centrality, betweenness centrality and eigenvector centrality (page-rank) have been the most important and widely applied ones. Networks where information, signal or commodities are flowing on the edges, surrounds us. Betweenness centrality comes as a handy tool to analyze such systems, but betweenness computation is a daunting task in large size networks. In this paper, we propose an efficient heuristic to determine the betweenness-ordering of $k$ vertices (where $k$ is very less than the total number of vertices) without computing their exact betweenness indices. The algorithm is based on a non-uniform node sampling model which is developed based on the analysis of Erdos-Renyi graphs. We apply our approach to find the betweenness-ordering of vertices in several synthetic and real-world graphs. The proposed heuristic results very efficient ordering even when runs for a linear time in the terms of the number of edges. We compare our method with the available techniques in the literature and show that our method produces more efficient ordering than the currently known methods.
Human review
How the literature uses it
3 arXiv papers cite this in 4 sentences
Papers citing it · 2 sentences without a confident label
Cites it as background 1 paper
-
There are two categories on the state-of-art sampling approximation algorithms: uniform sampling (e.g., to sample nodes with identical probability) [ref] and non-uniform sampling (e.g., each node has a different probability to be sampled) [ref] .
Refining Approximating Betweenness Centrality Based on Samplings · Related Works · 0.91
What it cites · 1 sentence without a confident label
Cites as background 1 paper
-
Several exact algorithms for large graphs (Sariyüce et al. [ref] ) and dynamic graphs (Lee et al. [ref] , Green et al. [ref] , Kas et al. [ref] , Goel et al. [ref] , Nasre et al. [ref] ) have been developed.
Betweenness Centrality -- Incremental and Faster · Related work · 0.88
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.