Complex Networks Theory and Agent-based Social Networks: A Synopsis
Shah Jamal Alam
Centre for Policy Modelling
20th October 2005
This review provides a survey of some of the most important concepts in the field of the so-called ‘complex networks’, and some classical and recent applications in various disciplines. Social networks are introduced in Section 2, and an overview of the traditional analysis techniques is presented. Section 3 addresses the issue of the techniques and issues that arise in the fieldwork research about social networks. We discuss, in Section 4, some recent critique of the traditional social networks analyses techniques and the ideas to tackle their dynamics, as presented researchers in the field. Finally, Section 5 discusses the used of agent-based modeling in the study of social networks.
Keywords: Complexity, complex networks, agent-based social networks
1 Theory of Complex Networks
This section begins with an attempt to explain complexity as defined by researchers in the relevant fields. We present the notion of ‘complex networks’ in general, followed by a discussion on the most important characteristic networks. The section ends with a quick overview of some recent applications of the complex networks theory in various disciplines.
The enormity of the size of networks in quite a few real-world applications, gave rise to a new surge in multidisciplinary research under the term called ‘complex networks’. The term umbrellas the size, similarity of structure and dynamics in the observed networks, which belong to a variety of disciplines, from natural and physical sciences, social sciences to the Web. In the last decade, extraordinary advancements have been made in the studies of complex networks. The studies have resulted in identifying characteristic networks and their relevant measures. A comprehensive review may be found in (Newman, 2003; Albert and Barabási, 2002).
1.1 Complexity and complex networks
The crux of the CAVES project is ‘tackling complexity’ (CAVES, 2005) and may be useful to present its notion in the context of aims of the project. Networks emerge when subsystems or in terms of social system, actors, are linked with respect to some relations. The idea of complex networks has been around for almost a decade now, which we discuss in the subsequent section.
To begin with, the Merriam-Webster dictionary (2005) defines the term ‘complex’ as (we pick the most relevant variant)
“a group of culture traits relating to a single activity (as hunting), process (as use of flint), or culture unit b (1): a group of repressed desires and memories that exerts a dominating influence upon the personality (2): an exaggerated reaction to a subject or situation c: a group of obviously related units of which the degree and nature of the relationship is imperfectly known”
Our purpose here is to present the notion of complexity that arises as a result of interaction among actors (individuals, organizations, etc.) which is in most cases is localized, but leads to the emergence of patterns that would be hard to predict given the simple nature of the rules-of-interaction. Complexity, complex systems and all sorts of relevant terms have appeared extensively in the contemporary scientific and philosophical literature, e.g. Edmonds (2001) define complexity which can be used in the context of the ‘level of difficulty’ involved in modeling the behavior of a natural or artificial system.
Definition: Complexity as defined by
Complexity is that property of a model which makes it difficult to formulate its overall behaviour in a given language, even when given reasonably complete information about its atomic components and their inter-relations.”
1.1.2 Complex Networks
Networks have been studied formally at least as early as from the 18th century, where Euler pioneered the Graph Theory in his attempt to solve the famous Königsberg bridge problem. Graph theoretic concepts have been applied ever since in various disciplines where there are a set of entities linked by means of some relationship. Investigating the structural properties of such networks has led to a whole range of analytic measures that form the basis of the modern graph theory. Application of such analysis tools in social sciences can date back to the start of the 20th century (Scott, 1991), in which ever since, the discipline of social network analysis (SNA) has stemmed as a result of the research of networks involving actors (individuals, organizations, etc.) and development of a metrics focusing on different aspects of social positions and interactions. We will discuss SNA in the Section 2.
1.2 Typical Complex Networks and Characteristics
We present only a brief overview of the typical complex network
characteristics and their salient features. An exhaustive literature is
available, especially (Barabási, 2001;
1.2.1 Random Graph Theory
One of the earliest attempts to study the behavior of these so-called ‘complex networks’ dates back to the seminal work on random graph theory by Paul Erdös and Alfréd Rényi, (the so-called E-R model) in the 1950s.
The basic E-R model requires connecting N nodes through n edges chosen randomly such that the resulting network is from a space of graphs, each equally likely. Several nodes can have the same degree in a random graph (large enough) which can be calculated. Given the probability of wiring p is not small, the diameter of random graphs is usually small and the diameter increases logarithmically, as a random graph evolves.
1.2.2 Pareto Distribution and Self-Organized Criticality
The underlying assumption in using the statistical methods, in many situations, is that the mean and standard deviation of the distribution of the data are known and are stable. In many cases, it was found that the simulation results in generation of data that has a fat-tail and thin-peak; a characteristic known as leptokurtosis.
One of the most studied characteristics of the complex networks is the appearance of the power-law distribution in many areas. Informally, it means that the most connected nodes in the network are relatively very few as compared to the lesser connected nodes (or vice versa). The so-called power-law(s) stem from the Pareto Distribution, a specialization of the Pareto Principle, named after Vifredo Pareto (Wikipedia, 2005). The probability density function of the distribution is defined as:
The distribution is parameterized by two parameters: xm and k. As Barthélémy (2003) discusses, if the shape (peakedness) parameter k Î (0,2] has value k ≤ 1, the mean is infinite; while for k ≤ 2 the variance is finite. Figure 1 shows the thin peakedness, which is the characteristic of the distribution. Our purpose is here is about the implications and not presenting a discussion on the analytical properties of the distribution, which can be found in any standard text on stochastic distributions.
One implication of the appearance of statistical properties like the power-law etc., is that they provide useful guide to analysis of multiagent based simulation of social phenomena (Moss et al., 2000). Such characteristics provide cues for further investigation of the underlying model and the phenomenon it addresses. We will come back to this issue later in this article. Another implication identified by (ibid) was that “the specification of utility maximising agents will not support an analysis of the properties of large, distributed systems if those systems are to mimic market systems as described by equilibrium economic theory”. This further encourages in looking for statistical signatures in validating the relevant theories. The fact that higher, thinner peak of the frequency distribution with respect to the corresponding normal distribution, i.e. leptokurtosis, are observed in the series of data from quite a few social networks (Moss, 2001; Moss and Edmonds, 2005), provides analysis of such behavior a highly prospective candidate for a thorough investigation. Therefore, it is interesting for both policy designers and modelers to not only identify the causes of volatility and clustering of data, but to look for means to be able to predict (if possible) the phase transition, which may be regarded as policy change, change of political views, etc.
Self-Organized Criticality (SOC) maybe interpreted as the response of slowly-driven system such that the outcome of the system’s behavior is limited by the magnitude of its size; thus, leading to the scale-free property (discussed in the subsequent section). Following Jensen (1998), one may explain SOC as the development of emergent patterns due to the interactions among meta-stable agents, such that at some critical state, the result of interactions affects the entire system such that ‘all members of the system influence each other’. For the rest of the period, the any local distortions resulting from agents’ interaction in their neighborhoods remain confined locally.
Several properties of the systems exhibiting SOC have been
reported. Moss and
Figure 1: Pareto Distribution; source (Wikipedia, 2005)
1.2.3 Small-World Networks
As shown by Erdös and Rényi, if the probability of connectedness p³ ln(N), N being the number of nodes in the network, then one can find a path of edges that connects any two nodes in the network. As the length of the shortest path between two nodes tends towards O(ln(N)), which is small, a random graph exhibits the property, the so-called ‘small world’ effect.
A seminal contribution was made by the sociologist Stanley Milgram whose study based on social networks led to the term ‘six-degrees of separation’. The term ‘small world’ thus implies that in most networks (even as large as the World Wide Web), there exists a significantly shorter path between two nodes present in the E-R model.
In 1998, Duncan Watts and Steven Strogatz presented their Watts-Strogatz (WS) model, see Figure 2, which ‘interpolated’ a small world graph as an intermediate of a purely random and a regular graph. The property displayed by the networks had been observed in quite a few social systems such as friendship, coworker networks, conflict networks etc., where the average path length is small and shows high clustering property characterized by the clustering coefficient. Informally, the clustering coefficient supports the phenomenon ‘the friend of my friend is also a friend’ or that the neighbors of a node are more likely to be linked to each other than in a pure random network.
Figure 2: Random rewiring procedure in the WS model. (Albert and Barabasi, 2002)
1.2.4 Scale-Free Networks
As explained by Albert and Barabasi (2002), just using the ER or the WS models just does not capture the two important aspects of real-world networks. First is the assumption that the number of starting nodes is fixed and is not changed. Secondly, in the random networks, the chances of a node being linked to another are equally likely. Real-world networks not only evolve over time but also exhibit the notion of preferential attachment, where the likelihood of a node being connected depends upon the number of edges it has.
The Barabasi and Albert model (BA) tackles the two aspects in two steps:
i. Growth of the network: This starts with a small number of nodes, say, N and each time step, a new node m is introduced in the network. The new node is connected to the nodes from N.
ii. Preferential attachment: The choice of nodes to which m(≤M) is connected, the probability that m will be connected to a node nÎ N depends upon the connectivity of the node such that,
After t (≤ T) time steps, the model evolves to a networks with t + m nodes and Mt edges. As demonstrated Albert and Barabasi (2002), the network evolves into a ‘scale-variant’ state such that the degree distribution follows a power-law, with the scaling component independent of M.
2 Social Networks Analysis (SNA)
Over several decades researchers have used social networks study methods either to investigate the patterns that emerge from in the interaction among people belonging to various kinds of networks, e.g. kinship, work, friendships etc; or to identify the major actors or nodes in the network which influence the structure of the network in a number of ways. It is important to note that despite the fact that social networks research is described in terms of the repertoire of the measures, it has a long history of qualitative research. Social networks, maybe regarded as important sub-discipline in the social sciences in broader terms. Hence studies in social networks range from pure qualitative research to development of sophisticated quantitative metrics that capture the macro-properties of the underlying network.
As we shall present the arguments raised by several researchers recently later in this article, that the any authentic evidence reported in a case-study comes before any analytically imposed structure when modeling social networks. This important characteristic of social networks distinguishes them from complex networks structures found in physical and biological systems.
3 Issues in Social Networks Fieldwork Research
While in principle, any social network research should be based on the empirical evidence, acquiring real-world is one of the most challengingf tasks for the field researchers. Unfortunately, this often leads to analysis of networks formulated on either very small data sets or some a priori set of hypotheses, which is even worse. A major obstacle is the often unwillingness (for any reasons) of the stakeholders to feed-in the researchers, especially when the questions are concerned about their relations (or lack of it) with other stakeholders in a case study area. Another obstacle is unavailability of funding to do fieldwork research; which could either lead to the paying less heed to study real-world social processes or the unjustified assumption that the available aggregate data adequately represent the stakeholders’ behavior.
As Schensul et. al. (1999) identify, some of the social networks descriptions based on case-studies include the following:
A primary objective for fieldwork researchers is to identify the boundaries of social groups that exist among the actors or the stakeholders and investigating the features that distinguish them.
Definition: Boundaries from Schensul et. al. (1999)
“Boundaries constitute the edges of networks and are defined by rules for entry and exit from groups as well as by other cultural patterns of participation that differentiate one group from another.”
As Schensul et. al. recommends, it is really important to interview as many as possible people in the case-study areas, as people’s views about their acquaintances and their groups help in identifying the inclusion/exclusion, closeness/openness within and among the groups.
Returning to the notion of neighborhood, physical neighbors maybe described in terms of the land use, segregation of sub-regions etc. while the social aspect of neighborhood is based on the ‘local social interactions, social class, ethnic and radical origins, life cycle characteristics of the population, length of residence, and place of work’ etc.
A focus of any evidence-based research is the community, a social unit, where people share common ‘values and needs’ and/or similar ideologies. As the concept of locality is embedded in its definition, a community may be identified as sharing social characteristics or as community space, where the interactions take place, or both. Local interaction among neighbors has been a subject of quite a few agent-based social simulations, and as we shall discuss later on, a number of such simulation models are inherently spatially explicit. One natural unit in a community space is the household or a cluster of households, e.g. in extended families etc. Identifying the community space and distinct regions is vital, especially in the context of modeling land-use changes etc. (LUCC, 2001)
As Bailey and Gatrell (1995) 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 those based on GIS (Graphical Information Systems) techniques highlight the importance, provided it exists, of neighborhood or influences, if any, in the actors’ behavior caused by the spatial-context. Schensul et al. (1999) has thoroughly covered the issues involving spatial mapping of data; we however, restrict to reporting a few most relevant points. For any social networks, the atomic units are obviously 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.
An important facet of a community, imminent for investigating social networks, is the existence of so-called ‘community organizations’, which operate within the perimeters of the community. Such organizations maybe identified in terms of their membership types (e.g. open, by reference, etc.), the services they offer (e.g. social, economical, etc.) and the minimum threshold of the number of members, and other factors. Such organizations can be state-managed, non-government organizations (NGOs), or loosely-coupled local clubs etc. For public or state-owned organizations, which usually serve for the general welfare of the inhabitants in a community, it is relatively easier to obtain data, than otherwise. In case of the local private clubs, dedicated to specific interests of their members, acquiring data is certainly a non-trivial task as people usually avoid disclosing their private social activities and affiliations. However, with respect to the social networks in the community, such local clubs are the building block and hence are most important to be investigated. A major difficulty in this regard is the local people’s mistrust to the fieldwork researchers, especially if the neighborhood is hard-pressed and poor. As the effects resulting form a qualitative research in social networks are not visible immediately, people tend to think such practices as waste of time and perhaps exploitation. It is therefore, of immense importance, that the researchers involved in qualitative social networks fieldwork, are supported with sufficient time and funds, so that they maybe able to gain the confidence of the local people, by staying and involving them as well. An interesting methodology involving the ‘players’, is the setting up of ‘role-playing games’, which we briefly review later.
4 Towards Non-Traditional SNA
Recently, the social network analysis community has been concerned over the use (and misuse) of metrics and validation techniques for both the empirical and simulated networks. With the plethora of available measurement tools, it has become immensely important to choose carefully the most suitable set of metrics depending upon the context of the underlying study. For example, whether it is about the spread of disease, asymmetric information exchange, dyadic friendships relations etc; especially, when identifying the key players in case of transmission. Hence whether the data are directed or undirected, the nature of the network and the context are important.
Borgatti and Mehra (draft) have recently addressed the four major criticisms on the traditional social network analysis. We present only their assessment related to dynamics and ‘agency’, briefly; details can be found in the original paper. The traditional structuralist approach has invited the criticism that network research is static and thus only the outcome are focused, and ignoring the factors that have caused evolution of the network. Nevertheless, with respect to the notion diffusion of information and the social impact, it is not only supported by strong theoretical basis, but also these concepts have led to the development of quite a few analytical and graphical analysis tools. Concerning the role of agency, we discuss the issue at length in the next section.
5. Agent-based Social Networks (ABSN)
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 benefited from it most as these models provided the provisions of simulating social behavior of autonomous individuals and the interactions among them. Agent-based models 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.
5.1 Spaces and Social Embeddedness
The importance of signifying boundaries and neighborhoods has been discussed in the previous section. 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 explicit per se.
Typically, in spatially explicit models, agents may include stakeholders, land owners, farmers, public institutions, policy or decision-making agencies. Moreover, as Brown (in press) elucidate on such models, the behavior of such agents, may vary from being triggered by some external stimulus or coping with certain stressors, to being goal-oriented. Especially, with regards to models incorporating land-use change, several criteria have been suggested for being spatially explicit, e.g. (Parker et al., 2001) as follows:
Modeling dynamical social networks where agents communicate with each other
and build relations over time, require the introduction of ‘social’ spaces that
go beyond the physically situated agents. Such agents can be called ‘socially
embedded’ (Granovetter, 1973; Edmonds, in press), i.e. an agent’s behavior is
fairly influenced by the network of social relations that it is part of.
Physical resources and interaction with the environment, does not fulfils the
demand for capturing the social interactions that may influence, for example, a
farmer’s decision to plant a certain type of crop, or use of their land. Social
spaces and the agents’ interactions can either be constrained via local
neighborhood, or could just be global (i.e., each agent can be directly related
to any other agent in the space). In the former case, the sociability of agents
depends upon the spatial neighborhoods and thus as
An example of incorporating both physical and social spaces, in order to better capture the complexity of stakeholders’ interactions, is the ‘CCDeW project’ by Downing et al. (2003), modeling the mutual influence on domestic water demands.
Figure 3: Interplay of Social and Physical Spaces;
Figure 3 illustrates the ‘social topology’ resulting from the neighborhood in the model used in CCDeW. As reported, the results from the simulation clearly show that the social network of the agents (households, in this case) has a significant effect on the ‘qualitative nature of the aggregate water demand patterns that result’.
Not many social networks model exploit the combining of both the social and physical spaces, which is pivotal for analyzing the underlying complexity and to which agent-based models are best suited as they support modeling both the spatial neighborhood as well agents’ cognition in building relations. Hence, research in the symbiosis of the two ‘spaces’ has still quite a few niches to be filled.
5.2 Some Other Examples of ABSN models
In this section, we briefly present some of the related work as examples of agent-based models for social networks. The examples are by no means exhaustive; the purpose is to discuss some representative approaches and models by other researchers.
5.2.1 Dynamic Network Analysis by Carley (2003)
Carley’s Dynamic Network Analysis (DNA) introduces the meta-matrix, proposes the schema for coping with the problems of multiple relations and co-evolution of both the agents (entities, nodes) and the relationships over time. Moreover, the advancement in this schema, as claimed by the author, are supplemented by the modeling of ties probabilistically, and ‘combining social networks with cognitive science and multi-agent systems’. The meta-matrix attempts to capture the interplay between people, resources, tasks and the organizations resulting in 10 inter-linked networks. The idea is that change in one network results in a change in the other and so individuals related in more than one networks implies a tie in the social network. Figure 4 illustrates the meta-matrix where the entries describe the inter-linked networks.
Figure 4: Meta-Matrix; source: Carley (2003)
FEARLUS: A System for
FEARLUS (2006) is the modeling framework designed for the assessment of land use change scenarios. Built upon the Swarm modeling system (SWARM, 2005), it supports a variety of agent-based modeling techniques and extensions such as hydrological model, land parcel trade, cropping techniques, effect of climatic variability on land parcels etc. A range of parameters and strategies are also implemented in the FEARLUS for modeling land managers’ preferences, spatially-explicit representation of the land, a built-in auction mechanism (Polhill et al., 2005), etc.
A significant aspect of FEARLUS is that both the social and physical neighborhoods are coupled, and are represented in the system, which was an important issue discussed in the start of this section. Figure 5, illustrates the social and physical neighborhoods as used in FEARLUS.
Figure 5: The left image shows the representation of social neighbourhood, whereas the physcial neighbourhood is shown on the right side; source (FEARLUS, 2006)
The social neighborhood in the system is used when farmers or owners of the land parcels (the land parcels are represented as cell in the 2-D grid) imitate each other in terms of deciding their strategies. On the left in the above figure, the black border shows the social neighborhood, while the black border on the right side represents the physical neighborhood; the farm is colored in burgundy.
5.2.3 Role Playing Games
An interesting aspect of social simulation, where the agents (or actors) are actual humans rather than computer-based simulations, can be characterized under the general theme of the ‘role playing games’ (RPG). Typically, the participants in such designed games are the stakeholders who assume different roles, such as farmers, funding agencies’ representatives, etc. As explained by Barreteau et al. (2001), “The initial idea is to consider the RPG as a living MAS in which players are the agents and the set of roles is the rule base.” The rules are set as simple and are designed based on the conceptual studies of the underlying domain.
Role-playing games in social simulation have a distinctive advantage for the understanding and validation of the MAS model as the stakeholders are the best judge of a model’s behavior. Actions represented as rules not only facilitate in explaining the players how to participate, but also support any evidence based modeling of the phenomenon. Figure 6 demonstrates the cyclic relationship of the multiagent systems and the role playing games.
The relation of MAS and RPG allows the stakeholder interaction and their feedback and thus incorporating evidence in understanding the complexity of the system via the agent-based models.
Figure 6: Association of MAS, RPG and field observations in a two-cycle method; source Barreteau et al. (2001)
5.3 Modeling Dynamic Social Networks using ABSS
In a recent paper,
Stressing upon the concept of social embeddedness
(discussed earlier in this section),
Although the proposed scheme only scratches the surface, it does identify the fact that there are quite a few niches to be filled in the research in dynamics of social networks and their analyses. These include:
Figure 7: An illustration of the use of simulation to
stage abstraction; source (
ALBERT, R., and Barabasi, A. (2001), Statistical Mechanics of Complex Networks, available at <www.arxiv.org>
ALBERT, R., and A. Barabási (2002), Statistical Mechanics of Complex Networks, Rev. Mod. Phys., 74, 47, available at <www.arxiv.org>
AXELROD, R. (1997), Advancing the Art of Simulation in the Social Science, in Conte, Hengselmann and Terno (eds.), Simulating Social Phenomena, Berlin et al: Springer-Verlag.
AXTELL, R.L. (2001), ‘Effects of Interaction Topology and Activation Regime in Several Multi-Agent Systems’, in Proceedings of Multi-Agent-Based Simulation (MABS 2000), Lecture Notes in Computer Science, vol. 1979, Berlin et al.: Springer-Verlag, pp. 33-48.
BARTHÉLÉMY, O. (2003), ‘The
impact of the model structure in social simulations’, in Proceedings of the
1st European Social Simulation Association (
BARRETAEAU, O., Bousquet, F., and Attonaty, J., 2001, ‘Role-playing games for opening the black box of multi-agent systems: method and lessons of its application to Senegal River Valley irrigated systems’, Journal of Artificial Societies and Social Simulation, vol. 4, no. 2,
BORGATTI, S.P. and Mehra, A. (draft), Network Research in Light of Four Traditional Criticisms.
CARLEY, K.M. (2003), Dynamic Network Analysis, in Breiger, Carley, and Pattison, (eds.), Dynamic Social Network Modeling and Analysis: Workshop Summary and Papers, Committee on Human Factors, National Research Council, National Research Council, pp. 133-145.
CAVES (2005), CAVES Project portal, <www.caves.cfpm.org>
DOWNING, T.E, Butterfield, R.E.,
FEARLUS (2006), Framework for
Evaluation and Assessment of Regional Land Use Scenarios, The Macaulay
GRANOVETTER, M. (1973), ‘The Strength of Weak Ties.’, American Journal of Sociology, vol. 78, pp. 1360-1380.
JENSEN, H.J. (1998), Self-Organized
Criticality: Emergent Complex Behavior in Physical and Biological Systems,
Merriam-Webster Online Dictionary, <www.m-w.com>
MOSS, S. (2001), ‘Policy Analysis
from First Principles’, in Proceedings of the
MOSS, S. and
MOSS, S., and
NEWMAN, M.E.J. (2003), The structure and function of complex networks, SIAM Review, vol. 45, pp. 167-256
Parker, D.C., Berger, T. and
Manson, S.M. (2001) eds., Meeting the Challenge of Complexity: Proceedings
of the Special Workshop on Agent-Based Models of Land-Use/Land-Cover Change,
POLHILL, J.G., Parker, D.C., and
Gotts, N.M (2005), ‘Introducing Land Markets to an Agent Based Model of Land
Use Change: A Design’, in Proceedings of 3rd European Social Simulation
SCOTT, J. (1991), Social Networks Analysis: a handbook,
SCHENSUL, J.J., LeCompte, M.D., Trotter II, R.T., Cromley,
E.K., and Singe, M. (1999), Mapping Social Networks, Spatial Data, &
Hidden Populations, Ethnographer’s Toolkit vol. 4,
SWARM (2005), <www.swarm.org>
Wikipedia (2005), ‘The Pareto distributions’, Wikipedia,