MD Sonia Gaucher
email: sonia.gaucher@htd.aphp.fr

PhD Nathalie Duchange

MD PhD Mohamed Jarraya

Jocelyne Magne

MD Jean-Michel Rochet

MD Jean Stéphanazzi

MD Christian Hervé

MD Grégoire Moutel

Severe adult burn survivors. What information about skin allografts?

Keywords: ethics, burn, skin allograft, skin donor, organ and tissue donation, information

Background and objective: During the acute phase of a severe burn, surgery is an emergency. In this situation, human skin allografts constitute an effective temporary skin substitute. However, information about the use of human tissue can not be given to the patients because most of the allografted patients are unconscious due to their injury.

Objective: This study explored the restitution of information on skin donation to patients who have been skin allografted and who have survived their injury.

Method: A qualitative study was conducted due to the limited number of patients in ability to be interviewed according to our medical and psychological criteria.

Results and discussion: Twelve patients who had been treated between 2002 and 2008 were interviewed. Our results show that 10 of them ignored that they had received skin allografts. One of the two patients who knew that they had received allografts knew that skin had been harvested from deceased donor. All patients expressed that there is no information that should not be delivered. They also expressed their relief to have had the opportunity to discuss their case and at being informed during their interview. Their own experience impacted their view in favor of organ and tissue donation.

Introduction

Early excision and immediate grafting has been shown to be a major advance in the surgery of severe burn patients [START_REF] Ong | Meta-analysis of early excision of burns[END_REF]. In practice, using the same surgical procedure, burns are excised as soon as possible after the onset of the injury, and excised areas are covered by skin grafts. Ideal coverage is skin autografts. However, when burn injuries are both deep and extensive, autografts are not available and skin substitutes have to be utilized.

In this situation, human skin allografts, harvested from deceased or living donors, constitute an effective temporary skin substitute. It is well known that, when allografts are applied on excised burns, they limit hydro-electrolytic losses and pain through the mechanical effect on the wounds they cover; they reduce infection risk; and they improve (enhance) recipient tissue granulation by providing the factors needed for healing [START_REF] Herndon | Comparison of serial debridement and autografting and early massive excision with cadaver skin overlay in the treatment of large burns in children[END_REF][START_REF] Cuono | Composite autologous-allogenieic skin replacement: development and clinical application[END_REF][START_REF] Kreis | Historical appraisal of the use of skin allografts in the treatment of extensive full skin thickness burns at the Red Cross Hospital Burns Centre[END_REF][START_REF] See | Our clinical experience using cryopreserved cadaveric allograft for the management of severe burns[END_REF][START_REF] Vloemans | A historical appraisal of the use of cryopreserved and glycerol-preserved allograft skin in the treatment of partial thickness burn[END_REF][START_REF] Naoum | The use of homograft compared to topical antimicrobial therapy in the treatment of second-degree burns of more than 40% total body surface area[END_REF]. After grafting on burn patients, allografts are usually rejected between two and four weeks [START_REF] Burke | Early excision and prompt wound closure supplemented with immunosuppression[END_REF][START_REF] Ninnemann | Prolonged survival of human skin allografts following thermal injury[END_REF][START_REF] Koller | Skin grafting options at the burn and reconstructive surgery department of the faculty hospital in Bratislava[END_REF]. The main drawbacks of this therapeutic human tissue are the risk of disease transmission [START_REF] Clarke | HIV transmission and skin grafts[END_REF], and in France poor availability due to lack of donors and lack of harvesting.

In our practice, human skin allografts are harvested from multi-organ and tissue donors, transferred in a tissue bank where they are prepared and stored in liquid nitrogen until total assessment versus putative transmitted diseases. Then only, allografts can be delivered to burn centers to be grafted on severely burn patients. Most of the time, burned recipients are unconscious due to the circumstances of the injury or due to their sedation treatment. Their prognosis is always engaged. Our habit is to inform verbally the relatives or the person of trust on skin allografts considering that consent is not required by the law.

Literature on impact of skin allograft in burn patient and ethical issues related to this treatment is poor. Most of the studies examined the life-quality, especially due to the impact of the scars [START_REF] Patterson | The 2000 clinical research award. Describing and predicting distress and satisfaction with life for burn survivors[END_REF][START_REF] Sheridan | Long-term outcome of children surviving massive burns[END_REF][START_REF] Van Loey | Do burn patients need burn specific multidisciplinary outpatient aftercare: research resulys[END_REF][START_REF] Cromes | Predictors of quality of life as measured by the burn specific health scale in persons with major burn injury[END_REF][START_REF] Landolt | Family impact greatest: predictors of quality of life and psychological adjustement in pediatric burn survivors[END_REF][START_REF] Anzarut | Quality-of-life and outcome predictors following massive burn injury[END_REF][START_REF] Brewster | Application of rehabilitation ethics to a selected burn patient population's perspective[END_REF][START_REF] Falder | Core outcomes for adult burn survivors: a clinical overview[END_REF][START_REF] Ullrich | Pain, depression, and physical functioning following burn injury[END_REF][START_REF] Brusselaers | Burn scar assessment: a systematic review of objective scar assessments tools[END_REF].

The aim of our study is to evaluate the knowledge of massive burns survivors about being recipients of donor skin, their perception of skin donation, and the impact of their history on donation in general (organs and tissues).

Methodology Population

A list of patients who have both been admitted in the adult burn unit of the Cochin hospital during the period 2002-2008 and have received skin allografts for their surgical treatment was established.

The following criteria were used to select those to be interviewed: 1) the patient is still living; 2) his/her physical and psychological conditions are compatible with being interviewed; 3) he/she has the ability to move and come to the clinical centre; and 4) there is a minimum of 2 years follow-up from the date of onset of burns (which is the minimum delay till scar maturing).

The evaluation of ability to be interviewed was made by both the surgeon and the clinical psychologist who were in charge of the patients both at the acute period of the burns and during the rehabilitation follow-up.

Semi-directed interviews

Questions to guide the interview were built by the Ethic Research group and validated by the clinical psychologist of the burn unit.

Patients were first contacted by phone by the surgeon. They were informed of the anonymous character of the interview. After receiving their assent, interviews were conducted during a face to face consultation and a dedicated time of about 2 hours. When possible, a first "yes or no" answer was sought before comments. Interviews were transcribed by taking notes.

Themes of the interviews

Themes are the information they had received about their surgical treatment as well as the impact on their position about organ and tissue donation through their experience of being a human tissue recipient.

Each patient was asked if he/she was aware of having received skin allografts. When the patient ignored it, the surgeon in charge of the interview gave him/her the information. This information was essential for conducting the rest of the interview. Then questions were asked about expectations in term of information concerning donation, followed by questions about their position relative to donation before and after burn injury. The interview was ended by asking if some information should not be issued to patient in this situation and their perception of the emotional level of the interview (open question).

Results

Interviewed patients

During the period 2002-2008, 1295 patients had been admitted in the adult burn unit of the Cochin hospital. Among them, 79 were treated with skin allografts harvested on deceased donors (multi-organ and tissue donors) (Table 1). Among these allografted patients, 24 deceased during their hospital stay whereas 55 survived. Twelve of them met the criteria of the study as specified in the methodology. All of the 12 patients agreed to be interviewed.

There were 4 men and 8 women. Mean age was 40 years (range 17-66) at the onset of injury. Mean percentage of total burn area was 50 % (range 23-64). Burn injuries occurred from domestic accidents for 5 patients, aggression for 3, accident at work for 2 and immolation for 2. None of them had been informed about skin allograft treatment at the time of the surgery due to medical sedation.

Patients' knowledge about skin allograft and expected information

Table 2 shows that, in response to question 1, 2 of the 12 patients knew that they had been grafted with skin allografts during their treatment. When these 2 patients were asked an additional question about skin procurement, only 1 knew that allografts had been harvested on deceased donors (data not shown). The 10 others were informed that they had received skin from a donor before conducting the interview.

In response to question 2, 3 patients declared that they did not wish to get any further information about the procurement of the allografts (Table 2). Among the 9 patients who wish to have more information, their expectations were to be informed about the donors profile, i.e. age, identity, living or deceased status. They also had questions about technical aspects. They wanted to know how did the allograft act (perform) on their wounds, which burned areas were concerned, and if skin allografts were still present on their body.

Impact on their position concerning donation

