Localized Bridging Centrality


Soumendra Nanda and David Kotz. Localized Bridging Centrality. Handbook of Optimization in Complex Networks: Communication and Social Networks, chapter 7, pages 197–218. Edited by My T. Thai and Panos M. Pardalos. Volume 58, Springer, October 2011. doi:10.1007/978-1-4614-0857-4_7. ISBN: 9781461408567. ©Copyright Springer. Revision of nanda:lbc.

Abstract:

Centrality is a concept often used in social network analysis (SNA) to study different properties of networks that are modeled as graphs. Bridging nodes are strategically important nodes in a network graph that are located in between highly-connected regions. We developed a new centrality metric called Localized Bridging Centrality (LBC) to allow a user to identify and rank bridging nodes. LBC is a distributed variant of the Bridging Centrality (BC) metric and both these metrics are used to identify and rank bridging nodes. LBC is capable of identifying bridging nodes with an accuracy comparable to that of the BC metric for most networks, but is an order of magnitude less computationally expensive. As the name suggests, we use only local information from surrounding nodes to compute the LBC metric. Thus, our LBC metric is more suitable for distributed or parallel computation than the BC metric. We applied our LBC metric on several examples, including a real wireless mesh network. Our results indicate that the LBC metric is as powerful as the BC metric at identifying bridging nodes. We recently designed a new SNA metric that is also suitable for use in wireless mesh networks: the Localized Load-aware Bridging Centrality (LLBC) metric. The LLBC metric improves upon LBC by detecting critical bridging nodes while taking into account the actual traffic flows present in a communications network. We developed the SNA Plugin (SNAP) for the Optimized Link State Routing (OLSR) protocol to study the potential use of LBC and LLBC in improving multicast communications and our initial results are promising. In this chapter we present an introduction to SNA centrality metrics with a focus on our contributed metrics: LBC and LLBC. We also present some initial results from applying our metrics in real and emulated wireless mesh networks.

Citable with [BibTeX]: \cite{nanda:lbc-book}

Projects: [meshmon]

Keywords: [wifi]

Available from the publisher: [DOI]

Available from the author: [bib] [pdf]
This pdf was produced by the publisher and its posting here is permitted by the publisher.

thumbnail image

[Kotz research]