Physical networks as network-of-networks.

Physical networks are made of nodes and links that are physical objects embedded in a geometric space. Understanding how the mutual volume exclusion between these elements affects the structure and function of physical networks calls for a suitable generalization of network theory. Here, we introduce a network-of-networks framework where we describe the shape of each extended physical node as a network embedded in space and these networks are bound together by physical links. Relying on this representation, we introduce a minimal model of network growth and we show for a general class of physical networks that volume exclusion induces heterogeneity in both node volume and degree, with the two becoming correlated. These emergent properties strongly affect the dynamics on physical networks: by calculating their Laplacian spectrum as a function of the coupling strength between the nodes we show that degree-volume correlations suppress the role of hubs as early spreaders in diffusive dynamics. We apply the network-of-networks framework to describe several real systems and find properties analog to the minimal model networks. The prevalence of these properties points towards general growth mechanisms that do not depend on the specifics of the systems.

Controllability, Matching Ratio and Graph Convergence.

There is an important parameter in control theory which is closely related to the directed matching ratio of the network, as shown in the paper of Liu et al. (Nature 473:167-173, 2011). We give proofs of two main statements of Liu et al.  (2011) on the directed matching ratio, which were based on numerical results and heuristics from statistical physics. First, we show that the directed matching ratio of directed random networks given by a fix sequence of degrees is concentrated around its mean. We also examine the convergence of the (directed) matching ratio of a random (directed) graph sequence that converges in the local weak sense, and generalize the result of Elek and Lippner (Proc Am Math Soc 138(8):2939-2947, 2010). We prove that the mean of the directed matching ratio converges to the properly defined matching ratio parameter of the limiting graph. We further show the almost sure convergence of the matching ratios for the most widely used families of scale-free networks, which was the main motivation of Liu et al.  (2011).