An Induction Scheme of Fast Initiative-Evacuation Based on Social Graphs

1. Introduction

During hurricanes, we determine the areas most vulnerable to damage. This conventional system encourages residents to evacuate when an evacuation order is issued by local governments (or authorities). Residents prevent damage by completely evacuating prior to the occurrence of strong wind and heavy rain. However, people are not psychologically keen on early evacuations.

Among factors that prevent people from evacuating, the concepts of “normalcy bias,” “reverse function of experience,” and “cry wolf effect” exist [1-3]. “Normalcy bias” implies that we cannot take appropriate actions because we feel okay even when faced with an unusual condition. A “reverse function of experience” expresses that this case will not cause problems because of experiences in past disasters. The “cry wolf effect” decreases the reliability of evacuation requests by authorities due to repeated false alarms. These concepts can explain the factors that delay or ignore evacuation behavior.

A trigger to initiate evacuation is vital because of the factors that delay evacuation. The initiative-evacuation and its executors, initiative evacuees, are factors that can lead to other evacuations [4,5].

The initiative evacuees take the initiative in evacuating and call out to their surroundings. Other people can easily recognize the need for evacuation and decide to evacuate. Although these are face-to-face actions, evacuation warnings have been announced via social network services (SNS) or online communication tools in recent years. With online tools, initiative evacuation can be more feasible and widely affected quickly.

This study focuses on the importance of the initiative evacuees and aims to reduce the evacuation time. Existing studies analyzed the perspective of people who did not evacuate through post-disaster surveys, and many studies highlight the importance of initiative evacuees as a trigger for evacuation. However, existing studies fail to mention how the differences in initiative evacuees affect the evacuation time and how to request initiative evacuation. The contributions of this study are to propose an induction method of initiative evacuation based on social graphs [6], and to confirm that the proposed evacuation scheme can reduce evacuation time. The novelty of this study lies in the arbitrary selection of evacuees. This study is an enhanced version of [7] and provides more detailed explanations with additional simulation results.

Section 2 describes related work. The proposed fast induction method and its evaluation are described in Sections 3 and 4, respectively. Discussion and conclusion are provided in Sections 5 and Section 6, respectively.

2. Related Work

2.1 Cry Wolf Effect

“The cry wolf effect” is a mechanism that prevents people from evacuating fast. It decreases the reliability of alerts or authorities through repeated false information about disasters.

Rigos et al. [3] investigated the cry wolf effect and proposed an equilibrium solution using game theory between the local government (authority) and evacuees. The local government and evacuees are the two players, and their strategies are configured. The local government decides whether to request evacuation, and evacuees decide whether to evacuate. Subsequently, the optimum solution is searched for by sequential equilibrium to maximize player gains. The accuracy of the signal is also classified into three stages for alarm systems, such as a smoke detector. The accuracy stage affected the optimum actions of the local government and evacuees. When evacuation drills are conducted without prior notice, we must carefully evaluate the benefits obtained from the training and reliability reduction caused by the cry wolf effect. Furthermore, the authors of [3] mentioned that improving the accuracy of equipment, such as fire alarms, for threat detection is important in preventing inefficiency caused by the cry wolf effect. However, technical restrictions make it difficult to improve the accuracy of these types of equipment.

2.2 Initiative-Evacuation

Initiative evacuees are one of the reference information sources and are those who take the initiative to evacuate while calling out to their surroundings. Existing studies found that initiative evacuees affect the evacuation of others. In the case of terrorism, tsunami, and sediment-related disasters, it is difficult to recognize the danger of an increase such as flooding of rivers. Hence, the presence of leading evacuees significantly promotes fast evacuations. We can call for evacuations through online text messages using SNS. The influence of initiative evacuees is limited to places within their line of sight or the reach of their voice. Therefore, studies visualize the behavior of initiative evacuees in real time using Internet of Things technology. If such a system is implemented, the initiative could produce more follow-up evacuees.

