| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday |
This page lists the abstracts for the talks part of the ECCS08 conference
| Talks Abstracts | ||
|---|---|---|
 |
Ricardo Baeza-Yates Yahoo! Research |
Complex Networks Derived from Queries User queries in search engines and Websites give valuable information on the interests of people. In addition, clicks after queries relate those interests to actual content. Even queries without clicks or answers imply important missing synonyms or content. In this presentation we will cover how to derive complex graphs from queries. We will show that these graphs strongly resemble scale-free networks and that almost all the measures of these graphs are well approximated by power laws. We will also show one of the main applications of them, how to extract knowledge from the usage of the Web, that is, from the wisdom of crowds. |
 |
Albert-Laszlo Barabasi Notre Dame |
Human Mobility Patterns Despite their importance for urban planning, traffic forecasting and the spread of biological and mobile viruses, our understanding of the basic laws governing human motion remains limited owing to the lack of tools to monitor the time-resolved location of individuals. We study the trajectory of anonymized mobile phone users, finding that, in contrast with the random trajectories predicted by the prevailing Le´vy flight and random walk models, human trajectories show a high degree of temporal and spatial regularity, each individual being characterized by a time independent characteristic travel distance and a significant probability to return to a few highly frequented locations. After correcting for differences in travel distances and the inherent anisotropy of each trajectory, the individual travel patterns collapse into a single spatial probability distribution, indicating that, despite the diversity of their travel history, humans follow simple reproducible patterns. This inherent similarity in travel patterns could impact all phenomena driven by human mobility, from epidemic prevention to emergency response, urban planning and agent-based modeling. |
 |
Ofer Biham The Hebrew University, Jerusalem. |
Efficient stochastic simulations of reaction networks with fluctuations Systems which consist of multiple species of reacting particles can be described by reaction networks. The dynamics of such networks is commonly modeled by rate equations, which are valid for macroscopic systems. However, in many chemical and biological systems, the copy numbers of some of the reactive species are small, giving rise to large fluctuations. Under these conditions, the rate equations fail and stochastic methods (such as the direct integration of the master equation and Monte Carlo simulations) are required. However, these methods are computationally intensive and are impractical for complex networks. In this talk I will present two methods that provide efficient stochastic modeling of reaction networks with fluctuations: (a) The multiplane method [1] is based on a dimensional reduction of the master equation, in which the dimensionality is dramatically reduced; (b) The moment equation method [2] consists of one equation for each reactive species and one equation for each reaction, which are derived from the master equation using a highly effective truncation scheme. The efficiency, accuracy and applicability of these methods to a broad range of chemical and biological systems will be demonstrated. References: 1. Efficient simulations of gas-grain chemistry in interstellar clouds. 2. Efficient stochastic simulations of complex reaction |
 |
Irun Cohen Weizmann Institute |
A Paradigmatic Complex System: The Immune System The immune system provides accessible data about the evolution, the organizational operation and the end function of a complex system; immunology exemplifies the evolution, the organizational sociology and the end function of complex systems’ research. I shall discuss select issues related both to the system and to the science that studies the system. The system: Evolution (from innate to adaptive immunity); Organization (degeneracy of recognitions and interactions; pleiotropic and redundant agents); End function (body protection or body maintenance). The science: Evolution (from clonal selection to systems biology; the quest for optimums); Organization (molecular biology versus physiology); End function (prevention and cure of disease). |
 |
Sol Efroni NIH |
Title abstract |
 |
Shintaro Funahashi Kyoto University |
Prefrontal cortex and decision-making The prefrontal cortex has been known to participate in working memory processes. Tonic sustained activation observed during the delay period (delay-period activity) has been considered as a neural correlate of the mechanism for active maintenance of information. Neurophysiological studies revealed that delay-period activity represents retrospective information (e.g., sensory events) as well as prospective information (e.g., forthcoming motor information). This suggests that delay-period activity participates in decision processes regarding motor performances based on the sensory information. To examine how delay-period activity participates in the decision of a motor behavior, we analyzed prefrontal activity while monkeys performed two tasks: ODR and S-ODR tasks. In the ODR task, monkeys were required to make a memory-guided saccade to the cue location after a 3-s delay. In the S-ODR task, four identical visual cues were presented simultaneously during the cue period and monkeys were required to make a saccade in any one direction after the delay. Delay-period activity was observed in both tasks in the same neuron with similar directional preferences. Neurons with delay-period activity were classified into several groups based on the temporal pattern of the activity itself and of the strength of the directional selectivity. Among these, neurons with an increasing type of delay-period activity with persistent directional selectivity throughout the delay period in the ODR task also showed directional delay-period activity in the S-ODR task. These results indicate that an increasing type of delay-period activity, which is thought to represent motor information, plays an important role in generating and enhancing directional bias in the S-ODR task and therefore contributes significantly to the decision process of the saccade direction in the S-ODR task. |
 |
