Dresden 2011 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

DY: Fachverband Dynamik und Statistische Physik

DY 19: Networks: From Topology to Dynamics II (with BP, SOE)

DY 19.9: Talk

Wednesday, March 16, 2011, 13:00–13:15, GÖR 226

Backbones and borders from shortest-path trees — •Daniel Grady, Christian Thiemann, and Dirk Brockmann — Northwestern University, Evanston, IL, USA

One of the most important tasks in complex network research is to distinguish between vertices and edges that are topologically essential and those that are not. To this end, a variety of vertex and edge centrality measures have been introduced, ranging from measuring local properties (degree, strength) to quantities that depend on the global structure of the graph (betweenness). Here we introduce a novel technique based on the family of shortest-path trees, which is applicable to strongly heterogeneous networks. This approach can identify significant edges in the network, distinct from conventional edge betweenness, and these edges make up a network backbone relevant to dynamical processes that evolve on such networks. We will show that important network structures can be extracted by investigating the similarity and differences of shortest-path trees and show that tree dissimilarity in combination with hierarchical clustering can identify communities in heterogeneous networks more successfully than ordinary reciprocal-weight distance measures. We demonstrate the success of this technique on complex multi-scale mobility networks.