# Modified Data Delivery Strategy Based on Stochastic Block Model and Community Detection in Opportunistic Social Networks

Authors: Limiao Li; Fangfang Gou; Jia Wu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

The nodes in the opportunistic network make up communities according to the relevance between them. Some of the structural characteristics of an opportunistic network can be reflected by the structure of the communities that exist in the network. Therefore, finding community from the network is of great significance for people to better study, use, and transform the network. The overlap of communities is considered to be an important feature of communities. Almost all community discovery algorithms were based on nonoverlapping communities in the past. A node in a nonoverlapping community belongs to only one community. However, there are overlapping and interrelated characteristics between communities, so it is not in line with the actual environment of the network. As a result, the previous algorithms have many shortcomings in the face of practical application scenarios, coupled with the limitation of the computing capacity of mobile devices; data transmission for low delay and the low energy consumption is difficult to meet the requirements. In the study, we formulate the problem of dividing nodes into several communities in the opportunistic social network as how to build communities dynamically according to weight distribution. Then, we propose a modified data delivery strategy based on stochastic block model and community detection (DDBSC). The simulation results show that, compared with other algorithms in the experiments, the strategy proposed in this paper exhibits good performance in terms of overhead, energy consumption, and delivery rate.


---

## Body

## 1. Introduction

With the rapid development of 5G wireless communication technologies and the rapid popularization of various mobile terminals, many huge networks formed by tens of thousands of mobile devices have risen. Those mobile devices in the Internet of things (IoT) such as mobile phones, tablets, smartwatches, POS terminals, and onboard computers, naturally have the characteristic of random movement due to they are carried by users [1–3]. When communication occurs, they consist of a system that can abstract out some of the characteristics of human networks [4]. In recent years, a thorough study of mobile networks has emerged, revealing the existence of a store-carry-send mechanism in opportunistic social networks. Under this mechanism, message transmission does not have to occur in a fixed communication path. The mobile communication devices can be regarded as the nodes in the opportunistic social networks, and the nodes can choose the adjacent node as the next station of message transmission [5–7]. Opportunistic social networks have been widely used in interplanetary networks [8], field tracking [9], disaster rescue [10], and networks in underdeveloped areas [11].Nodes in the opportunistic social networks will carry out a large amount of data transmission with their strongly related nodes [12–14]. Nodes form communities according to their associations, and some structural characteristics of the network can be reflected by the structure of the communities existing in the network [15, 16]. Therefore, finding communities from the network is of great significance for people to better study, use, and transform the network.However, almost all community discovery algorithms were based on nonoverlapping communities in the past [17, 18]. Nodes in nonoverlapping communities can only belong to a certain community, but there are overlapping and interrelated characteristics between communities. It is very inappropriate to think that a node belongs to only one community. As a result, the previous algorithms have many shortcomings in the face of practical application scenarios, coupled with the limitation of the computing capacity of mobile devices; data transmission for low delay and the low energy consumption is difficult to meet the requirement [19]. To realize the fast and large-capacity data transmission requirements under 5G standards, a routing algorithm based on a clearly defined community and discovery community is urgently needed.To solve the problems mentioned above, we put forward a data delivery strategy based on stochastic block model and community detection (DDBSC). This paper changes the current situation where the community is not clearly defined, according to the correlation degree of source nodes and destination nodes, dynamically component community, and on this basis to carry out efficient and relatively reliable data transmission. The main contributions of this paper can be summarized below.(1)
We first formulate the problem of dividing nodes into several communities in the opportunistic social network as how to build communities dynamically according to weight distribution(2)
In order to solve time complexity and decrease overhead costs for communication in the opportunistic social network, we propose the data delivery strategy based on the stochastic block model and community detection (DDBSC) on the basis of considering the nonuniformity of community(3)
We compare the proposed algorithm with four advanced routing algorithms. The simulation results show that the proposed DDBSC outperforms the other four algorithms in terms of overhead, energy consumption, and delivery ratioThe rest of this paper is organized as follows: the second section introduces some breakthrough routing algorithms on opportunistic networks. On this basis, we describe how community reconstruction happens according to weight distribution changes and proposes the data transmission strategy in the third section. Then, in the fourth section, the performance of the routing strategy is verified through simulation experiments. In the end, the paper is summarized.


## 2. Related Work

Due to the instability and randomness of node connection in an opportunistic network, the end-to-end universal link transmission mode is not feasible. In recent years, the research focus in the opportunistic network is on the data transmission between nodes. The following are some groundbreaking studies.Derakhshanfard et al. [20] proposed a sharing spray and wait routing algorithm in opportunistic networks. The approach adopts a store-carry-forward mechanism and constantly select the next hop and consider the number of copies to be transmitted according to the delivery time of the message and the probability of message delivery. Furthermore, the network is extended for analysis based on Markov chain. Simulation results show that the proposed method can improve the performance significantly in terms of delay, transfer ratio, and replication. Considering that the multicopy routing algorithm is easy to cause network congestion, Yuan et al. [21] introduced a disjoint-path (DP) routing algorithm. In the algorithm, every node can only deliver data packets once except the source nodes so that the number of packet copies in the network can be effectively controlled. Furthermore, the algorithm utilizes the discrete continuous time Markov chain (CTMC) to state transitions between nodes and uses the DP routing algorithm to calculate the number of data packer copies. Simulation results show that DP greatly improves the packet delivery ratio, average delivery delay, average network overhead, energy, and average hop count.Sharma et al. [22] proposed a secure and reliable routing protocol (called RFCSec) based on random forest classifier (RFC) in order to deal with the challenge of reliability of message passing in opportunistic network. The protocol is based on hashing message integrity and high grouping delivery to ensure spatial efficiency. Two phases compose the protocol. The RFC is trained on real data-trace and records the output in the first phase. In the second one, the encountered nodes of a given node are classified as one of the output classes of nodes according to their past behavior. This helps proactively isolate malicious nodes from the routing process and encourages nodes with good message forwarding behavior, low packet drop rates, high buffer availability, and a high likelihood of passing messages in the past to participate. Simulation results show that the proposed RFCSec is superior to MLPropH, RLPropH, and CAML routing protocols in terms of legitimate packet delivery, probability of message delivery, count of dropped messages, and latency in packet delivery.Kandhoul et al. [23] proposed a novel routing protocol for OppNets called Energy-Efficient Check-and-Spray Geocast Routing (EECSG). The routing protocol introduces a way of message distribution to every resident node geographic broadcast area; at the same time, it can reduce energy consumption by disabling unnecessary packet transmission. It also introduces a check-and-spray mechanism to lower the overhead of data packets in the geographic broadcast area. After simulation evaluation, comparing with the Efficient and Flexible Geocasting for Opportunistic Networks (GSAF) and the Centrality-Based Geocasting for Opportunistic Networks (CGOPP), it shows excellent performance in hop count, overhead ratio, number of dead nodes, number of messages forwarded, delivery ratio, and average latency.Singh et al. [24] proposed a delay-aware and cost-efficient probabilistic transmission method based on the probabilistic transmission scheme. This method defines the probabilities of direct and indirect encountering that is connected with latency and hop. Relay nodes in the method are set encountering delay and hop count thresholds by default, so that the probabilities of nodes to encounter the destination node within the threshold become transmission performance metrics. The simulation results show that the proposed method has significant improvement in reducing transmission delay and cost.Li et al. [25] proposed a causal broadcast algorithm and a Δ-causal broadcast algorithm based on causal barriers. They consider both cases where the messages diffuse in the network without or with a limited life cycle so ensure the causal sequence of broadcast messages in the opportunistic network. The simulation results show that they perform well in OppNets and the networks with high churn rates.Guidec et al. [26] proposed an advanced adaptive buffer management policy to address the pain point of buffer congestion. Limited network resources (such as energy and bandwidth) are taken into account by this strategy. The new solution depends on three strategies. They are blacklisting, scheduling, and dropping. It is designed to adapt with the modification of several network parameters such as data size, cache capacity, and network density. The simulation results show that can increase the delivery rate and decrease the network resource consumption to improve the performance of network.This paper proposes a more efficient routing strategy after learning the above algorithms’ experience.


## 3. Model Design

### 3.1. Community Model Design

