key: cord-0036179-03yr72zb
authors: Alam, Shah Jamal; Geller, Armando
title: Networks in Agent-Based Social Simulation
date: 2011-07-09
journal: Agent-Based Models of Geographical Systems
DOI: 10.1007/978-90-481-8927-4_11
sha: 3a86c98c18ebf5cf65c6bf56db299b263d1524b5
doc_id: 36179
cord_uid: 03yr72zb

Computational social science and in particular agent-based social simulation continue to gain momentum in the academic community. Social network analysis enjoys even more popularity. They both have much in common. In agent-based models, individual interactions are simulated to generate social patterns of all kinds, including relationships that can then be analyzed by social network analysis. This chapter describes and discusses the role of agent-based modeling in the generative-analytical part of this symbiosis. More precisely, we look at what concepts are used, how they are used (implemented), and what kind of validation procedures can be applied.

Agent-based modeling and network analysis enjoy a symbiotic relationship in the fi eld of computational social science. The former is a method of computationally representing individual interactions from which social patterns emerge; the latter is a method that affords (dynamic) structural analysis of (socio-) structural patterns. The renowned anthropologist Clyde Mitchell stated that the starting point of any analysis should be the actual relationships in which people are involved (Mitchell 1989 , pp. 77-79) . What he did not think of, interestingly, is to analyze, other than by observational and descriptive means, how these relationships form.

The focus of this chapter is to describe and discuss the symbiosis of agent-based social modeling and social network analysis. We shall look at how model topologies affect network topologies and provide an overview of different social network generation processes. How networks are implemented in ABMs and how agent-based social networks may be analyzed are also discussed.

In this section, we discuss physical and social neighborhoods in agent-based social simulation models. Agent-based simulation models of social phenomena date back to the mid 1980s. As Axelrod ( 1997 ) argues, the goal of this modeling approach has been to break simplistic assumptions required for mathematical tractability, e.g. homogeneity, ignoring interaction. With the advent of multiagent models, social simulation benefi ted from it most as these models provided the provisions of simulating the social behavior of autonomous individuals and the interactions between them. ABMs have been accredited, in most cases, as suitable for decentralized scenarios, especially when individual interactions lead to the emergence of collective patterns, like in the case of complex social networks.

Agent-based modeling affords taking geographical space into account in a straightforward manner. This is true for abstract spaces as well as for detailed Geographic Information Systems (GIS) referenced spaces. Perhaps the most commonly used topologies in agent-based modeling are the von Neumann or Moore neighborhoods on a plain or a toroid surface. Other possible topologies are, for example, irregular, hexagonal grids or vector-based (Crooks et al. 2008 ) . Differences in topologies lead to differences in network generation processes and resulting network structures (c.f. Flache and Hegselmann 2001 ) . The reason for this is that model topologies limit agents not only in their movement, but also in the manner by which they perceive information and interact with other agents. The underlying assumption is that space is important and matters in everyday (artifi cial) life, affecting both the individual's behavior and society as a whole. Choice of a topology depends very much on the modeler's needs. The focus of the discussion here is on the effect that different model topologies have on network evolution processes and network structures. In other words, how are dynamic social networks coupled to model space? Note that this question is distinct from questions of how space is represented in networks, which we discuss below.

As Bailey and Gatrell ( 1995 , p. 4 ) explain, "spatial data analysis is involved when data are spatially located and explicit consideration is given to the possible importance of their spatial arrangement in the analysis or interpretation of results." Spatial analysis, for example, that is based on GIS techniques, highlights the importance, provided it exists, of neighborhood infl uences, if any, in the actors' behavior caused by the spatial-context. Schensul et al. ( 1999 ) have thoroughly covered the issues involving spatial mapping of data; we report a few of the most relevant points. For any social networks, the atomic units are usually the individuals. In gathering data about individuals, it is quite useful to identify the general spatio-temporal constraints that limit most individuals' movements and interaction in the region. Typically, in spatially explicit models, agents may include stakeholders, land owners, farmers, public institutions, and policy or decision-making agencies. As Brown ( 2006 ) explains, the behavior of such agents may vary from being triggered by some external stimulus or coping with certain stresses to being goal-oriented.

