Session L22: Focus Session: Structure and Dynamics of Complex Networks

Functional Aspects of Biological Networks

We discuss biological networks with respect to 1) relative positioning and importance of high degree nodes, 2) function and signaling, 3) logic and dynamics of regulation. Visually the soft modularity of many real world networks can be characterized in terms of number of high and low degrees nodes positioned relative to each other in a landscape analogue with mountains (high-degree nodes) and valleys (low-degree nodes). In these terms biological networks looks like rugged landscapes with separated peaks, hub proteins, which each are roughly as essential as any of the individual proteins on the periphery of the hub. Within each sup-domain of a molecular network one can often identify dynamical feedback mechanisms that falls into combinations of positive and negative feedback circuits. We will illustrate this with examples taken from phage regulation and bacterial uptake and regulation of small molecules. In particular we find that a double negative regulation often are replaced by a single positive link in unrelated organisms with same functional requirements. Overall we argue that network topology primarily reflects functional constraints. References: S. Maslov and K. Sneppen. ``Computational architecture of the yeast regulatory network." Phys. Biol. 2:94 (2005) A. Trusina et al. ``Functional alignment of regulatory networks: A study of temerate phages". Plos Computational Biology 1:7 (2005). J.B. Axelsen et al. ``Degree Landscapes in Scale-Free Networks" physics/0512075 (2005). A. Trusina et al. ``Hierarchy and Anti-Hierarchy in Real and Scale Free networks." PRL 92:178702 (2004) S. Semsey et al. ``Genetic Regulation of Fluxes: Iron Homeostasis of Escherichia coli". (2006) q-bio.MN/0609042   

Optimal transport on complex networks

Transport optimization is a problem encountered in connection to many different types of complex networks, including biological networks, social networks, and a variety of natural and human-made transport and communication networks. We present results for transport optimization on random, scale-free, as well as geometric networks, obtained using a novel heuristic algorithm. Some of the results have been published in Phys.Rev.\ E {\bf 74}, 046106 (2006). Our algorithm balances transport by adjusting traffic routing at every iteration to minimize the betweenness of the busiest node on the network. This is done with the least possible lengthening of the paths passing through that node. Our results are compared with those obtained using classical shortest path routing, as well as previously proposed network transport optimization algorithms. We show that routing produced by our algorithm enables networks to sustain significantly higher traffic without jamming than in the case of any previously proposed routing optimization algorithm. Furthermore, we show that, in spite of unavoidable lengthening of the average path, the small-world character of network routing is preserved.   

Model framework for describing the dynamics of evolving networks

We present a model framework for describing the dynamics of evolving networks. In this framework the addition of edges is stochastically governed by some important intrinsic and structural properties of network vertices through an attractiveness function. We discuss the solution of the inverse problem: determining the attractiveness function from the network evolution data. We also present a number of example applications: the description of the US patent citation network using vertex degree, patent age and patent category variables, and we show how the time-dependent version of the method can be used to find and describe important changes in the internal dynamics. We also compare our results to scientific citation networks.   

Transport on weighted Networks: when correlations are independent of degree

Most real-world networks are weighted graphs with the weight of the edges reflecting the relative importance of the connections. In this work, we study non degree dependent correlations between edge weights, generalizing thus the correlations beyond the degree dependent case. We find that two measures, the disparity and the range, defined below, are able to discriminate between the different types of correlated networks. We also study the effect of weight correlations on the transport properties of the graphs. We find that positive correlations dramatically improve transport. The classic case of degree dependent weight correlations relates to our graphs with positive weight correlations.   

Limited Percolation on Complex Networks

We study the stability of network communication under removal of $q=1-p$ links when communication between nodes is possible only through a subset of the paths connecting them. We find a new percolation transition $\tilde{p}$ below which only a fractal fraction of nodes $N^{\gamma}$ can communicate, where $\gamma$ is a function of the accepted communication paths. Above $\tilde{p}$, order $N$ nodes can communicate. The results may be useful for the design of communication networks and immunization strategies.   

Criticality in finite dynamical networks