Table 3 shows that the position of patients is modified in favor of donation after the onset of burn injury.

In response to question 3, before the injury onset, 2 patients declared their agreement to be a skin donor, whereas 9 declined. Among these, 6 commented that they were not aware that this procedure existed. After injury onset, the number of patients in favor of skin donation increases from 2 to 8. Four responded negatively or expressed their doubt of being able to give anything because of their scars. One commented that he would willingly give his skin but declared: "My skin is out of use. When someone gives something, he/she gives a nice thing".

In response to questions 4 and 5 about other tissue donation (except skin) and organ donation, the number of potential donors also increases (7 out of 10 expressed positive answers in both cases). One patient commented: "Before my injury, my will was to be cremated. Currently, my opinion changed and I avoid all that deals with fire. Furthermore, I want that my death be useful for others by being a donor." Another patient expressed: "I needed the others, now I have to give back". Three other patients said that since their medical care for burns, they explicitly told to their relatives their desire to be a multi-organ and tissue donor and they undertook the necessary steps for that, whereas they never did it before.

In all cases, none of the patients who were initially in favor of donation did change their mind after their accident.

Impact of the interview

It has to be mentioned that all the 10 patients who had been informed during the interview of having been allografted, expressed their satisfaction at receiving this information.

All 12 patients said there is no information about what they underwent (during both their medical care and the present interview) that should not be given. They highlighted the importance of the temporality for the delivery of information and suggested a step by step process.

Three patients express the wish to see pictures of their acute burns in order to evaluate what they have been through and the progress they made.

Discussion

The small number of respondents is a recurrent problem in studies concerning the outcome of burn survivors [START_REF] Anzarut | Quality-of-life and outcome predictors following massive burn injury[END_REF][START_REF] Brewster | Application of rehabilitation ethics to a selected burn patient population's perspective[END_REF]. This calls for a qualitative reflection. Indeed, among the 79 patients who had been skin allografted in our adult burn unit between 2002 and 2008, 55 survived to their injury but only 12 were in ability to be interviewed according to our medical and psychological criteria.

Considering the principles of biomedical ethics described by [START_REF] Beauchamp | Principles of biomedical ethics[END_REF], it appears that when skin allograft has to be performed, the patient clinical status does not allow for the respect of the concept of autonomy and the process of informed consent. Prognosis is engaged, surgery is an emergency, and patients are unconscious due to their injury or sedation (artificial coma). Medical teams have a duty to act in the principle of beneficence [START_REF] Konigova | Ethical problems in burn medicine[END_REF]. However, at the time where medical paternalism is no longer conceivable, the question is to know how to reintegrate the process of patient information about his treatment. When managing an acute event, the French law recommends informing either the relatives or a person of trust, about the condition of their relatives. The question of post-emergency information is found in other medical care contexts and clinical research programs in situations of unconsciousness (Law N°88-1138 of December 20th, 1988 on the protection of persons accepting biomedical research (Huriet Law) revised July 25th, 1994. Journal Officiel 1988;26 juillet 1994).

From a medical point of view, information on donor skin is mandatory. Allografts are a human product and it remains that, despite the quality of safety procedures, a potential risk of transmission of pathogenic agents exists. From an ethical point of view, this information is imperative due to the respect to the donor, his family and the recipient. In our study, none of the 12 patients were able to be informed about the use of skin allograft at the time of surgery, and only 2 of them knew that they had been grafted with donor skin. Thus, doubts remain whether patients have really received all information [START_REF] Enoch | Informed consent should be obtained from patients to use products (skin substitutes) and dressings containing biological material[END_REF], and if they did receive the information, did they understand it and assimilate it ? The right timing for delivering such information is not an easy task. A lot of information needs to be delivered a posteriori, from the circumstances of the accident to the treatment of burn sequels. Caregivers should determine more precisely what can be told and be repeated at the different steps of patient recovery, and if there is a best time for delivering specific information to patients (i.e., at the regain of consciousness, at following-up dressings, at the entry in rehabilitation, etc...). Physicians also have the duty to respect the wishes of patients who do not want any further information, as 3 of our respondents who did not want to know more details about skin procurement modalities.

Regarding the content of the information, our study showed that during the interview several elements appeared essential to provide the patients with a concrete vision of their treatment, such as the origin of the allografts, the modalities of skin harvesting on the donor, the necessity of multiple donors for a single recipient, and the outcome of allografts (delay of rejection). Answering these questions allowed to alleviate their vision of the donor being "flayed alive". This also allowed discussion of donation principles which are based on generosity, anonymity and consent. Furthermore, informed patients will be able to testify about the importance of the donation. Patients who had benefited from a gesture of solidarity are grateful [START_REF] Sanner | Transplant recipients'' conceptions of three key phenomena in transplantation: the organ donation, the organ donor, and the organ transplant[END_REF]. Our results show that our patients have modified their position in favor of donation (organ and tissue) after their accident. This highlights the importance of communication, considering that tissue donation is less valued than organ donation in the society, that skin donation is less known than other tissues such as cornea [START_REF] Chua | Use of skin allograft and its donation rate in Singapore: an 11-year retrospective review for burns treatment[END_REF] and that situations of skin allografts unavailability are regularly encountered.

In conclusion, all our respondents were grateful to receive more information on their treatment and especially on skin allograft. They perceived the interview as a help for them, a relief, a catharsis, an opportunity to express their feelings and a new step for their reconstruction [START_REF] Gueniche | Plaidoyer pour les transplantés[END_REF].

What is already known about this subject? -Skin allograft has improved the outcome of patients with severe burns. -Consent is not required. Information of the relatives on skin allograft is recommended.

-There is no recommendation regarding the patient information on skin allograft after recovery.

-The awareness of the patients about skin allograft has not been evaluated.

What does this study add? -Patients are ignorant of having been grafted with donor skin.

-Patients want to get information about skin allografts.

-Through their experience, patients modify their position in favor of donation (organ and tissue).

-Reflection should be conducted by health professionals' about when and how to give information about skin allografts -There is a need to improve communication about tissue donation which is less known than organ donation.

Acknowledgements

Our special thanks to the patients for their participation to this study and to Mme Claire Coutzac.

Conflict of interest statement

None of authors has any personal relationships, commercial associations or financial disclosures that might create a conflict of interest with the work presented in this article.


Arnaud Banos
email: arnaud.banos@parisgeo.cnrs.fr

Network effects in Schelling's model of segregation: new evidences from agent-based simulation

Keywords: Agent based modeling, Cliques, Networks, Schelling, Segregation

According to two recent studies, Thomas Schelling' model of segregation is only weakly affected by the underlying spatial structure, whatever its complexity. Such a conclusion is important from an urban planning perspective as it suggests that only a very restricted range of possible actions, if any, would be able to contribute limiting social segregation, unless individual preferences are significantly modified. Our own simulations show that, using appropriate graph-based spatial structures, one can reveal significant spatial effects and thus provide alternative planning insights. Cliques in networks indeed play a significant role, reinforcing segregation effects in Schelling's model. Introducing a small amount of noise in the model permits us to reveal more precisely this effect, without modifying the global behavior of the initial model. Furthermore, we show how a logistic model describes in a concise but precise way this global behavior at an aggregated level.

Introduction