Earlier in this section we discussed the importance of signifying boundaries and neighborhoods. Modeling a social network requires identifying the spaces in which the agents exist and are related. All relations among real entities exist and are constrained through physical spaces. More importantly, case-studies involving land use change, distribution and utilization of physical resources are modeled spatially explicitly per se. Social networks are generated through social mechanisms and processes, i.e., agents that are embedded in society and that interact with each other produce them. It has become more and more accepted in the social sciences that the agents' (e.g., humans, primates, ants) behavior does not follow a linear pattern, but is non-linear in its own right. Social complexity, according to Moss ( 2008 , p. 2) , is a "condition whereby social behavior cannot be understood simply as a scaled-up replication of the behavior of the individuals comprising the society". The interplay of social processes as an outcome of socially embedded individuals gives rise to the social behavior, which, as Moss ( 2008 , p. 3) explains, "cannot be forecast on the basis of individuals' characteristics and predictions alone". The macro-phenomena resulting from such micro-level interactions are often complex in nature. We understand complexity as a "type of condition in which agent behavior and social interaction combine to generate macro-level outcomes that could not be predicted from knowledge of the behavior and nature of interactions alone, and result in sporadic volatile episodes, the timing, magnitude, duration and outcomes of which are themselves unpredictable" (Geller and Moss 2008 , p. 322) . By contrast, in the study of so called complex networks, the notion of complexity is related to network structures (both local and global) and characteristics that are not statistically signifi cant in a random network (Newman 2004 ; Wasserman and Faust 1994 ) . We are aware of other defi nitions of both complexity and complex networks (see Edmonds ( 1999 ) for a review), but those given should suffi ce for the purpose of this chapter.

Self-organized criticality (SOC) addresses the local mechanisms and processes that drive the emergence of complex systems. It can be interpreted as the response of a slowly driven system such that the outcome of the system's behavior is limited by the order of the magnitude of its size, thus, leading to the scale-free property (see below). Following Jensen ( 1998 ) , one may explain SOC as the development of emergent patterns due to interactions among meta-stable agents, so that at some critical state, the result of interactions affects the entire system such that all members of the system infl uence each other. For the rest of the period, any local distortions resulting from agents' interactions in their neighborhoods remain confi ned locally. Systems governed by SOC leave characteristic traces in the data they produce. The data conforms not to the assumption underlying standard statistical methods, namely that the mean and standard deviation of the distribution of the data are known and stable. Consequentially, the conditions for standard statistical hypothesis testing and regression techniques are not satisfi ed anymore, and there are cases where variance is infi nite (Barthélémy 2006 ) . However, of more importance to us in the present context is the fact that investigating such signatures provides useful guidance for the analysis of social simulations (Moss 2002 ) . Leptokurtosis in a distribution of relative changes can be a refl ection of episodes of volatility that are themselves unpredictable (Moss 2002 ) . That is, unpredictable clustering of volatility and the corresponding extreme events are identifi ably complex features of time series. Conversely, fi nding leptokurtosis in time series data would naturally incline us to look for extreme events. A vital implication of such approaches is that it is practically impossible to predict the outcomes to the system from simple stimuli (Jensen 1998 ) .

ABMs -not only of social systems -can represent such properties. This is an important assumption that needs to be taken into account when modeling networks with an agent-based approach, for agent behavior and interaction -as understood in SOC -will affect the kind of networks that emerge. With this in mind, we now present an overview of characteristic complex network topologies associated with complexity concepts that an agent-based modeler has to expect when running a simulation. Presented will be also measures appropriate for the analysis of agentbased social simulation generated networks.

Modeling dynamic social networks where agents communicate with each other and build relations over time requires the introduction of "social" spaces that go beyond the physically situated agents. Such agents can be called "socially embedded" (Edmonds 2006 ; Granovetter 1973 ) , i.e., an agent's behavior is fairly infl uenced by the network of social relations that it is part of. Physical resources and interaction with the environment do not fulfill the demand for capturing the social interactions that may infl uence, for example, a farmer's decision to plant a certain type of crop, or use of their land. Social spaces and the agents' interactions may either be constrained by a local neighborhood, or could be global (i.e., each agent may be directly related to any other agent in the space). In the former case, the sociability of agents depends on the spatial neighborhoods, and thus, according to Edmonds ( 2006 ) , the physical space is used as a proxy for social space.

