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

Hierarchical Link Clustering in Complex Networks

Identifying modular network structure is generally a problem of finding the correct community membership of each node in a network. An alternative approach, clustering links, naturally accounts for real world characteristics such as strong community overlap, multi-partite structure, and hierarchical organization. By introducing a pair-wise link similarity, we use a hierarchical clustering method to identify relevant communities in real-world examples such as biological networks. Our results reveal previously hidden organization of communities.   

Enhancing the scale-free network's attack tolerance

Despite the large size of most communication systems such as the Internet and World Wide Web (WWW), there is a relatively short path between two nodes, revealing the networks' small world characteristic which speeds the delivery of information and data. While these networks have a surprising error tolerance, their scale-free topology makes them fragile under intentional attack, leaving us a challenge on how to improve the networks' robustness against attack without losing their small world merit. Here we try to enhance scale-free network's tolerance under attack by using a method based on networks' topology re-constructing.   

Optimality and Directionality in Network Synchronization

In a network of dynamical elements, one of the most fundamental issues is the relationship between the network structure and the collective dynamics of the system. The study of complete synchronization, a simplest form of collective dynamics in a network, in which all oscillators behave in precisely the same way, provides an excellent starting point for understanding how collective behavior arises in a network. The stability of complete synchronization in a weighted directed network of oscillators can be formulated using the well known master stability function and the eigenvalues of the Laplacian matrix encoding the topological structure of the network. In this talk, I will use this formulation to address an interesting optimization problem: which network topology has the highest synchronizability? I will first show that the optimality condition can be expressed solely in terms of the Laplacian eigenvalues. The class of optimal networks contains all directed trees with appropriate connection weights, and most in the class have well-defined directionality. I will also discuss the robustness of optimality against the structural perturbation, as well as the role of directionality in the connectivity patterns in enhancing the synchronizability.   

Correlation Networks of Earthquakes

Earthquake events are complex spatiotemporal phenomena, the space and time dependence of which are still not understood. Recently work has been done to explain these events using network modeling, defining links by successive events or probabilities. Our novel approach defines a new kind of network model which defines links through correlation. We find broad correlations across large distances and memory-like signal self-similarity, with statistically significant ``synching'' of different locations to each other.   

Conjecture of Alexander and Orbach.

The dynamical properties of fractal networks have received wide range of attention. Works on this area by several pioneering authors$^{1-2}$ have led to the introduction of the \textit{spectral dimension} that dictates the \textit{dynamic} properties on a fractal lattice. Most of the studies involving spectral dimension have been performed on a type of fractal lattice known as \textit{percolation} network. Alexander and Orbach$^{2}$ conjectured that the spectral dimension might be exactly 4/3 for percolation networks with Euclidean dimension $d_{e }\ge $ 2. Recent numerical simulations, however, could not decisively prove or disprove this conjecture, although there are other indirect evidences that it is true. We apply a stochastic approach$^{3}$ to determine the spectral dimension of percolation network for d$_{e }\ge $ 2 $a$nd check the validity of the Alexander-Orbach conjecture. Our preliminary results on 2- and 3-dimensional percolation networks indeed show that Alexander-Orbach conjecture is true, resolving a long-standing debate. References: 1. P. G. deGennes, La Recherche 7 (1976) 919. 2. S. Alexander and R. Orbach, J. Phys. Lett. (Paris) 43 (1982) L625. 3. J. Rudra and J. Kozak, Phys. Lett A 151 (1990) 429.   

Dense Random Fiber Networks Deform as Stochastic Fractal Objects.

The mechanical behavior of random fiber networks is essential in many biological and non-biological systems such as the cytoskeleton, tissue scaffolds and cellulose structures. Here we show that random fiber networks of densities much larger than that of the stiffness percolation threshold are stochastic heterogeneous elastic media with fractal distribution of elastic constants. The elasticity of these networks, both elastic constants and fields, while fluctuating significantly with position, is long-range correlated. The range of scales for stochastic self-similarity is bounded below by the mean fiber segment length and above, by the fiber length. This implies that no scale decoupling exists and no representative volume elements can be identified on scales below the upper cut-off scale, which provides an explanation for the observed delocalized effect of local mechanical perturbations in systems of semi-flexible fibers such as the cytoskeleton.   

Voter dynamics on an adaptive network with finite average connectivity

We study a simple model for voter dynamics in a two-party system. The opinion formation process is implemented in a random network of agents in which interactions are not restricted by geographical distance. In addition, we incorporate the rapidly changing nature of the interpersonal relations in the model. At each time step, agents can update their relationships, so that there is no history dependence in the model. This update is determined by their own opinion, and by their preference to make connections with individuals sharing the same opinion and with opponents. Using simulations and analytic arguments, we determine the final steady states and the relaxation into these states for different system sizes. In contrast to earlier studies, the average connectivity (``degree'') of each agent is constant here, independent of the system size. This has significant consequences for the long-time behavior of the model.   

Dynamics of priority-queue networks

Recent application of priority queue models for human dynamics opened a way to study the human behavior under quantitative framework. Given the evident active engagement in social networking of individuals, dynamics of priority queues forming networks needs to be understood. Along this line, here we study the dynamics of priority-queue networks by generalizing the binary interacting priority queue model of Oliveira and Vazquez (OV). We found that the OV model with AND-type protocol for interacting tasks is in general not scalable for the queue networks with more than two queues, because the dynamics for interacting tasks become quickly frozen due to the priority conflicts. We then consider a scalable interaction protocol, an OR-type one, and examine the effects of the number of queues and the network topology on the waiting time dynamics of the priority-queue networks, finding that its distribution exhibits power-law tail in all cases considered, yet with exponents dependent on the network topology. We also show that when the tasks in the queue network are executed synchronously, priority conflicts affect the waiting time dynamics strongly, resulting in a different power law.   