Thomas Schelling' model of social segregation [START_REF] Schelling | Models of segregation[END_REF][START_REF] Schelling | Micromotives and Macrobehavior[END_REF] is certainly one of the most debated models in the social sciences 1 . Imagine two colored groups of individuals, living on a chessboard city, and having the capacity to change their place of living according to the color of their neighbors. Schelling demonstrated that if individuals have a mild preference for living near people of their own color, and if they move to satisfy their preference 2 , complete segregation at the city scale may occur. Its capacity to demonstrate, in a simple and elegant way, how interdependent but noncoordinated local residential decisions may lead to unexpected social segregation surely explains the large success of this model. While scientists from various disciplines, ranging from social sciences [START_REF] Clark | Understanding the social context of the Schelling segregation model[END_REF][START_REF] Fossett | Effects of city size, shape, and form, and neighborhood size and shape in agent-based models of residential segregation: are Schelling-style preference effects robust?[END_REF][START_REF] Laurie | The role of 'vision' in neighbourhood racial segregation: a variant of the Schelling segregation model[END_REF] and economics [START_REF] Fagiolo | Segregation in Networks[END_REF][START_REF] Pancs | Schelling's spatial proximity model of segregation revisited[END_REF] to physics [START_REF] Dall'asta | Statistical physics of the Schelling model of segregation[END_REF][START_REF] Gauvin | Phase diagram of a Schelling segregation model[END_REF][START_REF] Stauffer | Ising, Schelling and Self-Organising Segregation[END_REF][START_REF] Vinkovic | A physical analogue of the Schelling model[END_REF] and 1 For example, an advanced search of JASSS text using « Schelling » as a keyword points out 83 references on JASSS website. 2 Schelling's model is very limited in its scope at it is only based on individual preferences and thus does not take into account two other mechanisms at stake in social segregation, as identified for long by sociologists: discriminative processes (occurring at the institutional and/or individual level) and socio-economic factors. mathematics [START_REF] Pollicot | The dynamics of schelling-type segregation models and a nonlinear graph Laplacian variational problem[END_REF][START_REF] Zhang | A dynamical model of residential segregation[END_REF] handled this model, trying to find links with their own concepts and models, their conclusions all converged to Schelling initial nding: segregation may occur at the city level even if every single agent is tolerant enough (mild preference) to accept an integrated pattern. According to two recent studies [START_REF] Fagiolo | Segregation in Networks[END_REF][START_REF] Fossett | Effects of city size, shape, and form, and neighborhood size and shape in agent-based models of residential segregation: are Schelling-style preference effects robust?[END_REF]), Schelling's model of segregation is so robust that it is only weakly affected by the underlying urban structure: whatever the size and shape of city, this undesired emerging phenomenon will happen. According to other authors [START_REF] Clark | Understanding the social context of the Schelling segregation model[END_REF], individual preferences are evolving so slowly that no real improvement can be expected in a near future. Such conclusions may have important public policy and urban planning implications as they suggest that only a very restricted range of possible actions, if any, would be able to contribute limiting social segregation. However, the situation seems even worse than expected. Indeed, we can draw two complementary conclusions from our own simulations: actual and planned geometries of cities not only accelerate and reinforce Schelling' segregation processes but they may also favor intolerant behaviors. Therefore, fatalism should be banned: public policy and urban planning have their role to play in the more than ever urgent quest for sustainable cities.

Graph-based cities

The shape of an urban area and the way it is fed by the road network are two major ways that differences occur at the intra-urban level. There are also generally very marked differences in accessibility between the centre and the different suburbs. Moreover, certain areas or neighborhoods can be told apart by their relative impermeability: gated communities and ghettos can thus be defined as cliques, which in the network theory jargon describe subsets made up of nodes adjacent to one another. What can be demonstrated is that network shape in general and cliques in particular may play a significant role in the dynamic of Schelling' model, cliques acting as local attractors, or segregation "traps". Let us illustrate this point with four urban networks increasingly hierarchised, defined as: a) regular (grid), b) random, c) scale-free3 , and d) fractal (Sierpinski tree). These last two networks may appear a bit "exotic" to the non-specialist but in fact they share more similarities with real cities than regular or random networks. For example, Bin [START_REF] Jiang | A topological pattern of urban street networks: Universality and peculiarity[END_REF] demonstrated on a large sample of 40 US cities of different sizes that urban street networks based on street-street intersection display a scale-free property. Furthermore, fractal patterns are often presented as relevant for urban systems, when it comes to imagining more livable and sustainable cities [START_REF] Batty | The size, scale, and shape of cities[END_REF][START_REF] Frankhauser | Fractal geometry for measuring and modeling urban patterns[END_REF]. These four networks could have been compared directly, as in [START_REF] Fagiolo | Segregation in Networks[END_REF], but we believe this would have introduced a severe bias linked to the varying degree distribution. Indeed, as evaluation of preferences by each agent is based on the proportion of his n occupied neighbors having a given color, the de facto weight of each neighbor is 1/n and therefore small neighborhoods are more sensitive to changes than larger ones. To avoid this problem, we arbitrarily fix the number of neighbors: each node is connected to its n closest nodes, as defined by a Floyd routing algorithm [START_REF] Floyd | Algorithm 97: Shortest Path[END_REF]. The resulting neighboring graphs obtained then present an interesting effect: they are more or less marked by the existence of cliques. As the number of neighbors n is constant, each resulting network can be characterized by a simple clustering coefficient4 [START_REF] Watts | Collective dynamics of small-world networks[END_REF]:

C i = 2E i k i (k i 1) , 0 C i 1
where E i is the number of connected pairs among neighbors of node i and k i is the degree of node i. This indicator varies between 0 (no connected pairs among neighbors of node i) and 1 (fully connected neighbors). Averaging these local values provides a global indicator very useful when comparing different network structures:

C = 1 n C i i=1 n
The four networks defined, characterized by a fixed degree (10 neighbors), present different clustering values, as expected from their neighboring graphs (table 1).

Schelling's agents

According to Schelling's model, each node of these graphs may be seen as a possible living place, occupied (or not) by an agent belonging to a given category. It is well known, however, that density of agents needs to be nor too low nor too high for the system to get self-organised [START_REF] Gauvin | Phase diagram of a Schelling segregation model[END_REF][START_REF] Vinkovic | A physical analogue of the Schelling model[END_REF]. Too many vacant nodes would limit the contacts between agents, keeping their spatial distribution random whatever their individual preference level, while too few free nodes would just "freeze the system". For each generated network, a fixed proportion (80%) of nodes is then randomly populated with a corresponding number m of agents, half of them being of color x and the remaining part being of color y.

Each agent is able to identify his neighborhood composition, i.e. the proportion P ij of his occupied neighbors being unlike him. At each time step, each randomly selected agent A i computes his utility, defined as a step function:

U i = 0 if P ij > 1 if P ij
with a tolerance threshold value, embedding agent's preference. Agent A i then moves if he feels unsatisfied with his current location (U i = 0) and if there is at least one vacant noderandomly chosen if more than one -allowing him increasing his utility (U i = 0 U i = 1).

For various possible values of the tolerance parameter 5 ={0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100}, 1000 simulations were achieved and a social mixity index calculated. Following Schelling himself, this index is simply the mean proportion of contacts between unlike neighbors (omitting empty nodes):

M = 1 A P ij i=1 A
where A is the number of agents (cardinal). This index then varies between 0 (complete segregation) and approximately 50% (mixity). It may be noticed that a 50% mixity can be obtained either from a random distribution of agents (most probable and stable issue) or from a more integrated "chessboard" like pattern (highly improbable and unstable issue).

A simulation ends up if one of the two conditions is respected: either because the system converges towards equilibrium or because the simulation time exceeds a given threshold value (table 2). Equilibrium is obtained when each agent is satisfied with his current location, that is:

Published in Environment and Planning B,Volume 39,n°2,[393][394][395][396][397][398][399][400][401][402][403][404][405] 5/15

U i i=1 m = A
It may be noticed that static patterns (i.e. no agent moves anymore) can be obtained while no equilibrium is reached: et al, 2009) call such state a "frozen state". Results (Figure 2) confirm the robustness of Schelling's model but also stress significant discrepancies between the various networks, thus suggesting the possible role of network hierarchy and cliques in Schelling' segregation process. For high tolerance values ( > 70), the system rapidly converges (i.e. reaches equilibrium) towards a mixed state. Then, a dramatic change occurs for a slight decrease in tolerance ( = 70): while being still tolerant at an individual level (preferences), agents make by their moves the global system converge towards a segregated state. As tolerance decreases (30 < < 70), highly segregated states are obtained. For a mild preference value ( = 50), every simulation converges from an initial random distribution to a highly segregated pattern, for each of the four generated networks (figure 3). While having a mild preference, each agent ends up in a highly segregated community, with few or no contacts with unlike agents. Patterns are clearly related to the neighboring graphs (figure 1), underlying the importance of cliques as "segregation traps". Observing the model's dynamics confirms this role played by cliques, but also the locking-in role of "entry" nodes (figure 4). Rapidly, cliques are filled up by an agent population of one or another color. As their connection with the rest of the network is limited to a reduced number of nodes (we call them "entry" nodes), we can assume surface tension to be concentrated over this limited subset of nodes, thus reinforcing local anchorage of growing clusters. Network topology in general and cliques in particular seems to play an important role in the dynamic of the whole model, by channeling agents towards local attractors. Once these pockets of local order become filled in enough, agents are then "protected" from exogenous perturbations: no unlike agent will settle down anymore. This process may be compared to the one described by [START_REF] Keeling | The effects of local spatial structure on epidemiological invasions[END_REF] for epidemics, who showed how cliques reduce the initial spread of an epidemic, but also the final proportion of the population that the epidemic reaches. Decreasing tolerance ( = 30) then leads to a second phase transition: agents find less and less vacant nodes corresponding to their preference and therefore wait for a better place to get vacant, while being unsatisfied with their current location. This transition area ( = 30) is highly unstable and, depending on the initial configuration and the course of the simulation, "frozen states" can be reached. In such situation, the model does not converge towards equilibrium: while no agent can move anymore, a varying proportion of them are not satisfied with their current location. Table 2 shows the proportion of convergences towards equilibrium over 1000 runs, for this specific tolerance value ( = 30). Proportions vary from 30% of the runs for grid and scale-free network, to 48% for the random network and 56% for the Sierpinski tree. For very low tolerance values ( < 30), no equilibrium can be found, as agents are trapped in a global frozen state, waiting forever for better places (i.e. increasing their utility) to become available.

