Session H9: Complex Networks and Their Applications

Dependence on Initial Conditions in a Numerical Model of River Network Formation

We investigated the effect of initial conditions on river network formation, using a simple model of erosional dynamics. Previous research suggests that river network scaling and geomorphic properties may be sensitive to initial conditions, but this has not been systematically studied. We used simulations of a stream power law, with initial conditions consisting of a flat or sloping surface combined with random fluctuations in elevation, and considered dependence of steady-state solutions on initial slope and randomness. The sinuosity exponent and the sinuosity are sensitive to these initial conditions, while the Hack exponent and hypsometry show little or no sensitivity. The results suggest that initial conditions deserve greater consideration in attempts to understand the emergence of scaling in river networks.   

Optimization of Ramified Flow Networks

A class of Ramified graphs (RG) is introduced as Iterated Function Systems (IFS) to optimally design networks for efficient reverse osmosis desalination in deep seawater. Ramified flow networks of absorbers, ranging from simple structures with constant weights, branch angles, and branch ratios, to fully optimized binary networks are considered. A contracting IFS with fixed overall length is presented for the generation of RG's which serve as candidates for optimality in terms of desalination performance criteria. Using the analogy to electrostatics, the diffusion equation is solved for the desalination systems under three different boundary conditions, i) all nodes having the same pressure difference across the absorbers, ii) all nodes producing permeate at identical rates, and iii) each node having the same salinity. Optimal branching angles and branch length ratios will be found by phase-space methods for each boundary condition, which either maximize production of permeate or minimize expenditure of energy for different fixed numbers of absorbers. For constant salinity absorbers, we give the total water production rate as functions of branching angle and branching ratio for up to 10 branching generations. Both optimal angle and optimal ratios are found to be decreasing functions of generation for constant salinity absorbers.   

Reaction fronts and synchronization in ordered and disordered vortex networks

We present experimental studies of front propagation and synchronization in an advection-reaction-diffusion system. The reaction is either the excitable or oscillatory Belousov-Zhabotinsky chemical reaction, and the flow is an array or annular chain of vortices forced using magnetohydrodynamic techniques. The reaction in each vortex acts as a node in a complex fluid network, and communication between these nodes is via chaotic mixing. Mixing in this system is either diffusive (enhanced) or superdiffusive, depending on the forcing protocol. We find that the network with the oscillatory reaction synchronizes if the mixing is superdiffusive with long-range connections. We also find that reaction fronts in this system typically pin to moving vortices. We explore any changes in front propagation behavior when the transport changes from normal diffusion to superdiffusion.   

Infinitely Robust Order and Local Order-Parameter Tulips in Apollonian Networks with Quenched Disorder

For a variety of quenched random spin systems on an Apollonian network, including ferromagnetic and antiferromagnetic bond percolation and the Ising spin glass, we find the persistence of ordered phases up to infinite temperature over the entire range of disorder.[1] We develop a renormalization-group technique that yields highly detailed information, including the exact distributions of local magnetizations and local spin-glass order parameters, which turn out to exhibit, as function of temperature, complex and distinctive tulip patterns. [1] C.N. Kaplan, M. Hinczewski, and A.N. Berker, arXiv:0811.3437v1 [cond-mat.dis-nn] (2008).   

Correlated Spin Networks in Spin Glasses

We introduce a network model for frustrated spin systems based on highly correlated spin fluctuations, which allows us to quantify and visualize their ordering. In this model, individual lattice sites are treated as nodes, with links between any two nodes existing only if the correlated fluctuations between those two nodes are above a threshold value. As a test case, we have implemented this model on the two-dimensional Ising antiferromagnet on a triangular lattice with randomly inserted ferromagnetic bonds, which has a finite temperature spin-glass phase transition.$^{1}$ In the paramagnetic phase, nodes within a network are spatially contiguous and networks are localized to areas of relieved frustration. In the spin-glass phase, a very broad degree distribution physically manifests itself through networks of strongly correlated but non-contiguous spins. This finding is consistent with that predicted via chaotic rescaling.$^{2}$ 1. Grest G.S. and Gabl E.G., Phys. Rev. Lett. \textbf{43}, 1182 (1979). 2. McKay S.R., Berker A.N. and Kirkpatrick S., Phys. Rev. Lett. \textbf{48}, 767 (1982).   

Influence of spatial dependence on the eigenvalue spectrum of complex networks

Many real life networks are known to exhibit a spatial dependence (SD), i.e. the probability to form a link between two nodes in the network, inversely depends on the distance between them. We investigate the influence of SD on the eigenvalue spectrum of networks. By increasing the SD in Erd\"{o}s R\'{e}nyi (ER), scalefree, and small-world networks we find that the eigenvalue spectrum becomes asymmetric, as a result of the increased clustering in the system. We quantify this asymmetry by the skewness, kurtosis, and the change in highest and lowest eigenvalues of the spectrum as a function of SD. Our results show that the eigenvalue spectrum can be used as a tool to detect SD in real-life networks. We illustrate this ability for the eigenvalue spectrum of a spatial dependent polymeric gel.   

A family of fat-tail random matrix ensemble

We present a family of novel fat-tail random matrix ensembles characterized by a parameter $\lambda$. We show that the eigenvalue densities of the ensembles exhibit a power law distribution. In particular, for $\lambda>1$, the tail of the distribution is bounded, whereas for $\lambda<1$, the distribution has a fat tail. In the limit $\lambda=1$, the ensemble corresponds to the well-established critical ensemble. We evaluate the eigenvalue correlations in terms of a novel family of orthogonal polynomials that are generalizations of the q-Hermite polynomials. We show that the two-level correlation of the novel fat-tail ensemble is qualitatively different from that of either the Gaussian or the critical ensemble.   