About human activity, long-term memory, and Gibrat's law

A central research question in the social sciences for several centuries has been whether any law like patterns in the unintended outcomes of human action exist. Here we investigate the existence of scaling laws in the human activity of communication, considering the number of messages sent by individuals as a growth process in time. We analyze millions of messages sent in two social online communities and uncover power-law relations between fluctuations in the growth rate and the activity of the members. We attribute this scaling law to a long-term persistence of human activity beyond daily or weekly cycles holding up to more than a year. Based on such an underlying long-term correlated dynamics, we elaborate a consistent framework for the empirical evidences, establishing a missing link between the scaling behavior in the growth and long-term persistence. Our results indicate that large fluctuations in communication activity can be expected as an unintended consequence of human interaction. This finding is of importance for both designing communication systems and for understanding the dynamics of social systems.   

Tour de Sys: The traveler's view of a network

The plight of the Flatlander is imperfect information about a high-dimensional object. Yet even so, the clever inhabitant of a low-dimensional world can gain a great deal of information about such an object by examining it from many perspectives. We analyze complex transportation networks by using shortest-path trees to measure universal network properties from different locations. Furthermore, by defining a measure of a node's geographical access area we give a more realistic characterization of the centrality or remoteness of a location. The network topology indicates a clear distinction between the center and edge of a network, but we find that examining the weights of links is crucial, as the distinction in the weighted network for some quantities is even more pronounced. Often prior research has not focused on the weightedness of transportation networks, in spite of the fact that this property has an obvious bearing on how the networks are actually used. We show that measuring networks with weighted edges significantly affects their statistics. Our analysis indicates dynamical processes occurring on these networks should behave in a manner very different than what is predicted by considering topology alone.   

Universality and the lack of it in multiscale human mobility networks

Although significant research effort is currently devoted to the understanding of complex human mobility and transportation networks, their statistical features are still poorly understood. Specifically, to what extent geographical scales impose structure on these networks is largely unknown. In particular, in light of the use of human mobility models in the development of quantitative theories for spatial disease dynamics, a comprehensive understanding of their structure is of fundamental importance. The large majority of statistical properties (degree distributions, centrality measures, clustering, etc.) of these networks have been obtained either for large scale networks or on small scale systems, indicating significant yet poorly understood deviations. We will present the first investigation of multiscale and multi-national mobility networks, covering length scales of a few to a few thousand kilometers. We will report that certain properties such as mobility flux distribution are universal and independent of length scale, whereas others vary systematically with scale. In particular, controversial properties such as scale-free degree distributions lose their heavy tails in small to intermediate length-scale windows.   

Monte Carlo Studies of the Isoperimetric Dimension of Growing Droplets in Metastable Decay of the Ising Model on Small-World Graphs

For the Ising model on a regular, nearest-neighbor lattice of less than 6 dimensions, metastable decay occurs via the nucleation of critical droplets; subcritical droplets are biased toward shrinkage, whereas supercritical droplets are biased toward growth. The size of a critical droplet is governed by the competition between the coupling of the magnetic field to the volume of the droplet, which lowers the free energy, and the coupling of the droplet of the stable state to metastable state at the boundary of the droplet, which increases the free energy. This competition between volume effects and surface effects makes the isoperimetric dimension relevant to metastable decay. The simulations discussed here are for a triangular lattice with a small percentage of ``small-world'' connections. The system initially has only one ``down'' spin, from which the droplet grows; switching is irreversible and only occurs for ``up'' spins adjacent to at least one ``down'' spin.   

Functional vs. Structural Modularity: do they imply each other?

While many deterministic and stochastic processes have been proposed to produce heterogeneous graphs mimicking real-world networks, only a handful of studies attempt to connect structure and dynamics with the function(s) performed by the network. In this talk I will present an approach built on the premise that structure, dynamics, and their observed heterogeneity, are implementations of various functions and their compositions. After a brief review of real-world networks where this connection can explicitly be made, I will focus on biological networks. Biological networks are known to possess functionally specialized modules, which perform tasks almost independently of each other. While proposals have been made for the evolutionary emergence of modularity, it is far from clear that adaptation on evolutionary timescales is the sole mechanism leading to functional specialization. We show that non-evolutionary learning can also lead to the formation of functionally specialized modules in a system exposed to multiple environmental constraints. A natural example suggesting that this is possible is the cerebral cortex, where there are clearly delineated functional areas in spite of the largely uniform anatomical construction of the cortical tissue. However, as numerous experiments show, when damaged, regions specialized for a certain function can be retrained to perform functions normally attributed to other regions. We use the paradigm of neural networks to represent a multitasking system, and use several non-evolutionary learning algorithms as mechanisms for phenotypic adaptation. We show that for a network learning to perform multiple tasks, the degree of independence between the tasks dictates the degree of functional specialization emerging in the network. To uncover the functional modules, we introduce a method of node knockouts that explicitly rates the contribution of each node to different tasks (differential robustness). Through a concrete example we also demonstrate the potential inability of purely topology-based clustering methods to detect functional modules. The robustness of these results suggests that similar mechanisms might be responsible for the emergence of functional specialization in other multitasking networks, as well, including social networks.