U i i=1 m < A (Gauvin
While each of the four networks follows this global trend, significant differences occur at the two transition areas ( = 70 and = 30), and within the segregated state (30 < < 70). The two hierarchised and highly clustered networks (scale-free and Sierpinski) apparently contribute reinforcing the segregation process, letting the system converge towards significantly 7 higher segregation states.

Increasing the size of networks only marginally affects this very robust result. Figure 5 displays the curves for three Sierpinski networks of increasing size (respectively 364, 781 and 1464 nodes). As can be seen, the curves are very similar, whatever the network' size. However, increasing the degree (number of neighbors) significantly impacts the result. The segregation process is indeed retarded for high tolerance values ( = 70) while frozen states are systematically obtained for = 30. As stated in the "Graph-based city" section, the main explanation resides in the evaluation of preferences by each agent. Indeed, as it is based on the proportion of his n occupied neighbors having a given color, the weight of each neighbor is 1/n and therefore small neighborhoods are much more sensitive to changes than larger ones. Increasing the degree reduces the cascading effects leading to segregation for high tolerance values ( = 70) while it decreases to possibility for agents to find a free node corresponding to their preference for low tolerance values ( = 30). Such frozen states, easily obtained whenever one introduces more constraints in the system, suggest that adding some "flexibility" in the system may be interesting.

6 This threshold depends both on initial conditions (network size and shape, density of agents) and simulation parameters (tolerance). However, with the decision rules defined so far, the number of iterations needed to reach convergence (being defined either as an equilibrium or as a frozen state) is usually small. In the present case, preliminary convergence studies revealed that 50 iterations is a relevant limit: if the system does not converge in 50 iterations, then its probability to find such a state in more iterations is negligible. Introducing some noise in the system, as we do in the next section, increases this value by one order of magnitude. Varying "temperature" in Schelling's model

One could think of a physical analogy: by "heating up" this system, we would be able to increase its entropy and therefore increase the range of possibilities for agents, as well as the range of possible states the system could reach. Adding some noise in the agents' decision rule allows reaching such objective. Several options are therefore available. For example, one can introduce the possibility for satisfied agents to also move, and not just restrict such possibility to discontent ones [START_REF] Gauvin | Phase diagram of a Schelling segregation model[END_REF]. As quoted by authors, "that rule introduces some noise in the dynamics and is useful to avoid a particularity of the original Schelling model, namely that the system may end up in states where the clusters are large but finite, so that strictly speaking no large-scale segregation occurs". Another option is to introduce the possibility of "mistakes" [START_REF] Zhang | A dynamical model of residential segregation[END_REF]: agents willing to move may choose a destination decreasing their utility, for example because they have incomplete or twisted information on the new context they face. It is this last option we follow here, by introducing a new parameter N (for "Noise"), ranging from 0 to 1 and interfering with the decision process in the following way. For each unsatisfied agent A i,Ui=0 , we generate a random number n from a uniform distribution [0; 1] and use the following rule: if n < N, then agent A i will move to a randomly chosen vacant node, whatever its expected utility value on that destination node (U i = 0 U i = 1 OR U i = 0). Introducing even a small amount of noise (N = 0.1) considerably "fluidifies" the system, in a very striking way (figure 6). One sees immediately two interesting phenomena. First, introducing a small amount of noise in the model improves its capacity to reach equilibrium for low tolerance values ( < 40). For scale-free and Sierpinski networks, convergence is systematic even when tolerance is null ( = 0). Therefore, adding a small amount of noise transforms Schelling's model in an optimization algorithm, able to find spatial patterns respecting heavy constraints on parameter . The underlying topology reinforces this capacity, especially when networks are highly interconnected (presence of cliques). Furthermore, this capacity is extraordinarily targeted: the course of the model doesn't seem to be affected by this small amount of noise, unless the second phase transition is reached ( = 30). Figure 7 underlines clearly this property for the Sierpinski network: whatever the level of noise added, results are not significantly affected, until > 30. Then, for = 30 and = 20, any amount of noise allows reaching equilibrium while the standard Schelling's model doesn't. As decreases further on ( < 20 ), a new state appears for N = 1 (i.e. 100% of unsatisfied agents move to any vacant node whatever their expected utility there), characterized by never ending movements of unsatisfied agents. It may be noticed that this chaotic state appears only when N = 1, i.e. when the system is populated with "knee-jerk" agents, moving to any vacant node as soon as they feel unsatisfied. Therefore, preserving an even small amount of "opportunist" Schelling like agents is sufficient to let the system converge towards equilibrium.

Sensitivity to initial conditions and network effects

In this "tipping" model, segregation is then characterized as a stochastically stable state that tends to emerge and persist in the long run regardless of the initial state [START_REF] Zhang | A dynamical model of residential segregation[END_REF]. However, depending on the initial configuration of agents, their random selection and the succession of events (path dependency), very different equilibrium can be reached. In that sense, despite its global robustness, Schelling's model is also sensitive to initial conditions: different initial random patterns of agents may lead to very different final patterns. However, this sensitivity depends also on the value of the tolerance threshold used and its proximity to a stable or unstable zone of the parameters' space. Indeed, as illustrated by Figure 2, variability of final mixity index varies with tolerance value and reaches the highest values for = 30 and to a lesser extend for = 70 (phase transitions). Between these two values, final configurations obtained differ essentially in their details, as global state -measured by mixity index -is quite stable. However, the situation is completely different when = 30. Indeed, as figure 2 and table 2 suggest, this zone of the parameters' space is highly unstable and initial random distributions of agents can lead to very different configurations, depending on the capacity of the system to converge towards an equilibrium or to remain in a "frozen state". Figure 8 illustrates this phenomenon, which can be seen as a bifurcation: from given random initial distributions of agents and without added noise, system may converge towards a completely segregated configuration (mixity < 2% for both networks) or remain in a frozen state characterized by a high mixity index (mixity > 40% for both networks). Therefore, when = 30 Schelling's model is very sensitive to initial conditions and is consequently highly unstable, whatever the underlying network used. It may be noticed that adding a small amount of noise allows mastering this issue, as figure 5 and previous developments show. However, in addition to these global characteristics and adding just a limited amount of noise, one can also reveal a specific behavior of the model on Sierpinski network, characterized by a well-defined hierarchy of nodes. Indeed, as simulations point out (figure 9), the final state of major central nodes after convergence depends closely on the tolerance value. At any time during the simulation, nodes are characterized by one of the three possible states (vacant; occupied by an agent of color x; occupied by an agent of color y). On a completely homogeneous network, it is hardly possible to predict the final value of a given node. However, for Sierpinski network and for low tolerance values ( < 30), this is not true anymore: whatever their initial state, central nodes almost systematically converge towards the same final state (vacant), separating cliques of homogeneously colored agents. Therefore, for highly hierarchised networks such as Sierpinski network, some nodes display very specific behavior depending on their topological situation. Space does make a difference, both at global and local levels.

A global model

As figure 6 suggests, mixity can be defined as a step function of tolerance (), each underlying network having its own signature. Therefore, given the existence of two asymptotes (mixity = 0 and mixity = 50) and of an acceleration and deceleration phases between them, a three parameters logistic model may characterize this relation in a synthetic form:

y = 50 if U i i=1 m " < A # 1+ e $%$ &x if U i i=1 m " = A ' ( ) ) * ) )
with y = Mixity and x = Tolerance (). Estimating parameters {, , } for each of the four networks leads to very tight fits (R 2 > 0.99). Figure 10 shows the various S-curves obtained. The parameters obtained (table 3) -and especially {, } as is a scale parameter -allow comparing in a very synthetic manner Schelling's model behavior on various underlying structures. The surface between the two families of curves (grid and random versus scale-free and Sierpinski), coupled with the step-like structure of the logistic fits, give a precise idea of the capacity of the latter networks to accelerate and amplify Schelling like segregation.

Table 3. Parameters estimates and goodness-of-fit statistics (R 2 ) for each network

These results suggest that for a given underlying topology (network and degree) and by introducing a small amount of noise (with its conservative properties suggested), we should be able to characterize and even anticipate Schelling's model behavior. On large networks, characterizing real cities, this could make a difference as the computation burden involved by simulation may exceed our capacities. Combined with further knowledge on local segregation dynamics related with cliques, these results might contribute assessing urban planning policies.

Conclusion

So far, several conclusions can be drawn from our simulations. Firstly, and confirming previous works, Schelling's segregation process is robust and happens on very different underlying structures, even far away from the homogeneous grid initially used by Thomas Schelling. Secondly, this model is also very robust to random fluctuations. Indeed, introducing a small amount of noise in the model dynamic under the form of a small proportion of "knee-jerk" agents, moving to any vacant node as soon as they feel unsatisfied whatever their expected utility, has very limited impact on its global behavior. However, for specific tolerance values, such add-on allows reaching equilibrium solutions that were not attainable with the standard version. Under this slight modification, we show that the global behavior of Schelling's model can be formalized in a simple thus precise way, with a three parameters logistic model. These fundamental properties of Schelling's model then allowed us showing by simulation that, contrarily to previous conclusions [START_REF] Fagiolo | Segregation in Networks[END_REF][START_REF] Fossett | Effects of city size, shape, and form, and neighborhood size and shape in agent-based models of residential segregation: are Schelling-style preference effects robust?[END_REF], space does matter in this model. More precisely, network topology interferes with its dynamics, by accelerating and reinforcing its effects. Segregation occurs more rapidly on hierarchised networks characterized by cliques than on random and regular ones. Furthermore, such interconnected structures also authorize intolerant behaviors: equilibrium can indeed be reached with highly segregationists agents (tolerance weak or null), as soon as a small proportion of non opportunist agents is introduced in the system. Preliminary investigations led on "real" cities confirm these theoretical results. In [START_REF] Moreno | Integrating morphology in urban simulation through reticular automata[END_REF], the Schelling model was applied to a large network (120 000 nodes), each building being embedded in an anisotropic neighborhood, defined using accessibility and graph-based algorithms, in the same spirit we did in the present work. Clique effects were also identified, though in a less systematic way due to the computation burden involved by the network' size. These results may have important public policy and urban planning implications as they suggest that actual and planned geometries of cities may not only accelerate and reinforce Schelling' segregation processes but may also contribute favoring segregationist behaviors. Therefore, fatalism should be banned and laissez-faire should be fought: public policy and urban planning have their role to play. Limiting undesirable self-reinforcement processes may be possible and should be part of any ambitious urban politics. Moreover, this work highlights the need for more integrated approaches of urban systems. Indeed, as [START_REF] Frankhauser | Fractal geometry for measuring and modeling urban patterns[END_REF] shows, hierarchical and interconnected urban architectures prove useful on some aspects. Especially fractal geometries, which may benefit to cities and citizens, as they allow maintaining "a social mix by means of a higher local variability of densely and less densely populated zones and, on the other hand, to preserve huge empty zones in the neighborhood of urbanized areas, which may be imagined as natural reserves, agricultural zones or simply leisure areas offering rural amenities" [pp. 239]. Our simulations show evidence that such gains may be compensated by losses in terms of social mixity and integration. Based on these results, it seems obvious that more integrated approaches of urban systems should be encouraged and privileged in our more than ever urgent quest for sustainable cities. Among the challenges put at the forefront by this classical model, one finds news echoes here: can we imagine cities' shapes and forms able to limit Schelling's segregation process? Obviously, one cannot focus only on individual preferences, as suggested by [START_REF] Clark | Understanding the social context of the Schelling segregation model[END_REF]. Economic constraints, socio-economic context and precise survey-based knowledge of the precise mechanisms at work should be incorporated incrementally in the model, in order to gain new insights on its behavior in more complex situations, not limited to positive feedbacks and self-reinforcement processes. Carefully introducing heterogeneity in agent-based models, both at the level of agents' attributes and behaviors but also in the way we define agents' environment is therefore a key issue the community should handle more vigorously, in order to improve our understanding of cities dynamics.

Figure 1 .

 1 Figure 1. Regular, random, scale-free and fractal (Sierpinski) networks (up) and their corresponding neighboring graphs (bottom) for a fixed degree (d = 10; neighborhood defined using shortest path algorithm)

Figure 2 .

 2 Figure 2. Average mixity index and its standard-deviation (1000 simulations), for each of the four networks

Figure 3 .

 3 Figure 3. Examples of equilibriums attained for mild preferences ( = 50, Density = 80%, Degree = 10, white squares = vacant nodes)

Figure 4 .

 4 Figure 4. Cliques as segregation traps and the locking-in role played by "entry" nodes (Degree = 10; neighboring links not represented here)

Figure 5 .

 5 Figure 5. Comparison of results for 3 Sierpinski networks of increasing size (Average mixity index from 1000 simulations. "N" is for Nodes, "D" is for degree and "C" is for clustering coefficient. Example: "364N-D10-C0.95" is a network with 364 nodes, a degree of 10 neighbors and a clustering coefficient of 0.95. Confidence intervals are not shown)

Figure 6 .

 6 Figure 6. Average mixity index and its standard-deviation (1000 simulations) for each of the four networks, with noise in the system (N = 0.1)

Figure 7 .

 7 Figure 7. Mixity values reached for various noise levels, for the Sierpinski Network [density of occupied nodes 80%]

Figure 8 .

 8 Figure 8. Example of bifurcation at work when = 30 [Noise = 0; Density = 80%]

Figure 9 .

 9 Figure 9. Influence of nodes' centrality on their final state [Noise = 0.1; Density = 80%; varies from 0 (upper left corner) to 50]

Figure 10 .

 10 Figure 10. Logistic models fitted, for converging tolerance values [Noise = 0.1; in the legend "O" is for observed (from simulation) and "P" for predicted (model fitting)]

Table 1 . Properties of the four networks and their neighboring graphs (degree = 10)

 1

	Grid	Random	Scale-Free Sierpinski

Table 2 . Proportion of convergence towards equilibrium (each agent is satisfied with his current location) over 1000 simulations, for the 30% tolerance value and 50 iterations threshold 6

 2

Parameter Grid Network Random Network Scale-Free Network Sierpinski Network

		-6.064	-6.763	-11.319	-14.299
		0.092	0.101	0.166	0.205
		54.019	53.632	50.076	49.406
	R 2	0.991	0.992	0.999	0.999

Generated following preferential attachment rules as proposed in(Barabasi and Albert, 1999). See[START_REF] Song | Origins of fractality in the growth of complex networks[END_REF] for evidence on the non fractal topology of such networks.

See[START_REF] Newman | Random graphs with arbitrary degree distributions and their applications[END_REF] for a discussion on the limitation of this indicator when the degree varies and their proposal for a more robust indicator.Published inEnvironment and Planning B, Volume 39, n°2,[393][394][395][396][397][398][399][400][401][402][403][404][405]

is a proportion, expressed in percents, as it refers to a threshold value of P ij , defined for each agent A i as the proportion of occupied neighbors being unlike him.


On the Generalized Belief Propagation and its Dynamics

Jean-Christophe Sibel and Sylvain Reynal

Abstract-Numerous inference problems in statistical physics, computer vision or error-correcting coding theory consist in approximating the marginal probability distributions on Markov Random Fields (MRF). The Belief Propagation (BP) is an accurate solution that is optimal if the MRF is loop free and suboptimal otherwise. In the context of error-correcting coding theory, any Low-Density Parity-Check (LDPC) code has a graphical representation, the Tanner graph, which is a particular MRF. It is used as a media for the BP algortithm to correct the bits, damaged by a noisy channel, by estimating their probability distributions. Though loops and combination thereof in the Tanner graph prevent the BP from being optimal, especially harmful topological structures called the trappingsets. The BP has been extended to the Generalized Belief Propagation (GBP). This message-passing algorithm runs on a non unique mapping of the Tanner graph, namely the regiongraph, such that its nodes are gatherings of the Tanner graph nodes. Then it appears the possibility to decrease the loops effect, making the GBP more accurate than the BP.

In this article, we expose a novel region graph construction suited to the Tanner code, an LDPC code whose Tanner graph is entirely covered by trapping-sets. Furthermore, we investigate the dynamic behavior of the GBP compared with that of the BP to understand its evolution in terms of the Signal-to-Noise Ratio (SNR). To this end we make use of classical estimators and we introduce a new one called the hyperspheres method.

I. INTRODUCTION

A well-known problematic of the Markov Random Fields (MRF) is to extract their marginal probability distributions. Such an inference problem has numerous applications in computer vision, neural networks, image processing, statistical physics and channel coding. In [START_REF] Pearl | Probablistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF] has been proposed the Belief Propagation (BP), known to provide accurate estimates. In the realm of error-correcting coding theory, the BP is a decoding algorithm that helps to recover a sequence of bits sent through a noisy channel. To this end it is associated to Low-Density Parity-Check (LDPC) codes that apply artifical constraints between the bits, namely the parity-check equations. The bits joined with the parity-check equations form an MRF, called the Tanner graph, used as a media for the BP [START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF]. It is an accurate approximate inference algorithm knwown to provide low bit-error rates. However most LDPC codes have loop-like topologies, that leads the BP to wrong estimates, making this algorithm suboptimal [START_REF] Murphy | Loopy belef propagation for approximate inference: an empirical study[END_REF]. In particular, the combination of short loops, as the trapping-sets [START_REF] Richardson | Error floors of LDPC codes[END_REF], [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF], are very harmful. To circumvent this phenomenon, we bring out that the BP is equivalent to the Bethe approximation [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF]. This method is used in statistical physics to estimate statistical averages of thermodynamics quantities by neglecting -to some extent -correlations This work was supported by the French ANR Defis program under contract ANR-08-EMER-003 (COCQ project). between interacting spins. This technique suffers from the loop-like topology of the spin glasses. It has been generalized to the Kikuchi approximation, a technique that consists in gathering the interacting spins to absorb loops [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF]. Transposed to the case of the LDPC codes, the resulting graph, called the region-graph, is a media for a new messagepassing algorithm, the Generalized Belief Propagation (GBP) that turns out to be more accurate than the BP provided that the region-graph has absorbed damageable structures. Along the whole paper, we focus on the Tanner code [START_REF] Tanner | A Class of Group-Structured LDPC Codes[END_REF] whose main property is that it can be entirely described by a set of trapping-sets. Then the region-graph can be built by working on them.