In this part, we will give three theorems considering data transmission’s characteristic of random and nodes’ characteristic of movement in the opportunistic social network. These three theorems describe how the weight distribution affects the reconstruction of the community. Then, we give them their proofs.According to the definition of graph theory, we can define the topology of any opportunistic social network asG=V,E,w, where V represents the collection of nodes in the network and E represents the collection of edges in the network. We can use Figure 1 to describe this topology. The nodes in the figure correspond to various network terminal devices in our daily life, including cell phones, smart watches, computers, and car navigation. Devices can be connected to each other through the network and transmit information to each other, forming edges [27]. For example, in Figure 1, e∈E can also be expressed as u,v, where u∈V, v∈V. w represents the connection weight between node u and node v based on the dynamically constructed community. According to the communication relationships, these devices form a number of node clusters, which we call communities, and are represented by dashed circles in the figure.Figure 1
Nodes and edges in networks.In this study, we make a modular representation of the network. And we want to predict changes in the community based on this. Define the degree of modularity of the community at timem as
(1)χm=wyN−Rn24N2,where wy is the total weight with edges in the community y, N is the total weight with edges in the network, and Rn expresses total degree with nodes in the network.Theorem 1.
The increase of weight is positively correlated with the correlation degree of community.Proof.
Given that atm moment, the modularization degree of the network is χm, then at m+1 moment, it can be expressed as:
(2)χm+1=wy+wincN+winc−Rn+2winc24N+winc2.There are(3)χm+1−χm=wy+wincN+winc−Rn+2winc24N+winc2−wyN−Rn24N2=4N3winc−4N2Rnwinc−4N2wywinc+2N2Rnwinc4N2N+winc2−4NRnwinc2−Rnwinc22N2N+winc2≥4N3winc−6N2Rnwinc+2N2Rnwinc−2N2Rnwinc+Rnwinc24N2N+winc2=winc4N3winc−6N2Rn+2N2Rn−2NRnwinc+Rn2winc4N2N+winc2=winc2N2−2NRn−Rnwinc⋅2N−Rn4N2N+winc2.winc expresses the increment of weights in community y, and winc>0. Now, we will prove that χm+1−χm>0, the formula can be transferred to
(4)2N2−2NRn−Rnwinc⋅2N−Rn>0,that is to say,
(5)2N2−2NRn−Rnwinc>0,2N−Rn>0,winc>0,⇒0<winc<2WWRn−1,Rn<2W,⇒0<winc<2WWRn−1,2WWRn−1>0,Rn<2W,⇒0<winc<2WWRn−1,Rn<W.BecauseRn is the total degree with nodes in the networks, there is no community in the networks appearing degree greater than Rn. It can be seen from the above proof that the increase of weight will lead to the increase of community correlation.Theorem 2.
The community has not divided under this circumstance: when weight for an edge has decreased, two nodes connect by this edge which is the only one edge for a node.Proof.
Given that there is an edgeⅇ=u,v, its weight is wuv. If the community has divided, it has three conditions:
(6)wu+wv<w,muW−Ru24W2+mvW−Rv24W2<Ru+Rv+wuvW−Ru+Rv24W2,wuv>RuRv2W.After the change, the weight in the community becomes:(7)wu∗+wv∗>w∗,wuv<wcha+RuRv+RSwcha+wcha22W+wcha.wcha expresses the change of weight between node uand v; it could be explained as:
(8)RuRv2W<wuv<RuRv+wcha2W+wcha=RuRv+Ruwcha2W+wcha.Because(9)RuRv+Ruwcha2W+wcha−RuRvW=Ruwchaw−RvWW+wcha<0wcha<0.So, we can know that(10)RuRv+Ruwcha2W+wcha<RuRvW.That is to say,RuRv/2W<wuv<RuRv+wcha/2W+wcha is not true.It can be seen from the above proof that weight for an edge has decreased, and two nodes connect by this edge which is the only one edge for a node; community has not been divided.Theorem 3.
There are conditions for nodes to join the community. Assuming that nodeu is in the community C1, if the weights of wC1 and another community wC2 both increase and satisfy 4W+wcha⋅eC2k−eC1k+wcha+Rk+wcha⋅RC1−Rk−RC2−wcha2>0, then the node u can join the community wC2.Proof.
When the weight of an edge connecting two communities increases, the sum of the modularization degree of the two communities is:(11)χC1+χC2=wC1W+wcha−RC1+wcha24W+wcha+wC2W+wcha−RC2+wcha24W+wchaC1C2.If a nodek in the community leaves the original community C1 to join the community C2, the sum of the modularization degree of the two communities is:
(12)χC1′+χC2′=wC1−eC1kW+wcha−RC1+wcha4W+wcha+wC2+eC2k+wchaW+wcha−RC2+RK+2wcha24W+wcha.It is easy to see thatχC1′+χC2′>χC1+χC2, that is to say
(13)4W+wcha⋅eC2k−eC1k+wcha+Rk+wcha⋅RC1−Rk−RC2−wcha2>0.The above formula proves that when nodeC2 joins the modularity of community, C2 is increasing. Through the above analysis, we can see the relationship between nodes, weights, and communities. Section 3.2 mainly describes reconstruction-based communities for efficient data transfer.


### 3.2. Data Delivery Model Design

As shown in Figure2, this is a typical composition of social networks of opportunity, where mobile devices could act as mobile nodes. We divide the mobile nodes in the network into three communities, and the community composition is in dynamic change. The green nodes represent the source nodes, and the nodes with other colors represent their adjacent node. The source nodes undertake the tasks of transferring a large amount of data and calculation, so they consume more energy and resources. There are typically only one or two source nodes per community. The basis of community reconstruction is the correlation degree between source nodes and neighboring nodes [28, 29]. That is because the inner edge density of each community structure is significantly higher than the edge density between communities [30–32]. It can also be said that the community structure is a dense subgraph separated from each other. The traditional definition of community relies on the calculation of sides in different ways. But what really needs to be cared about is the probability that a node shares an edge with a subgraph. Community existence implies that there are strong relations of connections between some nodes than others [33, 34]. Therefore, within the same population, there should be special connection ways between nodes.Figure 2
Typical community structure. Green nodes express source nodes, and nodes in other colors express neighboring nodes. Data transmissions are initiated by the source nodes.The difference between the definitions of strong and weak communities lies in that in the definition of strong communities, the comparison of edge probability takes place on each pair of nodes, while in the definition of weak communities, the average value of the node group is taken. Therefore, a strong community also meets the definition of a weak community. Each of these hypotheses can form an edge generation model [35–37]. A reasonable model needs to take into account the possibility of the existence that groups of nodes behave similarly. The most famous network group structure model is the stochastic block model (SBM), and the application of this model to network community detectability will be introduced in the following section. Community detectability work is the premise of community discovery, and then, we will propose an advanced routing algorithm based on community discovery.Most of the networks of interest are sparse, and their average degree is much smaller than the number of vertices. This means that the number of edges in an actual network ofn nodes is usually much less than the maximum number of edges nn−1/2. On the other hand, the sparse nature of the network also brings some problems. Since the density of the edges is very low, a small amount of noise can seriously interfere with the structure of the system. For example, random fluctuations in a sparse network may make the algorithm constantly detect some nonexistent cluster structures, which causes the algorithm to time out. Meanwhile, these fluctuations may make the actual community structure undetectable.With a view to the above problems, our solution is: firstly, the network data is modeled by a stochastic block model, and the Bayesian inference is applied to the parameter deduction of the model. Then, the critical value of detectability is determined by the fixed point of the free energy theory in statistical physics. Finally, the back propagation algorithm is used for iterative calculation, and on this basis, data transmission is carried out. Each step is described in detail in the following paragraphs.


#### 3.2.1. Use Stochastic Block Model to Model the Network