Not many social network models exploit combining the social and physical spaces, which is pivotal for analyzing the underlying complexity and for which ABMs are well suited as they support modeling the spatial neighborhood as well as agents' cognition in building relations. Hence, symbiosis of the two "spaces" remains an active area of research.

The term complex networks is used as an umbrella term for the size, similarity of structure, and dynamics in real and simulated networks (for two comprehensive articles on the issue see Newman ( 2004 ) and Fortunato ( 2009 ) ). Cross-disciplinary research, especially in the last decade, has resulted in identifying characteristic network types and their statistical properties. Network structures are either modeled phenomenologically or they emerge from agents' local interaction (for an older, but relevant review concerning networks for ABMs see Amblard ( 2002 ) ). We briefl y look at three commonly occurring network structures in agent-based social simulation: random graphs, small world and scale-free networks. Regular lattice networks are used in cellular automata models -a lattice is a graph where vertices are placed on a grid and are connected to the neighboring vertices only.

An early attempt to study the behavior of complex networks dates back to Erdős and Rényi's ( 1959 ) seminal work on random graph theory. The basic Erdős-Rényi (ER) model requires connecting N nodes through n edges chosen randomly such that the resulting network is from a space of equally likely graphs, where N is the size of the network. Several nodes can have the same degree in a random graph. Given a high wiring probability p, the diameter of random graphs increases logarithmically with the growth of the graph. The ER graph also predicts the appearance of subgraph structures and the emergence of a unique giant component.

Random networks are to social network data what the Gaussian distribution is to statistical data; it is neither very likely to fi nd random network structures in real world data nor very realistic to assume that real world networks are of a random nature. Firstly, people do not behave randomly. Secondly, societies are complex systems. Randomness is diametrically opposed to this idea. It is, however, worthwhile to consider random networks as a useful concept in agent-based social network modeling since they constitute a test case. The networks generated by the simulation, and which are meant to represent an identifi ed (real world) target system, should be signifi cantly different with regard to certain key metrics from the corresponding ER network.

In 1998 Watts and Strogatz ( 1998 ) presented the Watts-Strogatz (WS) model, which interpolated a small world graph as an intermediate of a purely random and a regular graph. They showed that as the length of the shortest path between two nodes tends towards O(ln(N) ), which is small, a random graph exhibits the so-called small-world effect. That is, a WS network is characterized by short average path length ( L ) and a high clustering coeffi cient ( C ) compared to an Erdős-Rényi graph of the same size and density. This property displayed by small-world networks has been observed in a number of social systems, including friendship, co-worker, and confl ict networks.

Informally, a high C supports the ideas that the "friend of my friend is my friend" and that the neighbors of a node are more likely to be linked to each other than in a random network. More generally, small-world type networks should be of interest to us because they exhibit properties which are "suffi ciently well connected to admit rich structure, yet each element is confi ned to operate within a local environment that encompasses only a tiny fraction of the entire system" (Watts 1999 , p. 499) . This specification of the micro-level processes leading to the emergence of small-world networks is closely related to the idea of SOC and complex systems. Albert and Barabási ( 2002 ) argued that simply using ER or WS models does not capture the important aspects of real-world networks. The Barabàsi-Albert (BA) model is a special case of the stochastic model proposed by Herbert Simon (Simon 1955 ) for generating a class of highly skewed distributions, including the power-law distribution. The number of starting vertices is fi xed and the chances of a vertex being linked to another are equally likely. Instead, real-world networks evolve over time and exhibit a feature that is called preferential attachment. Albert and Barabási address these issues by introducing network growth. The network starts off with a small number of connected vertices. New vertices are added to the network one at a time and are linked to existing vertices. Then they introduce the idea of preferential attachment, meaning the probability that a new vertex is connected to an existing vertex depends upon the connectivity of the vertex, where k is the degree of the i -th vertex in the existing network. The network evolves into a scale-variant such that the degree distribution follows a power law.

Unlike physical systems, social processes are modeled descriptively and validated qualitatively. The evidence is gathered through fi eldwork. An individual's relations and actions are driven by their position and other factors affecting the system. Where the actions are constrained by both the endogenous and exogenous factors, one may fi nd episodic volatility in the observed time series (Moss and Edmonds 2005 ) . Next, we discuss some of the issues concerning social network data collection and incorporating them into ABMs. We then give some examples of ABMs of social networks.

