Procópio Stein
email: procopiostein@gmail.com

Anne Spalanzani
email: anne.spalanzani@inria.fr

Christian Laugier
email: christian.laugier@inria.fr

Vítor Santos

Leader Selection and Following in Dynamic Environments

A crucial requirement for service robots is to be able to move in dynamic environments shared with humans as well as interact with them. Navigation in such environments is a challenging task, as the environment is constantly changing, future states have to be predicted and planning and execution must be carried on-line.

However, even in very complex situations, humans can easily find a path that avoid both dynamic agents and static obstacles. This paper proposes a technique to take advantage of the human movement in such populated environments, using a probabilistic approach for the leader selection, according to the robot's desired destination.

By choosing a leader to be followed in dynamic environments, the robot can take advantage of the paths traveled by humans or other robots, effortlessly avoiding dynamic and static features as its leader does, relieving the robot from the burden of having to generate its own path. Both the leader selection and the leader following algorithms have been tested in a real environment, with a robotic wheelchair.

I. INTRODUCTION

With advances in mobile robotics and lowering costs of computers, it is becoming more and more common for us to find robots among groups of people. Service robots (home care, hospital, museum guides) are real example cases where robots have to be able to move and interact with humans in an ever changing environment. The success of interactions and human acceptance of service robots is directly related to the way they behave and approach others, as well as their capability to adapt to the environment.

However, navigation in dynamic environments is still an open and challenging issue for the robotic community. In such environments, sensor's measurements are prone to noise and the measurements have a short lifespan, being valid only for small time periods. Static features, that could guide a navigation algorithm, might not be detected. There are also limitations in the time spent by the navigation algorithm to provide solutions, and optimal approaches are unsuited for this task, as generated paths might be valid only for few time-steps.

Despite these difficulties, humans can easily navigate in dynamic environments. Moreover, their movement can provide indirect information of the environment, as they usually do not move at random. Instead of that, they move according to typical patterns, and their movements are related to features that they are interested in, such as doors, elevators, stairs or other people [START_REF] Mombaur | From human to humanoid locomotionan inverse optimal control approach[END_REF].

Taking advantage of that, several works propose to model those typical paths with probabilistic approaches as Gaussian Processes [START_REF] Tay | Modelling smooth paths using gaussian processes[END_REF] [3] [START_REF] Ellis | Modelling pedestrian trajectory patterns with gaussian processes[END_REF] or Hidden Markov Models [START_REF] Vasquez Govea | Growing hidden markov models: An incremental tool for learning and predicting human and vehicle motion[END_REF], to address the problem of navigating in populated environments [START_REF] Bennewitz | Learning motion patterns of people for compliant robot motion[END_REF], [START_REF] Fulgenzi | Probabilistic motion planning among moving obstacles following typical motion patterns[END_REF]. Correctly detecting and learning a likely path permit the robot to avoid trajectories that have a risk of future collision with a pedestrian, as well as avoiding social disturbances [START_REF] O'callaghan | Learning navigational maps by observing human motion patterns[END_REF], [START_REF] Sehestedt | Robot path planning in a social context[END_REF].

Those approaches, however, do not take into account changes people perform in their typical paths to avoid and adapt to other moving people [START_REF] Helbing | Simulating dynamical features of escape panic[END_REF]. These conditions allied to excessive future uncertainty may lead to situations where every generated path lead to colisions or frozen situations, as shown by [START_REF] Trautman | Unfreezing the robot: Navigation in dense, interacting crowds[END_REF].

The key insight of this paper is to present a navigation technique for dynamic environments that takes advantage of the typical movement of humans. This approach relies on the fact that people try to guarantee their safety and the safety of other people in the same environment, avoiding obstacles and avoiding hitting other persons.

In other words, people walking in populated scenarios can provide rich indirect information about their surroundings, as they are constantly dealing with large amount of high-level information and reacting to it, while following a goal.

A robot moving to a certain destination could identify behaviors of humans and detect a leader, someone moving along a typical pattern that would pass close to the destination point. After identification, the robot could follow people along that path, as "moving with the flow", relying more and more on people in front of it, as leaders or as part of a swarm.

A similar approach has been developed by [START_REF] Müller | Socially inspired motion planning for mobile robots in populated environments[END_REF]. With the difference that the main goal of that work is to implement a human-like motion behavior, and the choice of a leader is deterministic, based on the motion direction of the subject regarding the trajectory planned by the robot. Although such technique can be used for the same objectives that are proposed in this work, in some environments the algorithm may fail to find a leader as the extrapolation of the initial movement of a candidate may not match his/her actual goal, as illustrated in Fig. 1. In this paper, however, the choice of a leader is performed probabilistically, using the Growing Hidden Markov Models (GHMM) technique, an extension to the HMM capable of learning the models parameters and structure in an incremental fashion. This technique not only provides a prediction of the future states of a moving agent, but also its goal, which allows the robot to plan further ahead, with a probabilistic knowledge of the goals pursued by the moving persons.

The global path planning is implemented with the RiskRRT algorithm [START_REF] Fulgenzi | Probabilistic motion planning among moving obstacles following typical motion patterns[END_REF], which takes into account the risk of collision with dynamic obstacles while generating the tree. The use of this algorithm guarantees that the robot can find path solutions in dynamic environments when a leader is not found.

In section II the technique to choose a leader in dynamic environment is presented, followed by the explanation of a leader following technique, in section III. The experiments and their results are presented in section IV, and after that, the conclusions of this work are presented in section V.

II. CHOOSING THE LEADER

As the proposition of this work is to take advantage of the movements of a person, the method used to choose which person to follow plays a major role. Here, the choice of a leader is implemented based on the distance between the goal given to the robot and the predicted goal of the leader candidate.

The prediction of the motion and goal of a leader is not an easy task in dynamic environments. A simplistic approach may extrapolate the current orientation and speed of a moving person in an attempt to determine his/her likely goal. But due to environment or dynamic restrictions, the subjects can completely change their trajectory in the subsequent time steps, invalidating the extrapolation, as shown in Fig. 1. Here the dashed lines represent the goal and motion prediction using simple extrapolation or a Kalman Filter. Note however that due to the environment structure and interest points, the actual goal and paths, represented by solid lines, highly differ from the ones predicted using simplistic assumptions.

Knowing that the movement of humans is highly dependent on the environment structure and interest points, recent approaches take advantage of the typical paths in order to make predictions of motions and goals of humans. This approach can overcome the limitations posed by simple extrapolation techniques, as it allows to take into account the structure of the environment as well as the most common motion patterns. In the current work, in order to predict the goal of moving agents, the Growing Hidden Markov Models (GHMM) algorithm is used [START_REF] Vasquez Govea | Growing hidden markov models: An incremental tool for learning and predicting human and vehicle motion[END_REF]. It implements an approach where the learning and prediction phases are on-line concurrent processes, resulting in a learn and predict paradigm. The structure of the GHMMs are the same as the regular HMMs, with the difference that as new observations sequences are incorporated into the model, the transition structure and the number of states can change, updating the model, as seen in Fig. 2.

The GHMM algorithm consists of the use of the Growing Neural Gas (GNG) algorithm [START_REF] Fritzke | A growing neural gas network learns topologies[END_REF], used to estimate the model structure as well as the transition probabilities of a Hidden Markov Model (HMM). As the algorithm is adaptive, it is capable of creating or removing states to cope with new observations.

One very important aspect of the GHMM algorithm is that it is based on the hypothesis that moving agents always try to reach a goal in the environment. Therefore, each goal in the scenario has a different HMM associated to it. As the intention of the current work is to predict the most likely goal of a moving agent, the GHMM inherently provides a direct solution to that problem.

III. FOLLOWING THE LEADER

Once a moving agent has been detected as a leader, due to a similar goal with the robot's goal, there still remains the problem on how to follow the person. Simplistic approaches that try to use the current leader position as a subgoal may bring the robot to situations where undetected obstacles are present between the robot and the leader.

Following the leader path, generating subgoals along the tracked trajectory can overcome situations were obstacles that were not detected appear between the robot and the leader. However, if the robot is not close enough to the leader, it can lose track from the person or different agents that are not leaders may appear in the scene, blocking the tracked path.

Besides that, the motion algorithm has to be able to maintain a navigation solution even in situations where no leader is found, or after a leader is lost due to sensor occlusions or scene exit by the leader being followed. These constraints are addressed with the use of a variation of the RRT algorithm that efficiently explores the free space while at the same time takes into account the risk of collision with moving agents in a scenario.

A. Risk Rapid-exploring Random Tree

The Risk Rapid-exploring Random Tree (RiskRRT) is a variation of the classic RRT algorithm presented by [START_REF] Lavalle | Randomized kinodynamic planning[END_REF] developed for navigation in dynamic environments. It takes into account the risk of traveling along generated paths according to predicted objects' motion. It combines a part dedicated to perception (of static and moving obstacles) with another for planning trajectories. Navigation and planning are done in parallel.

The configuration-time space is searched randomly, and a tree T is grown from the initial configuration all over the configuration space. The algorithm chooses a point P in the configuration space and tries to extend the current search tree toward that point.

The points P are randomly sampled on the map, but at the beginning, and then once every 100 times, the goal itself is chosen; this bias, which has been empirically set, speeds up the exploration toward the goal. The node chosen for extension is the most promising node: all the nodes in T are weighted taking into account the risk of collision and the estimated length of the total path:

w(q N ) = L π (q N ) dist(q 0 , q N , P ) (1)
w(q N ) = w( q N ) q wq

(2)