The stochastic block model (SBM) is a stochastic graph model with a cluster structure. It is mainly used for research clustering and community detection and provides a broad research basis for the study of statistics and calculations occurring in networks and data. The stochastic block model is the most famous network group structure model, which is defined as follows: we suppose a network withn nodes is divided into q groups, i.e., g1,g2,…gq (gi represents group identifier, i=1,2,⋯,q). SBM assumes that the probability Pi↔j of the connection between node i and node j is only determined by their group membership: Pi↔j=Pgigj. Therefore, for two nodes in the same group, the probability of being associated with another group node is the same. The q∗q symmetric matrix formed by the probability Pgigj is called the stochastic block matrix. The diagonal element Pkkk=1,2,3,⋯,q denotes the probability of internal edges of nodes in the block k, while nondiagonal elements give the probability of edges between different blocks.We use the stochastic block model to model the network. Assume that the number of network nodes isS, and each node ii∈1,S has an implied label ai∈1,q, which means that the nodes are divided into q groups with the number of nodes δ1,δ2,⋯,δq. Each node selects label independently. Suppose Px is the probability that a given node chooses the label x as shown in
(14)Px=limS⟶∞δxS.In our configuration, only the adjacency matrix information of the graph is available. The adjacency matrix of the graph gives the information of all nodes in the graph and the information about whether there is a connection between them. Once the grouping is complete, a new matrix similar to the original adjacency matrix is obtained. For each pair of nodesi and ji<j, let their grouping be δi and δj, respectively. The probability of connection between the two nodes is Pij. The matrix formed is the correlation matrix of the initial adjacency matrix.


#### 3.2.2. Infer the Parameters of SBM Model by Bayesian Formula

Let us start with some basic knowledge of statistics and probability theory.Conditional probability: letA,B be two events, and PA>0, then PBA=PAB/PA is the conditional probability of event B under the condition that event A occurs. Generally, PBA≠PB, unless the two events are independent of each other.Total probability formula: if eventsA1,A2,…,An is a complete group of events, and all have positive probability, then
(15)PB=PA1PBA1+PA2PBA2+⋯+PAnPBAn=∑i=1nPAiPBAi.Bayes formula: let the eventsA1,A2,…,An is a complete event group, then for any event B, if PB>0, then
(16)PAiB=PAiBPB=PAiPBAi∑i=1nPAiPBAi.Bayes formula can be proved by the conditional probability definition and the total probability formula. Knowing that an event has occurred (prior probability) and asking for the probability of the various causes or circumstances that caused the event to occur (posterior probability), we can use the Bayes formula to get the answer.Apply Bayesian inference to stochastic block model. The conditional probability of the parametersθ=αa,βabof the stochastic block model τ is
(17)Pθiμi=PθiμiPμi=PθiPμiθi∑giPθiPμiθi.The summation part is to traverse the grouping of each node. Prior probabilityPθ contains the information for the model parameters that is independent of the figure. In this case, Pθiμi maximizes when Pμiθi maximizes. We call the function Pμiθi as the likelihood function, it is the probability of grouping when model takes θ as the parameter. When the parameters αa and βab are given, the best group assignment can be obtained by using the maximum likelihood method. But this is only appropriate for networks generated through this model. In a sparse network, if we only care about the maximum likelihood function, the phenomenon of data overfitting may occur.


#### 3.2.3. Use the Back Propagation (BP) Algorithm for Iterative Calculation

BP algorithm is a fast method for network community detection; at the same time, it is also an excellent algorithm performance analysis tool [38]. By analyzing the fixed points in BP algorithm, we can judge whether one method can be used to get the network community. Since this algorithm is optimal in one sense, if this algorithm fails, then all other algorithms will fail as well [39, 40]. This conclusion of BP algorithm not only refers to the specific algorithm but also includes other algorithms.It is shown that there are some special cases in the parameter space of stochastic block model. Under these special cases, the community structure cannot be algorithmically recovered. In particular, if the average degree is the same for all grouping formulas, there is a useless fixed point:φai⟶j=φai=δa. If q groups have the same size, that is, δa=1/q, BP algorithm will get the conclusion that all nodes are equally likely to belong to any group.In other cases, there may be more than one useless fixing point, and when these useless fixing points become unstable, they are called transition points. On the transition state point, by changing the initialization conditions of BP algorithm and using random information, the algorithm will soon leave the vicinity of the transition state point and reach other fixed points [41–43]. Therefore, it is computationally feasible to detect the community structure and accurately group the nodes, and the BP algorithm can complete this task quickly and stably.When the groups’ size is the same and the parameterρab of the random block model has only two values, as shown in
(18)ρab=ρin,a=b,ρab=ρout,a≠b.So, the positions of the transition state points are relatively easy to determine. Ifρin is obviously greater than ρout, then the community structure is obtained. However, as ρin and ρout approach gradually, the community structure becomes fragile. Although some statistical errors may occur, as long as ρin>ρout is satisfied, some researchers have thought that the community structure can be detected. This paper challenges the above view. In this paper, when the fixed point is stable, it needs to be satisfied
(19)ρin−ρout=qρ,where ρ represents the average degree of the entire network node, and its calculation formula is
(20)ρ=ρin+q−1ρoutq.If these useless fixed points are stable, the BP algorithm will behave differently, depending on whether the stability of the fixed points is local or global and depending on the number of groups. At this point, the global stability point is below the transition state point, so the community structure is undetectable. The BP algorithm will always converge at useless fixed points and return information with no community structure.


#### 3.2.4. Data Transfer

As we know, in opportunistic social networks, data is transmitted from the source node to the destination node in a multiroute manner. To reflect this process more clearly, we illustrate this process in Figure3. The green circle represents the source node, which looks for the node available for data transmission among neighboring nodes, namely, the available node. When an available node receives and stores some information, it becomes reserve node, and a community is formed according to the method mentioned above. The source node continues to move and look for available nodes to communicate with them. It is important to note that when the latter community is formed, its information also comes from the former community. The source node continues to move, and the process repeats itself. Until finally the message is delivered to the destination node.Figure 3
The process of data transmission after community detection.The algorithm design in DDBSC can be described in Algorithm1. In this algorithm, assuming that there are n nodes, the complexity of calculating the connectivity probability is Olog2n. It can be seen that the complexity of the entire DDBSC algorithm is Olog2n.Algorithm 1: The algorithm design in DDBSC
Output: The network has community structure or notBeginDivide nodes intoq groups, namely, g1,g2,…,gqWhile (i,j∈V){let the probability thati and j are connected be Pgigj}End whileGenerate the association matrix of the adjacency matrixMIf (!E≪VV−1/2)//not a sparse networkμ0=argmaxPθiμi//obtain the best group assignment μ0, θi denotes the parameter of the stochastic block modelEnd ifθ=θin+q−1θout/q.If (θin−θout=qθ)Then there exists community structureElse there is notEnd ifEnd


## 3.1. Community Model Design