Acquiring data on social networks is a challenging task for fi eldwork researchers depending upon socio-cultural and socio-political aspects of their research and resource constraints. Schensul et al. ( 1999 ) identify features for data that are of use for the description of social networks:

Identifi cation of network actor; • Defi nitions of and rules to defi ne group members by the people; • Inclusion and exclusion rules defi ning social network boundaries; • Familial and sexual relationships, (if any), within groups. • Network boundaries constitute the edges of networks and are defi ned by rules for entry and exit from groups as well as by other cultural patterns of participation that differentiate one group from another. An important facet of a community is the existence of so-called community organizations, which operate within the perimeters of the community. Such organizations can be characterized as being informal or institutionalized. Physical neighbors can be described in terms of land use and segregation of sub-regions. The social aspect of neighborhood is based, for example, on the "local social interactions, social class, ethnic and radical origins, life cycle characteristics of the population, length of residence, and place of work" (Schensul et al. 1999 ) . The concept of locality is embedded in its defi nition; hence a community can be identifi ed as sharing social characteristics or a community space, where social interactions are likely to take place.

Social network data can be derived from census data, third-party surveys and various forms of quantitative data (e.g., Eubank et al. 2004 ; Bearman et al. 2004 ; Geller and Moss 2008 ) .

Social network data may also be extracted from existing databases such as e-mail correspondence within an organization or social interactions among individuals in online communities. On the other hand, it is very diffi cult to conduct fully-fl edged surveys for acquiring social network data in distant, stressed or confl ict-torn regions such as Yemen or Afghanistan. Knowledge elicitation techniques based on participatory approaches (Barreteau et al. 2001 ; Pahl-Wostl and Hare 2004 ) may be used to model the behavior and social interaction of relevant actors through an iterative process involving data collection, validation and scenario exploration.

A social network is a graph where actors (e.g., individuals, households, fi rms) are represented as vertices and an existing relation between any two nodes represented as an edge between them. Multiple relations among agents embedded in space are represented as a two-mode sociomatrix, a hypergraph or a bipartite graph, where one representation can equivalently be mapped to another (Wasserman and Faust 1994 ) . Bipartite graphs are useful for simultaneous analysis of both actors and the affi liations (Degenne and Forsé 1999 ) . Typically, a graph, i.e. a social network, is implemented as an adjacency matrix or a doubly-linked list besides others. Choice of a suitable data structure for manipulating social networks may depend upon the structure of the underlying social network, e.g., single or multiple relations; directed/undirected; weighted edges, etc. Two of the most widely adopted data formats used for social networks are GraphML (Brandes et al. 2004 ) and DyNetML (Tsvetovat 2005 ) , both based on XML. Both support directed, undirected, and mixed graphs; hypergraphs; hierarchical graphs; and store nodes and edges attributes, for example agents' characteristics or type or strength of edges (see Tsvetovat ( 2005 ) for a comparison of commonly used social network data formats). Another well known data format is Pajek's .net format for rich social network data (de Nooy et al. 2005 ) .

Several simulation toolkits and software exist with built-in data structures and operations for analyzing and visualizing social networks. Widely-used software includes Pajek (de Nooy et al. 2005 ) , ORA (Carley et al. 2007 ) , StOCNET (Boer et al. 2006 ) and UCINet (Borgatti et al. 2004 ) (for a list of social network analysis software, see for example Wikipedia's entry under "Social network analysis software"). Several agent-based modeling platforms provide functionality for implementing and analyzing networks at runtime. These include RePast 3.1/Simphony (North and Macal 2007 ) , MASON (Luke et al. 2005 ) , NetLogo (Wilensky and Rand in press ) and Swarm (Minar et al. 1996 ) . Most of them intentionally provide only limited support for network analysis measures such as the basic centrality measures and community detection algorithms (Nikolai and Madey 2009 ) . Dedicated network modeling and analysis libraries such as the Java Universal Network/Graph library (JUNG) (O'Madadhain et al. 2005 ) ; the R Project packages statnet, sna, and igraph are to be used for more computationally-extensive handling of network data generated by ABMs. Social network analysis software and APIs provide an interface to read/write social network data in data formats such as GraphML or DyNetML. For a detailed discussion on the integration of GIS and agent-based modeling, see Crooks and Castle ( 2012 ) .