It has been shown analytically and experimentally that both random boolean and random threshold networks show a transition from ordered to chaotic dynamics at a critical average connectivity $K_c$ in the thermodynamical limit [1]. By looking at the statistical distributions of damage spreading (damage sizes), we go beyond this extensively studied mean-field approximation. We study the scaling properties of damage size distributions as a function of system size $N$ and initial perturbation size $d(t=0)$. We present numerical evidence that another characteristic point, $K_d$ exists for finite system sizes, where the expectation value of damage spreading in the network is independent of the system size $N$. Further, the probability to obtain critical networks is investigated for a given system size and average connectivity $k$. Our results suggest that, for finite size dynamical networks, phase space structure is very complex and may not exhibit a sharp order-disorder transition. Finally, we discuss the implications of our findings for evolutionary processes and learning applied to networks which solve specific computational tasks. [1] Derrida, B. and Pomeau, Y. (1986), Europhys. Lett., 1, 45-49   

Rich-club ordering in complex networks

Uncovering the hidden regularities and organizational principles of networks arising in physical systems ranging from the molecular level to the scale of large communication infrastructures is the key issue for the understanding of their fabric and dynamical properties. The ``rich-club'' phenomenon refers to the tendency of nodes with high centrality, the dominant elements of the system, to form tightly interconnected communities and it is one of the crucial properties accounting for the formation of dominant communities in both computer and social sciences. The talk will provide the analytical expression and the correct null models for the measurement of the rich-club ordering and its relation with the function and dynamics of networks in examples drawn from the biological, social and technological domains.   

Scaling properties of critical random Boolean networks

Until a few years ago, it was believed that random Boolean networks at the critical point (i.e., Kauffman networks) have a square-root relationship between the mean number of length of attractors and the system size N (i.e. the number of nodes). In the meantime, it became known that in fact the mean number and the mean length of attractors increase faster than any power law with increasing N. This talk gives an intuitive understanding of why this is the case. We investigate mainly analytically the scaling behavior of the number of nodes that are not frozen on all attractors, and of the number of relevant nodes, i.e. the nodes that determine the number and length of attractors. From the results it becomes clear that the relevant nodes form of the order of log(N) components, most of which have the form of simple loops. From this in turn attractor numbers and lengths follow by simple combinatorics. References: V. Kaufman, T. Mihalev, B. Drossel, PRE 72, 046124 (2005). B. Drossel, T. Mihalev, F. Greil, PRL94, 088701 (2005). B. Drossel, PRE72, 016110 (2005).   

Exhaustive percolation in binary avalanches

We introduce the concept of binary avalanches as a generalization of commonly investigated site or bond percolation processes. Binary avalanches are capable of displaying a behavior that we call exhaustive percolation, where the fraction of nodes that are not affected by an avalanche approaches zero in the large system limit. We present a numerical example of exhaustive percolation on a directed lattice and analytical results for directed random networks. For random networks, the transition to exhaustive percolation is second order with scaling properties different from ordinary percolation. Our numerical calculations indicate that the exhaustive percolation transition on the directed lattice is also second order. Our analytic results for random networks improve the understanding of dynamical properties in random Boolean networks.   

Heterogeneity in community structure and renormalization in scale-free networks

While many real-world networks contain community structures within them, their structural feature has not been fully understood yet. Here we study heterogeneities of community structures such as their sizes, cohesiveness, modularity, and renormalized degree, finding that there exist nontrivial power-law relationships between them, based on real-world networks. We show that such obtained relationships provide the condition of scale invariance of the degree distribution under renormalization. Also we show that the load or betweenness centrality of communities depends on such structural properties of communities.   

Price of Anarchy on Complex Networks

We present an optimization problem of decentralized transportation networks, where latency depends linearly on congestion of a link. The system shows that a collection of individual optimization of the flow does not always meet the most optimized outcome that is conventionally assumed. We suggest that the Price of Anarchy, the ratio of two optimums, can quantify such discrepancy and accordingly regarded as an index of inefficiency of the system. We also measure the Price of Anarchy of model networks with various underlying structures, and a simplified Boston road network. Our numerical result confirms the existence of the Price of Anarchy in the networks. Finally, we find Braess's paradox is not just a pedagogical example, but inefficiency that can counterintuitively take place in real.