CSSS 2010 Santa Fe-Final Papers

From Santa Fe Institute Events Wiki

CSSS Santa Fe 2010

Human Mobility in an Online World

Massive multiplayer online games provide a fascinating new way of observing hundreds of thousands of simultaneously interacting individuals engaged in virtual socio-economic activities. We have compiled a data set consisting of practically all actions of all players over a period of three years from an online game played by over 350,000 people. The universe of this online world is a network on which players move to interact with other players. This interaction may consist of trade, armed conflict, friendship and enmity. We focus on the mobility of human players on the network over a time-period of 500 days. We take a number of mobility measurements (daily and biweekly position changes, entropy, number of unique nodes visited) of players and compare them with measures of simulated random walkers on the same topology. Player mobility is highly different from the mobility of unbiased random walkers. The analysis of biased random walkers reveals the two essential ingredients which explain measured human mobility patterns most accurately: heterogeneity and a tendency to return to recently visited locations. We compare our entropy distributions with human mobility in real life world -- measured via mobile phone data -- and find a striking match.

By Michael Szell, Giovanni Petri, Kang Zhao, Drew Levin

Who Blogs What: Understanding Behavior, Impact and Types of Bloggers

We investigated bloggers’ publishing patterns by focusing on the topics that their posts cover. Applying clustering algorithms on the dataset from a blog website of 370,000 posts from 2,275 blogs, we identified two types of bloggers: specialists and generalists. Then we compared their respective contributions to the blogosphere in terms of productivity and buzz-factor. Our analysis suggests that specialists generally have a higher impact than generalists. It also reveals that among specialists, there are very few who create a large “buzz” or produce a voluminous output.

By Kang Zhao and Massimiliano Spaziani

Local and nonlocal information in a traffic network: how important is the horizon?

Recent advances in distributed sensor network technology have changed the landscape of traffic optimization in which small, mobile devices are able to sense local information and communicate in real time with one another. Naive optimization algorithms that operate solely on the local or global level are inherently flawed, as global optimization requires every local sensor to communicate with a centralized base-station, creating prohibitive bandwidth, robustness, and security concerns, while local optimization methods are limited by a near information horizon as they are unable to propagate or react to information beyond their immediate vicinity. This paper investigates an intermediate approach where individual sensors are able to propagate congestion information over a variable distance that is determined in real-time. This strategy consistently out-performs a naive strategy where every car simply takes the shortest path to its destination, but does worse than a simpler optimization algorithm that only incorporates local information. This is most likely because the intermediate solution directs cars along the same alternate path when attempting to free a congested area, thus creating new congestion along the detour. The results suggest that local information might set an upper bound on performance in models of cascading information. Further work is required to confirm this observation and develop an algorithm able to join both local and global information to effectively diffuse traffic around congestion.

By Giovanni Petri, Samuel Scarpino, Drew Levin, Tracey McDole, Kang Zhao and Leif Karlstrom

The Coevolution of Residential and Friendship Networks: An Extension of the Schelling Model

During the past few decades social network analysis has produced a great deal of insight into the workings of social systems. While social scientists have put a lot of work into the investigation of residential, friendship, trust, exchange or discussion networks, scientific inquiry has typically limited itself to investigating the characteristics of networks of only one kind. This approach has produced plentiful insight on the structure and function of different kinds of social networks, but the interaction between the different kinds of social networks has received insufficient investigation so far. Our work, in which we examine the interaction of residential and social networks represents an attempt at advancing this field of inquiry. More specifically, we extend a classic model of residential segregation (Schelling, 1968) by incorporating a social network that constructs -- and is influenced by -- residential preferences. We use Agent-Based Modelling to examine how social network topology affects residential segregation in the Schelling model. Given its current popularity in social simulation, extending the Schelling model is an important task in its own right, but we seek to achieve something more fundamental than a mere rehashing of an old model. We deploy Schelling's model as the basis for a way to understand multiplex networks, and seek to give a formal, methodologically practicable expression to Granovetter's concept of embeddedness. Attached here is just the first half of our working paper, and we'll upload the complete version soon.

By Bruno Abrahao, Pilar Opazo, Zhiyuan Song and Bogdan State

Terrestrial volcanism in the framework of complex network theory

Volcanoes are outputs to a hidden transport network of magma in the Earth's crust. This network spans grainscale melting of rocks in the upper mantle and eruptive events that may have caused the largest mass extinctions of life on Earth. We use the NAVDAT geologic dataset from volcanoes around the Western US to constrain the topology and dynamics of this network. These data include approximate ages and location of eruptions (best constrained in the last 5.2 Million years - the Pliocene Epoch), along with compositional data that may be used to infer timescales and processes within the network. This project includes statistical analysis of data, network inference, and forward dynamic modeling.

By Leif Karlstrom, with contributions from Samuel Scarpino, Yixian Song, Giovanni Petri, Griffith Rees and Tracey McDole

Dynamics of Shared Mental Representation: What can a simple network of agents tell us?