At numerator, the likelihood of π(q N ) is normalized with respect to the length of the path N ; at denominator, dist(.) is the sum between the length of the path from the root q 0 to the node q N (which is known) and an estimation of the length of the path to P .

The weights are normalized over the set of nodes in the tree (2). The node to grow next is then chosen taking the maximum over the weights or drawing a random node proportionally to the weight. The new node q + is obtained applying an admissible control from the chosen node q toward P . The weight of q + is computed. If w(q + ) ≥ w(q) the tree is grown again from q + toward P otherwise another point is sampled from the space.

The likelihood of each partial path can also be expressed as the multiplication of the independent probability of collision with static (P cs ) and dynamic components (P cd ):

L π (q N ) = N n=0 (1 -P cs (q N )) • N n=0 (1 -P cd (q N )) (3)
The prediction approach for forecasting the position of moving obstacles in the near future is done using the GHMM predictor. With the information of probable occupied positions in the future, the robot can anticipate the behavior of the agents. The selection of the best trajectories is done by taking into account the probability of collision for each path.

The probability of collision, or risk, can be seen in this case as a measure of the feasibility of a path, with the maximum accepted risk specified as a threshold. The RiskRRT algorithm also takes into account the interactions among humans so the robot can behave in a socially acceptable way. Therefore, the risk function must rely on safety but also in human friendly navigation.

After these extensions the "probability of success" calculated for every partial path is given by the probability of not encountering a collision along the path and not entering a social interaction zone. For more details about this method, refer to [START_REF] Rios-Martinez | Understanding human interaction for probabilistic autonomous navigation using Risk-RRT approach[END_REF].

B. Leader Following Algorithm

The developed program to follow a leader is shown in III-B. The program starts after receiving a desired goal for the robot, which is used to initiate the RiskRRT algorithm. At the same time, the tracking program starts, in order to detect moving agents in the scenario. The detected agents are fed into the GHMM predictor, which outputs the prediction of a goal for each person.

Leader Follower 1: procedure leader f ollower end while 26: end procedure After that, the Euclidean distance between the robot's current goal and each subject's predicted goal is computed. If Fig. 4. RiskRRT algorithm avoiding a moving person that obstructs the path being followed. The triangle represents the robot's subgoal, the black dotted line the leader's path and the colored circles are the tree exploration nodes, that get larger according to the risk.

this distance falls inside a threshold, the corresponding subject is chosen as a leader.

In the case a leader is found, the robot starts to track its path, but does not immediately starts to follow the leader. This only takes place once the elected leader is closer to the goal than the robot. The reason for this criteria is to avoid situations where the robot would have to move away from the goal in order to follow the path of a leader.

Once the criteria to start following a leader is satisfied, the robot calls an update routine in RiskRRT planning algorithm. This routine causes the RiskRRT algorithm to use the new subgoal instead of the original goal, in order to find a path.

As a result, the algorithm explores the open space and finds a path that poses the lesser risk to bring the robot to the chosen subgoal, which lies over the leader path. The getSubGoal routine decides when to pass a new subgoal of the path to the RiskRRT algorithm, based on the robot distance to the previously passed subgoal. This sequence of steps makes the robot follow the tracked leader's path.

The use of the Risk-RRT algorithm to reach and follow a leader's path has two main advantages. Firstly, it provides a reliable method to navigate until the leader's path start, since in a dynamic environment the space between the robot and its first subgoal may be occupied by moving agents or static obstacles, as can be seen in Fig. 4. Here the robot is following the path of a subject moving right, while a subject moving upwards blocks the path being followed. The algorithm successfully predicts a future collision and change its path, passing on the back of the obstructing subject.

In second place, once the robot reaches and starts to follow the leader path, the algorithm is capable of reusing nodes of its exploration tree to efficiently generate new paths for each new subgoal received by the update routine. The reuse of previously generated nodes, reduce the computational load of the algorithm, while still taking into account the risk of navigation.

Finally, in the case that a leader is not found, or the current leader is lost, the update routine sends once again to the RiskRRT algorithm its final goal, as chosen at the beginning of the program.

IV. EXPERIMENTS

The experiments were performed using several independent modules using the Robot Operating System (ROS) [START_REF] Quigley | ROS: an open-source robot operating system[END_REF].

To conduct the experiments, the main hall of INRIA Rhône Alpes has been chosen (Fig. 5). It is an interesting choice as

A. Real Data Acquisition

The trajectories used in the experiments to test the robot capability to chose and follow a leader are real human trajectories, that were previously tracked and recorded. An overhanging camera with wide angle lens provides an overview of the test area. The implemented tracker is based on the work of [START_REF] Snape | Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles[END_REF]. In the current work, fiducial markers were worn as hats by subjects in order to provide a robust and fast deployment tracker system, as shown in Fig. 6.

The GHMM is trained using a set of the real data acquired with the tracking system. Volunteers were asked to move naturally among interest points in the environment, as the entrance of the hall and the two doors. Fig. 7 shows a sample of the these trajectories.

B. Test Scenario

Two types of tests were conducted, one that evaluates the leader detection technique when several subjects move close to each other (Fig. 8), and another test that evaluates the advantage of the proposed technique to avoid moving agents (Fig. 9). The human perception and detection are performed by a second computer, using the techniques mentioned in the previous subsection.

The tests were conducted using a simulated robot, while the scenario agents represent real data recorded from the motion of humans. The scenario is simulated using PLAYER/STAGE and the robot has a copy of the environment map and localizes itself based on its odometry and a simulated laser range finder. The robot is represented as a light gray rectangle, and starts in the upper center of the scenario. The obstacles are colored dark gray and encompass walls, desks and sofas.

The circles are the persons detected by the overhanging camera, and the triangles are their respective predicted goals. They have a letter associated to identify their colors (Red, Green and Blue). The robot goal is marked as an X, located at the lower left of the test area. Finally, the dots represent the RiskRRT tree nodes and the solid line is the best path found by the planning algorithm.

C. Leader Detection Test

In the first test, shown in Fig. 8, three humans start to move just in front of the robot, and pursue one different goal each. After some iterations, as the subjects start to move in the scenario, the prediction algorithm gives an estimation for two of them (red and green). Based on that estimations, the leader following algorithm makes the choice of following the red subject, as its predicted goal lies within a distance threshold from the robot's goal.

It is interesting to note that, for the blue subject, no correct goal prediction is found until the subject is very close to its actual goal. This can be explained by the fact that not a single trajectory that ended on that point was used in the train of the GHMM algorithm. However, the fact that a goal is found in the last moments of the test exemplifies the capacity of the GHMM algorithm to adapt and learn when presented with new situations.

Once that the leader is closer to the goal than the robot, by an empiric factor, the planned trajectory is computed from the robot to the subgoal. This corresponds to the first position of the chosen leader's path, and the robot starts to move along the trajectory taken by the human, in the direction of its desired goal.

D. Dynamic Agents Avoidance Test

The objective of this test is to evaluate the benefits of following a leader in order to avoid other dynamic agents and is shown in Fig. 9. The way the robot selects and follow a leader occurs in the same fashion as in the previous test. The robot goal is again in the left bottom corner of the image, but here there are now two humans that move from the door to the stairs, in the opposite direction of the robot's desired trajectory. After the leader is chosen, using the same approach as in the previous test, the robot starts to follow him/her. As the leader approaches the two humans moving in the opposite direction, they naturally give room for him/her to pass. As the robot is closely following the path taken by the leader, it is able to continue to move without the need to take evasive measures to avoid the two incoming persons. As a result, the robot benefits from a straight trajectory toward its goal.

More test results can be seen in the following link: http://navigationadvantage.blogspot.fr/2012/04/ leader-selection-and-following-in.html

E. Discussion

The tests assessed the capability of the system to predict the goal of real moving agents, as well as the ability of the designed algorithm to properly follow a chosen leader, while avoiding other dynamic agents.

Results show that the leader following algorithm makes a proper choice of a leader, based on a probabilistic approach for goal prediction, even when the initial movement and is not directed toward his/her goal. This is an important advantage of a probabilistic approach for goal detection, based on previous knowledge of the most common trajectories in the environment.

The navigation technique employed to follow the leader's path continuously explore the surrounding space for alternative trajectories. In the case the leader is lost of the path being followed becomes blocked, the branches that were generated in different directions can be used to find a new path, without the need of replanning from scratch. This is a very important characteristic while navigating in dynamic environments, specially due to time constraints.

The resulting behavior is that the robot is able to follow the leader while at the same time exploring the open spaces to accommodate new and unpredicted situations.

In the second test scenario, the advantages of following a leader in a dynamic environment becomes evident. Classical approaches that would attempt to plan a trajectory taking into account the predicted motion of the incoming humans would fail to find an optimal solution, as a straight line to the robot's goal would be blocked.

However, as the robot follows a human that is able to correctly assume that the persons moving in the opposite direction will adapt their movement to avoid a collision, it is able to follow a straight trajectory to the goal. The result of this experiment clearly shows the benefit of the proposed technique, as the robot follows an optimal trajectory as a consequence of following a leader that has a better understanding on how to behave in such situations.

V. CONCLUSIONS

This work presents a method to take advantage of human motion in dynamic environments by selecting and following a leader. Its has two main contributions. The first is the methodology used to leader selection, which takes into account the typical paths in an environment and provides a probabilistic inference of subject's goal. The second is the modification of an algorithm designed for motion planning in dynamic environment, in order to adapt it to the task of leader following, while maintaining its original characteristics.

