-This paper proposes the use of methods for network analysis in order to study the properties of a dynamic graph that model the interaction among agents in an agent-based model. This model is based on Multi Agent System definition and simulates a multicultural crowd in which proxemics theory and distance perception are taking into account. After a discussion about complex network analysis and crowd research context, an agent-based model based on SCA*PED (Situated Cellular Agents for PEdestrian Dynamics) approach is presented, based on two separated yet interconnected layers representing different aspects of the overall system dynamics. Then, an analysis of network derived from agent interactions in the Proxemic layer is proposed, identifying characteristic structures and their meaning in the crowd analysis. At the end an analysis related to the identification of those characteristic structures in some real examples is proposed.
The analysis of networks can be traced back to the first
half of the XX century [
The analysis of social networks is an emerging topic also
in the Multi Agent System (MAS) area [
In this paper we propose an analysis of the graph structures of a social network derived from the interaction among agents in a MAS with the aim to support the simulation of crowd and pedestrian dynamics. This system is based on a model that is an extension of an agent-based approach previously presented in the pedestrian dynamics area: in particular, we refer to
In this approach, according to agent-based modeling and
simulation, crowds are studied as complex systems: other
approaches consider pedestrians as moving particles subjected
to forces (i.e., Social Force models [
These traditional modeling approaches focus on pedestrian
dynamics with the aim of supporting decision-makers and
managers of crowded spaces and events. Differently, in the
agent-based approach, pedestrians are instead explicitly
represented as autonomous entities, where the dynamics of the
system results from local behavior among agents and their
interactions with the environment. With respect to the particle
approach, the agent-based model can deal with individual
aspects of the crowd and differences between single agents
(or groups of agents) [
In this way some multidisciplinary proposals have recently
been suggested to tackle the complexity of crowd dynamics by
taking into account emotional, cultural and social interaction
concepts [
In this paper we focus on interactions among different
kinds of agents and we study how the presence of
heterogeneities in the crowd influence its dynamics. In particular,
the model we present explicitly represents the concept of
perceived distance: despite spatial distance, perceived distance
quantifies the different perception of the same distance by
pedestrians with different cultural attitudes. In the model we
assume that pedestrians keep a certain distance between each
other following the theory proposed by Elias Canetti [
The concept of perceived distance is strictly related to
the concept of proxemic distance: the term proxemics was
first introduced by Hall with respect to the study of set of
measurable distances between people as they interact [
In order to represents spatial and perceived distances, the proposed model represents pedestrians behaving according to local information and knowledge on two separated yet interconnected layers where the first (i.e., Spatial layer) describes the environment in which pedestrian simulation is performed and the second (i.e., Proxemic layer) represents heterogeneities in system members on the basis of cultural differences.
The methods and algorithms related to social network analysis can be applied on the network created from interaction among agents in the Proxemic layer. This study allows the evaluation of dynamic comfort properties (for each pedestrian and for the crowd) given a multicultural crowd sharing a structured environment.
The paper is organized as follow: after a description of general SCA*PED approach, we will describe deeply each layer of the structure. Starting from the analysis of the social network created at Proxemic layer, we will identify relevant structures and properties of the corresponding graph. In the end, we will propose some examples of those structures in real world situations.
In this section, the proposed multi-layered model is presented: after an introduction on SCA*PED general approach, we will describe the Spatial and Proxemic layer focusing on the interaction between layers and among agents.
In order to model spatial and perceived distances, we defined a constellation of interacting MAS situated on a twolayered structure (i.e., Spatial and Proxemic layers). Following the SCA*PED approach definition the agents are defined as reactive agents that can change their internal state or their position on the environment according to perception of environmental signals and local interactions with neighboring agents. Each MAS layer is defined by a triple
hSpace; F; Ai where Space models the environment in which the set A of agents is situated, acts autonomously and interacts through the propagation/perception of the set F of fields. IN particular Space is modeled as an undirected graph of nodes p 2 P .
A network, or graph, is a pair G = (V; E) where V is a
set of nodes and E V V is a set of edges. A graph G is
called undirected if and only if for all u; v 2 V , (u; v) 2
E , (v; u) 2 E. Otherwise the graph is called directed.
A graph can be also represented as an adjacency matrix A,
where the elements au;v of the matrix are 1 if (u; v) 2 E and
1These terms were first introduced in 1957 by H. Osmond in [
In the Spatial layer, each spatial agent aspa 2 Aspa emits and exports to Proxemic layer a field to signal changes on physical distance with respect to other agents. This means that when an agent ay 2 Aspa enters the neighborhood of an agent ax 2 Aspa (considering nodes adjacent to pax ), both agents emits a field fpro with an intensity id proportional to the spatial distance between ax and ay. In particular, ax starts to emit a field fpro(ay) with information related to ay and intensity idxy, and ay starts to emit a field fpro(ax) with information related to ax and intensity idyx. Obviously, idxy = idyx due to the symmetry property of distance and the definition of id.
When physical condition changes and one of the agents exits the neighborhood, the emitting of the fields ends.
Fields are exported into Proxemic layer and influences the relationships and interactions between proxemic agents. In Figure 1, a representation of the interaction between Spatial and Proxemic layers is shown. How this field is perceived and influences the agent interactions in the Proxemic layer, will be described in the next section.
As previously anticipated, Proxemic layer describes the agents behavior taking into account the dynamic perception of neighboring pedestrians according to Proxemics theory. Proxemic layer hosts a heterogeneous system of agents Apro where several kinds of agents 1; ::; n represent different attitudes of a multicultural crowd. Each type i is characterized by a perception function perci and a value of social attitude sai. This value takes into account proxemic categories introduced before and indicates the attitude to sociality for that type of agent.
In this layer, space is described as a set of nodes where each node is occupied by a proxemic agent apro 2 Apro and connected to the corresponding node at Spatial layer. Proxemic agents are influenced by fields imported from Spatial layer by means of their perception function. The latter interprets the field fpro perceived, amplifying or reducing the value of its intensity id on the basis of sa value.
When in the Spatial layer ax 2 Aspa emits a field with information on ay, in the Proxemic layer a0x 2 i perceives the field fpro(ay): perci(fpro(ay)) = sai idxy = ipxy and a0y 2 j perceives the field fpro(ax): percj (fpro(ax)) = saj idyx = ipyx
Values ipxy and ipyx quantify the different way to perceive the physical distance between ax and ay from the point of view of ax and ay respectively.
Each apro 2 Apro is also characterized by a state s 2 which dynamically evolves on the basis of the perceptions of different fpro imported from the Spatial layer. The transition of state represents the local change of comfort value for each agent. State change may imply also a change in the perception: this aspect may be introduced into the model by specifying it into the perception function (i.e., perci(fpro; s) = (1) (2) perci(fpro)). In this paper we do not consider this aspect: future works will consider this issue.
In general, the state evolves according to the composition of the different ip calculated on the basis of interactions which take place in the Spatial layer. where a01; ::; a0n 2 Apro are the corresponding proxemic agents of a1; ::an 2 Aspa which belong to the neighborhood of az 2 Aspa.
After the perception and modulation of fields perceived, it is possible to consider the relationship between i and j in (1) and (2).
If i = j the two agents belong to the same type (i.e., i = j ) and the values ipxy and ipyx resultant from the perception are equal (i.e., sai = saj and idxy = idyx for definition). Otherwise, if i 6= j the two agents belong to different kinds (i.e., i 6= j ) and the values ipxy and ipyx resultant from the perception are different (the agents perceive their common physical distance in different way).
Proxemic relationships among agents are represented as an undirected graph P G = (A; E) where A is the set of nodes (i.e., agents) and E is the set of edges. The edges of P G are dynamically modified as effect of spatial interactions occurring at Spatial layer and social attitude sa. In particular, when a field fpro(ay) is perceived from agent a0x with information on ay, an edge between a0x and a0y is created. When field emission ends due to the exit of the neighborhood by one agent, the edge previously created is eliminated. The edge (x; y) between nodes x and y is characterized by a weight wxy: wxy = jipxy ipyxj and represents the proxemic relationships between agents ax and ay in the Spatial layer. Obviously, only if ipxy 6= ipyx the wxy is non null.
In the next section we will introduce the basic notions on networks and the analysis of their properties.
In this section we introduce the basic properties and kinds of graph used in the analysis of networks.
Starting with the previous definition of graph, we can introduce the notion of node degree. The in-degree of a node is the number of incoming edges in the node: for v 2 V , in(v) = jf(u; v) 2 Egj. The out-degree of a node is the number of outgoing edges in a node: for v 2 V , out(v) = jf(v; u) 2 Egj. The degree deg(v) of a node v 2 V is the sum of its in-degree and out-degree. A first simple characterization of graphs can be done using their degree distribution. The degree distribution P (k) of a graph G is the ratio of nodes in the graph that have degree equal to k. For directed graph it is useful to distinguish between the in-degree distribution Pin(k) and the out-degree distribution Pout(k).
A first property of interest in a graph is the diameter, indicated by Diam(G). Let d(v; u) be the shortest path from the node u to the node v. The diameter is the maximum value assumed by d(u; v). If the graph G is not connected then the value of the diameter is infinite. Related to the diameter is the average shortest path length, defined as:
L =
1 jV j(jV j 1)
X u;v2V;v6=u d(u; v) As with the diameter, the average shortest path length is infinite when the graph is not connected.
Another measure used in the analysis of networks is the
clustering coefficient introduced by Watts and Strogatz [
Pu1;u2 av;u1 au1;u2 au2;v
deg(v)(deg(v) 1) The clustering coefficient of the graph G as a whole is the means of the clustering coefficient of the single nodes: C = 1
X c(v)
jV j v2V
Many variations of the clustering coefficient has been
proposed, for example to remove biases [
A structure of particular interest is the community
structure. The concept of community has been defined in social
sciences [
In the study of complex networks many kinds of network
structure have been proposed:
1) RANDOM GRAPH. This is the simplest type of graph,
where pairs of nodes where connected with a certain
probability p. Unfortunately it is not able of representing
many real world phenomena;
2) “SMALL WORLD” GRAPH. In many real world
networks there exists “shortcuts” in the communication
between nodes (i.e., edges connecting otherwise distant
parts of the graph). This property is called small world
property and is present when the average shortest path
of a graph is at most logarithmic in the number of nodes
in the graph. This property is usually associated with a
high clustering factor [
The majority of the nodes in scale-free networks have a low degree, while a small number of nodes have a very high degree. Those nodes are called hubs.
Since this kind of networks is ubiquitous, there are many
studies on their properties, the possible formation
processes and their resistance to attacks and damages [
This short introduction to network analysis is certainly not
complete. To a more in-depth introduction it is possible to
refer to one of the many survey articles [
In the next section we will apply those properties definitions to the graph of the Proxemic layer of the previously defined agent-based model.
A first interesting study is related to the identification of “friction zones”, where a homogeneous group of agents of type i is encircled by agents of different type j 6= i. We are interested in the study of the border between a group and other agents. This structure can be interesting since we can identify the presence of homogeneous zones in a MAS and how those structures evolve in time and interact with other homogeneous groups or single agents (that can belong to the same type or a different one).
Let G = (V; E) and H = (U; F ) be two undirected graph, f 1; : : : ; ng a partition of V and f : V 7! U an injective function. Let A ; B V such that B = V n A and that exist A A and B B with the following properties: i. For all v 2 A , v 2 i for some i 2 f1; : : : ; ng; ii. For all v 2 B, v 2= i; iii. For all v 2 A there exists u 2 B such that (v; u) 2 E and for all u0 2 B exists v0 2 A such that (u0; v0) 2 E; iv. For all v 2 A n A, deg(v) = 0; v. For all u; v 2 A there exist a sequence f (u) = f (u0); f (u1); : : : ; f (un) = f (v) in H such that
A subgraph GA;B = (VA;B = A [ B; EA;B) with EA;B = f(u; v) 2 E j u 2 A; v 2 B or u 2 B; v 2 Ag that respects all the previous properties will be called border for the group A . We will also call A the inner border and B the outer border. An example of a border structure is shown in Fig. 3.
Every property of the definition has an associated semantical motivation. The first property states that a group must be composed of agents of the same kind. The second property declares that the agents directly outside the group must be of a different kind (otherwise they must be part of the group). The third property states that for each agent inside the inner (resp. outer) border must exist at least one agent inside the outer (resp. inner) border that is aware of its presence. The fourth property declares that the agents of the group that are not in the border must be isolated from the outside social interactions. The fifth property uses a mapping function (that can be used to map agents in the Proxemic layer to loci in the Spatial layer) to assure that all the elements of the group are in the same spatial location. The last property assures that we are taking the entire group and not one subset of it.
Given a border GA;B = (VA;B; EA;B) and a weight function w, we can be interested in computing the average weight of the border:
WA;B = 1
X jEA;Bj (u;v)2EA;B wu;v
We are also interested in the average comfort of the inner border:
Cinner = 1
X sv jAj v2A We can define Couter in the same way. We assume that the concept of comfort previously introduced can be translated into a set of real values, where to higher values correspond to an higher level of comfort.
We can fix two values r 2 R (a discriminating value between low and high weights) and c 2 R (a discriminating value between comfortable and uncomfortable states) and obtain 4 possible situations in which a border GA;B can stand:
In this case the group A is uncomfortable with the agents outside it. The outside agents are also uncomfortable with the presence of A . The expected reaction of the group is to close itself and to move farther from the other agents. The agents in the outer border will also move away from the group;
In this case the group A is comfortable with the outer agents and the outer agents are comfortable with A . This is a situation in which it is possible for the group to be open with respect to the rest of the agents;
In this case the group A is comfortable with the outer agents but the converse is false. In this situation the outer agents are going to increase their distance from A ;
In this case the outer agents are comfortable with the group A but the converse is false. In this situation A will probably increase the distance from the outer agents and close itself.
Note that the concept of border it is also useful to identify a group inside the MAS graph P G. Since the set A is composed by agents of the same type that occupy a certain space, we can use A as our definition of group.
Another interesting study is the individuation of homogeneous groups of agents that are in the same spatial location. This homogeneous spatially located group (HSL-group) of agents is expected to behave as a unique entity, so its individuation allows us to understand better the complex dynamics of the whole system (due to an abstraction process on the system components).
In order to identify the structure we use a subgraph of the inverse graph of the perception representation in the Proxemic layer. We are doing this transformation because two agents of the same type i cannot be connected by an edge in the Proxemic Layer. This means that in the inverse graph they will be connected. It is necessary to note that we must take care of agents that are not connected but only as a consequence of the spatial distance. Those agents must remain unconnected. In this way we generate a graph where an edge between an agent u and an agent v has the following semantic: “u and v are of the same type and their spatial distance is low”.
Note that this definition of HSL-group is similar to the definition of group given previously. In fact, the former is a generalization of the latter since it is composed by spatially adjacent groups (under the assumption that when two agents u and v are spatially adjacent, u perceives v and v perceives u).
We will now proceed with a formal definition of HSL-group.
Let G = (V; E) be an undirected graph and g : V V 7! f0; 1g. We call the inverted graph with respect to g the graph G0 = (V; E0) where E0 = f(u; v) 2 (V V ) n E j g(u; v) = 1g.
The graph G0 is a subgraph of the inverse of G since we have added an auxiliary condition g. This condition can be defined in the following way: gip(u; v) = 1 , maxfipu;v; ipv;ug > 0 (i.e., if at least one of the agents perceives the other one).
Given G and a function g, a HSL-group is a connected component of G0. Note that in our MAS model the graph G is the representation of perceptions in the Proxemic layer P G and the function g is gip. An example of HSL-group is shown in Fig. 4.
Some interesting properties that can be studied inside a single HSL-group are: 1) the small world property, since we are interested in how the information can be propagated inside a single HSL-group and the influence of information propagation in the HSL-group dynamics. Recall that small world property implies small diameter and high clustering coefficient. For this reason, we expect that the presence of this property can generate a cohesion mechanism between the components of the HSL-group, otherwise we expect the group to be uncoordinated and to have a short lifespan as a single entity when the movement in the spatial layer are consistent;
scale-free structure of the HSL-group. Recall that a scale-free structure is characterized by hubs (i.e., nodes with high degree). Because of this, we expect the hubs of the HSL-group to be hypothetical leaders. In fact, when this condition appears, we expect to be able to understand the group dynamics using only the leader behaviour;
In the next section we will show some real examples where those structures can be identified.
In the first part we will identify a border structure inside a photo from the Hajj (i.e., the pilgrimage towards Mecca).
In the second part we will identify small HSL-groups at the entrance of the 1912 Democratic National Convention.
In Fig. 5 a particular situation during the pilgrimage towards Mecca is shown. During the Hajj, people of a lot of different cultures attend to the different phases of the rite. For this reason, a partitioning in cultural groups is expected. In the lower right part of the image there is a group of women dressed in dark, encircled by a cordon of men dressed in white. This cordon represents an inner border while people near the inner border compose the outer border. The group is composed of the cordon of men and the women. Note that since every HSLgroup is also a group, this structure is a simple example of HSL-group.
In Fig. 6 the entrance to the 1912 Democratic National Convention is shown. In this picture we can identify some HSL-groups: in particular, the most evident ones are the following:
A AND D. They are composed of four and three people respectively. In the first case the people are organized on two pair disposed on parallel lines while in the second case the people are aligned; B AND C. They are composed of only one person. This is a degenerate version of a group but, nevertheless, it still is an interesting case due to the effects of the interaction between a single person and a full-fledged group. In this picture it is difficult to see large groups, but we expect those groups to be identifiable in simulations and in monitored events with a large number of people.
In this paper we have introduced a new agent-based model for the modeling of pedestrian dynamics that includes not only spatial structures and distances but also perceived and proxemic distances. We have also introduced and formalized two structures of interest that can arise from the analysis of the network of perceived distances.
We plan to implement the proposed model and the algorithms to find the introduced structures in order to experimentally verify the consistence of the model and the hypothesis on the behavior of the structure introduced.
This work is part of an ongoing research project with the aim to study interaction between people in multicultural crowds.
This work is partially funded by CRYSTALS project, a collaboration between the Center of Research Excellence in Hajj and Omrah headed by Dr. Nabeel Koshak and the
Center headed by Prof. Stefania Bandini. The aim of the study is to investigate how the presence of heterogeneous groups influences emergent dynamics in the Hajj pilgrimage. Other financial supports for this paper have been done by the University of Milano-Bicocca within the project “Fondo d’Ateneo per la Ricerca - anno 2009”.