In this part, we will give three theorems considering data transmission’s characteristic of random and nodes’ characteristic of movement in the opportunistic social network. These three theorems describe how the weight distribution affects the reconstruction of the community. Then, we give them their proofs.According to the definition of graph theory, we can define the topology of any opportunistic social network asG=V,E,w, where V represents the collection of nodes in the network and E represents the collection of edges in the network. We can use Figure 1 to describe this topology. The nodes in the figure correspond to various network terminal devices in our daily life, including cell phones, smart watches, computers, and car navigation. Devices can be connected to each other through the network and transmit information to each other, forming edges [27]. For example, in Figure 1, e∈E can also be expressed as u,v, where u∈V, v∈V. w represents the connection weight between node u and node v based on the dynamically constructed community. According to the communication relationships, these devices form a number of node clusters, which we call communities, and are represented by dashed circles in the figure.Figure 1
Nodes and edges in networks.In this study, we make a modular representation of the network. And we want to predict changes in the community based on this. Define the degree of modularity of the community at timem as
(1)χm=wyN−Rn24N2,where wy is the total weight with edges in the community y, N is the total weight with edges in the network, and Rn expresses total degree with nodes in the network.Theorem 1.
The increase of weight is positively correlated with the correlation degree of community.Proof.
Given that atm moment, the modularization degree of the network is χm, then at m+1 moment, it can be expressed as:
(2)χm+1=wy+wincN+winc−Rn+2winc24N+winc2.There are(3)χm+1−χm=wy+wincN+winc−Rn+2winc24N+winc2−wyN−Rn24N2=4N3winc−4N2Rnwinc−4N2wywinc+2N2Rnwinc4N2N+winc2−4NRnwinc2−Rnwinc22N2N+winc2≥4N3winc−6N2Rnwinc+2N2Rnwinc−2N2Rnwinc+Rnwinc24N2N+winc2=winc4N3winc−6N2Rn+2N2Rn−2NRnwinc+Rn2winc4N2N+winc2=winc2N2−2NRn−Rnwinc⋅2N−Rn4N2N+winc2.winc expresses the increment of weights in community y, and winc>0. Now, we will prove that χm+1−χm>0, the formula can be transferred to
(4)2N2−2NRn−Rnwinc⋅2N−Rn>0,that is to say,
(5)2N2−2NRn−Rnwinc>0,2N−Rn>0,winc>0,⇒0<winc<2WWRn−1,Rn<2W,⇒0<winc<2WWRn−1,2WWRn−1>0,Rn<2W,⇒0<winc<2WWRn−1,Rn<W.BecauseRn is the total degree with nodes in the networks, there is no community in the networks appearing degree greater than Rn. It can be seen from the above proof that the increase of weight will lead to the increase of community correlation.Theorem 2.
The community has not divided under this circumstance: when weight for an edge has decreased, two nodes connect by this edge which is the only one edge for a node.Proof.
Given that there is an edgeⅇ=u,v, its weight is wuv. If the community has divided, it has three conditions:
(6)wu+wv<w,muW−Ru24W2+mvW−Rv24W2<Ru+Rv+wuvW−Ru+Rv24W2,wuv>RuRv2W.After the change, the weight in the community becomes:(7)wu∗+wv∗>w∗,wuv<wcha+RuRv+RSwcha+wcha22W+wcha.wcha expresses the change of weight between node uand v; it could be explained as:
(8)RuRv2W<wuv<RuRv+wcha2W+wcha=RuRv+Ruwcha2W+wcha.Because(9)RuRv+Ruwcha2W+wcha−RuRvW=Ruwchaw−RvWW+wcha<0wcha<0.So, we can know that(10)RuRv+Ruwcha2W+wcha<RuRvW.That is to say,RuRv/2W<wuv<RuRv+wcha/2W+wcha is not true.It can be seen from the above proof that weight for an edge has decreased, and two nodes connect by this edge which is the only one edge for a node; community has not been divided.Theorem 3.
There are conditions for nodes to join the community. Assuming that nodeu is in the community C1, if the weights of wC1 and another community wC2 both increase and satisfy 4W+wcha⋅eC2k−eC1k+wcha+Rk+wcha⋅RC1−Rk−RC2−wcha2>0, then the node u can join the community wC2.Proof.
When the weight of an edge connecting two communities increases, the sum of the modularization degree of the two communities is:(11)χC1+χC2=wC1W+wcha−RC1+wcha24W+wcha+wC2W+wcha−RC2+wcha24W+wchaC1C2.If a nodek in the community leaves the original community C1 to join the community C2, the sum of the modularization degree of the two communities is:
(12)χC1′+χC2′=wC1−eC1kW+wcha−RC1+wcha4W+wcha+wC2+eC2k+wchaW+wcha−RC2+RK+2wcha24W+wcha.It is easy to see thatχC1′+χC2′>χC1+χC2, that is to say
(13)4W+wcha⋅eC2k−eC1k+wcha+Rk+wcha⋅RC1−Rk−RC2−wcha2>0.The above formula proves that when nodeC2 joins the modularity of community, C2 is increasing. Through the above analysis, we can see the relationship between nodes, weights, and communities. Section 3.2 mainly describes reconstruction-based communities for efficient data transfer.


## 3.2. Data Delivery Model Design

As shown in Figure2, this is a typical composition of social networks of opportunity, where mobile devices could act as mobile nodes. We divide the mobile nodes in the network into three communities, and the community composition is in dynamic change. The green nodes represent the source nodes, and the nodes with other colors represent their adjacent node. The source nodes undertake the tasks of transferring a large amount of data and calculation, so they consume more energy and resources. There are typically only one or two source nodes per community. The basis of community reconstruction is the correlation degree between source nodes and neighboring nodes [28, 29]. That is because the inner edge density of each community structure is significantly higher than the edge density between communities [30–32]. It can also be said that the community structure is a dense subgraph separated from each other. The traditional definition of community relies on the calculation of sides in different ways. But what really needs to be cared about is the probability that a node shares an edge with a subgraph. Community existence implies that there are strong relations of connections between some nodes than others [33, 34]. Therefore, within the same population, there should be special connection ways between nodes.Figure 2
Typical community structure. Green nodes express source nodes, and nodes in other colors express neighboring nodes. Data transmissions are initiated by the source nodes.The difference between the definitions of strong and weak communities lies in that in the definition of strong communities, the comparison of edge probability takes place on each pair of nodes, while in the definition of weak communities, the average value of the node group is taken. Therefore, a strong community also meets the definition of a weak community. Each of these hypotheses can form an edge generation model [35–37]. A reasonable model needs to take into account the possibility of the existence that groups of nodes behave similarly. The most famous network group structure model is the stochastic block model (SBM), and the application of this model to network community detectability will be introduced in the following section. Community detectability work is the premise of community discovery, and then, we will propose an advanced routing algorithm based on community discovery.Most of the networks of interest are sparse, and their average degree is much smaller than the number of vertices. This means that the number of edges in an actual network ofn nodes is usually much less than the maximum number of edges nn−1/2. On the other hand, the sparse nature of the network also brings some problems. Since the density of the edges is very low, a small amount of noise can seriously interfere with the structure of the system. For example, random fluctuations in a sparse network may make the algorithm constantly detect some nonexistent cluster structures, which causes the algorithm to time out. Meanwhile, these fluctuations may make the actual community structure undetectable.With a view to the above problems, our solution is: firstly, the network data is modeled by a stochastic block model, and the Bayesian inference is applied to the parameter deduction of the model. Then, the critical value of detectability is determined by the fixed point of the free energy theory in statistical physics. Finally, the back propagation algorithm is used for iterative calculation, and on this basis, data transmission is carried out. Each step is described in detail in the following paragraphs.


### 3.2.1. Use Stochastic Block Model to Model the Network

The stochastic block model (SBM) is a stochastic graph model with a cluster structure. It is mainly used for research clustering and community detection and provides a broad research basis for the study of statistics and calculations occurring in networks and data. The stochastic block model is the most famous network group structure model, which is defined as follows: we suppose a network withn nodes is divided into q groups, i.e., g1,g2,…gq (gi represents group identifier, i=1,2,⋯,q). SBM assumes that the probability Pi↔j of the connection between node i and node j is only determined by their group membership: Pi↔j=Pgigj. Therefore, for two nodes in the same group, the probability of being associated with another group node is the same. The q∗q symmetric matrix formed by the probability Pgigj is called the stochastic block matrix. The diagonal element Pkkk=1,2,3,⋯,q denotes the probability of internal edges of nodes in the block k, while nondiagonal elements give the probability of edges between different blocks.We use the stochastic block model to model the network. Assume that the number of network nodes isS, and each node ii∈1,S has an implied label ai∈1,q, which means that the nodes are divided into q groups with the number of nodes δ1,δ2,⋯,δq. Each node selects label independently. Suppose Px is the probability that a given node chooses the label x as shown in
(14)Px=limS⟶∞δxS.In our configuration, only the adjacency matrix information of the graph is available. The adjacency matrix of the graph gives the information of all nodes in the graph and the information about whether there is a connection between them. Once the grouping is complete, a new matrix similar to the original adjacency matrix is obtained. For each pair of nodesi and ji<j, let their grouping be δi and δj, respectively. The probability of connection between the two nodes is Pij. The matrix formed is the correlation matrix of the initial adjacency matrix.


### 3.2.2. Infer the Parameters of SBM Model by Bayesian Formula