To investigate deeper the comparison between BP and GBP we focus on their dynamics according to the Signal-to-Noise Ratio (SNR). Studied from a theoretical point of view in [START_REF] Chung | Analysis of Sum-Product Decoding of Low-Density Parity-Check Codes Using a Gaussian Approximation[END_REF], [START_REF] Ruffer | On robust stability of the belief propagation algorithm for LDPC decoding[END_REF], the dynamics of the BP has also been investigated by experimental results in [START_REF] Zheng | Study of bifurcation behavior of LDPC decoders[END_REF]. In this paper we carry out a work on experimental study, by the use of estimators as the bifurcation diagram and the Lyapunov exponent to raise the behavior of the BP and the GBP according to the SNR.

The second II deals with preliminaries about the LDPC codes and the BP. In the section III are exposed the regiongraph construction rules and the GBP. Then we detail our novel construction of the region-graph for the Tanner code. The section IV is dedicated to the exposure of dynamics estimators to better understand the GBP and to highlight its relevant properties.

II. PRELIMINARIES

A. LDPC Codes -Belief Propagation

We consider N binary random variables X = {X 1 , . . . , X N } whose global state is x = [x 1 , . . . , x N ]. Each variable represent a bit to transmit through a noisy channel. We use the lightened notation x = [x 1 , . . . , x N ] to denote variables and states. An LDPC code is represented by M parity-check equations C = {c 1 , . . . , c M } such that for each j ∈ {1, . . . , M }, c j = xi∈Nj x i where the sum is binary. N j ⊂ x is the neighborhood of c j defined by the LDPC code. We define similarly N i the neighborhood of x i as the set {c j } j such that x i ∈ N j . c j and and x i ∈ N j form an edge e ij between two nodes, a variable node x i and a check node c j , in a graph G = (X ∪ C, {e ij } ij ), called the Tanner graph (see Fig. 1).