In this section, we present a selection of relevant work dealing with implementations of social networks in ABMs.

Central to landscape modeling, such as land use, land cover, habitat conservation and farming, is the identifi cation of community space and distinct regions (Brown 2006 ; Parker 2005 ) . For instance, Krebs et al. ( 2007 ) developed a spatially explicit ABM of a water irrigation system in the Odra River Valley in Poland. In their model, farmers' decisions to maintain the irrigation water canal depend on the relative location of their land (up-or downstream), how they perceive their physical neighbors, and the underlying social network. For a recent review on land-use from an agent-based modeling perspective, see Matthews et al. ( 2007 ) and Crooks ( 2010 ) . Becu et al. ( 2003 ) modeled the impact of upstream management in Thailand and explored several scenarios concerning land managers' collective action given their characteristic and social interaction (Ziervogel et al. 2006 ) . FEARLUS is an established modeling framework designed for the assessment of land use change scenarios (Polhill et al. 2008 ) . Built upon the Swarm modeling platform (Minar et al. 1996 ) , it supports a variety of agent-based modeling techniques and extensions such as a biophysical component, land trade and the effects of climatic variability on land parcels. The FEARLUS simulation begins with the land parcels assigned to land managers. At each annual cycle, managers select the land use of their land parcels based on the available selection strategies. They decide to harvest based on the expected yield for a particular year, select land parcels for sale or to clear off defi cits, or decide to retire, allowing new land managers to enter the system. FEARLUS incorporates social and physical neighborhoods. Social neighborhood and spatial distribution are both used by agents, representing farmers or land owners, to observe each other and decide what action to take. Further information on FEARLUS and how the physical and the embedded social neighborhoods are implemented can be found online at http://www.macaulay.ac.uk/fearlus . Edmonds ( 2006 ) extended the Schelling ( 1971 ) segregation model by adding an explicit social structure in the form of a friendship network to the agent neighborhoods which are defi ned by their spatial location on a regular grid. The friendship network is assigned randomly at the start based on the preference parameters: number of friends, neighborhood bias, and bias for racial similarity. Edmonds thus changes the motivation for switching the neighborhood. Instead of intolerance based on race, as implemented by Schelling, fear as a result of personal insecurity makes people leave for another neighborhood. Fear is a function of security related incidences and spreads through the friendship network. Communication of fear depends on the density of the social network on the other hand. At the same time friendship networks are not necessarily in the geographical vicinity of an agent. An agent can thus be attracted away to where its friends live. As a result, social and physical space becomes disjointed.

In their model of neighborhood change, Bruch and Mare ( 2006 ) used a variety of choice functions to introduce heterogeneity in individuals' preferences, thereby relaxing several of Schelling's ( 1971 ) assumptions. They utilized real data from several US cities where the population was divided into multiple racial and ethnic types. They demonstrate that the choice of the utility function can signifi cantly affect the observed patterns of segregation and neighborhood change. Crooks ( 2010 ) studied residential segregation using a spatially-explicit ABM using vector GIS. The model takes into account socioeconomic and geographical data where agents represent households with preferences for a neighborhood depending upon their properties. Crook's model is initialized with available aggregate census data of the wards in London (UK). Werth and Moss ( 2007 ) modeled migration under socioeconomic stress in the Sahel region in North Africa. They used an abstract spatial representation of the region, where household decisions to migrate to another location depend upon their existing social and kinship ties with other households in the neighborhood, in addition to their available food status. Rakowski et al. ( 2010 ) studied contact patterns among individuals in a transportation model in Poland.

Spatial and social propinquity can be key determinants in the spread of infectious diseases depending upon their infectiousness and the required level of intimacy for transmission. For instance, sexual transmission of HIV or transmission by sharing injection needles may be driven by the social and physical proximity among potential sex or needle-sharing partners. Diseases like smallpox may be transmitted when individuals happen to be in the same location where an infected person is present. Spread of airborne infections with high infectivity such as infl uenza, depends upon the migratory or activity patterns in a given population.