This paper develops a simple model of how individuals automatically and unconsciously use social information feedbacks from other individuals in order to determine the mental representation they will impose upon a social situation. An agent-based modelling approach is used to demonstrate how these learning processes, when carried out in an inter-subjective context, are sufficient to generate a number of dynamics that characterize real social systems. Results indicate that both network structure and updating strategies significantly determine the pattern of mental representation adoption across the set of agents. Significant findings include the non-trivialness of reaching full consensus in a group, the emergence of distinct sub-groups and cultural “brokers” between them, and the variable ability of a single agent acting independently of social feedbacks to drive the entire system toward consensus.

By Lynette Shaw, Sarah Wise, Micael Ehn, Ingrid van Putten

Diversification in Simulated Food Webs: The Role of Closed Motifs

We allow a simulated food web to self-construct by repeated introduction of predators. Networks start with a source of biomass, and predators choose their prey according to a niche model. Species thrive or go extinct according to a standard predator-prey biomass model. We examine the correlation between structural motifs and the evolution of network architecture. We find two motifs that correlate strongly with network expansion, and we speculate casually but optimistically on implications and further research possibilities.

By Jonathan Cannon, Gavin Fay, Andrew Hein, Vanessa Weinberger

Evolutionary dynamics of fitness driven walkers on a graph

The availability of empirical data on {humans and animal mobility has had a crucial impact on many dynamical processes found in both nature and society}. Here we take a closer look at the influences of both mobility and non-trivial network architecture on how interactions among individuals progress. Conventional models that involve spatial games are limited to representing players as nodes in the network with interactions steered by the linkages to other nodes, apart from the game rules. In this work, instead of using nodes to represent individual agents, we use the nodes to represent communities where players are situated. Two general processes are involved in this study namely, the inter-node and intra-node dynamics, where each is described by its own spatio-temporal scale. Inside the nodes, individual players evolve under the context of the Ultimatum Game. This paradigm provides a measure, which is the average fitness of individuals inside a node, that can be interpreted as a mechanistic drive behind the mobility of agents on a network.

By Roberta Sinatra, Chaitanya Gokhale, Erika Fille Legara

Energy, information, and the evolution of migration

Migration has been an important model for the study of how organisms perceive their environments, share information with one another, and make decisions in light of physiological constraints and trade-offs. Research on the navigation and collective behavior aspects of migration has primarily focused on how heritable genetic information allows migrants to use environmental cues to locate migration targets and how this information is shared among individuals. By contrast, work on physiological constraints and individual decision-making has largely focused on how individuals can maximize fitness by making decisions that affect the amount of energy or time required to complete migratory journeys given the constraints of physiological performance. Here, we integrate these perspectives using and agent-based simulation model to explore the evolution of sociality, navigation ability, physiology, and migration strategy.

By Andrew Hein, Oana Carja, Kyla Dahlin, Ana Hocevar, Daniel Jones

Evolutionary dynamics of structured genetic algorithms

This project is still evolving, this paper is a first draft which will be updated.

Populations are shaped by the spatial structure of their environment, it gives rise to a contact structure (interactions between individuals) and a population structure (interactions between (sub)populations). The topology of structures at both levels can have a profound influence on the evolutionary dynamics of a population. Here, we present a simple computational model in which genetic algorithms evolve cellular automaton rules to perform a classification task with which we investigate the evolutionary dynamics of (meta)populations consisting of sexually reproducing individuals that crossbreed within several distinct contact structures. We find that contact structures -- modeled as graphs with various topologies -- that limit the number of breeding partners show a higher evolvability and produce individuals with a higher fitness than populations with contact structures in which individuals have a high number of possible partners. Furthermore, we show that well-mixed populations greatly benefit from being subdivided into (coupled) subpopulations. Within a metapopulation setting well-mixed contact structures can attain a fitness comparable to populations with a structured contact structure.

By Felix Hol and Xin Wang

Diffusion at the Boundary: Measures to Characterize the Diffusion Process in Complex Networks

Many propagation processes on networks can be explained by assuming a simple random walk dynamics. Inspired by the well-known relation between number of steps and mean squared distance in pure diffusive process, we studied diffusion over complex networks, using several models of networks: random, small-world, scale-free and geographical. Because the rate at which the process reaches larger distances is also of interest, we additionally studied the spreading rate, which is simply a measure of the random walker efficiency to spread away from the node that started the process. Our results thus far show that many important features of the network topology are displayed by these measures. The results to come involve the scaling of these measures with network size and density.

By Lucas Antiqueira, Damian Blasi, Borys Wrobel

Human gossip networks and the dynamics of honesty: a simulation model of gossip assessment

To be posted soon.

By Mark Laidre, Megan Olsen, Daniel Jones, Susanne Shultz, Dan MacKinlay, Katarzyna Samson, Erika Fille Legara, Griffith Rees, Massimiliano Spaziani

Agent-based modelling of Tasmanian Devils (Sarcophilus harrisii): impacts of roadkill on evolution of interaction networks

To be posted soon.

By Gavin Fay,Megan Olsen,Joseph Gran,Oana Carja,Julie Granka,Anne Johnson, and Vanessa Weinberger