Tests used real data for the leader selection part, while the leader following algorithm was tested in a simulated and real environment. The results validated the proposed approach, with the robot being able to properly identify leaders among several subjects and follow him/her until its desired goal. It is our belief that the prediction algorithm can be further improved if it takes into account not only the position of the agents but also their speed and orientation, making it able to anticipate even more the future motion and goals of persons.

New ideas arose throughout this work, as the possibility to find leader that help the robot in portions of its path, which would required a more refined technique of leader selection, with the robot alternating between aided and unaided navigation.

The next step is to implement a tracking system onboard the robot, with sensors as a LIDAR and a Kinect camera. This will allow a better understanding of humans reactions and behavior when interacting with a robot, as well as the validation of the algorithms without the aid of external devices.

  This research has been funded by the INRIA PAL Project and by Fundac ¸ão para a Ciência e a Tecnologia SFRH/BD/46604/2008.

Fig. 1 .

 1 Fig. 1. Comparison of goal prediction using simple extrapolation and the actual goals of two moving agents

Fig. 2 .Fig. 3 .

 23 Fig. 2. GHMM learning algorithm overview (adapted from [5])

7 :

 7 goalP red ← GHM M (agents) for i = 1 → agents.size() do 8: d ← Distance(goal, goalP red[i])

Fig. 5 .

 5 Fig. 5. INRIA Rhône Alpes entrance hall

Fig. 7 .

 7 Fig. 7. Real data used in the GHMM initial training

Fig. 8 .

 8 Fig. 8. Results of a typical test of leader detection and following

ACKNOWLEDGMENT

We thank Dizan Vazques, Jorge Rios-Martinez and Arturo Escobedo for useful insights and discussions.


Dizan Vasquez

Proc Pio Stein

Jorge Rios-Martinez

Arturo Escobedo

Anne Spalanzani

Christian Laugier

Human Aware Navigation for Assistive Robotics

Ensuring proper living conditions for an ever growing number of elderly people is a significative challenge for many countries. The difficulty and cost of hiring and training specialized personnel has fostered research in assistive robotics as a viable alternative. In this context, an ideally suited and very relevant application is to transport people with reduced mobility. This may involve either autonomous or semiautonomous transportation devices such as cars and wheelchairs. For a working solution, a number of problems including safety, usability and economic feasibility have to be solved. This paper presents PAL s robotic wheelchair, an experimental platform to study and provide solutions to many of the aforementioned problems.

Motivation, problem statement and related work

Ensuring proper living conditions for an ever growing number of elderly people is a significative challenge for many countries. The difficulty and cost of hiring and training specialized personnel has fostered research in assistive robotics as a viable alternative. In this context, an ideally suited and very relevant application is to transport people with reduced mobility. In particular, this paper studies the case of a robotic wheelchair. For such a system, it is crucial to take into account the actual needs and characteristics of both its users and the people around them. The platform discussed in this paper has been designed around the following requirements: Safety: The system should avoid collisions with both static and dynamic entities.

Usability: People with motor disabilities often have problems using joysticks and other standard control devices. The system should account for this, for example by favoring the most reasonable actions when presented with an ambiguous command.

Comfort: Strong accelerations can be untolerable and even dangerous for a wheelchair user, this imposes an additional constraint on how the robot may move.

Respect of social conventions: When moving, a robot may considerably disturb people around it, especially when its behavior is perceived as unsocial. Even worse, the wheelchair s passenger may be held responsible for that behavior. It is thus important to produce socially acceptable motion. From the technical standpoint these requirements imply that, in addition to the conventional robot tasks (e.g. localization, path execution) the following points should be specifically addressed:

Integrated motion-planning and long-term motion prediction: Most human-populated environments are highly dynamic, requiring considerable look-ahead about how other objects will move in order to ensure collision-free robot motion under comfortable accelerations. This motivates the proposed integration of a long-term motion prediction algorithm based on the idea of typical behavior with a riskbased motion planning algorithm.

Interaction detection for socially acceptable robot-motion: Our approach is based on the simple idea that, when people interact, they often adopt spatial formations implicitly forming interaction zones . Thus, socially acceptable motion can be enforced by first detecting interaction zones and then computing the risk to invade them. One of our main ambitions with this platform is to provide an open benchmark that could be used to compare and evaluate different approaches. This is an important task given the large diversity of existing wheelchairs [START_REF] Simpson | Smart wheelchairs: A literature review[END_REF], including autonomous [START_REF] Kollar | Grounding Verbs of Motion in Natural Language Commands to Robots[END_REF], semi-autonomous [START_REF] Parikh | Usability study of a control framework for an intelligent wheelchair[END_REF] and social aware systems [START_REF] Kirby | Companion: A constraintoptimizing method for person acceptable navigation[END_REF], [START_REF] Rios-Martinez | Understanding human interaction for probabilistic autonomous navigation using Risk-RRT approach[END_REF].

Technical Approach

Figure 1 presents an overview of our system s architecture. It is divided into several subsystems:

1. Tracking subsystem: mobile objects are tracked both off-board and on-board the robotic wheelchair. 2. Prediction subsystem: the prediction subsystem processes data from the trackers and transforms it into probabilistic predictions about the configuration of the free space in the environment. It also features a social filter , which detects present and future interactions and creates virtual obstacles corresponding to interaction zones. 3. Navigation subsystem: the navigation subsystem includes a laserbased localization module and a motion-planner which integrate predictions to compute safe trajectories that are fed to the execution module.

Tracking systems

The off-board tracker provides global information about moving obstacles and provides learning input for our motion prediction module. At this point, we are still developing and testing our tracking systems. Meanwhile, we have performed several tests using augmented reality markers that people wear as hats. This has allowed us to validate the overall architecture, even if it is not a viable solution in the long run.

For the definitive version of the platform, we are working on a basic detect-then-track system, where moving objects are first detected using a Self-organizing network [START_REF] Vasquez | A novel self organizing network to perform fast moving object extraction from video streams[END_REF], after this, objects are encoded as a color histogram, and then detected in later frames using the mean-shift algorithm [START_REF] Comaniciu | Mean shift: A robust approach toward feature space analysis[END_REF]. Finally, the different detections are used as input for a tracker based on the Joint Probabilistic data Association Filter.

On the other hand, the on-board system will provide detailed information about the objects that appear in the robot s perceptual field. Its main use is to identify interactions between people (e.g. two persons shaking hands). The on-board tracking performs leg detection using a LIDAR sensor and people detection using the kinect sensor, according to the technique described in [START_REF] Loong | People detection using the Microsoft Kinect[END_REF].

Motion prediction

The motion prediction subsystem takes tracking data (i.e. position, orientation and velocity) and outputs K grids, representing the posterior probability of the space being occupied at times {t 1 , • • • ,t K } in the future. Prediction itself is accomplished with a Growing Hidden Markov Model [START_REF] Vasquez | Growing hidden markov models: a tool for incremental learning and prediction of motion[END_REF] and an Extended Kalman Filter but the grid representation makes it easy to experiment with other prediction algorithms. The prediction grids are then processed by a fusion module, which currently performs bayesian sensor fusion as described in [START_REF] Moravec | Sensor fusion in certainty grids for mobile robots[END_REF].

In order to produce socially acceptable motion, we have proposed the Social Filter , which integrates constraints inspired by social conventions in order to evaluate the risk of disturbance represented by navigation decisions. We focus on detecting and predicting conversations in the environment surrounding the wheelchair [START_REF] Rios-Martinez | Understanding human interaction for probabilistic autonomous navigation using Risk-RRT approach[END_REF].

Navigation

Our navigation system is based on Risk-RRT [START_REF] Fulgenzi | Probabilistic motion planning among moving obstacles following typical motion patterns[END_REF], a partial motion planner which integrates motion predictions to provide safe trajectories. We have also extended the approach by including a mechanism to obtain socially acceptable behavior. When the wheelchair is transporting a human, it will have to move in a populated environment where an optimal behavior may be perceived as unsocial. People will become uncomfortable if they are approached at a distance that is deemed to be too close, where the level of discomfort experienced by the person is related to the importance of his or her space. This simple idea was formalized introducing the concept of personal space, first proposed by Hall [START_REF] Hall | The hidden Dimension: Man s Use of Space in Public and Private[END_REF], which characterizes the space around a human being in terms of comfort to social activity. Another interesting social situation arises when two or more of the persons in the environment are interacting. We model interactions using the concept of o-space which has been developed by sociologists [START_REF] Kendon | Spacing and orientation in co-present interaction[END_REF]. This space can be observed in casual conversations among people where participants position and orientation are used to establish boundaries of the space. This space is respected by other people and only participants are allowed to access to it, therefore the intrusion of a stranger causes discomfort. In our path planner, human friendly paths are generated by including a Social Filter which transforms those spaces into corresponding cost functions which lead the robot to avoid them. As a result, the choice of a best path done by RiskRRT is based on the probability of success calculated for every partial path considering the probability of not encountering a collision along the path and not entering in a personal space or an o-space [START_REF] Rios-Martinez | Understanding human interaction for probabilistic autonomous navigation using Risk-RRT approach[END_REF].

Modeling Personal Space

We have modeled personal space as a mixture of two gaussians human centered, one for the front and one for the back of the space, the front is larger as people is more sensitive to this space. Fig. 2 shows an example of personal space as provided by the Social Filter. Modeling o-Space When more than two people are in conversation, they tend to make a formation with circular shape. The o-space could be taken as a circle whose center coincides with that of the inner space. For the specific case of two people, some formations, called F-formations, have been identified as being particularly frequent [START_REF] Kendon | Spacing and orientation in co-present interaction[END_REF]. The social filter identifies individual F-formations (Vis-a-vis, L-Shape, C-Shape or V-Shape) and builds the corresponding o-space. in Fig. 3, the calculated o-space for a Vis-a-Vis interaction is shown.