Urata and Hato [4] evaluated the probability of the formation of a network structure between evacuees and the probability of evacuation in that network structure. They also analyzed evacuees by considering detailed factors, such as location, age, health condition, and distance between evacuees. Kuhlman et al. [5] predicts that the evacuation rate will likely decrease because of crime concerns with a high rate of neighbor evacuations.

3. Proposed Method

This paper proposes a fast induction method based on social graphs for initiative-evacuation. This study determines how to select leading evacuees that will shorten the evacuation time. In comparing evacuation times, we equalized the number of leading evacuees for each method.

3.1 Overview

An incentive is an effective technique to reduce evacuation time. However, each authority can only provide incentives in the affected area according to their specific financial constraints. The success rate decreases if authorities reduce the number of incentives per person to provide for more people. Although additional discussions are required in the future, we propose a method to provide sufficient incentives for specific people in disaster areas. In addition, initiative evacuees evacuated themselves and induced other evacuations. Therefore, the proposed method does not randomly determine candidates for incentives, but determines them based on their effectiveness as initiative evacuees. The evacuation completion rate and time can be improved if candidates evacuate effectively as initiative evacuees and efficiently encourage other people to do so. In this study, “efficiency” means that more people evacuate in a shorter time at a limited cost. Fig. 1 shows the system structure and process flow of the proposed method. The following are the six procedures of the proposed method:

1. Authorities detect a disaster from observation equipment.

2. Authorities decide whether to issue an evacuation order considering the risk of a disaster.

3. Authorities collect information about the social graph.

4. The local government decides who will take the initiative by referring to the number of links of the evacuees.

5. Authorities request initiative evacuation from the candidates by incentives.

6. Initiative evacuees evacuate and provoke other evacuations by notifications to the linked nodes.

This study assumes that people construct a specific social graph, and the candidates are determined based on this social graph. It also assumed that people could communicate with each other based on social graphs. This study also assumes that the timing to collect information about the social graph and provide incentives is after the disaster or it is periodically executed in advance. This study disregards evacuation announcements depending on specific areas and locations in real situations.

3.2 Social Graph

Social graphs represent the social relationships among people [6]. People are assigned to nodes (vertices), and relationships are assigned to links (edges). The social graph is also called a “social network” [8-10]. In addition, social network sensors immediately detect crises by analyzing social networks in real time [11-13]. Alternatively, this study aims to accelerate evacuation by propagating messages from initiative evacuees based on social graphs.

Graphs are roughly classified as directed or undirected graphs. This study assumes that undirected graphs with bidirectional links represent the relationships because the linked people know each other. Fig. 2 shows an instance of a social graph when the total number of nodes is eight. The table on the right shows the number of links at each node in descending order. Fig. 2 also shows that the maximum number of links is seven, and the minimum number is one. Social graphs represent the relationships among people, and the number of links (degree) is biased for each node. Bias is represented by scale-free networks, where the degree follows the power law. The difference in the number of links is increased by the scale and number of total nodes.

3.3 Induction of Initiative-Evacuation

Social graphs exhibit bias in the number of links on each node (people). The proposed method collects information about social graphs and determines candidates for initiative evacuees under a limited number of incentives. The candidates are determined in descending order of the number of links on each node. Much-linked nodes can affect other nodes as initiative evacuees and accelerate the entire evacuation. Money, goods, and online coupons are such incentives. We assume that authorities request initiative evacuation via e-mail, SNS, or other online communication tools. Similar to the request by authorities, initiative evacuees affect other evacuations through online communication tools. Face-to-face communication and propagation by a third party are also expected. In practice, these evacuations are affected by people’s situations, personalities, and relationships with others. Although a large number of private information must be collected to consider many factors, the proposed method is highly feasible because it determines the candidates based only on the number of links on each node.

In the proposed method, the total number of sent messages for the first time 0 after receiving the authority’s request, [TeX:] $$m_0$$, is calculated as

where [TeX:] $$d_k$$ is the number of links in the k-th candidate of n initiative evacuees. In addition, the maximum number of messages sent at time [TeX:] $$t(1 \leq t) m_t$$ is calculated as

