Regensburg 2010 – scientific programme

Parts | Days | Selection | Search | Downloads | Help

BP: Fachverband Biologische Physik

BP 24: Networks: From Topology to Dynamics III (joint DY, BP, SOE)

BP 24.10: Talk

Thursday, March 25, 2010, 12:45–13:00, H44

Properties of transport networks need to be invariant under coarse graining — •Fabian J. Theis^1,2, Florian Blöchl¹, and Dirk Brockmann³ — ¹Helmholtz Zentrum München, Germany — ²Department of Mathematics, TU Munich, Germany — ³Engineering Sciences and Applied Mathematics, Northwestern University, USA

Transport networks can rarely be observed directly, especially not across many scales. Instead, the flow between two locations can now only be estimated from proxy data. This results in the need for spatial averaging, so we commonly only observe a histogram of the actual distributions. We denote this process as coarse graining.

In this contribution we analyze which network properties are invariant under coarse graining, following the rationale that we can only infer such properties of the true underlying transport network from the proxy data. We show that shortest-path distances, which cannot take self-loops into account, are a poor distance measure in such networks. Instead we illustrate that a distance based on random walks, namely mean fast hitting time (MFHT), is much more adequate for such type of networks. Moreover, we show that community measures are coarse-graining invariant.

Taken together, we can develop a coarse graining method that leaves MFHT fully invariant: we first cluster the nodes into communities via hierarchical clustering of the mean commute time matrix. We then reconstruct a weighted graph connecting our communities, solving a distance realization problem, which we recently addressed in (Wittmann et al., TCS 2009). We illustrate the method on toy and real networks.