Shlomo Havlin Bar Ilan University |
Complex networks: theory and applications Complex systems which are composed of many interacting entities can be represented, analyzed and better understood using a network representation, where the entities are represented by nodes and the interactions by links. In recent years it was realized that the topology of many real networks is very different from that of the classical graph theory. In particular, while classical graphs were assumed to be homogeneous with every node having a typical number of links (degree) real networks are usually heterogeneous (e.g., the Internet) with nodes having very different degrees. Thus, many properties of networks were not understood and many open questions were asked. The finding of the new topology led, in recent years, to the emergence of a active field of complex networks where new suitable theories and approaches are developed. I will discuss these developments as well as many recent applications, such as robustness, effective immunization strategies and optimal transport in real world networks. References: [1] Transport in weighted networks: partition into superhighways and roads Z. Wu, L.A. Braunstein, S. Havlin, H.E. Stanley Phys. Rev. Lett. 96, 148702 (2006) [2] Limited path percolation in complex networks E. Lopez, R. Parshani, R. Cohen, S. Carmi, S. Havlin Phys. Rev. Lett. 99, 188701 (2007) [3] A model of Internet topology using k-shell decomposition S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, E. Shir PNAS 104, 11150 (2007) [4] Climate networks around the globe are significantly affected by El Nino K. Yamasaki, A. Gozolchiani, S. Havlin Phys. Rev. Lett. 100, 228501 (2008) [5] Finding a Better Immunization Strategy Y. Chen, G. Paul, S. Havlin, F. Liljeros, and H. E. Stanley Phys. Rev. Lett. 101, 058701 (2008) |
 |
Plamen Ivanov Boston University |
Statistical Physics in Physiologic Dynamics: Scale-invariant aspects abstract |
 |
Janos Kertesz Budapest University of Technology and Economics |
Modeling social networks on large scale Recent development in information and communication technology has enabled to study networks of social interactions of unprecedented size. Such systems include email or phone networks and e-communities. In contrast to the traditional, questionnaire-based investigations, in these cases a natural quantitative measure of the strength of the interactions is present (like the frequency or duration of calls) leading to weighted network representations. One important observation is that this strength of the interactions varies over many orders of magnitude. A natural conclusion is that the weights play important roles both in the evolution of the networks and in the dynamics of the processes on them. Based on simple rules borrowed from sociology we construct a model, where the emergence of the community structure is a consequence of the interplay between topology and weights. We show that the model reflects well the observations made on a huge call network. References: |
| Alan Kirman G.R.E.Q.A.M. |
The economy as a complex system. In this contribution I will try to explain why the complex systems approach is of particular interest currently for economists. Economic theory has recently been attacked on two fronts. The first is the problem of aggregation, how is the behavior of the economic system related to that of the individuals tbat make it up ? The second is that of why do individuals behave as they do ? The answer to the first question is simple but undermines much of modern macro-economics which is based on the idea that the behavor of the aggregate can be treated as the behavior of an individual. Yet what is known is that the standard model of a system composed of isolated indiviuals each solving his own maximising problem does not allow one to treat the system as an individual. The second question is that posed by behavioral economics which questions the idea of the isolated maximising individual. Ideas from Simon (1957) onwards have suggested that individuals reason in a limited and local way. Experiments, observation, and examination of the neural processes utilised in making decisions all suggest that homo economicus is not an accurate or adequate description of human decision making. All of this suggests that one might want to take a very different view of how the economy functions. In particular, the notion of a complex system as used in many parts of science, seems to correspond well to an intuitive vision of the economy. Just as in an ants’ nest individuals perform tasks without having any idea of the behavior of the system, individuals in an economy go abour their business and achieve a remarkable degree of coordination. I will use theory, experiments and simulations to provide examples of the approach I recommend. |
|
 |
Imre Kondor Collegium Budapest |
Strong random correlations in complex systems Complex systems (living organisms, the brain, society, the economy, etc.) seem to depend on a huge number of details which makes them nearly irreducible, so that they cannot be described in terms of a small number of variables. This poses fundamental difficulties for the modeling of such systems and the parametrization or calibration of any model that we may propose to describe them. Furthermore, this irreducibility also implies the existence of strong random correlations between a large number of the components of the system that are not necessarily close neighbours in a geometric sense, or not necessarily linked by strong, direct interactions. This makes the system sensitive to changes in the external control parameters, to boundary conditions, etc., and poses a serious challenge to computer simulations. These ideas are illustrated on some toy models: a spin glass, a random cellular automaton, and a game theoretical model. |
 |