Experimental Results

It is important to highlight that the proposed experimental platform is an ongoing effort. Thus, the results described below should be considered preliminary. We have conducted experiments both in simulation and with the real platform as described in § 3.1 and 3.2, respectively. Before going into the details of our results, it is convenient to discuss the graphical elements we will use in our figures. In our tests, humans are represented by a 3D model of a man or woman (4a), red points are used to represent the personal space that should be avoided by the robot. Finally, colored squares in front of the human represent a simple estimation of future positions, with each color representing a different moment in time. The wheelchair (Fig. 4(b) is represented by a 3D model of a wheelchair surrounded by rounded points that represent explored RiskRRT nodes. As in the case of people, different colors are associated with different moments in time. The size of the points represents the computed risk of navigation to that position, where larger points mean bigger risks. Finally, a red solid line is used to represent the path to be followed, with a blue arrow indicating the robot s goal.

Simulation

Test scenarios

The tests focused on two main functions: predictive navigation and socially acceptable navigation. In the first case, people interfered with the robot s plans by either following the same path than the robot in the opposite direction or intersecting it at some point. In both cases the robot had to anticipate the human trajectories and generate an alternative collision-free plan. In the second case, we aimed to assess the capability of the robot to avoid disturbing or causing discomfort to persons that were not moving but were interacting with each other. People were arranged in a manner that the direct path to the robot s goal would be inside a social interaction zone, so a straight movement to the goal would violate the interaction zone and therefore, the robot had to find alternative paths.

Prediction and Navigation

We have conducted extensive tests of the RiskRRT algorithm in simulation. Fig. 5 shows one iteration of the navigation main loop. As it can be seen, the resulting trajectory differs from optimal trajectories obtained by traditional planning algorithms, the robot actually opts for a larger trajectory that avoids obstructing the moving pedestrians. In all our simulations the speed of pedestrians has been fixed to one m/s and maximum speed of our wheelchair is also one m/s. We have performed a number of tests to assess the effect of including prediction in our motion planning algorithm. Fig. 6 compares the paths that were obtained using predictions of pedestrian movements (left column) with those obtained without predictions (right column). The robot s initial position is on the left end of the corridor while the goal is at right end. Since the corridor is narrow, the only way to avoid colliding or disturbing the pedestrian is by moving aside in the corridor opening before continuing to the goal. In the figure, it is possible to see how, by using predictions, the wheelchair is capable to detect a possible collision in the middle of the corridor (6 a)) and to choose an alternative path to reach the goal. Without prediction it takes a straight path to reach the goal Fig. 5. Predictive navigation example. RiskRRT selected a plan (red line) to the goal (blue arrow). The chosen path leads the robot to pass by the back of the first person, and then reduces the speed to let the second person to pass as well. With this strategy, the robot minimizes the risk of collision and the discomfort caused for the two pedestrians.

Once second person has passed, the algorithm choses a straighter path to the goal. Frames at the right of the figure show that estimated risk is bigger at future positions of the wheelchair (circles) which are close to predicted positions of pedestrians (squares). which, at first does not seem to pose any risk (6 b)) later, when the wheelchair detects the collision (6 d)) and tries to avoid the person, it is already too late.

Socially Acceptable Navigation

In order to test socially acceptable behavior, we conducted several simulation tests. Our first test scenario consisted of two interacting people, together with the wheelchair. We realized thirty executions of the planner in very similar conditions, as it can be seen in Fig. 7, when the social filter is off, the plans do avoid people but do not respect social space. When the social filter is turned on again, all the plans managed to respect interaction space without disturbing the involved people.

Real platform

Experimental platform Our mobile platform (Fig. 8(b)) is a robotic wheelchair manufactured by BlueBotics for the European project MOVE-MENT. It is built on a mobile base equipped with a SICK LMS-200 LIDAR, and a Microsoft Kinect RGBD camera. The wheelchair is also equipped with an on-board computer to take care of the low-level hardware control tasks, on top of that it also carries a notebook computer with the navigation, prediction and tracking software. In addition to the mobile platform, there is also an external camera (Fig. 8 nal computer that communicates with the wheelchair via wireless network.

From the software perspective, the system has been implemented as a number of independent modules using the Robot Operating System (ROS) [START_REF] Quigley | ROS: an open-source robot operating system[END_REF].

Motion Prediction

The proposed prediction algorithms has been extensively validated and compared about other state of the art techniques [START_REF] Vasquez | Growing hidden markov models: a tool for incremental learning and prediction of motion[END_REF]. Our approach consistently yields comparable predictions with much smaller models and is able to update its knowledge as new motion patterns are observed.

To validate the results obtained with our predictor, the scenario chosen to conduct the experiments is the main hall of INRIA Rhône Alpes (Fig. 9(a). It is an interesting choice as it has a large flow of people during different times of the day, entering and leaving the building during lunch hours and at the beginning and the end of a working day. These conditions provide a realistic and challenging place to conduct experiments on dynamic environments. The GHMM has been trained using a set of 190 real trajectories. Volunteers were asked to move naturally among interest points in the environment, as the entrance of the hall, the two corridors and the two doors. Fig. 9(b) shows a sample of these trajectories, where the tree interest points located at the stairs illustrates the three separate paths that can be taken when climbing it. A great advantage of the GHMM is it capability to automatically create, remove and merge redundant states while learning, which result in a more efficient training compared to classical HMM. Fig. 10 illustrates the learned states (represented by spheres) along the INRIA s hall.

Socially acceptable navigation

Test were conducted in the INRIA hall, linking together the tracking, social filters and navigation modules, previously presented. The tracking module fed information to the social filter module which computed social interaction zones, according to the orientation and position of humans in the scene. Several tests were conducted to evaluate the capability of the robot to avoid zones that would cause discomfort to the people interacting with each other. We also compared results with and without the social filter module, to demonstrate that not taking into account the zones of social interaction would result in paths that are shorter but rude or even frightening.

Fig. 12 shows the two experiments that were performed. The image shows roughly the same initial configuration for the robot and the interacting persons, as well as the same goal. The only difference is that, in the left column the social filter has been disabled while in the right one it is active, which is illustrated by the point cloud between persons.

Due to the absence of a social space, in the left column images, the planning algorithm treats the humans are simple obstacles, and the chosen path is the one that moves straight to the goal. However, when the social filter is active, nodes that are generated inside the interaction zone are penalized with a high risk, and then are excluded during the path search.

This example clearly shows that although a straight path to the goal can be considered to be more efficient in terms of energy and total distance that was traveled, it moves in such a way that it causes discomfort to interacting groups of people in the environment. On the other hand, the example shown in the right column, manages to avoid the zone of interaction, at the cost of traveling a longer distance.

Conclusions and future work

As we have mentioned above, the platform presented in this paper should be considered work in progress. Nevertheless, we consider that the results we have obtained until now are both relevant and promising and had been instructive in relation to several aspects of the problem at the application and the technical level: Socially acceptable behavior is very important. Even in our scripted tests, both interacting people and the wheelchair s user reported that they felt very uncomfortable when the robot passed right through the middle of a talking group.

Predictive behavior leads to socially acceptable behavior. For example, when pedestrians were passing through the robot s path, it often happened that it stopped (knowing that the path was going to be free) to let the person pass. This seems to indicate that in many cases, knowing how people will move, the most reasonable thing to do is to be polite. It also suggests game theory as a possible way to analyze these interactions. On the other hand, there are several open fundamental issues that need to be addressed, in particular, the problem of defining proper ways of evaluating comfort and social compliance has not been tackled here. The reason lies in the difficulty to put together experiments which really factor out all those variables that are not being studied. For example, during our experiments, we were applying questionnaires to the wheelchair passenger with very inconclusive results because the environment contained a flight of stairs going down. The result was that people were too frightened about the wheelchair falling there to be able to consider social discomfort.

As future work we plan to have the help of sociologists to aid in the formulation of questionnaires that can better capture the variables we want to study, as the comfort, for example. We also noticed that the reduced size of the useful space of our test environment (approximately 70m 2 ) posed limitations to the variety of tests that we could perform. So future tests will be conducted in a larger and safer (without stairs) environment, with a larger number of humans and more free space for the robot to maneuver, so we can better explore the limitations and advantages of our techniques.

Fig. 1 .

 1 Fig. 1. Achitecture overview.

Fig. 2 .

 2 Fig. 2. Personal space calculated by Social Filter Module. Height of the gaussian means Risk of disturbance then maximum disturbance is located at human position.

Fig. 3 .

 3 Fig. 3. O-space calculated by Social Filter Module for a Vis-a-Vis F-formation. Maximum risk of disturbance is located at o-space center, in the picture the disturbance is represented by height of Gaussian.

Fig. 4 .

 4 Fig. 4. (a) Human visualization and symbols meaning; (b) Robot visualization and symbols meaning

Fig. 6 .

 6 Fig.6. Qualitative comparison of predictive navigation (first column) vs non predictive navigation (second column). Prediction helps to discover future high-risk states (a) and anticipate avoidance paths to finally reach the goal (g). Without prediction avoidance begins too late (f) and a collision is unavoidable (h).

Fig. 7 .

 7 Fig. 7. Socially acceptable navigation. Each figure shows a sample of generated plans (in red) for thirthy executions of RiskRRT: a) without social filter social spaces are not respected, b)and c) with social filter, navigation is socially acceptable. In c) people are looking towards walls, therefore there is no social interacting zone, then navigation respects only their personal spaces.

Fig. 8 .

 8 Fig. 8. Experimental platform.

