Betweenness computation in the single graph representation of hypergraphs

Rami Puzis*, Manish Purohit, V. S. Subrahmanian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

Many real-world social networks are hypergraphs because they either explicitly support membership in groups or implicitly include communities. We present the HyperBC algorithm that exactly computes betweenness centrality (or BC) in hypergraphs. The forward phase of HyperBC and the backpropagation phase are specifically tailored for BC computation on hypergraphs. In addition, we present an efficient method for pruning networks through the notion of "non-bridging" vertices. We experimentally evaluate our algorithm on a variety of real and artificial networks and show that it significantly speeds up the computation of BC on both real and artificial hypergraphs, while at the same time, being very memory efficient.

Original languageEnglish (US)
Pages (from-to)561-572
Number of pages12
JournalSocial Networks
Volume35
Issue number4
DOIs
StatePublished - Oct 2013
Externally publishedYes

Keywords

  • Algorithms
  • Betweenness centrality
  • Hypergraphs

ASJC Scopus subject areas

  • Anthropology
  • Sociology and Political Science
  • General Social Sciences
  • General Psychology

Fingerprint

Dive into the research topics of 'Betweenness computation in the single graph representation of hypergraphs'. Together they form a unique fingerprint.

Cite this