Fabrizio Lillo University of Palermo |
How markets slowly digest changes in supply and demand I revisit the classic problem of price formation from a microstructure point of view, explaining how fluctuations in supply and demand are slowly incorporated into prices. Because revealed market liquidity is extremely low, large orders to buy or sell can only be traded incrementally, over periods of time as long as months. As a result order flow is a highly persistent long-memory process. Maintaining compatibility with market efficiency has profound consequences on price formation, on the dynamics of liquidity, and on the nature of impact. I review a body of theory that makes detailed quantitative predictions about the volume and time dependence of market impact, the bid-ask spread, order book dynamics, and volatility. Comparisons to data yield some encouraging successes. This framework suggests a novel interpretation of financial information, in which agents are at best only weakly informed and all have a similar and extremely noisy impact on prices. Most of the processed information appears to come from supply and demand itself, rather than from external news. The ideas reviewed here are relevant to market microstructure regulation, agent-based models, cost-optimal execution strategies, and understanding market ecologies. |
 |
Vittorio Loreto ISI Foundation, Roma “La Sapienza” |
Collective dynamics of social annotation Recent years have seen the explosion in popularity for social annotations systems through which users annotate resources (web pages, bibliographic references, digital photographs, etc.) with free-form text keywords, i.e., tags. The emergent data structures are complex networks with two unique peculiarities: i) they represent an externalization of semantic structures (networks of concepts grounded in cognition and typically hard to access; ii) the network is collectively built by the uncoordinated activity of thousands to millions of users, entangling semantics and user behaviour into a techno-social system. In this talk we show that the process of social annotation can be seen as a collective exploration of a semantic space, modeled as a graph, through a series of random walks. Strikingly these simple assumptions reproduce several main aspects, so far unexplained, of social annotation, among which the peculiar growth of the size of the vocabulary used by the community and its complex network structure. |
 |
Marc Mézard Université de Paris Sud |
Can nature solve hard problems? Nature certainly poses a lot of hard problems to the physicist or the chemist.But can natural systems, or nature-inspired artifacts, be used to solve hard problems? This general question can be made a bit more precise by focusing on combinatorial optimization problems. Simple attempts at solving problems like Hamiltonian path or Steiner tree seem far from the goal, and in many case it seems that the occurence of a glassy transition, which freezes the relaxation in metastable states, is the major obstacle. Recently, some of the hardest constraint satisfaction problems have been addressed successfully through message passing methods, with algorithms which partly get around the freezing transition. The talk will review this approach and discuss its limitations. Message passing, which is a purely local strategy based on the exchange of simple probabilistic messages along a graph of constraints, is not only very powerful, but also appealing since its basic ingredients share some similarity with neural networks. This points to alternative, ``natural'' ways of solving hard problems, through artifacts which get around the basic physical limitations of usual thermal systems. |
 |
Balázs Papp Hungarian Academy of Sciences |
Robustness revisited: The condition dependency of genetic interactions Why are most genes dispensable in most organisms? The impact of gene deletions may depend on the environment, the presence of compensatory mechanisms (mutational robustness), or both. Here, we analyse the interaction between these two factors by exploring the condition dependence of synthetic genetic interactions that define redundant functions and alternative pathways. We performed systems-level flux balance analysis of the yeast (Saccharomyces cerevisiae) metabolic network to identify genetic interactions and then tested the model's predictions with in vivo gene deletion studies. We found that the majority of synthetic genetic interactions are restricted to certain environmental conditions, partly due to the lack of compensation under some (but not all) nutrient conditions. These findings suggest that these gene pairs have at least partially independent functions, and hence compensation is only a by-product of their evolutionary history. Our work supports the view that functional redundancy may be more apparent than real, and it offers a unified framework for the evolution of environmental adaptation and mutational robustness. |
 |
Prabhakar Raghavan Yahoo! Research |
Heavy tails, search, and networks Heavy-tailed distributions have been observed in many phenomena involving consumer behavior, especially on the internet. We consider the problem of assembling a search engine of the future. We examine the impact of such heavy-tailed consumer behavior on the design choice for such an engine, and in the process highlight our poor understanding (and the need for much further research) into many concrete aspects of economically viable search engine operation. |
 |