Fig. 9 .

 9 Fig. 9. (a) INRIA Rhône Alpes entrance hall. (b) Real trajectories used in the GHMM training.

Fig. 10 .

 10 Fig. 10. GHMM learned states (represented by connected nodes) and the prediction of a goal for a person beginning to move from the left door (represented by larger nodes at the left portion of the stairs.

Fig. 11 (Fig. 11 .

 1111 Fig.11(a) shows one image of two persons interacting while the robot passes by, with a researcher closely following. Fig.11(b)shows the same situation but taken from the overhanging camera linked to the tracker computer, where the robot position, its plan and intended destination can be seen.

Fig. 12 .

 12 Fig. 12. The robot is represented by a rectangle, the goal by the leftmost arrow, and interacting people by black circles. Images (a,c,e) show the social filter module deactivated, the resulting trajectory is shorter but socially unacceptable; (b,d,f) images shows a trajectory that is longer but respects the social interaction zones displayed as clouds of blue points.

* Proc pio Stein and Arturo Escobedo are funded by the INRIA large initiative scale called PAL (Proc pio Stein is also funded by FCT SFRH/BD/46604/2008 and personnaly thanks his Thesis supervisor Prof. V tor Santos. Jorge Rios-Martinez is also funded by CONACYT 250140/308006. Dizan Vasquez was funded by UPMF as invited Professor.


Bianca Laís Zimmermann

Maurício Pereira

Didier Bouchon

Paula Beatriz Araujo

DETECTION OF WOLBACHIA (ALPHAPROTEOBACTERIA: RICKETTSIALES) IN THREE SPECIES OF TERRESTRIAL ISOPODS (CRUSTACEA: ISOPODA: ONISCIDEA) IN BRAZIL

Keywords: Wolbachia, terrestrial isopods, 16S rDNA, Brazil. Wolbachia are Alphaproteobacteria that infect a wide

Terrestrial isopods are widely infected with Wolbachia. However, little is known about the presence of bacteria in the Neotropical species. The objective of this study was to test the hypothesis of presence of Wolbachia infection in the native species of terrestrial isopods, Atlantoscia floridana and Circoniscus bezzii, and in the introduced species Burmoniscus meeusei.

variety of arthropods and nematodes [START_REF] Werren | Wolbachia: master manipulators of invertebrate biology[END_REF]. These bacteria use different strategies of symbiosis in their hosts, acting as reproductive parasites in arthropods and as mutualists in nematodes [START_REF] Bordenstein | Parasitism and mutualism in Wolbachia: what the phylogenomic trees can and cannot say[END_REF]. Wolbachia has attracted considerable interest, not only because of its pandemic nature [START_REF] Hilgenboecker | How many species are infected with Wolbachia? a statistical analysis of current data[END_REF], but also because of the reproductive phenotypes observed as a consequence of its reproductive parasitism [START_REF] Werren | Wolbachia: master manipulators of invertebrate biology[END_REF]. Moreover, the potential of Wolbachia as a biocontrol agent has been explored in recent years, with studies that suggest their use in controlling pests and disease vectors [START_REF] Bian | The Endosymbiotic Bacterium Wolbachia Induces Resistance to Dengue Virus in Aedes aegypti[END_REF][START_REF] Bourtzis | Wolbachia-based technologies for insect pest population control[END_REF][START_REF] Moreira | A Wolbachia symbiont in Aedes aegypti limits infection with dengue, chikungunya, and Plasmodium[END_REF].

Terrestrial isopods are important representatives of the soil fauna, because they take part in soil formation and also in nutrient recycling, in addition to being a food source for a variety of animals [START_REF] Sunderland | A serological study of arthropod predation on woodlice in a dune grassland ecosystem[END_REF][START_REF] Van Sluys | Diet, reproduction and density of the Leptodactylid litter frog Zachaenus parvulus in a atlantic of southeastern Brazil[END_REF][START_REF] Vitt | Comparative ecology of sympatric Gonatodes (Squamata: Gekkonidae) in the western Amazon of Brazil[END_REF]. This group has developed structural, physiological and behavioral characteristics in order to become fully independent of the aquatic medium for reproduction, which has enabled them to occupy a variety of environments, from the coastal zone to deserts [START_REF] Schmalfuss | World catalog of terrestrial isopods (Isopoda, Oniscidea)[END_REF].

Terrestrial isopods are widely infected with Wolbachia; however, the majority of studies of these associations have been conducted in Europe [START_REF] Bouchon | Feminizing Wolbachia and the evolution of sex determination in isopods[END_REF]. The first molecular identification of Wolbachia was in 1992, in populations of Armadillidium vulgare and Porcellio dilatatus from France [START_REF] Rousset | Wolbachia endosymbionts responsible for various alterations of sexuality in arthropods[END_REF]. The presence of the bacterium was detected in Chaetophiloscia elongata and Porcellionides pruinosus, also in France, in 1994 [START_REF] Juchault | New evidence for feminizing bacteria in terrestrial isopods evolutionary implications[END_REF]. Later, Wolbachia was found in more than 14 European species of terrestrial isopods [START_REF] Bouchon | Evidence for widespread Wolbachia infection in isopod crustaceans: molecular identification and host feminization[END_REF] and in Hyloniscus riparius, Trachelipus rathkii and T. ratzeburgii in Hungary [START_REF] Nyirõ | Detection of Wolbachia pipientis infection in arthropods in Hungary[END_REF]. More recently, the infection was detected in 11 species from Tunisia (4) and in two species of Philoscia sp. occurring in Thailand [START_REF] Wiwatanaratanabutr | Molecular phylogeny of Wolbachia strains in arthropod hosts Based on groE-homologous gene sequences[END_REF]. Little is known about the presence of bacteria in terrestrial isopods in Brazil, which has a rich isopod fauna of more than 120 species [START_REF] Schmalfuss | World catalog of terrestrial isopods (Isopoda, Oniscidea)[END_REF].

  The terrestrial isopods were dissected according to the methodology proposed by Bouchon et al.[START_REF] Bouchon | Evidence for widespread Wolbachia infection in isopod crustaceans: molecular identification and host feminization[END_REF]. The DNA extractions were performed from reproductive tissue (ovaries of females and utricles of males), part of the nerve cord, and the muscle at the base of the pereiopods, using the Chelex (Bio-Rad) protocol. The PCR assays to detect the presence of Wolbachia were performed under conditions adapted from Bouchon et al.[START_REF] Bouchon | Evidence for widespread Wolbachia infection in isopod crustaceans: molecular identification and host feminization[END_REF], targeting the 16S rDNA gene[START_REF] O'neill | 16S rDNA phylogenetic analysis of the bacterial endosymbionts associated with cytoplasmic incompatibility in insects[END_REF]. The use of this gene is due to the fact that it has proven to be the most efficient to detect Wolbachia in Neotropical terrestrial isopods (data not shown). Part of 16S rDNA gene was amplified using the Wolbachia specific primers 99F 5'-TTG TAG CCT GCT ATG GTA TAA CT -3' and 994R 5' -GAA TAG GTA TGA TTT TCA TGT -3', which produced fragments of approximately 900 bp[START_REF] O'neill | 16S rDNA phylogenetic analysis of the bacterial endosymbionts associated with cytoplasmic incompatibility in insects[END_REF].The PCRs were carried out in volumes of 25 µl, using 1.0 µl of DNA, 0.16 µl of Platinum® Taq (5 U/µl) (Invitrogen), 2.5 µl of 10X buffer (Invitrogen), 1.6 µl MgCl 2 (50 mM) (Invitrogen), 0.5 µl of forward primer (20 µM), 0.5 µl of reverse primer (20 µM), 0.5 µl of dNTPs (10 mM) (Invitrogen) and 18.18 µl of ultrapure water. The amplifications were carried out under the following conditions: 35 cycles (1 min at 95°C, 1 min at 50.6°C, 1 min at 72°C), including an initial denaturation step of 95°C for 2 min and a final extension step of 72°C for 5 min. As a positive control for the PCR reaction, DNA extracted from an individual of the terrestrial isopod Balloniscus glaber was used, in which infection by Wolbachia was previously detected (unpublished data). PCRs were confirmed by electrophoresis in 1% agarose gels. Possible failures in the amplifications with the 16S rDNA primers could occur for the following reasons: (i) absence of Wolbachia; (ii) a flaw in the DNA extraction process; and/or (iii) an incorrect concentration of DNA solution[START_REF] Werren | Distribution of Wolbachia among neotropical arthropods[END_REF]. In order to control the last two possibilities, we tested samples assumed to be negative, with primers of subunit I of the Cytochrome Oxidase mitochondrial gene (COI)[START_REF] Folmer | DNA primers for amplification of mitochondrial cytochrome c oxidase subunit I from diverse metazoan invertebrates[END_REF]. Samples that generated a product of the expected size were considered to be truly negative for the presence of Wolbachia. The amplified DNA fragments of positive samples were sent to the company MACROGEN Advancing through Genomics for purification and sequencing. This company uses the BigDye™ Terminator protocol, and sequencing was conducted on a 3730xl DNA analyzer. The resulted sequences were compared by the Blastn algorithm (http://blast.ncbi.nlm.nih.gov/Blast.cgi) with sequences deposited in the GenBank database. All sequences were subsequently submitted in the Genbank-EMBL database (http://www.ncbi.nlm.nih.gov/) under accession numbers: JF799948, JF799949, JF799950 and JF799951. Alignment of sequences was performed using the BioEdit program (12). The Wolbachia strain names were based on the nomenclature system proposed by Zhou et al. (29) and specified by Charlat et al. (10). Each strain's name is defined by w (in italics) denoting Wolbachia. This is followed by three letters coming Zimmermann, B.L. e t a l . Detection of Wolbachia from the first three letters of the species name. Multiple strains present in a given species are distinguished by numbers added at the end. Positive samples were detected in the three species A. floridana, B. meeusei and C. bezzii, representing the first record of Wolbachia infection in these species. The infection was observed in 30 individuals: 25 females of A. floridana, 2 females of B. meeusei and 3 females of C. bezzii (Table 1). A greater number of individuals of A. floridana were tested because this species usually occurs in abundance in nature (1), which facilitates their collection. However, B. meeusei and C. bezzi are difficult to collect. In addition, this is the first record of the presence of B. meeusei in the state of Rio Grande do Sul; until now, this species has been known only from Santa Catarina. A single 16S rDNA sequence from Wolbachia was identified for A. floridana (wFlo) and B. meeusei (wMee). For C. bezzii, two very different 16S rDNA sequences (wBez1 and wBez2) were found in two different individuals (Figure 1). Thus, multiple infections were not detected. Natural multiple infections in a single host have never been demonstrated in terrestrial isopods species (24), and this work supports this statement. This study reports one of the first records of Wolbachia infection in species of terrestrial isopods in Brazil, in particular in the native species A. floridana and C. bezzii and the introduced species B. meeusei. Although these bacteria are widely studied, very few investigations of their interactions with terrestrial isopods and other organisms have been carried out in the Neotropical region. It is hoped that further studies will be undertaken to expand knowledge of the Wolbachia bacteria and their Neotropical hosts.

Figure 1 .

 1 Figure 1. Alignment of Wolbachia 16S rDNA sequences found in A. floridana (wFlo), B. meeusei (wMee) and C. bezzii (wBez1 and wBez2).

Corresponding Author. Mailing address: Avenida

	Zimmermann, B.L. e t a l .	Detection of Wolbachia
	The objective of the present study was to test the
	Bento Gonçalves, nº 9500, Bairro Agronomia, Porto Alegre, RS, Brasil. Cep.: 91501-970.; Tel.: (+5551)
	3308-7698 Fax: (+5551) 3308-7696.; E-mail: bia.lais@gmail.com

*hypothesis of presence of Wolbachia infection in the native species Atlantoscia floridana and Circoniscus bezzii, and in the introduced species Burmoniscus meeusei. Atlantoscia floridana occurs in the United States, Ascension Island and St. Helena, and from northern Brazil to La Plata in Argentina (2). It is a generalist species in terms of habitat (19), occurring in diverse environments, often in abundance (1, 3). Circoniscus bezzii is a little-studied species that occurs in Brazil (in the states of Minas Gerais and Pará) and Paraguay (15). Burmoniscus meeusei is an introduced species from Asia, with records in England, Hawaii, Brazil and Taiwan (21). The specimens of A. floridana and B. meeusei examined were collected in Porto Alegre in Rio Grande do Sul, and the individuals of C. bezzii were collected in the municipality of Presidente Olegário in Minas Gerais. The specimens were collected by hand, fixed in absolute ethanol, and transported to the Carcinology Laboratory at Federal University of Rio Grande do Sul, where they were stored in a freezer at -20°C for subsequent DNA extraction.

Table 1 .

 1 Total of individuals of each species tested for the presence of Wolbachia. FT: females tested; MT: males tested; FI: females infected; MI: males infected; RS: Rio Grande do Sul; MG: Minas Gerais.

	Species	FT MT FI MI	Locality	Geographical Coordinates
	Atlantoscia floridana	45	3	25	0	Porto Alegre/RS	30°04'76''S/51°07'28''W
	Burmoniscus meeusei	2	0	2	0	Porto Alegre/RS	30°04'49''S/51°07'31''W
	Circoniscus bezzii	7	0	3	0	Presidente Olegário/MG	18°24'02''S/46°25'50''W

ACKNOWLEDGEMENTS

To CAPES for the doctoral fellowship for BLZ, and to CNPq for financial support (Projects Number: 479412/2008-1 and 472381/2009-1) and for the research productivity grant to PBA.


Stéphan Clémençon

Hector De Arazoza

Fabrice Rossi

Viet-Chi Tran

Hierarchical clustering for graph visualization

This paper describes a graph visualization methodology based on hierarchical maximal modularity clustering, with interactive and significant coarsening and refining possibilities. An application of this method to HIV epidemic analysis in Cuba is outlined.

Introduction

Large graphs and networks are natural mathematical models of interacting objects such as persons in social networks, articles in citation networks, etc. [START_REF] Newman | The structure and function of complex networks[END_REF]. Unfortunately, the sizes of real networks strongly limit visual exploratory analysis of their properties. Indeed, despite the numerous graph visualization methods available [START_REF] Di Battista | Graph Drawing: Algorithms for the Visualization of Graphs[END_REF][START_REF] Herman | Graph visualization and navigation in information visualisation[END_REF], displaying a graph with hundreds of vertices or more in a meaningful way remains difficult. It is therefore common to rely on simplification techniques to draw a summary of a complex graph: in general, a graph clustering algorithm is used to identify clusters of nodes and the graph induced by the clustering is drawn [START_REF] Eades | Multilevel visualization of clustered graphs[END_REF]. When the clustering is hierarchical, the full graph can be represented using the structure imposed by the hierarchy: the general layout is given by the higher level of the hierarchy in which the graph is strongly simplified, then details are added in a top down way by descending the hierarchy (see e.g., [START_REF] Bourqui | How to draw clustered weighted graphs using a multilevel force-directed graph drawing algorithm[END_REF] for a recent algorithm of this type).

Those approaches generally consider the (hierarchical) clustering of the graph nodes to be obtained via one of the numerous graph clustering methods available [START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Schaeffer | Graph clustering[END_REF]. In addition, the significance of the hierarchical clustering is generally not questioned, while a bad clustering could lead to serious interpretation errors. We propose in this paper a methodology that addresses those two aspects.

Clustered graph construction

This section described the proposed methodology which consists in building a hierarchical graph clustering with guaranteed significance at each level, using maximal modularity clustering as a building block.

Maximal modularity clustering

As show in recent surveys [START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Schaeffer | Graph clustering[END_REF], dozens of graph clustering methods have been proposed. However, as pointed out in e.g. [START_REF] Rossi | Optimizing an organized modularity measure for topographic graph clustering: a deterministic annealing approach[END_REF], not all of them are adapted to graph visualization. In seems indeed important to obtain clusters of nodes with a high density of internal connections and a low number of external connections, i.e., to find what is frequently called communities. Among the corresponding clustering methods, the ones that maximize the modularity of the obtained partition seem the more adapted: modularity maximization has been shown to produce interesting partitions in many applications [START_REF] Fortunato | Community detection in graphs[END_REF] and maximizing the modularity is equivalent [START_REF] Noack | Modularity clustering is force-directed layout[END_REF], to some extend, to optimizing the energy models used in many graph visualization method, such as the standard Fruchterman Reingold algorithm [START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF].

While maximizing the modularity is a NP hard problem, high quality suboptimal solutions can be obtained efficiently, for instance using deterministic annealing [START_REF] Rossi | Optimizing an organized modularity measure for topographic graph clustering: a deterministic annealing approach[END_REF] or greedy methods such as [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF]. Those latter methods have reasonable computational complexities, proportional to the number of edges in the graph multiply by the number of nodes: the implementation proposed in [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF] can cluster a graph with 75 000 nodes and 120 000 edges in less than 2 minutes on standard PC hardware.

Clustering Significance

While modularity is normalized and takes values between -1 and 1, it is a priori difficult to tell whether a given value corresponds to an actual significant partition of the graph or is just a manifestation of random fluctuation. Indeed modularity maximization algorithms will generally discover some partition in a random graph with no cluster structure. As clustered graph visualization strongly relies on the hierarchical partitioning scheme, only significant partitions should be considered. This could be done with the help of theoretical results from [START_REF] Reichardt | Partitioning and modularity of graphs with arbitrary degree distribution[END_REF]. Indeed, the authors compute the expected maximal modularity of random graphs with arbitrary degree distribution. Given a graph, one can apply those results to its empirical degree distribution to get a threshold value for the modularity; then if a clustering has a larger modularity, it is assumed to be significant, i.e., to represent a real structure in the graph.

This approach suffers from two drawbacks. Results from [START_REF] Reichardt | Partitioning and modularity of graphs with arbitrary degree distribution[END_REF] are only asymptotically valid in the limit of large and dense graphs. In addition, only the expected value is given, not the fluctuations around this value (e.g., the variance). We propose therefore to rely on a simpler monte carlo strategy. We built random graphs with no structure that have exactly the same degree distribution as the one of the graph under study (this is the configuration model random graph, see e.g., [START_REF] Newman | The structure and function of complex networks[END_REF]). Then we apply a maximal modularity clustering algorithm (the one from [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF]) to each of the random graph. The obtained distribution of the modularity is valid under the null hypothesis of no clustering and can be used to compute an estimate of the p-value of the modularity of the clustering obtained on the original graph. This procedure is time consuming, but current clustering methods are efficient enough to allow it for medium scale graphs for e.g. 100 random trials. We recommend to consider the clustering significant only if no random graph lead to a modularity higher than the one of the original graph, i.e., for a p-value lower than 1%. For large scale graphs, we fall back to the approximation provided in [START_REF] Reichardt | Partitioning and modularity of graphs with arbitrary degree distribution[END_REF].

Hierarchical clustering

To produce a clustered graph, we proceed as follows. We first compute a maximal modularity clustering of the full graph and assess its significance using the simulation strategy described above. If the clustering is not relevant, then no meaningful representation can be done: this is reported to the user as it means that the graph under study is better modelled as a random network without structure than via clustering.

Depending on the size of the graph and on the number of clusters produced by the clustering algorithm, more coarsening and/or more refinement might be useful. Following the general idea of clustered graph analysis, the clustering is refined on a per cluster basis: we apply the same clustering method to each of the clusters of the original graph, considered separately, that is discarding inter-cluster connections. This can be repeated recursively if needed, while keeping only significant clusterings. More precisely, two significance levels are checked. We first apply the methodology described above while considering the sub-graph in isolation. If the clustering is significant, we also test its impact when integrated in the global clustering of the graph: we make sure that, apart from the bottom level, each level of the hierarchy contains a significant clustering of the original graph.

Coarsening is done differently by applying the greedy strategy used by efficient modularity maximization algorithms, in its simplest form: cluster pairs that induce the least reduction in modularity are merged recursively as long as the modularity of the obtained clustering remains above the significance level.

Visualization

The visualization of the clustered graph is based on classical solutions, such as [START_REF] Bourqui | How to draw clustered weighted graphs using a multilevel force-directed graph drawing algorithm[END_REF], with an important difference. Indeed, efficient modularity maximization algorithms use generally greedy coarsening techniques: any merge of the clusters of the best clustering will reduce the modularity. Therefore, using the highest level of the hierarchy to guide the display of the graph is likely to induce suboptimal visualization (based on results of [START_REF] Noack | Modularity clustering is force-directed layout[END_REF]). Then we rely on the following strategy.

A variant of the Fruchterman Reingold (FR) algorithm [START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF] is used to layout the quotient graph with the best modularity: the repulsive force from a node is weighted by the size of cluster it represents, rather than being uniform. This resulting display is the original solution proposed to the user (see Figure 1 be used to encode cluster specific information, such as the internal connection density, or, as shown on Figures 1 and2, to display quantities related to the distribution of some node property inside the cluster.

Then an interactive exploration is provided. The user can request the refining of the clustering. This is done by descending in the hierarchical partition, down to the last level that provide a significant clustering. At each refinement step, the layout of the previous level is used for non refined nodes, while the FR algorithm is applied to the refined node (see Figure 1 (b)).

Coarsening is done in a similar but simpler way: the position of the node that replaces nodes merged from the previous level is obtained as the center of mass of those nodes, weighted by the size of the associated clusters (see Figure 2).

Application to the Cuban HIV-AIDS epidemic

The proposed methodology is used to explore the largest connected component of a graph of sexual contacts between patients infected by the HIV in Cuba (see [START_REF] De Arazoza | The HIV/AIDS epidemic in Cuba: description and tentative explanation of its low prevalence[END_REF] for details). The corresponding database has been obtained via the infection tracing methodology: when an individual is tested as HIV positive, she/he is asked to name her/his sexual partners in the last two years. The sexual contact is recorded for each partner already in the database. Others are contacted and proposed a diagnosis. Positive new cases are added to the database and the tracking proceeds. The database includes important information about the patients, including there sexual orientation, age at detection, etc. Up to 2006, the database contains almost 5 400 persons, among which 2 386 belong to a single connected component. Applied to the corresponding graph, classical visualization algorithms provide no insight on the epidemic.

Using [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF], we obtain a partition of the graph into 39 clusters, with a modularity of 0.85. This is significantly higher than the modularities of random graphs The possibility of refining the clustering in this case is quite limited: only 5 of the 39 clusters have a significant substructure. Nevertheless, Figure 1 (b), which shows the fully refined graph (with modularity 0.81) gives interesting insights on the underlying graph. For instance, an upper left gray cluster is split into 6 white clusters: while the best clustering of those persons lead to an atypical sexual orientation distribution, this is not the case of each sub-cluster. This directs the analyst to a detailed study of the corresponding persons: it turns out that the cluster consists mainly of bisexual male patients, who represent 76 % of the original connected component. Sub-clusters are small enough (∼ 7 patients) for bisexual male dominance to be possible by pure chance, while this is far less likely for the global cluster with 41 patients (among which 39 are bisexual males).

Coarsening can be done more aggressively on this graph: clusterings down to 8 clusters have modularity above the random level. With 11 clusters, the modularity reaches 0.81, a similar value as the maximally refined graph. While Figure 1 (a) is legible enough to allow direct analysis, the coarsening emphasizes the separation of the graph into two sparsely connected structures with mostly atypical sexual orientation distributions in the associated clusters, as shown in Figure 2 (a). Figure 2 (b) represents the Pearson's residuals of the chi square tests for the "bisexual male" sexual orientation: it clearly shows that a part of the largest connected component contains more than expected bisexual males (red nodes) while the other part contains less than expected (blue nodes). Further analysis of those data confirm the existence of a mostly homosexual/bisexual recent epidemic and of an older and more heterosexual epidemic involving women.

Conclusion

The proposed methodology leverages progress in graph clustering, especially the availability of fast modularity maximization algorithms. As shown on the Cuban infection network, the visual results lead to important insight on the graph content. Further work includes extensive comparisons to alternative methods and combination of the proposed hierarchical clustering approach with other clustered graph visualization approaches.

Fig. 1 :

 1 Fig. 1: Clustered graph visualization

Fig. 2 :

 2 Fig. 2: Coarsened clustered graph visualization

* This work was supported by the French Agency for Research under grant ANR Viroscopy (ANR-08-SYSC-016-03) and by AECID project D/030223/10


Stéphan Clémençon
email: stephan.clemencon@telecom-paristech.fr

Hector De Arazoza

Fabrice Rossi
email: fabrice.rossi@telecom-paristech.fr

Viet-Chi Tran

Visual Mining of Epidemic Networks

We show how an interactive graph visualization method based on maximal modularity clustering can be used to explore a large epidemic network. The visual representation is used to display statistical tests results that expose the relations between the propagation of HIV in a sexual contact network and the sexual orientation of the patients.

Introduction

Large graphs and networks are natural mathematical models of interacting objects such as computers on the Internet or articles in citation networks. Numerous examples can be found in the biomedical context from metabolic pathways and gene regulatory networks to neural networks [START_REF] Newman | The structure and function of complex networks[END_REF]. The present work is dedicated to one type of such biomedical network, namely epidemic networks [START_REF] Keeling | Networks and epidemic models[END_REF]: such a network models the transmission of a directly transmitted infectious disease by recording individuals and their contacts, other individuals to whom they can pass infection.

Understanding the dynamic of the transmission of diseases on real world networks can lead to major improvements in public health by enabling effective disease control thanks to better information about risky behavior, targeted vaccination campaigns, etc. While transmissions can be studied on artificial networks, e.g., some specific types of random networks [START_REF] Keeling | Networks and epidemic models[END_REF], such networks fail to exhibit all the characteristics observed in real social networks (see e.g. [START_REF] Newman | The structure and function of complex networks[END_REF]). It is therefore important to get access to and to analyze large and complex real world epidemic networks. As pointed out in [START_REF] Keeling | Networks and epidemic models[END_REF], the actual definition of the social network on which the propagation takes place is difficult, especially for airborne pathogens, as the probability of disease transmission depends strongly on the type of interaction between persons. This explains partially why sexually transmitted diseases (STD) epidemic networks have been studied more frequently than other networks [START_REF] Keeling | Networks and epidemic models[END_REF][START_REF] Liljeros | Sexual networks: implications for the transmission of sexually transmitted infections[END_REF].

We study in this paper a large HIV epidemic network that has some unique characteristics: it records almost 5400 HIV/AIDS cases in Cuba from 1986 to 2004; roughly 2400 persons fall into a single connected component of the infection network. STD networks studied in the literature are generally smaller and/or do not exhibit such a large connected component and/or contain a very small number of infected persons. For instance, the Manitoba study (in Canada, [START_REF] Wylie | Patterns of chlamydia and gonorrhea infection in sexual networks in manitoba, canada[END_REF]) covers 4544 individuals with some STD, but the largest connected component covers only 82 persons. The older Colorado Springs study [START_REF] Rothenberg | Social networks in disease transmission: The colorado springs study[END_REF] covers around 2200 persons among which 965 falls in connected component (the full network is larger but mixes sexual contacts and social ones; additionally, the sexual networks contains only a very small number of HIV positive persons).

While the large size and coverage of the studied network is promising, it has also a main negative consequence: manual analysis and direct visual exploration, as done in e.g. [START_REF] Liljeros | Sexual networks: implications for the transmission of sexually transmitted infections[END_REF], is not possible. We propose therefore to analyze the network with state-of-the-art graph visualization methods [START_REF] Clémençon | Hierarchical clustering for graph visualization[END_REF].

We first describe the epidemic network in Section 2 and give an example of the limited possibilities of macroscopic analysis on this dataset. Then Section 3 recalls briefly the visual mining technique introduced in [START_REF] Clémençon | Hierarchical clustering for graph visualization[END_REF] and shows how it leads to the discovery of two non obvious sub-networks with distinctive features.

Cuban HIV/AIDS Database

The present work studies an anonymized national dataset which lists 5389 Cuban residents with HIV/AIDS, detected between 1986 and 2004. Each patient is described by several variables including gender, sexual orientation, age at HIV/AIDS detection, etc. (see [START_REF] De Arazoza | The HIV/AIDS epidemic in Cuba: description and tentative explanation of its low prevalence[END_REF] for details.)

Data collection

The Cuban HIV/AIDS program produces this global monitoring using several sources that range from systematic testing of pregnant women and all blood donations to general practitioner testing recommendations. In addition, the program conducts an extended form of infection tracing that leads to the epidemic network studied in this work.

Indeed, each new infected patient is interviewed by health workers and invited to list his/her sexual partners from the last two years. The primary use of this approach is to discover potentially infected persons and to offer them HIV testing. An indirect result is the construction of a network of infected patients. Sexual partnerships are indeed recorded in the database for all infected persons. Additionally, a probable infection date and a transmission direction are inferred from other medical information, leading to a partially oriented infection network. While this methodology is not contact tracing stricto sensu as non infected patients are not included in the database (contrarily to e.g. [START_REF] Rothenberg | Social networks in disease transmission: The colorado springs study[END_REF]), the program records the total number of sexual partners declared for the two years period as well as a few other details, leading to an extended form of infection tracing. (see [START_REF] Keeling | Networks and epidemic models[END_REF] for differences between contact and infection tracing.)

Macroscopic analysis

The 5389 patients are linked by 4073 declared sexual relations among which 2287 are oriented by transmission direction. A significant fraction of the patients (44 %) belong to a giant connected component with 2386 members. The rest of the patients are either isolated (1627 cases) or members of very small components (the second largest connected component contains only 17 members).

As the sexual behavior has a strong influence on HIV transmission, it seems important to study the relations between the network structure and sexual orientation of the patients. In the database, female HIV/AIDS patients are all considered to be heterosexual as almost no HIV transmission between female has been confirmed [START_REF] Kwakwa | Female-to-female transmission of human immunodeficiency virus. Clinical infectious diseases: an official publication of the[END_REF]. Male patients are categorized into heterosexual man and "Man having sex with Men" (MSM); the latter being men with at least one male sexual partner identified during their interview.

The distributions of genders and of sexual orientations is given in Table 1: the giant component contains proportionally more MSM than the full population; this seems logical because of the higher probability of HIV transmission between men [START_REF] Varghese | Reducing the risk of sexual hiv transmission: Quantifying the per-act risk for hiv on the basis of choice of partner, sex act, and condom use[END_REF]. Additionally, as shown on Figure 1 detected patients changes through years (note that year 2004 is incomplete and therefore has not been included in this analysis): the percentage of heterosexual men seems to decrease. This is also the case for women, but to a lesser extent. However, the evolution of the percentage of MSM through time is difficult to analyze at a macroscopic level. For instance, multiple explanations can be offered to explain the influence of the sexual orientation of the patients on their average shortest path distances in the graph (see Table 2). One the one hand, temporal Fig. 1: Yearly sexual orientation distribution in the giant component a short time span. Then one might expect short paths between heterosexual men as they should be concentrated in the early phase of the epidemic and long chains should be rare. However, on the other hand, heterosexual men could also be linked to the network mostly through women. Then their relative short distances could be explained via the relative short distances between women themselves and the time aspect would play no role in the observed distances.

Visual Mining

Because of the size of the giant component, a direct visual analysis is impossible and the interplay between sexual orientation and infection is difficult to analyze. We show in this section how the difficulty can be circumvented by combining clustered graph visualization techniques [START_REF] Eades | Multilevel visualization of clustered graphs[END_REF] with efficient maximal modularity graph clustering [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF], as proposed in [START_REF] Clémençon | Hierarchical clustering for graph visualization[END_REF]. The methodology introduced here can be used to analyze the relation between other quantities and the infection structure.

Methodology

This section briefly explains the graph visualization method used to analyze the infection network. Details can be found in [START_REF] Clémençon | Hierarchical clustering for graph visualization[END_REF]. The classical strategy used to display a large network (e.g., with more than a hundred nodes) is to coarsen the network via a clustering method, leading to the so-called clustered graph visualization problem [START_REF] Eades | Multilevel visualization of clustered graphs[END_REF]. To implement this strategy, we use a maximal modularity graph clustering approach [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF], as maximizing the modularity leads in general to meaningful clusters [START_REF] Fortunato | Community detection in graphs[END_REF] which are additionally well adapted to visualization [START_REF] Noack | Modularity clustering is force-directed layout[END_REF]. Then rather than displaying the original network, we use the standard Fruchterman Reingold algorithm [START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF] to display the network of clusters. Figure 2 gives concrete examples of the results: in the present context, each cluster consists of a group of patients linked by sexual relationships (the size of the group is represented by the surface of the disk used in the figures). Two groups are linked in the display when there is at least one sexual partnership between patients of the two groups. The thickness of the link encodes the number of between group sexual contacts. We implemented the hierarchical principle used in [START_REF] Eades | Multilevel visualization of clustered graphs[END_REF] by providing interactive coarsening and refining of the clustering. Indeed the best clustering of the network might be too coarse to give insights on the structure of network or too fine to lead to a legible drawing. Coarsening is implemented by a greedy merging of clusters (as is used in [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF]) while refinement is obtained by applying maximal modularity clustering to each sub-cluster, taken in isolation from the rest of the network. We keep only statistically significant coarsenings and refinements: the modularity of the selected clusterings must be higher than the maximal modularity obtained on random graphs with the same degree distribution (see [START_REF] Clémençon | Hierarchical clustering for graph visualization[END_REF] for details). Figure 2 (b) gives an example of a refinement for the clustering used in Figure 2 (a), while Figure 3 is based on a coarsening of the clustering.

Results

Using [START_REF] Noack | Multi-level algorithms for modularity clustering[END_REF], we obtain a partition of the giant component into 39 clusters, with a modularity of 0.85. This is significantly higher than the modularities of random graphs with identical sizes and degree distributions: the highest value among 50 random graphs is 0.74. The corresponding layout is given by Figure 2 (a). We use this layout as a support for visualization exploration of the sexual orientation distribution: nodes are darkened according to the p value of a chi squared test conducted on the distribution of the sexual orientation of persons in each cluster versus the distribution of the same variable in the full connected component.

It appears clearly that some clusters have a specific distribution of the sexual orientation variable.

The possibilities for refining the clustering in this case are quite limited: only 5 of the 39 clusters have a significant substructure. Nevertheless, Figure 2 (b), which shows the fully refined graph (with modularity 0.81) gives interesting insights on the underlying graph. For instance, an upper left gray cluster is split into 6 white clusters: while the best clustering of those persons leads to an atypical sexual orientation distribution, this is not the case of each sub-cluster. This directs the analyst to a detailed study of the corresponding persons: it turns out that the cluster consists mainly in MSM patients. Sub-clusters are small enough (∼ 7 patients) for MSM dominance to be possible by pure chance, while this is far less likely for the global cluster with 41 patients (among which 39 are MSM). This finding directs the analyst to a sub-population study. The original 39 clusters are merged into three groups: MSM clusters (atypical clusters in the upper part of the graph which contain more MSM than expected), Mixed clusters (atypical clusters in the lower part of the graph, which contain less MSM than expected) and typical clusters. Then the geodesic analysis summarized in Table 2 This analysis shows that the two groups made of atypical clusters are far from each other compared to their internal distances. This is confirmed by the detection date analysis displayed on Figure 4. It appears that the epidemic in the giant component has two separated components. One mostly male homosexual component tends to dominate the recent cases (note that even typical clusters contain at least 57 % of MSM), while a mixed component with a large percentage of female patients was dominating the early epidemic, but tends to diminish recently. It should also be noted that this mix component is dominated by the growth of the homosexual component, but seems to decay only slightly in absolute terms. In other words, the reduction should be seen as an inability to control the growth homosexual epidemic rather than as a success in eradicating the heterosexual epidemic.

Conclusion

The proposed visual mining method for graphs has been shown to provide valuable insights on the epidemic network. It is on links between modularity and visualization and leverages recent computationally efficient modularity maximizing methods. Future works include the integration of the proposed methods in graph mining tools such as [START_REF] Bastian | Gephi: An open source software for exploring and manipulating networks[END_REF] and its validation on other aspects of epidemic networks analysis.

Fig. 2 :

 2 Fig. 2: Clustered graph visualization

Fig. 3 :

 3 Fig. 3: Coarsened clustered graph visualization

Figure 3 (

 3 b) represents the Pearson's residuals of the chi square tests for the MSM sexual orientation: it clearly shows that a part of the largest connected component contains more than expected MSM (circle nodes) while the other part contains less than expected (square nodes).

Fig. 4 :

 4 Fig. 4: Yearly distribution of the three groups of clusters

Table 1 :

 1 , the sexual orientation of the newly Gender and sexual orientation distributions in the whole network and in the giant component

		full network giant component
		absolute relative absolute	relative
	woman	1109	0.21	472	0.20
	heterosexual man	566	0.11	110	0.05
	MSM	3714	0.69	1804	0.76

Table 2 :

 2 Average shortest path distances in the giant component of the infection network, conditioned by the sexual orientation of the extremal points (the global average is 10.24) distance should be reflected by distance in the graph as the infection tracing has

	MSM heterosexual man woman
	MSM 10.30	10.83	10.24
	heterosexual man 10.83	9.87	9.30
	woman 10.24	9.30	8.76

  is done at this group level, leading to Table3.

		MSM clusters Mixed clusters Typical clusters
	MSM clusters	9.79	12.28	11.93
	Mixed clusters	12.28	7.56	9.24
	Typical clusters	11.93	9.24	12.04

Table 3 :

 3 Average geodesic distances between members of the three cluster groups. Paths are restricted to patients belonging to the groups under consideration

This work was supported by the French Agency for Research under grant ANR Viroscopy (ANR-08-SYSC-016-03) and by AECID project D/030223/10