{'fraction_non_alphanumeric': 0.025519340974212035, 'fraction_numerical': 0.006044054441260745, 'mean_word_length': 4.756958762886598, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Novel Routing Method for Social Delay-Tolerant Networks

The lack of continuous connectivity and a complete path from source to destination makes node communication quite difficult in Delay-Tolerant Networks (DTNs). Most studies focus on routing problems in idealized network environments without considering social properties. Communication devices are carried by individuals in many DTNs; therefore, DTNs are unique social networks to some extent. To design efficient routing protocols for DTNs, it is important to analyze their social properties. In this paper, a more accurate and comprehensive metric for detecting the quality of the relationships between nodes is proposed, by considering the contact time, contact frequency, and contact regularity. An overlapping hierarchical community detection method is designed based on this new metric, and a tree structure is built. Furthermore, we exploit the overlapping community structure and the tree structure to provide message-forwarding paths from the source node to the destination node. The simulation results show that our Routing method based on Overlapping hierarchical Community Detection (ROCD) achieves better delivery rate than SimBet and Bubble Rap, the classic routing protocols, without affecting


Introduction
Delay-Tolerant Networks (DTNs) [1] are challenging networks, as they lack continuous connectivity between nodes, and a complete path from source to destination does not usually exist or is quite unstable and could break down at any time. Some examples of these networks are interplanetary networks, sensor networks for wildlife tracking, rural area networks, and pocket switched networks; these networks operate in mobile environments, extreme terrestrial environments, and planned networks in space. Designing an efficient routing protocol for DTNs is a key concern because of the characteristics of DTNs.
Many communication devices are carried by individuals who tend to form communities [2][3][4] , and members of the same community tend to contact one another more often than members of different communities; therefore, using the community structure helps to improve the routing performance of DTNs. In real scenarios, one member may belong to more than one community, resulting in community overlapping, and these kinds of members play a crucial role in the network in bridging communities [5] . For example, when delivering a message from a source node in one community to a destination node in another community, it is best to first forward the message to nodes that can bridge these two communities, as shown in Fig. 1.
In a network environment, communication devices are carried by the existing individuals, who tend to form communities; therefore, individuals with strong friendships could form a community. When a message needs to be forwarded from a source to a destination, the source should decide which individual to forward the message to those encountered. In this study, a more accurate and comprehensive metric for detecting the quality of the relationships between nodes is proposed, in which the contact time, contact frequency, and contact regularity are considered. An overlapping hierarchical community detection method is designed based on this new metric, and a tree structure is built. Furthermore, we exploit the overlapping community structure and the tree structure to provide a messageforwarding path from a source node to a destination node.
In this paper, we first present a new comprehensive metric that considers both the frequency and the length of contacts, and a social graph is constructed based on this metric. An overlapping hierarchical community detection algorithm is designed, and an efficient routing method is proposed based on overlapping communities.
The main contributions of the paper are as follows: (1) We consider a more accurate metric to detect relationships between every two nodes and view contact regularity as a penalty parameter.
(2) Social network analysis is used in DTNs. Overlapping community structures are detected in a tree structure for efficient message routing.
(3) The tree structure is also exploited to forward messages, which results in a hierarchical structure to the routing strategy.
The rest of this paper is organized as follows. Section 2 presents a brief overview of previous studies. Section 3 provides a comprehensive metric to measure the relationships between nodes; in this section, the overlapping hierarchical community detection algorithm and the routing method based on the overlapping community are examined. In Section 4, the simulation results are discussed, and finally, the paper is concluded in Section 5.

Related Work
Most of the previous routing protocols fall into three categories: multi-copy-based, single-copy-based, and erasure coding-based. In the first category [6,7] , the system keeps more than one copy of the same message, which can be forwarded independently to improve robustness and delivery ratio. However, too many copies may lead to congestion and large overheads. In single-copy-based routing protocols [8,9] , only one copy of each message can exist in the network. In the third category [10,11] , numerous relays are allowed while a constant overhead is maintained, which results in fewer cases of long delays.
In some scenarios (e.g., pocket switch networks), node movements are not random, and the social relationships between nodes directly affect the contacts. Several studies have been performed on the use of inherent social properties to improve routing performance [12][13][14][15] .
In Ref. [16], SimBet Routing is proposed, which exploits the exchange of pre-estimated betweenness centrality metrics and locally determined social similarity to the destination node. It is a utilitybased routing scheme, and all utilities are calculated based on the contact graph. However, the contact graph changes substantially over time in DTNs, which leads to inaccurate utility calculations. Hui et al. [17] proposed the Bubble Rap routing protocol, which uses two social and structural metrics: centrality and community. Bubble Rap detects community using a social graph, but it only considers the number of contacts and contact duration when calculating relationships between nodes. Bulut and Szymanski [18] defined a new metric called social pressure metric and proposed a local community formation based on this new friendship detection metric, which contributed to the high performance of the forwarding strategy. One study [19] provided a framework that formalized the distributed version of the community detection problem for a general model of the dynamic network and presented an efficient provably good coloring task of the dynamic graph. Zhu et al. [20] summarized the positive and negative properties of DTNs, provided a survey of the recent social-based DTN routing protocols, and discussed some open issues and challenges in socialbased approaches. In Ref. [21], Li and Wu presented a community-based epidemic forwarding scheme that efficiently detects the community structure using limited local information and improves the forwarding efficiency based on the community structure.
In this paper, we introduce a new routing algorithm different from those of above studies. We define a more comprehensive and accurate metric and propose an overlapping hierarchical community detection algorithm based on this new metric. Then, we exploit the community structure and the tree structure for efficient message forwarding.

Analysis of node relationships
Detecting the relationships between nodes is the most important aspect of constructing a social graph from a recorded contact graph; it affects the accuracy and efficiency of the social-based routing protocols. Several properties of the contacts are considered to acquire the social relationships [18] , such as the total or average contact duration, encounter frequency, shortest separation period, and average separation period. Here we adopt a new comprehensive metric that reflects the contact frequency, contact duration, and contact regularity. As expected, two nodes that make frequent and regular contact and keep contact for a long time have better relationships, and the weight of the edge between them is higher.
Considering contact frequency and duration, the edge weight between the nodes a and b is defined as follows: where m denotes the total number of contact periods during the time interval OE0; T . The function f .t/ returns the remaining time of the first contact after time t . When the nodes are not within communication range, The contact record of the nodes a and b (shown in Fig. 2) can be rewritten as follows: 2m The fluctuation in the separation period is not neglected, and contact with even distribution is preferred. Therefore, an irregularity metric l a;b , which is used to measure the uniformity as shown in Eq. (3), is defined as We view the irregularity value as a penalty on the edge weight between the nodes a and b; the edge weight is defined as where˛denotes the penalty parameter.
In the network graph G D .V; E/, V is the set of all nodes, and E is the set of all edges. The metric measuring relationship of all the nodes in G is defined as where n denotes the number of nodes in the graph G. Based on the above formulas, a social graph can be constructed in which the vertex represents the communication node, and the edge weight represents the relationships between the nodes. If the edge weight between the nodes a and b is less than a certain threshold, there will be no edge between them.

Overlapping hierarchical community detection algorithm
Community is an important attribute of human society, and nodes in the same community meet one another much more often than the average inter-meeting time. This is a concept from ecology and sociology. Communication devices are almost always carried by individuals; therefore, it is easy and reasonable to extend the concept of social community to DTNs [22,23] . Nodes in the same community of DTNs tend to contact one another more often [24,25] , which improves the routing performance. Furthermore, the community does not change much because the social ties between the nodes are quite stable over time.
Overlapping community is an important expansion of traditional community, and it is natural that a node may belong to several communities in real life scenarios. Such common nodes can serve as bridges. Detecting overlapping communities is the preliminary task of community-based routing protocols. The input of the overlapping hierarchical community detection algorithm, which is described in Algorithm 1, is the social graph constructed in Fig. 3.
Assuming that the weighted graph of the entire network is constructed as shown in Fig. 3, by applying Algorithm 1 to the graph, a tree structure corresponding to the network topology is obtained as shown in Fig. 4.
The set C obtained by Algorithm 1 contains some clusters that have inclusion relationships as well as clusters without strong relationships between nodes. It is necessary to tailor the set C . All elements in C are ordered by W G , and elements that are less than a threshold are deleted from C . If one element c 1 of C is included in the other cluster, it is also deleted. Some nodes may not be contained in any cluster after tailoring, and these nodes are viewed as independent clusters. Taking the tree structure in Fig. 4 as an Algorithm 1 Overlapping community detection algorithm 1: Define all the edges whose weight exceeds a thresholdˇas set E i , all the nodes that are the vertexes of edges in E i as set v 0 , and every two nodes that are linked by the edge in E i as set g i . 2: Each node that is contained in the set .V v 0 / is assigned the set g 0 i , and the union of all g i and g 0 i is assigned as V k , where V k D fv i ji D 1; 2; ; ng, which represents the initial clusters of the algorithm. 3: If jV k j > 1, proceed to step 4; otherwise proceed to step 6. 4: Examine V k , and calculate the metric W G , where G is the subgraph constructed by any two clusters in V k . The union of two clusters v i and v j with the largest value of W G as v i;j is set as V k D V k [ fv i;j g fv i ; v j g. 5: Include v j i in set C , and return to step 3. 6: A tree structure is obtained at the end of the algorithm and all non-leaf clusters are included in the set C .  example, and assuming that D 0:6 after tailoring, the set C is ffA; B; Eg; fB; C; F g; fDgg.
Thus, we can obtain some communities that may overlap one another and form a tree structure; this is the foundation of our community-based routing.

Routing based on overlapping communitiess
Once the hierarchical structure is constructed, to forward a message, a message-carrying node can find a forwarding path from the source to the destination by using the structure. The common nodes of the overlapping communities can serve as bridges that link different communities. The utility for the path preferences is defined as Thus, we can use the tree structure to find the path with the highest value of P path and forward the message according to this path. Without loss of generality, let us assume that there is a source node s, which intends to send a message to a destination node d , if s and d are in the same community, there are two scenarios: intracommunity routing and inter-community routing. Intercommunity routing can be divided into one-hop intercommunity routing and multi-hop inter-community routing based on whether the communities overlap one another. Details of the routing method are as follows: (1) Intra-community routing. Intra-community routing occurs when the source node s and the destination node d are in the same community c 1 . First, c 1 is located in the tree structure, and by going through the children nodes of c 1 , the smallest cluster c 1 (in some situations c 0 1 is c 1 considering that c 1 may be the smallest cluster) that contains both s and d is found. All the nodes in c 1 are the routing nodes. The routing path with the highest c path from the nodes s to d can be determined, and it is thought to be the optimal path. For instance, in Figs. 3 and 4, when the node A wants to send a message to node B, and these two nodes are in the same community fA; B; Eg, a smaller cluster fA; Bg is found in the children nodes of fA; B; Eg, and it is easy to determine that the optimal path is directly from A to B.
Inter-community routing occurs when the nodes s and d belong to different communities. In this situation, a forwarding path between the two nodes consists of a community path set and a node path set.
One-hop inter-community routing occurs when the communities c s and c d of the nodes s and d overlap each other and have at least one common node. If one of the common nodes is chosen as the bridge node b, then, the community path is composed of c s and c d . The intra-community routing method is used to find paths from the node s to the bridge node b and from the bridge node b to the destination node d .
Multi-hop inter-community routing occurs when the communities c s and c d of the nodes s and d are independent; i.e., they do not have any common node. After going through the tree structure, the smallest cluster c s;d that contains both the nodes s and d is found. Then, the shortest community path that can bridge c s and c d is determined by going through the children nodes of c s;d . Then, the bridge node between any two neighboring communities is identified. The intra-community routing scheme can be used to find the optimal path from the source node s to the bridge node, the bridge node to the bridge node, or the bridge node to the destination node d (if the destination community and the penultimate community on the community path overlap each other). For instance, in Figs. 3 and 4, assuming that the node A wants to send a message to node D, and these two nodes belong to independent communities fA; B; Eg and fDg. The smallest cluster in the tree structure that contains both A and D is fA; B; C; E; F; Dg. By examining its children nodes, we can determine that the shortest community path is fA; B; Eg, fB; C; F g, and fDg. The bridge node is B, and the optimal path is fA; B; C; F; Dg.

Performance Evaluation
In this section, we describe the simulations used to evaluate the performance of our Routing method based on Overlapping hierarchical Community Detection (ROCD) and compare it with SimBet and Bubble Rap.

SimBet and Bubble Rap
SimBet is a utility-based routing protocol. It exploits the betweenness centrality metric and similarity metric to determine the message-forwarding strategy. Centrality in graph theory and network analysis is a quantification of the relative importance of a vertex within a graph. To calculate betweenness centrality in distributed environments, SimBet uses the concept of ego networks, in which analysis can be performed locally by individual nodes without complete knowledge of the entire network to substitute the whole network. Similarity is calculated as the number of common neighbor nodes. The SimBet routing protocol calculates a final utility by combining normalized betweenness utility and similarity utility. Messages are forwarded to the nodes with large utilities (i.e., nodes with large centrality and similarity with the destination node).
Bubble Rap exploits centrality and community to design the routing protocol. It uses the K-CLIQUE algorithm to detect the community structure of DTNs and combines the betweenness centrality to decide whether to forward the messages. Its forwarding strategy is a combination of RANK and LABEL. However, unlike SimBet, its betweenness metric is calculated by flooding messages and counting the times, and a node acts as a relay for other nodes in all the shortest delay deliveries.
SimBet and Bubble Rap are two efficient and classic routing strategies. Considering the real dataset we used in the experiments and the social properties we used in our routing strategy, these two routing strategies were selected as references.

Performance analysis
Experiments were conducted using the opportunistic network environment simulator [26] . A trace of the node contacts from the MIT Reality Mining project was used to evaluate the performance of the routing method.
All parameters were carefully selected so that the routing methods can achieve their best performance. In our experiments, the following metrics are used.
Delivery rate: The percentage of successfully delivered messages.
Average delay: The average time taken by the delivered messages to arrive at the destination node.
Average number of hops: The average number of hops a message must take to be successfully delivered.
The average number of hops is meaningful because communication between the nodes is energyconsuming, and the battery power is limited for each node. Figure 5 shows the delivery rates of the three routing protocols against time. We can see that Bubble Rap outperformed SimBet, and ROCD [27,28] achieved the best performance. The delivery rates of the three routing protocols increased with time because more messages were successfully delivered. At 200 000 s, the already delivered messages were those that could easily reach the destinations; therefore, the three protocols achieved similar results. Moreover, the delivery ratio increased with time, which is reasonable because a longer time leads to a higher delivery probability. Figure 6 compares the average delay of the three routing protocols. SimBet exhibited the longest delivery delay. In addition, ROCD outperformed both Bubble Rap and SimBet. This is because ROCD uses the social group found by the algorithm and finds a more efficient path to deliver the message; therefore, the average delay of ROCD is the shortest among the three methods. The average delay also increases with time; in other words,  a longer simulation time leads to a longer average delay, which is also reasonable. Figure 7 shows a plot of the average number of hops of the three routing protocols. SimBet exhibited the optimum performance in terms of the average number of hops, followed by ROCD, and then Bubble Rap; this result is acceptable considering ROCD optimum performance in delivery rate and average delay.
In conclusion, the simulation results show that ROCD achieves a better delivery rate than the classic routing protocols, SimBet and Bubble Rap, without affecting the average delay.

Conclusion
In this paper, we propose a routing method based on overlapping hierarchical communities, ROCD, in delaytolerant networks, in which the communication devices are carried by individuals. First, a new comprehensive metric was defined to quantify the relationships between nodes, considering contact frequency, contact duration, and contact regularity. Using this metric, a social graph can be constructed from the existing contact graph. Furthermore, an overlapping community detection algorithm was presented and a tree structure was generated. By talloring, communities that had strong relationships and that might overlap each other were obtained. Lastly, the routing method based on overlapping communities and the tree structure was given. Simulation results showed that ROCD achieved better routing performance than the existing routing methods. Our future work will focus on improving the energy of ROCD.
Xiangyu Meng is currently working toward the PhD degree in the Department of Computer Science and Technology at Jilin University, China. His research interests are in data mining, cloud computing, and software defined network.
Kuo Zhao received the BS, MS, and PhD degrees from Jilin University in 2001, 2004, and 2008, respectively. He is currently an assoicate professor in the College of Computer Science and Technology at Jilin University. His research interests are operating systems, computer networks, and information security.
Gaochao Xu received the BEng degree from Jilin University in 1988, MEng and PhD degrees from Jilin University in 1991 and 1995, respectively. Currently, he is a professor and PhD supervisor at Jilin University, China. His main research interests include distributed system, grid computing, cloud computing, Internet of things, information security, software testing, and software reliability.