Federico Ricci-Tersenghi University of Rome "La Sapienza" |
Phase transitions in random constraint satisfaction problems and algorithmic implications In very recent years the application of tools from statistical mechanics of disordered systems (spin glasses) to the study of random constraint satisfaction problems has led to the discovery of a very rich structure in the space of solutions of these problems. Many phase transitions have been identified, that typical instances undergo when the number of constraints per variables is increased. Algorithms for searching solutions are most probably sensible to some of these transitions and work is still in progress to understand this connection. |
 |
Willi Semmler The New School for Social Research |
Dynamic Decisions, Multiple Equilibria and Complexity Agent-based models represent the interaction between a multiplicity of agents through dynamic systems, often giving rise to intricate and complex dynamics. We can extend this type of economic analysis by emphasizing that economic agents have memories, form expectations, and are guided by intentional behavior within the context of a certain decision horizon. However, it is important to note that the agents' decisions and actions change the economic environment and affect the system dynamics. The interaction of agents is often stylized as predator-prey, competitive and cooperative interactions in the context of Lotka-Volterra systems. We start with these types of systems and show that economic agents' decisions can be understood as a perturbation term in the general system dynamics. The dynamics of a model with zero time-horizon, which has small effects on the system dynamics, can often be studied analytically and taken as starting point for a numerical analysis with a longer time horizon. Since, due to nonlinearities, multiple equilibria frequently arise, this generates path dependency and complex dynamics. We solve these types of models by using dynamic programming with a flexible grid size that can capture multiple equilibria and threshold and bifurcation behavior. Heterogeneity of agents and multiple attractors predict a bimodal distribution of outcomes which can empirically be verified using Markov transition matrices. We give a number of examples from resource economics, development economics, investment theory, industrial organization, imperfect capital markets, growth, distribution, and climate change. We give prototype examples and illustrate economic mechanisms wherein such complicated dynamics, e.g., those with threshold and bifurcation behavior, can occur. These types of models can not only be empirically tested, but have strong policy implications in the sense that policy can tilt the dynamics toward superior equilibria and increase the domain of attraction for preferable equilibria. |
 |
Fernando Vega-Redondo European University Institute, Florence |
Network Organizations It is common to define a network organization as one that is fast and flexible in adapting to changes in the underlying environment. But besides the short-run advantages of adaptability, fast changes in the structure of the organization can also be detrimental in the longer run. This happens because a widespread knowledge of the organization's structure is important in channelling (and thus speeding up) search. I discuss the trade-off between adaptability and structural stability in a changing environment where, if the structure of the organization adjusts, information on the exact nature of the change becomes known only with some lag. The main conclusion is that, as environment becomes more volatile, the optimal operational mode of the organization essentially passes from being totally flexible to being completely rigid, i.e. no intermediate options are ever optimal. Intuitively, this is a reflection of what could be heuristically understood as increasing returns to structural stability. Thus, when the preservation of some structure is beneficial, the optimal arrangement involves the preservation of all structure. An analogous conclusion applies in the opposite direction: when it is beneficial to have a partially adaptive structure, full adaptation is optimal. |
 |
Tandy Warnow The University of Texas at Austin |
Computational and mathematical challenges involved in estimating evolutionary histories. Phylogenetic inference presents enormous computational and mathematical challenges, but these are particularly exacerbated when dealing with very large datasets (containing thousands of sequences) or when sequences evolve under complex evolutionary processes (ranging from simple "indel" models, to horizontal gene transfer, to genome rearrangement events). In this talk, I will describe some of the recent progress on evolutionary history reconstructing under complex evolutionary processes, focusing in particular on multiple sequence alignment and its implications for large-scale phylogenetics. Related Link: http://www.phylo.org - CIPRES project webpage. |
 |
Gur Yaari ISI Foundation |
The case of the altruist meme Altruism elicits in humans very powerful and diverse feelings. Its paradoxical nature makes it mysterious and challenging to understand. It is difficult to understand why a rational being would sacrifice its own interests for somebody else, especially if one's reproduction fitness depends on them. It is also difficult to believe that such a trait would survive natural selection. In fact it was shown by rigorous theorems in a wide range of conditions that the Nash stable strategy is to be selfish and not to share. We show that the resources sharing phenotype is highly favored and wins natural selection dramatically if instead of incurring fixed gain and losses, the players gain or loose fixed fractions of their current resources. Thus the solution of the sharing paradox resides in recognizing the random multiplicative (rather then the usual game-theory "additive") character of the real life, society, economic and cultural "games". In this talk I will present analytical and numerical results for different variations of the model along with results from intensive computer simulations that support and clarify these results |