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

From network dynamics to human activity and mobility patters

The next challenge of network research is to go beyond the structure and quantify the dynamics of interconnected systems. A particular difficult facet of this research requires us to understand the temporal and spatial driving forces that govern social, technological and biological networks. In this talk I will focus on the dynamical mechanism that drive the activity of social networks. While none of us thinks of our daily activity pattern as random, most modeling efforts approximate human activity with fundamentally random spacial and temporal patterns. My purpose is to offer evidence of a series of significant deviations from this random expectation. I will talk about the bursty temporal character of human activity patterns and the travel patterns of individuals. I will show that both human activity and travel patterns are far more regular than the standard Poisson and diffusion models would predict, with implications on agent based models, epidemic modeling as well as the nature of time and space experienced by humans. The work was done in collaboration with Marta Gonzales, Cesar Hidalgo, Kwang-il Goh, Joao Oliveria, and Alexei Vazquez.   

Finite Size Effects and Symmetry Breaking in the Evolution of Networks of Competing Boolean Nodes

The effects of finite network size on the evolutionary dynamics of a Boolean network are analyzed. In the model considered, Boolean networks evolve via a competition between nodes that punishes those in the majority. Finite size networks evolve in a fundamentally different way than infinitely large networks do. The symmetry of the evolutionary dynamics of infinitely large networks that selects for canalizing Boolean functions is broken in finite size networks. In finite size networks there is an additional selection for input inverting Boolean functions. Classes of functions are found empirically to evolve with the same frequency. The classes depend on the symmetry of the evolutionary dynamics and correspond to orbits of the relevant symmetry group. The empirical results match analytic results, determined by utilizing Polya's theorem, for the number of orbits expected in both finite size and infinitely large networks. The reason for the symmetry breaking is due to the need for nodes in finite size networks to behave differently in order to cooperate to collectively perform efficiently. The results suggest that both finite size effects and symmetry are important for understanding the evolution of real-world complex networks, including genetic regulatory networks.   

Attractors in continuous and Boolean networks

Random Boolean models of complex regulatory networks are known to exhibit rich dynamical behaviors, including an order/disorder transition. We show that implementation of the nominal Boolean logic of a network using differential equations involving sigmoidal switching functions generically leads to deviations from the Boolean predictions. On simple rings, the ``reliable'' set of Boolean attractors corresponds to the stable attractors of the analogous continuous system. For networks with more complex logic, however, the set of the continuous attractors is determined by non-Boolean characteristics of the switching events. In large random networks, the nature of the order/disorder transition is altered by collective effects associated with compositions of the sigmoidal switching functions.   

Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks

The topology have profound impact on the efficiency of search on unstructured peer-to-peer (P2P) networks as well as other networks. It has been well-known that search on scale-free (power-law) topologies offer outstanding search efficiency as good as $O(\ln \ln N)$ for a range of degree distribution exponents. However, generation and maintenance of such scale-free topologies are hard to realize in a distributed and potentially uncooperative environments as in the P2P networks. A key limitation of scale-free topologies is the high load (i.e. high degree) on very few number of hub nodes. In a typical unstructured P2P network, peers are not willing to maintain high degrees/loads as they may not want to store large number of entries for construction of the overlay topology. So, to achieve fairness and practicality among all peers, hard cutoffs on the number of entries are imposed by the individual peers. Thus, efficiency of the flooding search reduces as the size of the hard cutoff does. Interestingly, we observe that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases.   

A Self--organized model for network evolution

Here we present a self-organized model for the evolution of complex networks. Vertices of the network are characterized by a variable evolving through an extremal dynamics process. The network topology is in turn shaped by the variable itself. More specifically, to each vertex a fitness is assigned; then, in the evolution, the vertex with minimum fitness and its neighbors are updated by extracting new fitnesses. For any given realization of fitnesses we can determine the edges in the network through a fitness dependent rule. We show analytically and numerically that this system self--organizes to a nontrivial state. A power--law decay of dynamical and topological quantities above a threshold emerges spontaneously, as well as a feedback between different dynamical regimes and the underlying network's correlation and percolation properties.   

Money circulation networks reveal emerging geographical communities

Geographical communities and their boundaries are key determinants of various spatially extended dynamical phenomena. Examples are migration dynamics of species, the spread of infectious diseases, bioinvasive processes, and the spatial evolution of language. We address the question to what extend multiscale human transportation networks encode geographical community structures, how they differ from geopolitical classifications, whether they are spatially coherent, and analyse their structure as a function of length scale. Our analysis is based on a proxy network for human transportation obtained from the geographic circulation of more than 10 million dollar bills in the United States recorded at the bill tracking website www.wheresgeorge.com. The data extends that of a previous study (Brockmann et al., Nature 2006) on the discovery of scaling laws of human travel by an order of magnitude and permits an approach to multiscale human transportation from a network perspective.   