where [TeX:] $$\bar{d}$$ is the average number of links in all nodes and [TeX:] $$m_{t-1}$$ is the number of messages sent in the previous time t – 1 if there is no delay in receiving the messages. Further, [TeX:] $$m_t$$ is the geometric progression, and its total amount from time 0 to t, [TeX:] $$S_t,$$ is calculated as

Eqs. (2) and (3) represent the theoretical maximum values because not all the nodes always evacuate and send messages to all their linked nodes, even if they receive messages from evacuees. However, Eq. (3) shows that the first sent messages are important for the messages sent after and their total amount.

4. Evaluation

This study evaluates the proposed method through simulation.

4.1 Simulation Environment

Simulations are often used because the effect of the method cannot be confirmed in actual disasters [14,15]. Multi-agent simulation (MAS) is performed on a computer using multiple agents. Complex situations can be reproduced by describing the interactions between the agents. We used artisoc Cloud [16] as the simulator. The artisoc Cloud is a multi-agent simulator that designs social systems. By describing the actions of agents and the interactions between them, the artisoc Cloud can observe changes at each step (unit time). Several types of social graphs represent social relationships. This study assumed that the social graph is scale-free, where some of the nodes have multiple links. Scale-free graphs can be generated using the Barabashi-Albert (BA) model. The BA algorithm generates a graph by adding nodes one by one.

When a new node is added, the number of links is biased at each node because the probability of connecting to other nodes is increased by the number of already constructed links. This simulation had 100 nodes. In addition, the total number of links is approximately 300. Graphs were generated using random numbers, and different graphs were used each time. Fig. 3 shows an example of the generated social graphs. This simulation measured the number of steps required to complete the evacuation for each node. In Step 0, the determined initiative evacuees begin evacuation. The determination was based on the following five methods:

1. l% of the nodes in ascending order from the smallest number of links.

2. l/2% nodes in ascending order and l/2% nodes at random; total l% nodes.

3. l% nodes at random.

4. l/2% nodes in descending order and l/2% nodes at random; total l% nodes.

5. l% of the nodes in descending order from the largest number of links.

Here, l represents the rate of the requested initiative evacuees (%). This study used 20% and 10% as l. In method 1, all nodes are sorted by the number of links, and l% nodes become initiative evacuees in ascending order from the smallest links. In method 3, l% of nodes becomes initiative evacuees randomly from all nodes. The compared method 2 combines methods 1, 3, and l/2% nodes to become initiative evacuees. The proposed method 5 sorts all nodes by the number of links, and l% of nodes becomes initiative evacuees in descending order from the largest links. The compared method 4 combines methods 3, 5, and l/2% nodes to become initiative evacuees. For the decision to evacuate, each node evacuates if over x% of the linked nodes have already evacuated. x is the threshold, and this simulation employed 30% and 15% thresholds. For x = 30 and node e in Fig. 2, node e evacuates if at least one of the three linked nodes has evacuated. In addition, this simulation configured the delay time for each node because the time to communicate or decide to evacuate is different for different people and environments. The average configured delay is five steps, and the standard deviation is one step, following a normal distribution. Each node starts evacuation and announces it to the linked and unevacuated nodes if over x% of the linked nodes have already been evacuated. This simulation was executed 100 times for each method, l, x, and the average evacuation time was calculated. A social graph is generated for each simulation. In the real world, people send online messages until evacuation is complete. Therefore, this simulation also measures the number of messages sent at each step as loads to the communication network. For node e that had already evacuated and node b that began to evacuate, three messages were additionally counted at this step because messages were sent to linked nodes a, c, and d. Similar to the evacuation time, the average number of messages was calculated from 100 examinations for each method, l, and x.

Next, the simulation conditions for adding weights to the links are described. The link weight represents the reliability between nodes. Additionally, three types of evacuation criteria were established. The link weights were generated using the Zipf distribution [17] and then given individually for all links. For instance, Fig. 4 shows the Zipf distribution when the number of links was 300. The horizontal and vertical axes represent the rank and the normalized frequency of each rank, respectively. Only a few links are assigned high reliability, and most are assigned low reliability. The Zipf distribution was obtained using the following formula:

Here, C represents the total number of elements, and n represents the order (subscript). s satisfies s≥ 0 and the bias of the value changes depending on s, but this study set s = 1. The total number of links was obtained by adding all the links possessed by each node, and the value was set to C.

The weights of the links are set asymmetrically, and the reliability of evacuation target person A to evacuation target person B and the reliability from evacuation target person B to evacuation target person A differ. For evacuees, the evacuation criteria may differ depending on internal factors, such as risk due to personality and terrain and whether it is difficult to move.

The evacuation criteria are listed in Table 1. Type A evacuees were assumed to be elderly people who had difficulty moving. According to the Japanese government, the population aged 65 and over was 36.19 million, and the aging rate was 28.8% on October 1, 2020. The number of people who have difficulty moving is less than the aging rate of 28.8%, and the proportion of type A is 25%. Half of the remaining evacuees were type B and reluctant to evacuate, while the rest were type C and positive. For types A and B, thresholds x are added by 0.2 and 0.1, respectively. Regarding the completion of evacuation, considering that evacuation criteria are strict, depending on the type, evacuation is considered completed when 80% of the evacuees are evacuated. Therefore, we could not simply compare the evaluation results when no weight was added.

4.2 Results without Link Weights

Fig. 5 shows the relative frequency of evacuees at each step, where the rate of initiative evacuees is l=20, and each node evacuates if x=30% of the nodes have already evacuated in the linked nodes. The vertical axis represents the normalized frequency of completed evacuation, and the horizontal axis represents the steps. Fig. 6 shows the cumulative values of the same results. In both figures, methods 1–5 are plotted in blue, orange, green, red, and purple, respectively.

In Fig. 5, the proposed method 5 completes all evacuations in Steps 9–16. The worst-case scenario is when the proposed method finishes approximately l/2 of the steps in method 3. Although methods 3–5 finished evacuations in all examinations, methods 1 and 2 had cases in which some nodes had incomplete evacuations. This is because all the nodes cannot overcome the threshold x=30% midway, and no messages are sent among the nodes. Once nodes come to this situation, some of the evacuations cannot be completed even if additional steps pass.

Figs. 7 and 8 show the results when the parameters are l=20 and x=15%. Method 3 finished all evacuations in Steps 11–17. Methods 5 and 4 were completed in Steps 7–12 and 8–15, respectively. Compared with the case of x=30, methods 1 and 2 also completed all evacuations. In addition, the evacuation time was reduced in all methods, and the differences among the methods were reduced.

Figs. 9 and 10 show the results when the parameters are l=10 and x=30%. T he proposed method five frequently took approximately 15 steps to finish. Method 4 is frequently finished at Step 18. Method 3 was completed in many steps until Step 55. Compared with the case of x=30, approximately five steps were increased in methods 4 and 5. In addition, the evacuation time was significantly increased in methods 1–3. In particular, method 1 did not complete almost all evacuations. Fig. 10 shows the cumulative values obtained from similar results. Methods 4 and 5 finished at approximately Step 22. In contrast, methods 1–3 did not finish until Step 22 in most cases.

4.3 Number of Messages

Figs. 11 and 12 show the number of messages and their cumulative values at each step, respectively. The number of nodes is 100, the rate of initiative evacuees is l=20, and each node evacuates if x=30% of the nodes have already evacuated in the linked nodes. Fig. 11 shows the total number of messages sent from the nodes in each step, and Fig. 12 shows the cumulative values. The number of messages in the first step (Step 0) differs for methods 1–5. From Steps 0–5, a few messages were sent. This is because the initiative evacuees begin evacuating at Step 0, and a randomized delay is configured on each node to send messages. The number of messages was sorted by methods 5, 4, 3, 2, and 1 in descending order. The amount of change and cumulative values were in the same order. Methods 4 and 5 sent messages until Step 10. The cumulative values increased by approximately 100 and 70 for methods 4 and 5, respectively. In method 3, the cumulative value of the messages increases gradually from Steps 5 to 22, and the cumulative value is approximately 250. Although method 2 had almost the same cumulative value as method 3, the completion rate of evacuation was lower. The efficiency of evacuation induction significantly decreases if the initiative evacuees are determined from less-linked nodes.