Let us start with some basic knowledge of statistics and probability theory.Conditional probability: letA,B be two events, and PA>0, then PBA=PAB/PA is the conditional probability of event B under the condition that event A occurs. Generally, PBA≠PB, unless the two events are independent of each other.Total probability formula: if eventsA1,A2,…,An is a complete group of events, and all have positive probability, then
(15)PB=PA1PBA1+PA2PBA2+⋯+PAnPBAn=∑i=1nPAiPBAi.Bayes formula: let the eventsA1,A2,…,An is a complete event group, then for any event B, if PB>0, then
(16)PAiB=PAiBPB=PAiPBAi∑i=1nPAiPBAi.Bayes formula can be proved by the conditional probability definition and the total probability formula. Knowing that an event has occurred (prior probability) and asking for the probability of the various causes or circumstances that caused the event to occur (posterior probability), we can use the Bayes formula to get the answer.Apply Bayesian inference to stochastic block model. The conditional probability of the parametersθ=αa,βabof the stochastic block model τ is
(17)Pθiμi=PθiμiPμi=PθiPμiθi∑giPθiPμiθi.The summation part is to traverse the grouping of each node. Prior probabilityPθ contains the information for the model parameters that is independent of the figure. In this case, Pθiμi maximizes when Pμiθi maximizes. We call the function Pμiθi as the likelihood function, it is the probability of grouping when model takes θ as the parameter. When the parameters αa and βab are given, the best group assignment can be obtained by using the maximum likelihood method. But this is only appropriate for networks generated through this model. In a sparse network, if we only care about the maximum likelihood function, the phenomenon of data overfitting may occur.


### 3.2.3. Use the Back Propagation (BP) Algorithm for Iterative Calculation

BP algorithm is a fast method for network community detection; at the same time, it is also an excellent algorithm performance analysis tool [38]. By analyzing the fixed points in BP algorithm, we can judge whether one method can be used to get the network community. Since this algorithm is optimal in one sense, if this algorithm fails, then all other algorithms will fail as well [39, 40]. This conclusion of BP algorithm not only refers to the specific algorithm but also includes other algorithms.It is shown that there are some special cases in the parameter space of stochastic block model. Under these special cases, the community structure cannot be algorithmically recovered. In particular, if the average degree is the same for all grouping formulas, there is a useless fixed point:φai⟶j=φai=δa. If q groups have the same size, that is, δa=1/q, BP algorithm will get the conclusion that all nodes are equally likely to belong to any group.In other cases, there may be more than one useless fixing point, and when these useless fixing points become unstable, they are called transition points. On the transition state point, by changing the initialization conditions of BP algorithm and using random information, the algorithm will soon leave the vicinity of the transition state point and reach other fixed points [41–43]. Therefore, it is computationally feasible to detect the community structure and accurately group the nodes, and the BP algorithm can complete this task quickly and stably.When the groups’ size is the same and the parameterρab of the random block model has only two values, as shown in
(18)ρab=ρin,a=b,ρab=ρout,a≠b.So, the positions of the transition state points are relatively easy to determine. Ifρin is obviously greater than ρout, then the community structure is obtained. However, as ρin and ρout approach gradually, the community structure becomes fragile. Although some statistical errors may occur, as long as ρin>ρout is satisfied, some researchers have thought that the community structure can be detected. This paper challenges the above view. In this paper, when the fixed point is stable, it needs to be satisfied
(19)ρin−ρout=qρ,where ρ represents the average degree of the entire network node, and its calculation formula is
(20)ρ=ρin+q−1ρoutq.If these useless fixed points are stable, the BP algorithm will behave differently, depending on whether the stability of the fixed points is local or global and depending on the number of groups. At this point, the global stability point is below the transition state point, so the community structure is undetectable. The BP algorithm will always converge at useless fixed points and return information with no community structure.


### 3.2.4. Data Transfer

As we know, in opportunistic social networks, data is transmitted from the source node to the destination node in a multiroute manner. To reflect this process more clearly, we illustrate this process in Figure3. The green circle represents the source node, which looks for the node available for data transmission among neighboring nodes, namely, the available node. When an available node receives and stores some information, it becomes reserve node, and a community is formed according to the method mentioned above. The source node continues to move and look for available nodes to communicate with them. It is important to note that when the latter community is formed, its information also comes from the former community. The source node continues to move, and the process repeats itself. Until finally the message is delivered to the destination node.Figure 3
The process of data transmission after community detection.The algorithm design in DDBSC can be described in Algorithm1. In this algorithm, assuming that there are n nodes, the complexity of calculating the connectivity probability is Olog2n. It can be seen that the complexity of the entire DDBSC algorithm is Olog2n.Algorithm 1: The algorithm design in DDBSC
Output: The network has community structure or notBeginDivide nodes intoq groups, namely, g1,g2,…,gqWhile (i,j∈V){let the probability thati and j are connected be Pgigj}End whileGenerate the association matrix of the adjacency matrixMIf (!E≪VV−1/2)//not a sparse networkμ0=argmaxPθiμi//obtain the best group assignment μ0, θi denotes the parameter of the stochastic block modelEnd ifθ=θin+q−1θout/q.If (θin−θout=qθ)Then there exists community structureElse there is notEnd ifEnd


## 3.2.1. Use Stochastic Block Model to Model the Network

The stochastic block model (SBM) is a stochastic graph model with a cluster structure. It is mainly used for research clustering and community detection and provides a broad research basis for the study of statistics and calculations occurring in networks and data. The stochastic block model is the most famous network group structure model, which is defined as follows: we suppose a network withn nodes is divided into q groups, i.e., g1,g2,…gq (gi represents group identifier, i=1,2,⋯,q). SBM assumes that the probability Pi↔j of the connection between node i and node j is only determined by their group membership: Pi↔j=Pgigj. Therefore, for two nodes in the same group, the probability of being associated with another group node is the same. The q∗q symmetric matrix formed by the probability Pgigj is called the stochastic block matrix. The diagonal element Pkkk=1,2,3,⋯,q denotes the probability of internal edges of nodes in the block k, while nondiagonal elements give the probability of edges between different blocks.We use the stochastic block model to model the network. Assume that the number of network nodes isS, and each node ii∈1,S has an implied label ai∈1,q, which means that the nodes are divided into q groups with the number of nodes δ1,δ2,⋯,δq. Each node selects label independently. Suppose Px is the probability that a given node chooses the label x as shown in
(14)Px=limS⟶∞δxS.In our configuration, only the adjacency matrix information of the graph is available. The adjacency matrix of the graph gives the information of all nodes in the graph and the information about whether there is a connection between them. Once the grouping is complete, a new matrix similar to the original adjacency matrix is obtained. For each pair of nodesi and ji<j, let their grouping be δi and δj, respectively. The probability of connection between the two nodes is Pij. The matrix formed is the correlation matrix of the initial adjacency matrix.


## 3.2.2. Infer the Parameters of SBM Model by Bayesian Formula

Let us start with some basic knowledge of statistics and probability theory.Conditional probability: letA,B be two events, and PA>0, then PBA=PAB/PA is the conditional probability of event B under the condition that event A occurs. Generally, PBA≠PB, unless the two events are independent of each other.Total probability formula: if eventsA1,A2,…,An is a complete group of events, and all have positive probability, then
(15)PB=PA1PBA1+PA2PBA2+⋯+PAnPBAn=∑i=1nPAiPBAi.Bayes formula: let the eventsA1,A2,…,An is a complete event group, then for any event B, if PB>0, then
(16)PAiB=PAiBPB=PAiPBAi∑i=1nPAiPBAi.Bayes formula can be proved by the conditional probability definition and the total probability formula. Knowing that an event has occurred (prior probability) and asking for the probability of the various causes or circumstances that caused the event to occur (posterior probability), we can use the Bayes formula to get the answer.Apply Bayesian inference to stochastic block model. The conditional probability of the parametersθ=αa,βabof the stochastic block model τ is
(17)Pθiμi=PθiμiPμi=PθiPμiθi∑giPθiPμiθi.The summation part is to traverse the grouping of each node. Prior probabilityPθ contains the information for the model parameters that is independent of the figure. In this case, Pθiμi maximizes when Pμiθi maximizes. We call the function Pμiθi as the likelihood function, it is the probability of grouping when model takes θ as the parameter. When the parameters αa and βab are given, the best group assignment can be obtained by using the maximum likelihood method. But this is only appropriate for networks generated through this model. In a sparse network, if we only care about the maximum likelihood function, the phenomenon of data overfitting may occur.


## 3.2.3. Use the Back Propagation (BP) Algorithm for Iterative Calculation