Functional structure through dynamic clustering of neuronal networks

We propose a new method for detecting functional structure in neuronal networks based solely upon the information derived from the spike timings of the neurons. Unlike traditional algorithms that depend on knowledge of the topological structure of the network to parse the network into communities, we dynamically cluster the neurons to build communities with similar functional interactions. We define means to derive optimal clustering parameters and investigate what conditions have to be fulfilled to obtain reasonable predictions of functional structures.   

Citation analysis: Beyond the Journal Impact Factor

The journal impact factor is a robust measure of the average citation performance of a journal, but the number of citations varies widely from paper to paper within any journal. Therefore, it makes sense to look for additional ways of characterizing journals in terms of their impact. We introduce the ``citation density curve'' (citations per paper in a given year for papers published in the previous two years, plotted vs. the citation rank of these papers). This curve, which displays a Zipf's law behavior, contains all the pertinent information about a journal: its size, its impact factor, the maximum number of citations per paper, the relative size of the top-cited portion of the journal, how the citation density varies within the journal, etc. Being the ``fingerprint'' of a journal, the citation density curve can be used: (a) by editors, for strategic decisions affecting the future of their journal; (b) by citation analysts, for comparing (ranking) journals; and (c) by authors, for assessing the relative impact of their published work. Further, we identify a complementary metric to the impact factor, a single number that characterizes the top-cited portion of a journal. This metric reproduces the ranking of the citation density curves for various journals, and can be readily calculated from the same data used in the impact factor calculations. We propose that this new metric be used as an essential complement to the impact factor in assessing the true impact of journals.   

Epidemics on adaptive networks with geometric constraints

When a population is faced with an epidemic outbreak, individuals may modify their social behavior to avoid exposure to the disease. Recent work has considered models in which the contact network is rewired dynamically so that susceptibles avoid contact with infectives. We consider extensions in which the rewiring is subject to constraints that preserve key properties of the social network structure. Constraining to a fixed degree distribution destroys previously observed bistable behavior. The most effective rewiring strategy is found to depend on the spreading rate.   

Some aspects on human preference in communication and friendship

The objects of our investigation are social networks consisting of individual actants as nodes and their relations as links. Recently, on-line communities have gained immense popularity as indicated by millions of members participating in these platforms. Fortunately, the information given by member activity provides an ideal environment to study structural preferences of social behavior. In particular, we address the questions of how network topology benefits the establishment of new relations between the actants. Among others, we find that actants tend to get connected at a distance of 2. Further analysis indicates that the more common neighbors two actants have, the more likely they will be in relation with each other. We attribute this behavior to some kind of social pressure imposed by the neighborhood biasing the actants preferences.   

Studying Human Dynamics Through Web Analytics

When Tim Berners Lee, a physicist at the European Center for Nuclear Research (CERN) first conceived the World Wide Web (WWW) in $1990$ as a way to facilitate the sharing of scientific information and results among the centers different researchers and groups, even the most ingenious of science fiction writers could not have imagined the role it would come to play in the following decades. The increasing ubiquitousness of Internet access and the frequency with which people interact with it raise the possibility of using it to better observe, understand, and even monitor several aspects of human social behavior. Websites with large numbers of frequently returning users, such as search engines, company or university websites, are ideal for this task. The properly anonymized logs detailing the access history to Emory University's website is studied. We find that a small number of users is responsible for a finite fraction of the total activity. A saturation phenomenon is observed where, certain connections age, becoming less attractive to new activity over time. Finally, by measuring the average activity as a function of the day of the week, we find that productivity seems to be higher on Tuesdays and Wednesdays, with Sundays being the least active day.   

Which Route Will You Choose to Use For Driving Home Tonight in Rush-Hour Traffic?

The best answer to the question posed in the title for a city of drivers requires knowing the optimal routes for congested traffic flow on complex networks. This is known to be an NP-hard problem. Despite this fact, we will present answers calculated in only polynomial time using extensions of a recently introduced heuristic algorithm [Danila, et al., PRE 74, 046106 (2006)] that, at least, scale optimally with network size. Using the optimal routes allows a network to support the maximum traffic load and significantly reduces the average travel time in congested traffic. The results presented apply to vehicular traffic and to traffic on wireless communication networks.   

Epidemic of cell phone virus

Standard operating systems and Bluetooth technology will be a trend for future cell phone features. These will enable cell phone viruses to spread either through SMS or by sending Bluetooth requests when cell phones are physically close enough. The difference in spreading methods gives these two types of viruses' different epidemiological characteristics. SMS viruses' spread is mainly based on people's social connections, whereas the spreading of Bluetooth viruses is affected by people's mobility patterns and population distribution. Using cell phone data recording calls, SMS and locations of more than 6 million users, we study the spread of SMS and Bluetooth viruses and characterize how the social network and the mobility of mobile phone users affect such spreading processes.