4.4 Results with Link Weights

The result of adding weight to the link and incorporating the difference in the evacuation criteria is shown in Fig. 13. The parameter values were the same as those shown in Fig. 5, with l=20 and x=30. As a result of the completion of the evacuation, due to the difference in the selection method of initiative evacuees, the descending order was the fastest, and the order did not change. The completion rate for selection methods 4 and 5 is 1.0, but the evacuation completion rate is low for selection methods 1, 2, and 3. Compared with Fig. 5, the graph in Fig. 13 shows a lower evacuation completion rate in selection methods 1, 2, and 3. However, there is no change in the order of the graphs owing to differences in the selection method.

5. Discussion

This paper describes a fast induction method for an initiative-evacuation based on social graphs. The simulation results of the proposed method show that the evacuation time is significantly reduced when initiative evacuees are determined from the much-linked nodes. Even when the percentage of evacuees who take initiative l, the threshold value when the node evacuates x and the evacuation criteria are applied by adding weights to the links. The results show the same tendency in each simulation. We also confirm the number of messages sent as loads to the communication network. Regarding the number of messages, the number of messages in the first step differed significantly depending on how initiative evacuees were determined. There was also a difference in the cumulative number of messages. For the combination of descending and random orders, the results were often close to those obtained when a purely descending order was selected. In all the determination methods, the order was descending, descending, random, random, ascending, random, and ascending, in order from the fastest. In addition, the effect of the proposed method was greater when the rate of initiative evacuees was low, and the threshold value when the node was evacuated was high. From the above, much-linked nodes should be determined as initiative evacuees to achieve quick evacuation for many evacuees under limited incentives. In addition, if the number of nodes with many links is limited, a random determination can be combined because the simulation results do not show large differences from the fully descending order.

In addition, the transmission of evacuation information is not uniform because the degree of human relations differs. When selecting the initiative evacuees, better results can be obtained by considering the number of links and the weight of the number of links and by selecting a person with many acquaintances and high reliability. However, in reality, it is difficult to accurately obtain weights owing to privacy issues. Therefore, we determine whether the link connection status is unidirectional or bidirectional and highly value those that have many bidirectional links.

This study mainly investigated whether the evacuation completion time differed depending on the determination method of the initiative evacuees, but did not consider the incentive parameters in the model. We change the incentives given to those who have many links and those who do not and then investigate how to select the initiative evacuees who minimize the time to complete evacuation after setting constraints on the total amount of incentives. Moreover, the current location is not considered in the proposed model. In the real world, the range in which the initiative evacuees can induce the evacuation of the surrounding residents is limited to the range in which the voices of the initiative evacuees can reach and be visible. Therefore, there might be a difference on whether evacuation behavior is adopted between those who are vulnerable to damage and those who are not. In the future, we will conduct a simulation that considers the current location of each evacuee.

6. Conclusion

This paper proposed and evaluated a high-speed method for inducing evacuation based on a social graph. In the proposed method, based on the social graph, we requested an evacuation target (node) with many links to take the initiative in evacuation using incentives. The requested evacuees take the initiative to evacuate many people by evacuating the target of the link connection destination. The evaluation involved the simulation with and without weighting the links, and the transition in the number of transmitted messages was investigated. We confirmed that the evacuation time was reduced compared to when the evacuees were randomly selected regardless of the weight of the link. Multiple messages were observed during the early stages of evacuation.

In future work, we plan to consider geographical factors and use data that conforms to reality. We also confirm the effectiveness of the proposed method in a specific simulation environment with 100 nodes and approximately 300 links. We also plan to evaluate the proposed method in a large-scale environment.