EpiSims is a large-scale disease propagation ABM capable of simulating millions of agents based on real data (Eubank et al. 2004 ) . Locations in EpiSims represent a physical place, for example an offi ce or a school building, where individuals get into contact with each other provided that they are in the same location at the same time given their preferences and shared activities. During the simulation, a dynamic contact network is developed by recording the amount of time each individual shares with each other person. The duration of contact between infected and susceptible persons determines the spatially-distributed spread of the infectious disease (Stroud et al. 2007 ) . Yang and Atkinson ( 2008 ) developed an ABM of the transmission of airborne infectious diseases using activity bundles, where individual contacts are driven by social activities or physical proximity or both. Huang et al. ( 2004 ) modeled the spread of the SARS epidemic by using a small-world social network whereas the individuals' activity spaces were modeled upon a two-dimensional cellular automata. Dunham ( 2005 ) demonstrated an implementation of the spread of three viruses using a spatially-explicit agent-based epidemiological model developed in MASON. Huang et al. ( 2010 ) propose a four-layer architecture for network-based epidemic simulation comprised of individuals' social interaction, passive connections between individuals and locations, use of abstract geographical mapping to refl ect the neighborhood, and the use of demographic or geographic data.

In addition to the models presented above, there are many other examples of ABMs of social networks. In many of these models, the mechanisms generating the social networks have been empirically derived. This stands in stark contrast to modeling exercises where the authenticity of social network generating mechanisms is less of a concern, such as in statistical mechanics. The purpose of many of these models is an explanatory one. Companion (sometimes also called participatory) modeling and role-playing games are certainly at the forefront of an explanatory modeling agenda. The primary objective of companion modeling is to understand complex environments through stakeholder participation, affording to validate model assumptions and to make informed policy recommendations (Barreteau et al. 2001 . Companion modeling stresses that no a priori hypotheses are made about the target system. Priority is thus assigned to evidence gathering during fi eldwork. Similarly, role-playing games incorporate a special function in the understanding and validation of ABMs. The idea is to consider role-playing games as "living" multi-agent systems in which players are the agents and the set of roles is the rule base. Through rule design in collaboration with the players an understanding of the complexity of the system to be modeled is developed.

It should become clear at this point, that integrating social networks in ABMs goes beyond mere measurement of social network metrics at the aggregate level, but includes a thorough study of the processes underlying network generation, i.e., the structural-dynamic consequences of the actual relationships in which people are involved as mentioned by Mitchell ( 1989 ) . Geller and Moss ( 2008 ) developed a model of power structures in Afghanistan. Barthélémy ( 2006 ) modeled water consumption, where a household was represented as the smallest unit in the modeled community space. studied dynamic sexual networks based on a village in the Limpopo Valley case where neighborhood and kinship networks serve as safety-nets at times of socioeconomic stress for the households. Pujol et al. ( 2005 ) have modeled the evolution of complex networks from local social exchange, simulating networks with similar characteristics as scale-free and small-world networks. They show that properties characterizing complex networks emerge from the local interactions of the agents, imperfect knowledge and sociologically plausible behavior. Jin et al. ( 2001 ) demonstrated how a smallworld friendship network may be evolved from simple probabilistic rules. The forest fi re model by Leskovec et al. ( 2005 ) is another example of a generative process that represents networks phenomenologically with heavy-tailed distributions and shrinking diameters.

So far we have only talked about extra-individual networks. But networks do not only exist between agents; they exist also as mappings of organization beyond social structure. "Structure exists not only as sets of ties between actors but as networks among cognitive and cultural entities and study of these entities by means of network analysis is just as important as study of interpersonal relations" (Tsvetovat 2005 , p. 111) . The utilization of networks in agent-design and in particular in the agent reasoning processes hence becomes obvious. In this respect the concept of semantic networks offers particular usefulness, for it expresses, in the most general way, relations of meanings between concepts in terms of nodes and links. Semantic networks are thus often used for the representation of knowledge; knowledge that bears -represented as a semantic network -some form of content-related domain specifi city (DiMaggio 1997 ) . It is beyond the scope of this chapter to pursue this route any further. We would nevertheless like to make clear that we see great potential in the use of semantic networks in the modeling of socio-culturally grounded cognitive and action selection processes.

The choice of suitable measures for agent-based social networks depends upon our understanding of the phenomenon under study. Analyzing social networks in and generated by agent-based social simulation does not impose new requirements for social network analysis. Metrics such as: geodesic distance; average path length; network density; reachability; clustering; centrality and centralization and their meaning, continue to be useful in that they characterize network topologies and process-based complexity. However, most of the analysis will have to deal with dynamic social networks. Considering only a priori and ex post snapshots of networks is not helpful in identifying network measures for agent-based simulations. Applying graph-theoretic measures over a network snapshot may increase the risk of losing the context of a particular agent's position in the network (Borgatti et al. 2006 ; Carley 2003 ; Edmonds and Chattoe 2005 ) . In complex systems, it is hard to anticipate how emerging patterns result from interactions at the micro-level. It could be thus misleading to apply measures on a single snapshot of the network. Carley's dynamic network analysis introduces the meta-matrix, a scheme for coping with the problem of multiple relations and co-evolution of both agents (entities, vertices) and their dynamically changing edges (Carley 2003 ) . This approach is further supplemented by combining social network analysis with cognitive science and multiagent systems, the idea being that change in one network may affect change in another. Edmonds and Chattoe ( 2005 ) suggest a scheme that makes use of agent-based social simulation in order to fi nd better means for abstraction. Again, networks in ABMs are dynamic in nature and ties may be added or removed between agents during a simulation run. The network evolves with changes in the agent population, i.e., the agents that participate in a given (social) network. Consequently, the time-series measures of the simulated social network changes as the network evolves. Therein the focus can lie on standard statistical metrics, such as skewness and kurtosis of the absolute relative differences of network measures, such as changes in the clustering coeffi cient over time. Since we deal with a complex system, we would expect these measures to be indicators for volatile episodes in the time series (Moss and Edmonds 2005 ) . Of course, we would not expect the time-series to be normally distributed and exhibit heteroskedasticity. But in general, for dynamic networks, where the population of participating agents in a network changes over time, we should also look for the stability (or change) of network measures over one or multiple simulation runs. The choice of measures is therefore important when comparing networks of varying sizes within and/or across simulation runs. See McCulloch ( 2009 ) and Alam et al. ( 2009 ) for methods of detecting patterns in dynamic social networks.

Networks sharing similar global characteristics can nevertheless differ in terms of their local structures. Identifying subgraph structures and their properties have been studied extensively in social network analysis, particularly with regard to triads as building blocks of a network (c.f. Wasserman and Faust 1994 ) . Milo et al. ( 2002 ) introduced the concept of local structures as "motifs" that are statistically signifi cant in comparison to local structures in a random network. Hales and Arteconi ( 2008 ) provide a good example of applying motif analysis in an ABM of a peer-to-peer network.

Closely related to motif analysis are endeavors to identify communities in networks. Fortunato ( 2009 ) and Mucha et al. ( 2010 ) provide a good overview of community detection algorithms for static and longitudinal networks. Without going into the details, the problem is twofold: Firstly, from a socio-scientifi c point of view, the non-trivial issue of solving the boundary specifi cation problem needs to be solved for a given network. Second, the algorithm for dealing with boundary specifi cation issues needs to be fast, since iterating over the whole network at each time step is computationally expensive.

Agent-based social simulations should be cross-validated (Moss and Edmonds 2005 ) . That is, the model output should be compared against the model's target system data. This comparison can happen at the aggregated level (e.g., statistical signatures of time-series data) or it can happen at a qualitative level, informing on social mechanisms that are assumed to drive the social network. For example, as Watts ( 1999 ) reports, small-world structures are likely to be present in many real social networks. Geller and Moss ( 2008 ) report a small-world-like structure for Afghan power structures.

Social and physical networks are important with respect to modeling systems that require both socio-cultural as well as geographical information. However, spatial ABMs incorporating social networks are few. On the other hand, social spaces in the form of friendship, kinship and other socio-cultural networks are often modeled in ABMs without any explicit reference to physical spatial representation or constraints. Some of the examples cited in this chapter show how physical and social space can be coupled together for the purpose of understanding complex social systems. Social networks in ABMs may emerge as a result of agent interaction, which can be contextualized or abstract. On the other hand, incorporating physical networks such as a neighborhood, road networks, etc. is important when understanding the dynamics of urban planning and growth, irrigation systems and road transport. We also discussed in this chapter issues related to data collection for social networks as well as the technical aspects of incorporating networks in ABMs.

Comparing two sexual mixing schemes for modelling the spread of HIV/AIDS

Identifying structural changes in networks generated from agent-based social simulation models

Modelling contextualized reasoning in complex societies with endorsements

Statistical mechanics of complex networks

Which ties to choose? A survey of social networks models for agent-based social simulations

Advancing the art of simulation in the social science

Interactive spatial data analysis

Role-playing games for opening the black box of multi-agent systems: Method and lessons of its application to Senegal River Valley irrigated systems

Our companion modelling approach

Untangling scenario components with agent based modelling: An example of social simulations of water demand forecasts

Chains of affection: The structure of adolescent romantic and sexual networks

Agent based simulation of a small catchment water management in northern Thailand: Description of the CATCHSCAPE model

StOCNET: An open software system for the advanced statistical analysis of social networks

UCINET: Software for social network analysis

On the robustness of centrality measures under conditions of imperfect data

Social mechanisms: An analytical approach to social theory

The GraphML fi le format

The earth's changing land: An encyclopedia of land-use and land-cover change

Neighborhood choice and neighborhood change

Dynamic social network modeling and analysis: Workshop summary and papers

ORA user's guide

Agent-based modeling in political science

A theoretical model of individual radicalization: Understanding complexity in terrorism and insurgency' . Poster prepared for the 2009 annual European Social Simulation Association conference

The integration of agent-based modelling and geographical information for geospatial simulation

Key challenges in agent-based modelling for geo-spatial simulation. Computers, Environment and Urban Systems

Exploratory social network analysis with Pajek

Introducing social networks (A

An agent-based spatially explicit epidemiological model in MASON'

Capturing social embeddedness: A constructivist approach

Agent-based computational modelling: Applications in demography, social, economic and environmental sciences

When simple measures fail: Characterising social networks using simulation

Modelling disease outbreaks in realistic urban social networks

Multi-agent systems: An introduction to distributed artifi cial intelligence

Do irregular grids make a difference? Relaxing the spatial regularity assumption in cellular models of social dynamics

Community detection in graphs

Growing qawm : An evidence-driven declarative model of Afghan power structures

The strength of weak ties

Economic action and social structure: The problem of embeddedness

Motifs in evolving cooperative networks look like protein structure networks

Dissecting the social: On the principles of analytical sociology

Junkie business: The evolution and operation of a heroin dealing network

Simulating SARS: Small-world epidemiological modeling and public health policy assessments

Network-based simulation architecture for studying epidemic dynamics

Self-organized criticality: Emergent complex behavior in physical and biological systems

Structure of growing social networks

Modelling social and economic infl uences on the decision making of farmers in the Odra Region

Graphs over time: Densifi cation laws, shrinking diameters and possible explanations

MASON: A multi-agent simulation environment

Agent-based land-use models: A review of applications

Detecting changes in a dynamic social network

Network motifs: Simple building blocks of complex networks

The Swarm simulation system: a toolkit for building multiagent simulations (Working paper 96-06-042)

Ethnography and network analysis

Policy analysis from fi rst principles

Simplicity, generality and truth in social modelling part 1: Epistemology

Sociology and simulation: Statistical and qualitative crossvalidation

Community structure in time-dependent, multiscale, and multiplex networks

The structure and function of complex networks

Tools of the trade: A survey of various agent-based modeling platforms

Managing business complexity: Discovering strategic solutions with agent-based modelling and simulation

Analysis and visualization of network data using JUNG

Processes of social learning in integrated resources management

Integration of geographic information systems and agent-based models of land use: Challenges and prospects

Effects of land markets on competition between imitators and innovators: Results from FEARLUS-ELMM

How can social networks ever become complex? Modelling the emergence of complex networks from local social exchanges'

Large scale daily contacts and mobility model -An individual-based countrywide simulation study for Poland

Dynamic models of segregation

Mapping social networks, spatial data & hidden populations

On a class of skew distribution functions

Introduction to stochastic actor-based models for network dynamics

Spatial dynamics of pandemic infl uenza in a massive artifi cial society

Social structure simulation and inference using artifi cial intelligence techniques

Social network analysis: methods and applications

Networks, dynamics, and the small-world phenomenon

Collective dynamics of "small-world" networks

Modelling migration in the Sahel: An alternative to cost-benefi t analysis

An introduction to agent-based modeling: Modeling natural, social and engineered complex systems with NetLogo

Individual space -Time activity-based model: A model for the simulation of airborne infectious-disease transmission by activity-bundle simulation

Adapting to climate variability: Pumpkins, people and policy