BP algorithm is a fast method for network community detection; at the same time, it is also an excellent algorithm performance analysis tool [38]. By analyzing the fixed points in BP algorithm, we can judge whether one method can be used to get the network community. Since this algorithm is optimal in one sense, if this algorithm fails, then all other algorithms will fail as well [39, 40]. This conclusion of BP algorithm not only refers to the specific algorithm but also includes other algorithms.It is shown that there are some special cases in the parameter space of stochastic block model. Under these special cases, the community structure cannot be algorithmically recovered. In particular, if the average degree is the same for all grouping formulas, there is a useless fixed point:φai⟶j=φai=δa. If q groups have the same size, that is, δa=1/q, BP algorithm will get the conclusion that all nodes are equally likely to belong to any group.In other cases, there may be more than one useless fixing point, and when these useless fixing points become unstable, they are called transition points. On the transition state point, by changing the initialization conditions of BP algorithm and using random information, the algorithm will soon leave the vicinity of the transition state point and reach other fixed points [41–43]. Therefore, it is computationally feasible to detect the community structure and accurately group the nodes, and the BP algorithm can complete this task quickly and stably.When the groups’ size is the same and the parameterρab of the random block model has only two values, as shown in
(18)ρab=ρin,a=b,ρab=ρout,a≠b.So, the positions of the transition state points are relatively easy to determine. Ifρin is obviously greater than ρout, then the community structure is obtained. However, as ρin and ρout approach gradually, the community structure becomes fragile. Although some statistical errors may occur, as long as ρin>ρout is satisfied, some researchers have thought that the community structure can be detected. This paper challenges the above view. In this paper, when the fixed point is stable, it needs to be satisfied
(19)ρin−ρout=qρ,where ρ represents the average degree of the entire network node, and its calculation formula is
(20)ρ=ρin+q−1ρoutq.If these useless fixed points are stable, the BP algorithm will behave differently, depending on whether the stability of the fixed points is local or global and depending on the number of groups. At this point, the global stability point is below the transition state point, so the community structure is undetectable. The BP algorithm will always converge at useless fixed points and return information with no community structure.


## 3.2.4. Data Transfer

As we know, in opportunistic social networks, data is transmitted from the source node to the destination node in a multiroute manner. To reflect this process more clearly, we illustrate this process in Figure3. The green circle represents the source node, which looks for the node available for data transmission among neighboring nodes, namely, the available node. When an available node receives and stores some information, it becomes reserve node, and a community is formed according to the method mentioned above. The source node continues to move and look for available nodes to communicate with them. It is important to note that when the latter community is formed, its information also comes from the former community. The source node continues to move, and the process repeats itself. Until finally the message is delivered to the destination node.Figure 3
The process of data transmission after community detection.The algorithm design in DDBSC can be described in Algorithm1. In this algorithm, assuming that there are n nodes, the complexity of calculating the connectivity probability is Olog2n. It can be seen that the complexity of the entire DDBSC algorithm is Olog2n.Algorithm 1: The algorithm design in DDBSC
Output: The network has community structure or notBeginDivide nodes intoq groups, namely, g1,g2,…,gqWhile (i,j∈V){let the probability thati and j are connected be Pgigj}End whileGenerate the association matrix of the adjacency matrixMIf (!E≪VV−1/2)//not a sparse networkμ0=argmaxPθiμi//obtain the best group assignment μ0, θi denotes the parameter of the stochastic block modelEnd ifθ=θin+q−1θout/q.If (θin−θout=qθ)Then there exists community structureElse there is notEnd ifEnd


## 4. Simulation

### 4.1. Baseline Algorithms

To evaluate the performance of the proposed method, we compare it with the following three typical algorithms. They are status estimation and cache management algorithm (SECM), information cache management and data transmission algorithm (ICMT) [38], and spray and wait routing algorithm (SW). Here is a brief introduction of how they work effectively.
(1)
SECM: the basic principle of status estimation and cache management algorithm is to evaluate the probability of data transmission between nodes and neighboring nodes. Then, adjust the data cache distribution to achieve the goal of a high transfer rate. In this algorithm, neighboring nodes share caching tasks with each other to achieve efficient information distribution(2)
ICMT: the main technique of information cache management and data transmission algorithm is the identification and evaluation of neighbor nodes in the same project. On this basis, the cache is adjusted to reach the high project probability of the node(3)
SW: the main technique of the spray and wait routing algorithm is to generate a lot of copies, spray them across the network, and wait until one of them reaches the destination node. An important performance parameter of this algorithm is the number of copies. In this study, we selected 10 and 30 copies, respectively


### 4.2. Metrics

Metrics are used to measure the performance of algorithms in opportunistic social networks. Four are selected in this paper; they are overhead on average (call overhead for short), energy consumption on average (call energy consumption for short), end-to-end delay on average (call delay for short), and the delivery ratio [4]. Here is a brief introduction of what they mean.
(1)
Overhead: the average overhead in data transmission between two nodes(2)
Energy consumption: the average energy consumption in data transmission between two nodes(3)
Delay: the average delay in data transmission between two nodes(4)
Delivery ratio: the probability of a source node choosing an available node to transfer data


### 4.3. Environment and Parameters

In this paper, we use a ONE simulation tool for experiments. We set the parameters according to the stochastic model of the social network, as shown in Table1. Among them, our simulation time is 6 hours, and data is recorded every 0.5 hours. We selected an area of 4500m×3400m on the map as the simulation area. All nodes choose the social model as the transmission mode. Furthermore, each source node carries 10 packets.Table 1
The main system parameters.
ParameterValueSimulation time6 hNumber of nodes500Transmission patternBroadcastTransmission interval20-25 sNode movement modeRandom site movement modelArea in networks4500∗3400m2Size of data packet100-200 KBData transfer range10 m2Node movement speed0.5-1.5 m/sFrequency of data packet25-35 sCache5-40 MBInitial value of energy100 JTransmission energy consumption of a single node1 J


### 4.4. Results