G is an MRF whose {b i (x i )} 1≤i≤N are the beliefs, i.e. the estimate of the marginal probability distributions. x is the estimate of the input bits such that xi = arg max xi b i (x i ). The Tanner graph is used as a media for the propagation of messages to get x from the BP. {m

(k) ij } ij and {n (k) ji } ji
are respectively the messages from the variable nodes to the check nodes, and the messages from the check nodes to the variable nodes at iteration k whose equations are detailed in [START_REF] Pearl | Probablistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF], [START_REF] Kschischang | Factor Graphs and the Sum-Product Algorithm[END_REF] such that:

∀e ij , m (k) ij = f ij {n (k-1) yx } (x,y) , l i (1) n (k) ji = g ji {m (k) xy } (x,y) (2)
with {f ij } ij , {g ji } ji the implicit update equations and {l i = p(y i |x i )} i the likelihoods computed from the observation variables {y 1 , . . . , y n }. The messages {n

(k)
ji } are then computed by an iterated map Q = g • f such that:

∀e ij , n (k) ji = Q ji ({n (k-1) nm } (m,n) , {l i } i ) (3)

III. THE GENERALIZED BELIEF PROPAGATION

A. The region-graph construction

The region-graph R is a directed graph of depth D built level by level. We decompose this construction in two steps.

The first step is the construction of the first level R 0 . The principle is to gather the nodes of the Tanner graph in order to absorb some harmful topological structures, as loops or combinations thereof. These gatherings, called regions, are nodes of R 0 if and only if each check node c j with N j is included in at least one of these regions. The second step is the construction of the next levels R 1 , . . . , R D-1 . A level R l is constructed by searching for the intersections between the regions of the previous level R l-1 . We respectively define C r and X r the sets of check nodes and variable nodes of the region r.

A set r = X r ∪ C r is a region of R l if and only if there is n ≥ 2 regions {r 1 , . . . , r n } ∈ R n l-1 such that: • ∀c j ∈ C r , ∀r k ∈ {r 1 , . . . , r n }, c j ∈ C k , • ∀x i ∈ X r , ∀r k ∈ {r 1 , . . . , r n }, x i ∈ X k .
A region-graph of the Hamming code presented previously is displayed on Fig. 2. The used method [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF] consists in including only one check node and its neighborhood per region in R 0 .

The GBP performance are dependent on the region-graph, and particularly on the regions of R 0 . The difficulty is to

x 0 x 1 x 2 x 3 x 4 x 5 x 6 c 0 c 1 c 2 Fig. 1. Tanner graph of the Hamming code c 0 x 0 , x 1 , x 2 , x 4 c 1 x 0 , x 1 , x 3 , x 5 c 2 x 0 , x 2 , x 3 , x 6 x 0 , x 1 x 0 , x 2 x 0 , x 3
x 0 Fig. 2. A region-graph of the Hamming code find a construction that both implies relevant performance of the GBP and fair complexity. In the previous example, the construction is easy to implement and the complexity is low enough but there is no link with the Tanner graph toppology, preventing the GBP from obtaining relevant performance.

B. The message-passing algorithm

The region-graph is a Bayesian network whose probability distribution is estimated by the GBP. As in the BP case, the principle is to convey messages on the edges of the regiongraph where a message m (k) rq from a region r to a region q is the a posteriori probability distribution of the region q given by the region r at iteration k. We compute messages only between connected regions, i.e. m (k) rq is considered if and only if (r → q) is a directed edge of the region-graph, we say that q is one of the children C r of r. An iteration of the algorithm consists in the computation of all the messages {m (k) rq } r,q whose equations are detailed in [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF], [START_REF] Pakzad | Estimation and marginalization using Kikuchi approximation methods[END_REF]. Here we only give the implicit equation:

∀(r, q) ∈ R 2 s.t. q ⊂ C r , m (k) rq = F rq {m (k-1) ps } p,s , {l i } i (4)
In [START_REF] Yedidia | Constructing free energy approximations and Generalized Belief Propagation algorithms[END_REF] is highlighted that the GBP suffers from a poor convergence. To circumvent this phenomenon is included a uniform weighting:

m (k) rq = 1 2 F rq + 1 2 m (k-1) rq (5)

C. A novel construction

We present here a particular construction of the regiongraph for the Tanner code [START_REF] Tanner | A Class of Group-Structured LDPC Codes[END_REF] of length N = 155 with M = 93 parity-check equations. Its Tanner graph is a sophisticated concatenation of topological structures called Trapping-Sets (TS). A TS(a, b), introduced in [START_REF] Richardson | Error floors of LDPC codes[END_REF] and studied in [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF] among other, is a Tanner graph which contains a variable nodes and b unsatisfied parity-check equations. Here the TS(5, 3) (see Fig. 3) are sufficient to cover the whole Tanner graph. Such a structure is known to damage the decoding [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF] because only the total null state enables to verify all the parity-check equations. Thus to build the first level R 0 of the regiongraph, it would be relevant to absorb them into regions. However, the complexity of the message-passing would soar because these regions are too large. Therefore, we had better break these structures into several smaller regions as on Fig. 4 with:

• r = {X r = {x 0 , x 1 , x 3 }, C r = {c 0 , c 2 , c 6 }}, bit parity-check equation unsatisfied parity-chek equation x 0 x 1 x 2 x 3 x 4 c 0 c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8
Fig. 3. TS(5, 3) : 5 variables and 3 unsatisfied constraints X r , C r X p , C p X q , C q X r∩p∩q , C r∩p∩q Fig. 4. Region-graph of the TS(5, 3)

• p = {X p = {x 1 , x 2 , x 3 }, C p = {c 1 , c 4 , c 7 }}, • q = {X q = {x 1 , x 3 , x 4 }, C q = {c 3 , c 5 , c 8 }}.

D. Results

The region-graph of the TS(5, 3) is loop free which makes the decoding optimal. When we apply this construction to all the TS(5, 3) of the whole code, unfortunately we do not get a loop free region-graph because all the nodes belong to several TS [START_REF] Sankaranarayanan | Failures of the Gallager B Decoder: Analysis and Applications[END_REF][START_REF] Murphy | Loopy belef propagation for approximate inference: an empirical study[END_REF]. Nevertheless, the performance are still relevant to make the GBP a good candidate for the decoding.

We present on Fig. 5 the BER in terms of the iteration of the GBP on the Tanner code for error events, made by the noisy channel, that are truly harmful for the Belief Propagation particularly because of the TS(5, 3). On the Fig. 5(b) we can see the BER of the BP which is oscillating, making the decoding divergent and wrong. On the same figure is displayed the BER of the GBP. It clearly appears that such an algorithm does not bring any improvement if we do not use the uniform weighting, noticing that it is often worse than the BP that highlights the true lack of convergence of the GBP update. When this factor is set to 0.5 then the BER is dramatically reduced.

IV. DYNAMICS

In this section, we expose estimators to evaluate the dynamical behaviors of the GBP compared with the BP. To this end, we first define the mathematical environment in which these estimators are relevant.

A. State space definition and properties

To compare the dynamics of the BP and GBP, we need to define two state spaces that are similar. Using the fact that both are message-passing algorithms, we should consider the messages as the state variables. This choice fits perfectly with the convergence conditions written in the previous section for the GBP and written down here for the BP: We consider respectively {G ij } (i,j) and {F rq } (r,q) as two sets of iterated maps on the state variables {n

∀e ij , n (k) ji = n (k-1) ji (6)
(k)
ji } (i,j) and {m (k) rq } (r,q) which are called trajectories in the associated state spaces, denoted E BP and E GBP , whose dimensions are the number of messages to compute at each iteration. We denote by

U (k) = {n (k) ji } (i,j) and by V (k) = {m (k)
rq } (r,q) the points of the trajectories of the BP and the GBP.

B. Parameters and scaling

In [START_REF] Zheng | Study of bifurcation behavior of LDPC decoders[END_REF] the Signal to Noise Ratio (SNR) is used as a parameter in such a way that different values imply different dynamics of the BP. However, the most of their simulations are done for particular noise realizations scaled on the SNR, that prevents from evaluating a statistical behavior. A reason is that the noise realizations that lead the BP not to converge or to converge to a wrong estimate are rare events, essentially because the LDPC codes and the iterative algorithms are created to this end. A way to get statistical evaluations of the behavior of the BP and the GBP is the following:

1) finding some of these noise realizations, 2) storing the corresponding points {T (0) } in the state space, 3) for each T (0) , averaging the estimators for a sufficient set of initializations whose points in the state space are close enough to T (0) in the sense of the Euclidean distance. By this way, we can target the guenine critical values of the SNR for which the algorithms blatantly change in their behaviors, i.e. for which the algorithm undergoes bifurcations. However, we have to be cautious because our simulations have shown that the state space is not uniform, i.e. the statistical evaluations are relevant for each T (0) but averaging over them do not offer relevant statistics of the SNR critical values. This precision is crucial because it reveals that we do not work on the whole state space but only on subspaces of it where the systems, BP or GBP, do not behave trivially, that is to say we only deal with rare events. For all the estimators presented in the following of the paper, we use this method to get statistical results which are relevant enough to describe the behavior of the BP and the GBP.

C. Bifurcation diagram

A relevant method to extract the critical values of the SNR is the bifurcation diagram. For the explanation, we consider that we work on the BP. For a given noise realization, i.e. for a given T (0) inside E BP it consists in evaluating the value of a description function E computed from the state variables at their steady state k = K for J different values of the SNR. Obviously, there is no reason that the dynamic system reaches any steady state at iteration K but we need to suppose it for computation time's sake. We get a sequence E = [E 1 , . . . , E J ] that represents the behavior of the system in terms of the SNR. We consider the following function exposed in [START_REF] Zheng | Study of bifurcation behavior of LDPC decoders[END_REF] called the mean square beliefs: where the input sequence in the channel is [x 1 , . . . , x N ] and the beliefs are computed at the last iteration K of the algorithm. The property of this function that we consider here is that E j = 1 indicates that all the beliefs provide the ouput sequence equal to the input one, which is a successfull decoding. More generally, the amplitudes provides information about the decoding performance, and the variation between successive values gives us the critical values of the SNR. We display on Fig. 6 the mean bifurcation diagrams of the BP and the GBP for a given noise realization computed as we exposed in the previous subsection. We observe that for SNRs lower than 2.19 dB, the BP follows an increasing evolution. Such a behavior is analoguous to that of the GBP except that the critical value is 2.07 dB. When the SNR is greater than these two critical values, the algorithms follow two distinct dynamics. The BP seems to oscillate while the SNR is lower than 2.49 dB, and for values in [2.5 dB, 2.98 dB] however it does not appear any known evolution which is an indication of chaos. Concerning the GBP, it appears globally three intervals: in [2.08 dB, 2.43 dB] the shape of E j indicates irregular oscillations whereas for SNRs in [2.44 dB,2.69 dB] we cannot assert anything meaning that the chaos would appear. From 2.70 dB up to 3.02 dB, the GBP tends to the right decoding state whereas the BP does not present this behavior before 2.99 dB. Moreover the shapes of the two whole signals indicate that the GBP is globally beyond the BP one, that shows that the GBP tends faster than the BP to the right state.

∀j ∈ {1, . . . , J}, E j = 1 N N -1 i=0 b 2 i (x i ) (7)

D. Reduced trajectory

Another use of the mean square beliefs function is the representation of the trajectory in a 3-dimensional state space. To this end, we use the phase space reconstruction exposed in [START_REF] Hilborn | Chaos and Nonlinear Dynamics: An Introduction for Scientists and Engineers[END_REF]. The method consists in computing E at each iteration to get the following sequence

E j = [E j (k)] 0≤k≤K .
Afterthat we share this one dimensional sequence in a three dimensional sequence as follows:

Ẽj =    E j (0) E j (1) E j (2) . . . . . . . . . E j (K -2) E j (K -1) E j (K)    (8)
On Fig. 7 and Fig. 8 are displayed few reduced trajectories of the BP for SNR between the critical values computed previously. It appears for the BP four typical behaviors that match with the four intervals exposed in the previous paragraph. We obtain a very small sized attractor for SNR = 2.10 dB, whereas the reduced trajectory transforms to a limit cycle when the SNR is between 2.19 dB and 2.49 dB. A crucial point is that the thickness of the trajectory along this limit cycle increases as the SNR is getting greater up to 2.50 dB. Actually the limit cycle interleaves with other limit cycles, that is as a sequence of period doubling bifurcations, as is displayed on the figure 9 with two interleft cycles. Such a phenomenon is a typical route to chaos [START_REF] Alligood | Chaos: An Introduction to Dynamical Systems[END_REF], observable from 2.51 dB. A chaotic evolution means that there is not any periodic evolution or fixed point convergence anymore, as it is displayed for 2.70 dB. When the SNR reaches 2.99 dB the trajectory collapses to a single point that is a true fixed point. Concerning the GBP, whose reduced trajectories are displayed on Fig. 10 and Fig. 11, we cannot split the SNR values so accurately because the reduced trajectory does not transform as blatantly as the BP one. However, it is possible to distinguish also four different behaviors that follow the same order than that of the BP: small attractor, limit cycle, chaos and fixed point. The corresponding SNR intervals match with what have been revealed previously.

We have to be cautious because Ẽj is not a true trajectory, it does not respect the Cauchy-Lipschitz condition [START_REF] Hilborn | Chaos and Nonlinear Dynamics: An Introduction for Scientists and Engineers[END_REF] due to the non bijection between the messages and the beliefs. Thus, this sequence only has the role of giving clues about the true behavior of the considered algorithm as the possible shape of the actual trajectory in E BP or E GBP that are: convergence to a fixed point, convergence to a limit cycle and convergence to a chaotic attractor. To distinguish these shapes, we need a criterion that reflects the behavior by its own value. A good candidate is the Lyapunov exponent.

E. Lyapunov exponents

A well-known estimator to describe the dynamics of any dynamic system is the Lyapunov exponent λ [14], [START_REF] Hilborn | Chaos and Nonlinear Dynamics: An Introduction for Scientists and Engineers[END_REF], [START_REF] Wolf | Determining Lyapunov Exponents from a Time Series[END_REF]. Its computation consists in evaluating at each iteration

λ = ln d K d 0 (9)
Numerous papers have brought out the link between the sign of λ and the behavior of the associated system. Using the averaging method exposed previously, we compute λ for the same noise realization as in the previous subsections. We display it on Fig. 12. For SNRs lower than 2.19 dB, λ is closed to 0, that means that the trajectories neither move away one from the other nor get closer, there is no chaos but not fixed point either. The reduced trajectory indicated in that sense that this corresponded to a very small sized attractor. Then, λ crosses the x-axis, that is the sign of a bifurcation [START_REF] Hilborn | Chaos and Nonlinear Dynamics: An Introduction for Scientists and Engineers[END_REF], and it goes higher to a constant while the SNR does not go over 2.49dB, that corresponds to the limit cycle interval: the trajectories turn around. Once the SNR exceeds this value, after a x-axis crossing indicating a new bifurcation, λ soars which is a sign of chaos, confirmed by the reduced trajectory displayed previously at 2.70dB. It means that the trajectories are close at the beginning but they quickly change behavior and they move away one from the other. From 3.1dB λ falls to negative values. It means that the trajectories get closer to the same fixed point, it is stable. Concerning the GBP, λ can provide pieces of information as the first critical values of the SNR, 2.08dB, that is to say the SNR for which the algorithm becomes unstable. From 2.08dB to 2.43dB, λ is getting greater, that corresponds to the irregular oscillations given by the bifurcation diagram. We observe a peak at 2.44dB, that matches with the beginning of the transcient chaos illustrated by the reduced trajectory. The last critical values that we can read is 3.02 dB where the GBP tends to the right decoding state according to the bifurcation diagram.

F. Hyperspheres method

We see that it is not trivial to extract information about the stability of the GBP due to its particular update equations. So Reduced trajectory for the GBP on the Tanner code with SNR = 2.80 dB and 3.00 dB it seems necessary to include other tools to the investigation to raise more relevant conclusions.

We propose here a novel method to evaluate the unstability of the BP and the GBP, based on their own trajectory in E BP and E GBP . This method is complementary to the Lyapunov exponent because it reveals the size of the attractor that the trajectory falls into and other properties about the attractors.

This method consists in computing the radius R k of the hypersphere circumscribed to the trajectory inside a given temporal window centered around a point U (k) (or V (k) ) of the trajectory. By dragging the window, we obtain a sequence of radii. On Fig. 13 are displayed for the BP the parallel evolutions of two radi that correspond to two initially close trajectories in the Euclidean sense. We only display for SNR that correspond to chaos i.e. for SNR greater than 2.49 dB. For SNR in [2.19dB, 2.49dB] simulations show that both radii oscillate at the same frequence of 23 iterations. For lower SNR the raddi do not change a lot, their values are close to O that correspond to the small sized attractor exposed by the reduced trajectory. At 2.70 dB, on Fig. 13, the radii moved away one from the other as it was predicted by the Lyapunov exponent observations. More accurately we can see that the radii have different oscillation steps. This is due to the period doubling bifurcations explained previously. During 92 iterations in average over numerous trajectories, for k ≤ 500, the trajectories are trapped in limit cycles of period 23 iterations, for the next 92 iterations they fall into other limit cycles of different radii but same period. For k ≥ 500 we observe a sequence of period doublings that lead to the chaos. Such an observation makes our method relevant to bring out crucial information by a one dimensional function. Another important aspect of the hyperspheres method is the raising of the behavior differences between two initially close trajectories: we easily observe that the evolution of the radii cannot be distinguished while k ≤ 200 but as k is getting greater, the evolution of the radii differentiate even though they follow the same kind of dynamics. For both of them the hypervolumes of the state space in which they are locking in, that is the hypervolumes circumscribed to the attractors, are quite of the same size. When the SNR reaches the last critical value we observe that one of the radii decreases to the null value because the BP has converged to a fixed point. The other radius has not collapsed yet because the SNR is just at the critical value, if it was increased a little we would see the two radii going to zero. Concerning the GBP, for low SNR values we did not display the evolutions of R k because it follows quiet the same dynamics as that of the BP. On Fig. 14, at SNR = 2.70 dB we observe that the radii of the trajectories are quite smaller than that of the BP. Furthermore, the maximum value of the radius is still lower than the minimum value of the BP radius. The comparison between both radii on the GBP makes us deduce that even though each trajectory eventually reaches a particular attractor of the state space, their size are not very different and they collapse at the end. Because this is not the case about the BP, the GBP appears more stable than the BP for the suited construction we have proposed.

V. CONCLUSION

In this paper, we have presented a novel method of construction of the region-graph for the GBP algorithm based on the topology of the Tanner graph. The results have shown that the error correction power was improved compared with the BP one. Furthermore it appears that the GBP was more stable than the BP. To uphold this assertion, we have used classical estimators of the dynamics. The results provided four different dynamics of that depends on the SNR values. To get more details about the dynamics of the GBP that turned out to be non trivial compared with that of the BP, we introduce a new estimator, the radius evolution of the circumscribed hypersphere. The results highlighted that the GBP converges towards small sized attractors contrary to the BP, even for transcient chaos. Finally, this work leads to conclude that a suited region-graph construction provides a good candidate to surpass the famous BP. Furthermore, the construction we propose for the Tanner code can be adapted to any other LDPC code provided that it is covered by a set of TS(a, b). In future works, we propose to find a mathematical criterion to evaluate the relevancy of any region-graph according to the associated GBP performance. Also we propose other handlings of the TS(5, 3) to build region-graphs that could present better correction power and improved stability.

BPFig. 5 .

 5 Fig. 5. BER of the BP and the GBP on the Tanner code with the suited region-graph construction

Fig. 6 .

 6 Fig. 6. Bifurcation diagrams of the BP and the GBP

Fig. 8 .Fig. 9 .

 89 Fig. 8. Reduced trajectory for the BP on the Tanner code with SNR = 2.70 dB and 3.00 dB

Fig. 12 .Fig. 13 .Fig. 14 .

 121314 Fig. 12. Lyapunov exponents of the BP and GBP on the Tanner scaled on the SNR