Poisson vaccination for epidemic control in adaptive social networks

We study an epidemic model for disease spread on an adaptive network modeling avoidance behavior. Individuals are assumed to adapt their social behavior to minimize their risk of disease. Non-infected nodes rewire their connections away from infected nodes to connect instead to other non-infected nodes, and the disease follows an SIS (susceptible-infected-susceptible) dynamics. We add Poisson distributed vaccination of susceptibles. Effects of the vaccination frequency and amplitude are studied in the full system and compared to a mean field theory. Disease extinction rates using vaccination are found for both adaptive and static networks. We show that vaccine control is much more effective in adaptive networks than in static networks due to an interaction between the rates of adaptive network rewiring and vaccine application.   

Epidemics in Complex Networks: The Diversity of Hubs

Many complex systems are believed to be vulnerable to spread of viruses and information owing to their high level of interconnectivity. Even viruses of low contagiousness easily proliferate the Internet. Rumors, fads, and innovation ideas are prone to efficient spreading in various social systems. Another commonly accepted standpoint is the importance of the most connected elements (hubs) in the spreading processes. We address following questions. Do all hubs conduct epidemics in the same manner? How does the epidemics spread depend on the structure of the network? What is the most efficient way to spread information over the system? We analyze several large-scale systems in the framework of of the susceptible/infective/removed (SIR) disease spread model which can also be mapped to the problem of rumor or fad spreading. We show that hubs are often ineffective in the transmission of virus or information owing to the highly heterogeneous topology of most networks. We also propose a new tool to evaluate the efficiency of nodes in spreading virus or information.   

Prevalence of and Epidemic Spreading on Hierarchical Networks

Recent studies show that real networks are organized in a modular or even hierarchical fashion. However, there is no clear mathematical definition of hierarchy and current studies do not tell us the degree to which a network is hierarchical. In this talk, we will discuss a quantitative measurement of hierarchy. We find that networks of protein interactions, metabolic pathways, electronic circuits, power grids, and emails display strong hierarchy compared with networks generated at random or scale free networks of the Barab\'asi-Albert model. Further, we investigated the spread of virus in hierarchical networks. Viral spread on hierarchical networks displays quite different pattern from scale free and random networks.   

Understanding the spreading patterns of mobile phone viruses

Mobile viruses are little more than a nuisance today, but given our increased reliance on wireless communication, in the near future they could pose more risk than their PC based counterparts. Despite of the more than three hundred mobile viruses known so far, little is known about their spreading pattern, partly due to a lack of data on the communication and travel patterns of mobile phone users. Starting from the traffic and the communication pattern of six million mobile phone users, we model the vulnerability of mobile communications against potential virus outbreaks. We show that viruses exploiting Bluetooth and multimedia messaging services (MMS) follow markedly different spreading patterns. The Bluetooth virus can reach all susceptible handsets, but spreads relatively slowly, as its spread is driven by human mobility. In contrast, an MMS virus can spread rapidly, but because the underlying social network is fragmented, it can reach only a small fraction of all susceptible users. This difference affects both their spreading rate, the number of infected users, as well as the defense measures one needs to take to protect the system against potential viral outbreak.   

Partitioning Links: A New Approach to Communities in Complex Networks

We propose a new viewpoint for the problem of community detection in complex networks. Rather than defining a community as a set of densely interconnected nodes, we define a community as a set of (related) links. We show how this alternative viewpoint incorporates significant aspects including overlapping communities. A quantitative framework for evaluating the link partitions is also introduced.   

Community Structure in Online Collegiate Social Networks

Online social networking sites have become increasingly popular with college students. The networks we studied are defined through ``friendships'' indicated by Facebook users from UNC, Oklahoma, Caltech, Georgetown, and Princeton. We apply the tools of network science to study the Facebook networks from these five different universities at a single point in time. We investigate each single-institution network's community structure, which we obtain through partitioning the graph using an eigenvector method. We use both graphical and quantitative tools, including pair-counting methods, which we interpret through statistical analysis and permutation tests to measure the correlations between the network communities and a set of characteristics given by each user (residence, class year, major, and high school). We also analyze the single gender subsets of these networks, and the impact of missing demographical data. Our study allows us to compare the online social networks for the five schools as well as infer differences in offline social interactions. At the schools studied, we were able to define which characteristics of the Facebook users correlate best with friendships.   

Patterns of behavior in an online community

Human behavior can be seen as the expression of inherent motives. Despite the diverse range of these motives, social theorists have long identified a small number of distinct underlying mechanisms, where, consciously or unconsciously, every individual tries to exploit a different aspect of social interactions and/or optimize the efficiency of certain procedures for the benefit of the society or for personal gain. Here we show that users in an online community follow certain behavioral patterns and the choice of their favorite members is far from a random process. More importantly, these patterns are systematically modified with time as a member becomes more involved in such a community. We are able to identify a crossover in the average behavior of the members when their favorites list exceeds roughly 10 favorites. Additionally, this process allows us to identify individuals with a markedly different behavior than the average person. This study can help us understand the process of establishing friendships and the motives behind this process.   

Renormalization describes distinct regimes of information flow in complex networks

The speed at which information travels from one site to another in a complex system is largely determined by the number of short-cuts within the network topology. It remains an important open question how to optimize the connectivity of the links in the network structure to minimize the travel time. Here we show that ideas taken from renormalization group theory applied to complex self-similar networks are essential to define distinct regimes of information flow within the network. We find that networks that are human decision based such as the WWW are sufficiently randomized to give a topology that is close to optimal. On the other hand, biological evolution-based networks show evidence of clear sign of a modular deterministic structure shaped by evolution showing suboptimal large-world character which may be even so as a mean of protection, preservation and conservation.