The simulation results are as follows. Figures4–7 show the changes of the four performance measurement parameters of the five selected algorithms with the increase of simulation time. Among them, the simulation time is mainly calculated from the time when the source node starts to transmit data, and the monitoring is continued for 6 hours. In addition, in the experiment, the cache size of the node is set to 15 MB.Figure 4
The overhead situation changes over time.Figure 5
The energy consumption situation changes over time.Figure 6
The delay situation changes over time.Figure 7
The delivery ratio situation changes over time.Figure4 shows the change of data transmission overhead of the five algorithms with the increase of simulation time. It can be seen that the overhead of DDBSC has been a stable and good performance. It stays below 150 MB. As simulation time increases, the number of nodes involved in data transmission is bound to increase. The reason the DDBSC algorithm remains stable is that it can ensure the efficient reconstruction of the community. At the same time, in order to solve the time complexity and reduce the communication overhead cost in opportunistic social networks, we propose a data delivery strategy based on the random block model and community detection (DDBSC), taking into account the nonuniformity of the community. ICMT performs well, which reaches its peak at time is 2 h and then begins to decline steadily. That is because it controls the interval between data transfers. You can also see that the spraying and waiting algorithm with 30 copies has the worst performance in terms of overhead.Figure5 shows the change of data transmission energy consumption of the five algorithms with the increase of simulation time. It can be seen that DDBSC remained at a low level before 3.5 h, and its energy consumption after 3.5 h ranked the lowest among the five algorithms. When the time reaches 6 h, the total energy consumption of DDBSC is not more than 250, less than half of the maximum energy consumption algorithm. The DDBSC algorithm takes into account community nonuniformity and is based on a random block model and community detection. Other algorithms use copies more or less, but the DDBSC algorithm avoids this and the power-saving benefits become more prominent as simulation time increases. Therefore, in the entire data transmission process, its energy consumption is the lowest.Figure6 shows the change of end-to-end delay on average of the five algorithms with the increase of simulation time. This time around, the latency of the SECM algorithm is the highest, the average is other, and the average is twice that of the SW algorithm with 10 copies. The DDBSC was only a middling performer, but it is much lower than the SECM algorithm. Because the SW algorithm generates a large number of copies and sprays through the network, its diffusion ability is very strong. Our experiments show that the spraying and waiting algorithm performs best when the number of copies is 10. The end-to-end latency of the DDBSC algorithm, while stable, is consistently around 20 units higher.Figure7 shows the change of delivery ratio on average of the five algorithms with the increase of simulation time. It can be seen that the delivery of DDBSC has been maintained above 55%, with the average value exceeding 60% and the highest value reaching 68%. Such good performance is attributed to the proper selection of the community model and the efficient reconstruction of communities over time. Since we use the random block model to model the network data and apply Bayesian inference to the parameter derivation of the model, it has changed the current situation that the community is not clearly defined and greatly increased the average delivery. The ICMT algorithm identifies the probabilistic selection of all neighbor nodes and thus the best relay node; therefore, its message delivery rate is also high. In the SW algorithm, when the number of message copies is 30, the message delivery rate is the lowest.To sum up, we can draw the conclusion that with the increase of time, the performance of DDBSC in overhead, energy consumption, and the delivery ratio is the best among the five algorithms. However, the performance in terms of latency is still weaker than that of the spraying and waiting algorithm with 10 copies. As the simulation time continues to increase, the average delay performance of DDBSC is closer and closer to it.The cache size of a node is an important parameter that affects the efficiency of data transmission in the network. Figures8–11 show how the four performance parameters of the five algorithms change as the cache size changes. In this set of experiments, we change the node cache size every 0.5 h.Figure 8
The overhead situation changes with cache size increases.Figure 9
The energy consumption situation changes with cache size increases.Figure 10
The delay situation changes with cache size increases.Figure 11
The delivery ratio situation changes with cache size increase.Figure8 shows the change of data transmission overhead on average of the five algorithms with the increase of nodes’ cache size. It can be seen that with the steady increase of node cache capacity, the overhead of all routing algorithms decreases steadily. The routing overhead for DDBSC dropped from 210 to 25, the spray and wait routing algorithm (copy=10) dropped from 290 to 75, and the information cache management and data transmission algorithm dropped from 270 to 40. In the process of change, our DDBSC algorithm also has the largest drop in routing overhead. It dropped from about 200 to 40. Also, the overhead of the DDBSC algorithm is always the lowest. The drop in the above three algorithms is noteworthy as it shows a larger node cache and lower node overhead. The result shows that increasing node cache is an effective way to reduce routing overhead.Figure9 shows the change of data transmission energy consumption of the five algorithms with the increase of nodes’ cache size. It can be seen that with the increase of node cache capacity, the energy consumption of other algorithms increases significantly except that the energy consumption of DDBSC remains at a relatively stable low level. The DDBSC algorithm has the lowest energy consumption when the node cache is 15. As the node cache increases, although its energy consumption increases, the increase is smaller and is always the lowest among all algorithms. The significant reduction in energy consumption of DDBSC stems from its adoption of community-provided messaging methods. We dynamically form communities according to the degree of association between source nodes and destination nodes, and on this basis, perform efficient and relatively reliable data transmission. The SW routing algorithm consumes the most energy due to a large amount of replication and spraying. This is especially obvious when the number of replicas increases. The ICMT algorithm uses encounter transmission mode to copy information through a single replication. Compared with the spray and wait routing algorithms, the efficiency of energy optimization is better.Figure10 shows the change of end-to-end delay on average of the five algorithms with the increase of nodes’ cache size. It can be seen that, with a few exceptions, the end-to-end delay of all the five algorithms decreases with the increase of node capacity. Among them, the spray and wait routing algorithm (copy=10), the SECM algorithm, and the ICMT algorithm are the three algorithms with the most obvious time delay reduction. The DDBSC algorithm and the SW routing algorithm (copy=30) have very low delivery delays, so the decrease is not obvious. When the node cache capacity increases from 5 MB to 40 MB, the DDBSC drops from 78 to 25. It further reflects the low latency of our algorithm. This is mainly because DDBSC dynamically builds a community according to the weight distribution, applies Bayesian inference to the parameters during model building, and uses the back-propagation algorithm for iterative calculation, which greatly reduces the message delivery delay.Figure11 shows the change of delivery ratio on average of the five algorithms with the increase of nodes’ cache size. The delivery ratio of the five algorithms increases with the increase of node cache capacity. It can be seen that the DDBSC with the highest delivery ratio has the lowest value of 0.55 and the highest value of 0.85. The reason for its high delivery rate is that it realizes the nonuniformity of the community structure, dynamically forms the community according to the degree of association between the source node and the destination node, and successfully modeled it with SBM. While the SW algorithm uses the flood information transmission mode, the large amount of information loss results in the low delivery ratio. This defect becomes more apparent when the number of replicas is large. Its delivery rate is consistently below 0.6.Finally, in order to verify the impact on message transmission after the transmission size is changed in the above experiments. We performed the following experiments, as shown in Figure12. We set the node cache size to 15 MB and measured it from the initial experiment time. It can be seen from the figure that initially, with the increase of data packets, the transmission success rate of various algorithms is increasing. When the data packet reaches about 150 KB, the transmission success rate of the algorithm gradually decreases. This is mainly because with the increase of data packets, the packet loss rate begins to increase, so the transmission performance of the algorithm is affected. In the SW algorithm, the greater the number of message copies, the lower the delivery rate of the algorithm, which is always below 0.4. The delivery rate of the SECM algorithm reaches the maximum when the data packet is 150 KB. But the average delivery rate is not high. Compared with the SW and SECM algorithms, although the delivery rate of the ICMT algorithm is greatly affected by the packet size, the delivery rate is always higher than those of these two types of algorithms. The delivery rate of the DDBSC algorithm is always the highest, which is roughly consistent with that in Figure 7, indicating that the packet size has little effect on the algorithm.Figure 12
The delivery ratio situation changes with data packet increase.It can be seen from the above research that the excellent performance of the DDBSC algorithm is also reflected in the stability of energy consumption when the node cache capacity increases.


## 4.1. Baseline Algorithms

To evaluate the performance of the proposed method, we compare it with the following three typical algorithms. They are status estimation and cache management algorithm (SECM), information cache management and data transmission algorithm (ICMT) [38], and spray and wait routing algorithm (SW). Here is a brief introduction of how they work effectively.
(1)
SECM: the basic principle of status estimation and cache management algorithm is to evaluate the probability of data transmission between nodes and neighboring nodes. Then, adjust the data cache distribution to achieve the goal of a high transfer rate. In this algorithm, neighboring nodes share caching tasks with each other to achieve efficient information distribution(2)
ICMT: the main technique of information cache management and data transmission algorithm is the identification and evaluation of neighbor nodes in the same project. On this basis, the cache is adjusted to reach the high project probability of the node(3)
SW: the main technique of the spray and wait routing algorithm is to generate a lot of copies, spray them across the network, and wait until one of them reaches the destination node. An important performance parameter of this algorithm is the number of copies. In this study, we selected 10 and 30 copies, respectively


## 4.2. Metrics

Metrics are used to measure the performance of algorithms in opportunistic social networks. Four are selected in this paper; they are overhead on average (call overhead for short), energy consumption on average (call energy consumption for short), end-to-end delay on average (call delay for short), and the delivery ratio [4]. Here is a brief introduction of what they mean.
(1)
Overhead: the average overhead in data transmission between two nodes(2)
Energy consumption: the average energy consumption in data transmission between two nodes(3)
Delay: the average delay in data transmission between two nodes(4)
Delivery ratio: the probability of a source node choosing an available node to transfer data


## 4.3. Environment and Parameters

In this paper, we use a ONE simulation tool for experiments. We set the parameters according to the stochastic model of the social network, as shown in Table1. Among them, our simulation time is 6 hours, and data is recorded every 0.5 hours. We selected an area of 4500m×3400m on the map as the simulation area. All nodes choose the social model as the transmission mode. Furthermore, each source node carries 10 packets.Table 1
The main system parameters.
ParameterValueSimulation time6 hNumber of nodes500Transmission patternBroadcastTransmission interval20-25 sNode movement modeRandom site movement modelArea in networks4500∗3400m2Size of data packet100-200 KBData transfer range10 m2Node movement speed0.5-1.5 m/sFrequency of data packet25-35 sCache5-40 MBInitial value of energy100 JTransmission energy consumption of a single node1 J


## 4.4. Results

