Betweenness Centrality and Its Applications from Modeling Traffic Flows to Network Community Detection

Doctoral Dissertation
Thumbnail

Abstract

As real-world complex networks are heterogeneous structures, not all their components such as nodes, edges and subgraphs carry the same role or importance in the functions performed by the networks: some elements are more critical than others. Understanding the roles of the components of a network is crucial for understanding the behavior of the network as a whole. One the most basic function of networks is transport; transport of vehicles/people, information, materials, forces, etc, and these quantities are transported along edges between source and destination nodes. For this reason, network path-based importance measures, also called centralities, play a crucial role in the understanding of the transport functions of the network and the network’s structural and dynamical behavior in general.

In this thesis we study the notion of betweenness centrality, which measures the fraction of lowest-cost (or shortest) paths running through a network component, in particular through a node or an edge. High betweenness centrality nodes/edges are those that will be frequently used by the entities transported through the network and thus they play a key role in the overall transport properties of the network. In the first part of the thesis we present a first-principles based method for traffic prediction using a cost-based generalization of the radiation model (emission/absorption model) for human mobility, coupled with a cost-minimizing algorithm for efficient distribution of the mobility fluxes through the network. Using US census and highway traffic data, we show that traffic can efficiently and accurately be computed from a range- limited, network betweenness type calculation. The model based on travel time costs captures the log-normal distribution of the traffic and attains a high Pearson correlation coefficient (0.75) when compared with real traffic. We then focus on studying the extent of changes in traffic flows in the wake of a localized damage or alteration to the network and we demonstrate that the changes can propagate globally, affecting traffic several hundreds of miles away. Because of its principled nature, this method can inform many applications related to human mobility driven flows in spatial networks, ranging from transportation, through urban planning to mitigation of the effects of catastrophic events.

In the second part of the thesis we focus on network deconstruction and community detection problems, both intensely studied topics in network science, using a weighted betweenness centrality approach. We present an algorithm that solves both problems efficiently and accurately and demonstrate that on both benchmark networks and data networks.

Attributes

Attribute NameValues
URN
  • etd-03052015-171939

Author Yihui Ren
Advisor Zoltan Toroczkai
Contributor Kathie E. Newman, Committee Member
Contributor Nitesh Chawla, Committee Member
Contributor Zoltan Toroczkai, Committee Chair
Contributor Dervis Can Vural, Committee Member
Degree Level Doctoral Dissertation
Degree Discipline Physics
Degree Name PhD
Defense Date
  • 2015-03-05

Submission Date 2015-03-05
Country
  • United States of America

Subject
  • network science

  • first-principle based

  • betweenness centrality

  • traffic prediction

Publisher
  • University of Notre Dame

Language
  • English

Record Visibility and Access Public
Content License
  • All rights reserved

Departments and Units

Files

Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.