The Evolution Of Unstable Social Relationship And Community Division In Opportunistic Networks

In social opportunistic networks, there are social relations between nodes. The nodes with close social relations form communities. Social relations and com-munity relations are the core basis of message routing decision in social oppor-tunistic networks, it is of great scientific significance to research the evolution of unstable social relationship and community division in opportunistic networks.At present, it is assumed that the social relations are stable and static in the research of the sociality in opportunistic networks and the routing strategy which is based on the sociality. And the community based on this hypothesis is stable. However, in the practical application scenarios of opportunistic networks, social relations and relations of the community are usually dynamic, including:a node only forwards a specific type of message, when a message sequence which is formed staggerly and repeatly by different types of messages is spreading in the networks, the available social relations and community relations change and vibrate repeatly, finally present a unstable state. Because nodes are mobile and they encounter each other randomly, Social relations and community relations change dynamicly over time. The cohesion of social relations between nodes is uncertain, hence communities which are based on these relations, are uncertain and exists in the form of probability.According to the characteristic of the dynamic change of social relations and community relations in opportunistic networks, in this thesis, we analyze and solve the problem of community division under opportunistic networks which vibrate unstably and evolute dynamicly. In this thesis, we mainly include three interrelated problems:Firstly, we solve the problem of vibration which is caused by the sensitive message in the social relations. Secondly, we also solve the problem that the social relation is unpredictable while changing over time, and we establish a prediction model to predict social relations in the future. Finally, we establish uncertain social relations based on the predicted social relations, and solve the problem of which we can’t get communities that are closer to real-ity on uncertain social relations.The main contributions and innovations of this thesis are as follows:1. Propose a hierarchical model of opportunistic networks under unstable social relations. In opportunistic networks, a node only forwards a spectific type of message. When different types of messages are spreading in the networks, the set of available node is different. Therefore, when a message sequence, which is formed staggerly and repeatly by different types of messages is spreading in the networks, the available social relations change repeatedly, which presents that social relations are in the unstable state of vibration because of the sensitive message. Consequently, the results of community division cannot reuse and greatly increases the period of community division. To solve the problem, we propose a hierarchical model of opportunistic networks to eliminate the unstate of vibration caused by sensitive message in social relations, and improve the reusability of community divisions. At the same time, we also reduce the time consumption of community divisions. Firstly, we map the set of physical nodes of opportunistic networks to a set of virtual nodes which is matched with the types of messages, and based on this mapping to establish virtual opportunistic networks layers. Then we establish the social relationon on the virtual opportu- nistic networks layer. At the same time, the sensitive message of social relations is changing from unstable and vibrated state to the stable state. Finally, we use the social relations on the vitural layer to divide the communities. This model makes the times of community divisions only based on the number of message types, and the times cannot be changed by the number of massages in the mas-sage sequences or by the interleaving of massage types. And the model reduces the time consumption of community divisions. When the number of massages is same, under this situation, when the type difference of the adjacent position in the message sequence is 40% or is 100%, compared with dividing communities directly on the opportunistic networks, the time consumption of community di-visions which apply the hierarchical model of opportunistic networks will re-duce about 58% and 89% respectively.2. Propose a dynamic evolution predicted model of the social relations in opportunistic networks. In opportunistic networks, because social relations change over time, we need divide communities after establishing social relations. Hence this situation also increases waiting time. In order to solve the problem, in this thesis, we propose a predicted model of social relations in opportunistic networks, which is based on the Markov chain. Using this model, we will pre-dict social relations accurately and reduce the waiting time of community divi-sions, and this model also reduces the preparation time of transmiting messages. Firstly, we decompose the operation time of the opportunistic networks isome-tric time slices, and we build the social relations between nodes, which is based on the encounter state of nodes in a time slice. Secondly, in the sequence of time slices, recording the encounter state of node pairs in different time slices, and build the sequence of the encounter state of node pairs, which is corresponding to the sequence of time slices. Thirdly, based on the sequence we mentioned be-fore, the Markov chain is used to establish the probability matrix for the trans i- tion of the encounter state. Finally, according to the dynamic predicted evolution model of the social relations which we proposed in this thesis, we can predict the encounter state of node pairs in the next time slice. And when we use this model, the accuracy of the prediction can reach more than 80%.3. Propose a K-clique filtering algorithm based on the Community Social Cohesion. At present, community divisions in the opportunistic networks is based on the certain social relations between nodes. However, in the actual situ-ation, social relations are determined by the node’s encounter frequency and the success rate of communication, and social relations are uncertain. In order to solve the problem about how to divide communities in the uncertain social rela-tions of opportunistic networks, we propose a K-clique filtering algorithm which is based on the social conhesion in this thesis. Firstly, according to the encounter state of nodes and the communication between nodes, we build an uncertain model of social relations in opportunistic networks. Secondly, we propose the concept of social cohesion, and we define the meaning of communities in the uncertain social relations, which based on the social cohesion. Finally, we pro-pose an improved K-clique filtering algorithm based on social cohesion. The al-gorithm can divide the communities with the uncertain social relations, and get a structural and practical significant community. The experiment shows that, compared with the existed K-clique filtering algorithm, the K-clique filtering algorithm based on the Community Social Cohesion, we can get much time slices (80%) and get the reasonable result of divisons in opportunistic networks.