The simulation results are as follows. Figures4–7 show the changes of the four performance measurement parameters of the five selected algorithms with the increase of simulation time. Among them, the simulation time is mainly calculated from the time when the source node starts to transmit data, and the monitoring is continued for 6 hours. In addition, in the experiment, the cache size of the node is set to 15 MB.Figure 4
The overhead situation changes over time.Figure 5
The energy consumption situation changes over time.Figure 6
The delay situation changes over time.Figure 7
The delivery ratio situation changes over time.Figure4 shows the change of data transmission overhead of the five algorithms with the increase of simulation time. It can be seen that the overhead of DDBSC has been a stable and good performance. It stays below 150 MB. As simulation time increases, the number of nodes involved in data transmission is bound to increase. The reason the DDBSC algorithm remains stable is that it can ensure the efficient reconstruction of the community. At the same time, in order to solve the time complexity and reduce the communication overhead cost in opportunistic social networks, we propose a data delivery strategy based on the random block model and community detection (DDBSC), taking into account the nonuniformity of the community. ICMT performs well, which reaches its peak at time is 2 h and then begins to decline steadily. That is because it controls the interval between data transfers. You can also see that the spraying and waiting algorithm with 30 copies has the worst performance in terms of overhead.Figure5 shows the change of data transmission energy consumption of the five algorithms with the increase of simulation time. It can be seen that DDBSC remained at a low level before 3.5 h, and its energy consumption after 3.5 h ranked the lowest among the five algorithms. When the time reaches 6 h, the total energy consumption of DDBSC is not more than 250, less than half of the maximum energy consumption algorithm. The DDBSC algorithm takes into account community nonuniformity and is based on a random block model and community detection. Other algorithms use copies more or less, but the DDBSC algorithm avoids this and the power-saving benefits become more prominent as simulation time increases. Therefore, in the entire data transmission process, its energy consumption is the lowest.Figure6 shows the change of end-to-end delay on average of the five algorithms with the increase of simulation time. This time around, the latency of the SECM algorithm is the highest, the average is other, and the average is twice that of the SW algorithm with 10 copies. The DDBSC was only a middling performer, but it is much lower than the SECM algorithm. Because the SW algorithm generates a large number of copies and sprays through the network, its diffusion ability is very strong. Our experiments show that the spraying and waiting algorithm performs best when the number of copies is 10. The end-to-end latency of the DDBSC algorithm, while stable, is consistently around 20 units higher.Figure7 shows the change of delivery ratio on average of the five algorithms with the increase of simulation time. It can be seen that the delivery of DDBSC has been maintained above 55%, with the average value exceeding 60% and the highest value reaching 68%. Such good performance is attributed to the proper selection of the community model and the efficient reconstruction of communities over time. Since we use the random block model to model the network data and apply Bayesian inference to the parameter derivation of the model, it has changed the current situation that the community is not clearly defined and greatly increased the average delivery. The ICMT algorithm identifies the probabilistic selection of all neighbor nodes and thus the best relay node; therefore, its message delivery rate is also high. In the SW algorithm, when the number of message copies is 30, the message delivery rate is the lowest.To sum up, we can draw the conclusion that with the increase of time, the performance of DDBSC in overhead, energy consumption, and the delivery ratio is the best among the five algorithms. However, the performance in terms of latency is still weaker than that of the spraying and waiting algorithm with 10 copies. As the simulation time continues to increase, the average delay performance of DDBSC is closer and closer to it.The cache size of a node is an important parameter that affects the efficiency of data transmission in the network. Figures8–11 show how the four performance parameters of the five algorithms change as the cache size changes. In this set of experiments, we change the node cache size every 0.5 h.Figure 8
The overhead situation changes with cache size increases.Figure 9
The energy consumption situation changes with cache size increases.Figure 10
The delay situation changes with cache size increases.Figure 11
The delivery ratio situation changes with cache size increase.Figure8 shows the change of data transmission overhead on average of the five algorithms with the increase of nodes’ cache size. It can be seen that with the steady increase of node cache capacity, the overhead of all routing algorithms decreases steadily. The routing overhead for DDBSC dropped from 210 to 25, the spray and wait routing algorithm (copy=10) dropped from 290 to 75, and the information cache management and data transmission algorithm dropped from 270 to 40. In the process of change, our DDBSC algorithm also has the largest drop in routing overhead. It dropped from about 200 to 40. Also, the overhead of the DDBSC algorithm is always the lowest. The drop in the above three algorithms is noteworthy as it shows a larger node cache and lower node overhead. The result shows that increasing node cache is an effective way to reduce routing overhead.Figure9 shows the change of data transmission energy consumption of the five algorithms with the increase of nodes’ cache size. It can be seen that with the increase of node cache capacity, the energy consumption of other algorithms increases significantly except that the energy consumption of DDBSC remains at a relatively stable low level. The DDBSC algorithm has the lowest energy consumption when the node cache is 15. As the node cache increases, although its energy consumption increases, the increase is smaller and is always the lowest among all algorithms. The significant reduction in energy consumption of DDBSC stems from its adoption of community-provided messaging methods. We dynamically form communities according to the degree of association between source nodes and destination nodes, and on this basis, perform efficient and relatively reliable data transmission. The SW routing algorithm consumes the most energy due to a large amount of replication and spraying. This is especially obvious when the number of replicas increases. The ICMT algorithm uses encounter transmission mode to copy information through a single replication. Compared with the spray and wait routing algorithms, the efficiency of energy optimization is better.Figure10 shows the change of end-to-end delay on average of the five algorithms with the increase of nodes’ cache size. It can be seen that, with a few exceptions, the end-to-end delay of all the five algorithms decreases with the increase of node capacity. Among them, the spray and wait routing algorithm (copy=10), the SECM algorithm, and the ICMT algorithm are the three algorithms with the most obvious time delay reduction. The DDBSC algorithm and the SW routing algorithm (copy=30) have very low delivery delays, so the decrease is not obvious. When the node cache capacity increases from 5 MB to 40 MB, the DDBSC drops from 78 to 25. It further reflects the low latency of our algorithm. This is mainly because DDBSC dynamically builds a community according to the weight distribution, applies Bayesian inference to the parameters during model building, and uses the back-propagation algorithm for iterative calculation, which greatly reduces the message delivery delay.Figure11 shows the change of delivery ratio on average of the five algorithms with the increase of nodes’ cache size. The delivery ratio of the five algorithms increases with the increase of node cache capacity. It can be seen that the DDBSC with the highest delivery ratio has the lowest value of 0.55 and the highest value of 0.85. The reason for its high delivery rate is that it realizes the nonuniformity of the community structure, dynamically forms the community according to the degree of association between the source node and the destination node, and successfully modeled it with SBM. While the SW algorithm uses the flood information transmission mode, the large amount of information loss results in the low delivery ratio. This defect becomes more apparent when the number of replicas is large. Its delivery rate is consistently below 0.6.Finally, in order to verify the impact on message transmission after the transmission size is changed in the above experiments. We performed the following experiments, as shown in Figure12. We set the node cache size to 15 MB and measured it from the initial experiment time. It can be seen from the figure that initially, with the increase of data packets, the transmission success rate of various algorithms is increasing. When the data packet reaches about 150 KB, the transmission success rate of the algorithm gradually decreases. This is mainly because with the increase of data packets, the packet loss rate begins to increase, so the transmission performance of the algorithm is affected. In the SW algorithm, the greater the number of message copies, the lower the delivery rate of the algorithm, which is always below 0.4. The delivery rate of the SECM algorithm reaches the maximum when the data packet is 150 KB. But the average delivery rate is not high. Compared with the SW and SECM algorithms, although the delivery rate of the ICMT algorithm is greatly affected by the packet size, the delivery rate is always higher than those of these two types of algorithms. The delivery rate of the DDBSC algorithm is always the highest, which is roughly consistent with that in Figure 7, indicating that the packet size has little effect on the algorithm.Figure 12
The delivery ratio situation changes with data packet increase.It can be seen from the above research that the excellent performance of the DDBSC algorithm is also reflected in the stability of energy consumption when the node cache capacity increases.


## 5. Conclusion

This paper dynamically builds communities in the opportunistic network according to the weight distribution and takes into account the nonuniformity of communities. To solve the hot transmission problems of time complexity and decrease overhead costs, this paper proposes an effective data transmission strategy based on SBM and community detection. The experiment results show that compared with the other four effective data transmission algorithms of the opportunistic network, the algorithm proposed in this paper has an excellent performance in overhead, energy consumption, and delivery ratio.In the future, with the increase of the huge network composed of mobile devices, data transmission will have more and more prominent requirements for low delay and low energy consumption. A further study of reducing time complexity for the routing algorithm in the opportunistic network is of great significance. Our next focus will be on this.



---

*Source: 5067849-2022-05-05.xml*