Hindawi Wireless Communications and Mobile Computing Volume 2019, Article ID 3173152, 16 pages https://doi.org/10.1155/2019/3173152 Research Article Exploiting Temporal and Spatial Regularities for Content Dissemination in Opportunistic Social Network Zhiyuan Li ,1,2 Junlei Bi,1 and Carlos Borrego3 1 School of Computer Science and Communication Engineering, Jiangsu University, China 2 Jiangsu High Technology Research Key Laboratory for Wireless Sensor Networks, Jiangsu, China 3 Department of Information and Communications Engineering, Autonomous University of Barcelona, Spain Correspondence should be addressed to Zhiyuan Li; lizhiyuan81@126.com Received 2 October 2018; Revised 11 January 2019; Accepted 13 February 2019; Published 6 March 2019 Guest Editor: Sujata Pal Copyright Β© 2019 Zhiyuan Li et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Recently, content dissemination has become more and more important for opportunistic social networks. The challenges of opportunistic content dissemination result from random movement of nodes and uncertain positions of a destination, which seriously affect the efficiency of content dissemination. In this paper, we firstly construct time-varying interest communities based on the temporal and spatial regularities of users. Next, we design a content dissemination algorithm on the basis of time-varying interest communities. Our proposed content dissemination algorithm can run in 𝑂(𝑛 log 𝑛) time. Finally, the comparisons between the proposed content dissemination algorithm and state-of-the-art content dissemination algorithms show that our proposed content dissemination algorithm can (a) keep high query success rate, (b) reduce the average query latency, (c) reduce the hop count of a query, and (d) maintain low system overhead. 1. Introduction OSN. Although the epidemic content dissemination is an optimal solving method under no contention, it is wasteful Opportunistic social networking (OSN) emerges as a new for network resources due to amounts of data message paradigm of mobile social networking [1, 2]. Different from copies. In the probability-based content dissemination [6, 7], online social networking, the mobile users have to use wire- every node records historical contact information with its less short distance communication technologies to oppor- neighbors. And then, the nodes can create frequent contact tunistically communicate with others in OSN. There are new lists according to the historical contact information. The data challenges in OSN, and one of the most challenging ones is message is forwarded to a close node who can possibly deliver content dissemination [3]. The goal of content dissemination this query to resource holders. The probability-based content in OSN is to successfully propagate a data message to a dissemination is a locally optimal method, and hence the destination node. Nowadays, the existing content dissemi- methods make the data messages stay in a small search scope. nation has been classified into three categories, such as the For the interest community-based content dissemination epidemic content dissemination [4, 5], the probability-based [19], each device is associated with an interest vector extracted content dissemination [6–17], and the interest community- from user profiles, and the devices with same interests form based content dissemination [18–23]. an interest community. Each data message is also described Epidemic content dissemination originates from flooding by an interest vector. The data messages are disseminated data messages in intermittently connected mobile networks within one interest community or multiple interest com- [4]. For the epidemic content dissemination, each node munities. However, the drawbacks of content dissemination maintains a list of messages it carries. Whenever it encounters based on interest community lie in two aspects. One aspect another node, the two nodes exchange the messages that is topology mismatched due to not considering the physical they do not have with each other. If the connection lasts connections of nodes. The other aspect is inaccurate interest long enough, the data messages may traverse all nodes in representation since nodes provide little privacy information. 2 Wireless Communications and Mobile Computing The two aspects lead to the performance degradation of have been proposed to improve the efficiency of content content dissemination based on interest community. dissemination. Saha and Misra define a function for To cope with the aforementioned limitations of content probabilistic replication of any message m in [3]. When the dissemination, we propose a content dissemination based function value is greater than or equal to a random number on time-varying interest community in OSN. The main π‘Ÿ ∈ [0, 1], the message m is replicated and forwarded. Daly contributions of this study are shown as follows. and Haahr [6] proposed a content dissemination protocol (a) We use temporal and spatial correlations to construct based on social network analysis, called SimBet. The SimBet a time-varying interest community model. content dissemination uses betweenness centrality and (b) Based on the time-varying interest community model, similarity metrics to identify some β€œbridge” nodes (with high we propose a content dissemination which runs in 𝑂(𝑛 log 𝑛) values on these metrics) in networks. To control the system time. overhead, node n calculates the betweenness centrality 𝐡𝑒𝑑𝑛 (c) We evaluate the performances of proposed content and similarity π‘†π‘–π‘šπ‘› with its local neighborhood. Then, the dissemination in terms of query success rate, average query node n can compute its SimBet value, which is a weighted latency, hop count of a query, and system overhead. combination of the betweenness utility and the similarity The remainder of this paper is organized as follows: utility. If π‘†π‘–π‘šπ΅π‘’π‘‘π‘ˆπ‘‘π‘–π‘™π‘š(𝑑) is greater than π‘†π‘–π‘šπ΅π‘’π‘‘π‘ˆπ‘‘π‘–π‘™π‘›(𝑑), Section 2 describes the related work and motivation. In. node n forwards the data message to node m. Otherwise, Section 3 presents a content dissemination algorithm based node n continues to hold the message. But, it is still possible on time-varying interest communities. In Section 4, the that the node with high SimBet utility fails to deliver the performances of our proposed method are evaluated and message to the destination due to the uncertainty of future analyzed. Finally, Section 5 concludes our study and gives the encounters and underlying social graph. To construct an future directions of this research. opportunistic ordered service chaining in [7], Saha and Misra also compute the delivery probability values by PRoPHET. 2. Related Work and Motivation However, unlike PRoPHET, they select a node who has the highest delivery probability as the intermediate node In this section, the advantages and drawbacks of existing con- and uses the unicast way to deliver the data message to the tent dissemination methods are analyzed by classifying them best service providers. Reference [16] studied the message into three categories: the epidemic content dissemination, replication for content dissemination in opportunistic the probability-based content dissemination, and the interest mobile networks. In this study, authors in [16] considered community-based content dissemination. multiple attributes for message replication decision, such as interest hits, the number of entries in forwarding information 2.1. Epidemic Content Dissemination. For uncertain positions base, and the average time interval between two successive of destinations in OSN, Vahdat et al. [4] proposed an contacts. And then, they designed an interests replication epidemic-based message dissemination for partially con- algorithm from node i to node j according to the attributes nected ad hoc networks. The epidemic-based content dis- mentioned above. The interests replication algorithm can semination is for sending messages to destinations through help the node i to make a decision about whether sending those moving nodes. When the moving nodes meet, they the interest message to other nodes or not. exchange their summary vectors to determine which mes- sages remotely stored have not been seen by the local node. 2.3. Interest Community-Based Content Dissemination. Inter- In turn, each node then requests copies of messages that est community is an overlay network to enhance the scala- it has not yet seen. In this way, the data messages can bility of content dissemination [17]. In ecology, a community arrive at every node in the network. The epidemic content is an assemblage of two or more populations of different dissemination outperforms two other content dissemination species occupying the same geographical area. In sociology, methods in terms of successful rate of message delivery. a community is usually defined as a group of interacting However, the epidemic content dissemination can generate people living in a common location. Community ecologists multicopies of a data message during a task execution, and and sociologists study the interactions between species and hence the method may incur high system overhead, such people in communities at many temporal and spatial scales as network bandwidth and battery depletion. To control the [18–22]. Once interest communities are constructed, the system overhead, Spyropoulos et al. [5] presented the spray content dissemination is efficiently implemented on top of and wait content dissemination including basic spray and the overlay network. Li and Wu [20] proposed a mobile wait and binary spray and wait. In the spray and wait content community-based pub/submethod to promote the efficiency dissemination, the number of copies of a message is set to of message delivery. In [20], communities are constructed reduce the system overhead. However, how to automatically using encounter frequencies of nodes. However, people with adjust the parameter L to achieve the tradeoff between the long-term social ties do not necessarily have similar interests. successful rate of message delivery and the system overhead For example, the graduate students and their advisors usually is still a puzzle. work and talk in the same office from 9 a.m. to 5 p.m., but their interests may be different. Chen et al. [18] leverage 2.2. Probability-Based Content Dissemination. In OSN, the interest similarity to study content dissemination in dis- probability-based content dissemination methods [3, 6, 7, 16] connected wireless networks, called SPOON. In SPOON, an Wireless Communications and Mobile Computing 3 (d) Time-varying community (c) Interest community optimization Dormitory Buildings Cr1 Library 2 Dining Temporal and 5 12 3 7 Room spatial correlations Cg1 4 Cg2 10 1 6 Computer Community 11 School Cr2 renewal 8 Cy1 9 Cy2 Content Loop Social Social closeness Dissemination regularity strength Cr 2 4 2 1 3 5 10 Keywords 4 3 5 6 extraction 11 8 Cg 12 Interest 1 7 6 12 similarity 11 7 10 8 9 Cy 9 (b) Interest community (a) Underlying networks (Overlay networks) Figure 1: Relationship between components in system model. interest extraction is used to collect a node’s interests from its the structure optimization of interest communities are given. file resources. The nodes with common interests are classified Then, the time-varying community model based on temporal into the same interest community. Then, the epidemic content and spatial correlations is presented. Based on the time- dissemination is used within a community. Through the varying communities, we propose a content dissemination social network analysis, the nodes frequently visiting other algorithm. communities are assigned as the community ambassadors for intercommunity content dissemination. However, topology 3.1. Overview. Figure 1 illustrates the principle of system mismatch affects the performances of SPOON. The topology model. In the figure, different colored circles represent nodes mismatch is defined as the difference between the interest with different interests. community and the underlying networks. The interest com- Figure 1(a) shows the underlying networks. As shown in munity only shows the logical connections among nodes. the subfigure, different interest nodes are connected through For example, node i is a neighbor of node j in the interest wireless access points. Interest communities are constructed community. However, node i is far from node j over the as overlay networks on top of underlying networks, as physical networks. Hence, the topology mismatch seriously shown in Figure 1(b). The nodes in interest communities have affects the efficiency of content dissemination in OSN. similar interests and show the consistent behavior patterns. To cope with the aforementioned limitations of content To overcome the deficiencies of constructed interest commu- dissemination, we have extracted interests and preferences of nities, we study the social relations of users and present the users and constructed time-varying interest communities by definition of social closeness strength. Then, the metric of the factor of temporal and spatial correlation. The detailed social closeness strength is used to optimize the topological descriptions are shown in Section 3. structure of interest communities. Figure 1(c) shows that interest communities are divided into closer subcommunities 3. System Model and Content by the metric of social closeness strength. After that, time- Dissemination Implementation varying community model based on temporal and spatial correlations is proposed to reconstruct interest communities. In this section, we firstly describe the overview of system The reconstruction process for interest communities can be model. Next, both the formation of interest communities and achieved according to steps Figures 1(a)–1(c). Finally, we 4 Wireless Communications and Mobile Computing Table 1: Summary of presented symbols. Step 1 (interest representation of a node). We firstly use spaCy package to scan the metadata of multimedia contents and Name Description the titles of documents in a tablet, e.g., surface pro 4. After π‘˜β„Ž The β„Ž-th keyword some natural language processing steps including removing π‘“β„Ž The frequency of the β„Ž-th keyword stop words (the most common words), such as the, is, at, π‘“π‘˜(𝛼) (𝑛) The frequency of keyword π‘˜(𝛼) for node 𝑛 which, and on, stemming and lemmatization, the keywords of π‘€π‘›π‘˜(𝛼) The weight of keyword π‘˜(𝛼) for node 𝑛 a node are extracted. The combination of multiple keywords can show interests of a node. Preset threshold for interest community π‘‡π‘ π‘–π‘š Interests of a node i are represented using an interest construction vector 𝑠(𝑖), as shown in 𝑇𝑖𝑗 Average inter-contact time between nodes 𝑖 and 𝑗 πœ† Social closeness strength 𝑠 (𝑖) = {(π‘˜1 , 𝑓1 ) , (π‘˜2 , 𝑓2 ) , β‹… β‹… β‹… (π‘˜π‘› , 𝑓𝑛 )} (1) Time remaining to the next contact between 𝑓(𝑑) nodes after time 𝑑 where the symbol π‘˜β„Ž refers to the h-th keyword, the symbol π‘“β„Ž is the frequency of the h-th keyword, the key-value pairs (π‘˜β„Ž , π‘“β„Ž ), β„Ž ∈ [1, 𝑛] are sorted by the frequency π‘“β„Ž in design and implement a content dissemination based on the descending order, and the subscript n is self-defined. interest communities. The weight of a keyword π‘˜(𝜏) for an interest vector 𝑠(𝑖) is In order to enhance the readability of this paper, the denoted as summary of presented symbols is shown in Table 1. π‘“π‘˜(𝜏) (𝑖) π‘€π‘–π‘˜(𝜏) = (2) 3.2. Interest Community Formation. Users with common βˆ‘π‘›π›½=1 𝑓𝛽 (𝑖) interests tend to join the same community, and their shared resources are similar. The resources owned by users are used where the symbol π‘€π‘–π‘˜(𝜏) refers to the weight of a keyword π‘˜(𝜏) to show their interests, such as frequently used documents, for an interest vector 𝑠(𝑖) of node i. photos, music, and videos, but not limited to these items. Hence, we can extract interests of nodes from profiles of users Step 2 (interest similarity between nodes). Formula (3) is or metadata of shared resources. Next, we describe the steps used to calculate the interest similarity π‘–π‘›π‘‘π‘’π‘Ÿπ‘’π‘ π‘‘ π‘ π‘–π‘š(𝑖, 𝑗) of interest community formation. between nodes i and j. βˆ‘π‘š π‘˜(𝛼) 𝛼=1 𝑀𝑖 Γ— π‘€π‘—π‘˜(𝛼) π‘–π‘›π‘‘π‘’π‘Ÿπ‘’π‘ π‘‘ π‘ π‘–π‘š (𝑖, 𝑗) = 2 2 √ βˆ‘π‘š π‘˜(𝛼) 𝛼=1 (𝑀𝑖 ) Γ— √ βˆ‘π‘š π‘˜(𝛼) 𝛼=1 (𝑀𝑗 ) βˆ‘π‘š 𝑛 𝑛 𝛼=1 (π‘“π‘˜(𝛼) (𝑖) / βˆ‘π›½=1 𝑓𝛽 (𝑖) Γ— π‘“π‘˜(𝛼) (𝑗) / βˆ‘π›½=1 𝑓𝛽 (𝑗)) = (3) 2 2 √ βˆ‘π‘š 𝑛 √ π‘š 𝑛 𝛼=1 (π‘“π‘˜(𝛼) (𝑖) / βˆ‘π›½=1 𝑓𝛽 (𝑖)) Γ— βˆ‘π›Ό=1 (π‘“π‘˜(𝛼) (𝑗) / βˆ‘π›½=1 𝑓𝛽 (𝑗)) βˆ‘π‘š 𝑛 𝑛 𝛼=1 (π‘“π‘˜(𝛼) (𝑖) Γ— π‘“π‘˜(𝛼) (𝑗) / βˆ‘π›½=1 𝑓𝛽 (𝑖) Γ— βˆ‘π›½=1 𝑓𝛽 (𝑗)) = 2 2 √ βˆ‘π‘š 𝑛 √ π‘š 𝑛 𝛼=1 (π‘“π‘˜(𝛼) (𝑖) / βˆ‘π›½=1 𝑓𝛽 (𝑖)) Γ— βˆ‘π›Ό=1 (π‘“π‘˜(𝛼) (𝑗) / βˆ‘π›½=1 𝑓𝛽 (𝑗)) where π‘š is the number of same keywords between nodes i vector to its neighbors. After that the neighboring nodes will and j, π‘˜(𝛼), 𝛼 ∈ [1, π‘š] denotes the same keyword of nodes calculate the interest similarity with node 𝑖 using formula i and j, and π‘€π‘–π‘˜(𝛼) and π‘€π‘—π‘˜(𝛼) represent the weights of the (3). If their interest similarities are greater than or equal keyword π‘˜(𝛼) for nodes i and j, respectively. π‘“π‘˜(𝛼) (𝑖) and to the preset threshold π‘‡π‘ π‘–π‘š , the nodes will join the same π‘“π‘˜(𝛼) (𝑗) are the frequencies of the keyword π‘˜(𝛼) for nodes i community. Otherwise, a new community is created. When and j, respectively. the nodes in network are not connected, it is necessary to Each node can calculate interest similarity with others wait for the next contact between them. The procedure above using formula (3). Then, we can construct different interest is repeated until the constructed interest communities may communities for nodes in OSN. cover all nodes in OSN. It is noted that a node only belongs to an interest community. In other words, if a node has Step 3 (interest community construction). The nodes can already joined in an interest community, the node will not get their interest vectors using formula (1). When the nodes join another interest community. The algorithm of interest in network are connected, node 𝑖 will broadcast its interest community construction is shown in Algorithm 1. Wireless Communications and Mobile Computing 5 Input: Interest vector of node 𝑛π‘₯ , π‘₯ ∈ [1, 𝑁] and the total number of nodes 𝑁 Output: Interest communities 𝐢𝑖 , 𝑖 ∈ [0, 𝑁] (1) Initiation: Create the first interest community 𝐢𝑖 = βŒ€, 𝑖 = 0 (2) Begin (3) 𝐢𝑖 = {𝑛0 } (4) do (5) { (6) if connections among nodes exist (7) { (8) for each neighbor 𝑛𝑒 of node 𝑛π‘₯ do (9) { (10) 𝑛π‘₯ broadcastTo its neighbor𝑛𝑒 (11) 𝑛𝑒 calculate π‘–π‘›π‘‘π‘’π‘Ÿπ‘’π‘ π‘‘ π‘ π‘–π‘š(π‘₯, 𝑒) (12) if π‘–π‘›π‘‘π‘’π‘Ÿπ‘’π‘ π‘‘ π‘ π‘–π‘š(π‘₯, 𝑒) β‰₯ π‘‡π‘ π‘–π‘š (13) then { (14) 𝐢𝑖 = 𝐢𝑖 βˆͺ 𝑛 𝑒 (15) } (16) else { (17) creatNewCommunity 𝐢𝑖++ (18) } (19) } (20) } (21) else (22) { (23) Wait the next contact (24) Goto (6): (25) } (26) } (27) While (Union 𝐢 of interest community set 𝐢𝑖 == N) (28) Return 𝐢 (29) End Algorithm 1: Interest community construction. Next, we give an example to explain the algorithm. Suppose that node 𝑛0 firstly joins the first created interest time community 𝐢0 . After that, when node 𝑛0 meets with node 𝑛2 0 T and their interest similarity is greater than or equal to π‘‡π‘ π‘–π‘š , f(t) f(t) f(t) node 𝑛2 sends a request to node 𝑛0 for joining the interest Figure 2: Contacts between nodes i and j. community 𝐢0 . Otherwise, node 𝑛2 can create a new interest community, called 𝐢1 . If both node 𝑛5 and nodes 𝑛0 and 𝑛2 have higher interest similarity than the preset threshold π‘‡π‘ π‘–π‘š , node 𝑛5 and its first contact node are in the same interest j during the period [0, 𝑇]. In this figure, the width of a community. The running of this algorithm will terminate box represents the contact time, the time interval between until all nodes have joined an interest community. two adjacent boxes represents the inter-contact time 𝑓(𝑑), and the frequency of contacts is four during the period 3.3. Interest Community Optimization Based on Social Close- [0, 𝑇]. ness Strength. In this section, we firstly give the metric Next, we give the formal definition of social closeness definition of social closeness strength. Then, we use the social strength. The average intercontact time between nodes i and closeness strength to represent social relationship between j is denoted as nodes. The social relationship can help us to optimize the 𝑇 topological structure of interest community. For example, βˆ«π‘‘=0 𝑓𝑖𝑗 (𝑑) 𝑑𝑑 𝑇𝑖𝑗 = (4) we use the nodes with high social closeness strength instead 𝛾𝑖𝑗 of current neighbors of a node in an interest commu- nity. where 𝑇𝑖𝑗 represents the average intercontact time between The social closeness strength contains three social fea- nodes i and j, 𝑓(𝑑) represents the time remaining to the tures, such as contact time, intercontact time, and contact next contact between nodes i and j after time t, and 𝛾 is the frequency. Figure 2 shows the contacts between nodes i and frequency of contacts between them during the period [0, 𝑇]. 6 Wireless Communications and Mobile Computing Cr (6) again. Node 𝑛6 finds that it is still no result. That is because 2 node 𝑛6 never contacts nodes 𝑛9 and 𝑛11 . The edges between 10 4 3 5 node 𝑛6 and nodes 𝑛9 and 𝑛11 are cut off. After that node 𝑛9 12 Cg 1 7 Cy 6 tries to calculate the social closeness strength with node 𝑛11 8 11 using formula (5). As a result, node 𝑛9 can get the direct social C3 9 Cr1 closeness strength with node 𝑛11 . The edge between nodes 2 12 3 5 7 𝑛9 and 𝑛11 is added into the interest community Cy2 . For the Cg1 Interest community Cy2 interest community 𝐢𝑔 , the social closeness strength between 10 1 6 4 Cg2 Cr2 11 nodes 𝑛2 and 𝑛12 is calculated via the relay node 𝑛1 by formula 8 Cy1 1 2 4 (6). Also, the social closeness strength between nodes 𝑛4 and 3 5 9 6 𝑛8 is calculated via the relay node 𝑛5 by formula (6). The edge 12 11 8 Interest community optimization between nodes 𝑛2 and 𝑛12 is added into the community 𝐢𝑔1 . 10 7 Besides, the edge between nodes 𝑛4 and 𝑛8 is also added into 9 the community 𝐢𝑔2 . Underlying Networks Figure 3: Community optimization using social relationship. 3.4. Time-Varying Community Model Based on Temporal- Spatial Correlations. The community structure depends on social behaviors of people and hence the constructed interest Definition 1 (direct social closeness strength). Direct social community has its life cycle. The life cycle of an interest closeness strength between nodes i and j is the inverse of community contains three states: born state, active state, and average intercontact time between the two nodes, as shown dead state. The three states depend on time and places of in formula (5). The smaller the value 𝑇𝑖𝑗 is, the closer the social activities. Next, we present time-varying community friendship between nodes i and j is. model. As shown in formula (7), we define two matrices T and S. T is the time matrix of state transition for a community, 1 𝛾𝑖𝑗 and the element 𝑑𝑖𝑗 in matrix T represents the transition time πœ† 𝑖𝑗 = = 𝑇 (5) from state i to state j for a community. S is the probability 𝑇𝑖𝑗 ∫ 𝑓 (𝑑) 𝑑𝑑 𝑑=0 𝑖𝑗 matrix for a community stay at state i, and the element π‘ π‘–πœ€ in matrix S represents the probability for the sojourn time of a In OSN, it is possible for some nodes not to contact with community stay at state i less than πœ€ time units. others ever before. It is necessary to define the indirect social closeness strength. Definition 2 (indirect social closeness strength). Indirect 0 𝑑12 β‹… β‹… β‹… 𝑑1𝑗 social closeness strength is defined as 𝑑21 0 β‹… β‹… β‹… 𝑑2𝑗 𝑇=( . . ), 𝑀=𝑖,𝑗 ΜΈ .. .. d ... πœ†βˆ—π‘–π‘— = ∏ πœ† 𝑖𝑀 Γ— πœ† 𝑀𝑗 π‘€βˆˆπ‘Ÿπ‘’π‘™π‘Žπ‘¦ 𝑑𝑖1 𝑑𝑖2 β‹… β‹… β‹… 0 (6) (7) 𝑀=𝑖,𝑗 ΜΈ 𝛾𝑖𝑀 Γ— 𝛾𝑀𝑗 𝑠11 𝑠12 β‹… β‹… β‹… 𝑠1πœ€ = ∏ 𝑇 𝑇 𝑠21 𝑠22 β‹… β‹… β‹… 𝑠2πœ€ π‘€βˆˆπ‘Ÿπ‘’π‘™π‘Žπ‘¦ ∫ 𝑓𝑖𝑀 (𝑑) 𝑑𝑑 Γ— βˆ«π‘‘=0 𝑓𝑀𝑗 (𝑑) 𝑑𝑑 𝑑=0 𝑆=( . . ) .. .. d ... where 𝑀 represents the relay nodes between nodes i and j, 𝛾𝑖𝑀 is the frequency of contacts between nodes i and 𝑀, 𝛾𝑀𝑗 𝑠𝑖1 𝑠𝑖2 β‹… β‹… β‹… π‘ π‘–πœ€ is the frequency of contacts between nodes 𝑀 and j, 𝑓𝑖𝑀 (𝑑) represents the time remaining to the next contact between nodes i and 𝑀 after time t, and 𝑓𝑀𝑗 (𝑑) represents the time Then, the transition probability of a community from remaining to the next contact between nodes 𝑀 and j after state i to state j after 𝜎 time units is defined as time t. Figure 3 depicts the process of interest community opti- 𝐿 𝑖𝑗 (𝜎) = 𝑃 (π‘‹πœŽ = 𝑗 | 𝑋0 = 𝑖) = 𝑝𝑖𝑗 𝑠(𝑖)(πœŽβˆ’π‘‘π‘–π‘—) (8) mization. After the interest communities 𝐢𝑔 , Cr , and Cy are constructed, the social closeness strength between nodes in the Ci is calculated using formulas (5)-(6). Let us take where 𝑝𝑖𝑗 is the transition probability of a community from the interest community Cy as an example. Node 𝑛6 tries to state i to state j. The value 𝑝𝑖𝑗 is generated by the social calculate the social closeness strength with nodes 𝑛9 and 𝑛11 regularity of users. For example, most people work in their using formula (4), but node 𝑛6 finds it to be impossible to offices between 9 a.m. and 5 p.m. during the weekdays. After calculate this value. And then, node 𝑛6 tries to calculate the that, they will leave their working places and go home or social closeness strength with nodes 𝑛9 and 𝑛11 using formula attend parties of their friends. Wireless Communications and Mobile Computing 7 Dormitory Comprehensive Learning Dormitory Buildings Community Buildings Library Comprehensive Learning Community Restaurant Library Restaurant Computer Null Mobility School Computer Community Computer School 10 a.m. Dormitory Dormitory Buildings Null Buildings Mobility Comprehensive Community Mobility Library Restaurant Library Restaurant Comprehensive y it Community bil Null Mo Security Null Community Computer Computer School 10 p.m. School noon Figure 4: Temporal and spatial correlations-based community transformation. When a community transits from state i into state j via constructed at library and dormitory buildings. Few people intermediate state r, the transition probability of a commu- are in restaurant, and hence no community is constructed. nity is defined as At noon, students and faculties enter restaurants. The com- prehensive community is constructed at the restaurants. πœŽβˆ’1 The constructed interest communities at computer school, 𝐿 π‘–π‘Ÿπ‘— (𝜎) = ∏ ∏𝐿 π‘–π‘Ÿ (𝜏) 𝐿 π‘Ÿπ‘— (𝜎 βˆ’ 𝜏) (9) library, and dormitory buildings are dismissed. At 10 p.m., ΜΈ 𝜏=1 π‘Ÿ=𝑖,𝑗 students and faculties go back to their dormitory buildings. Hence, the general state transition probability of a com- The comprehensive community is constructed at dormitory munity is shown in buildings. The constructed communities at computer school and library have been transformed into security community 𝑝𝑖𝑗 𝑠(𝑖)(πœŽβˆ’π‘‘π‘–π‘—) , π‘Ÿ=0 to protect security of public properties. After communities { { { have transformed, some old communities are dismissed, and 𝐿 𝑖𝑗 (𝜎) = { πœŽβˆ’1 (10) some new communities are constructed. The new communi- { { ∏ βˆπ‘π‘–π‘Ÿ π‘π‘Ÿπ‘— 𝑠(𝑖)(πœβˆ’π‘‘π‘–π‘Ÿ) 𝑠(π‘Ÿ)(πœŽβˆ’πœβˆ’π‘‘π‘Ÿπ‘— ) , π‘Ÿ =ΜΈ 0 ties are constructed and updated by Sections 3.2 and 3.3. {π‘Ÿ=𝑖,𝑗 ΜΈ 𝜏=1 We take an example to illustrate the transformation of 3.5. Content Dissemination Based on Interest Community. a community, as shown in Figure 4. This figure shows that We take a programming interest community as an example time-varying communities change with social activities of to illustrate content dissemination based on interest com- nodes. At 10 a.m., the computer community is constructed at munity. From 9 a.m. to 5 p.m., the programming interest computer school; the comprehensive learning community is community is constructed at computer school and library 8 Wireless Communications and Mobile Computing Community 3 D Destination ng di S en S n2 Moving n1 Ambassador n2 Mo v in g Sending S Community 2 n1 Ambassador Source Community 1 Community Node Historical Moving Trajectory Figure 5: Content dissemination out of an interest community using mobility similarity. buildings. From the sunset to the sunrise, the program- community, the data message is immediately sent out of the ming interest community is reconstructed at dormitory community by an ambassador. Figure 5 shows an example buildings. When the time-varying communities keep active, about the content dissemination out of the interest commu- content dissemination includes two aspects. The first aspect nity by the comparison of mobility similarity. is the content dissemination within an interest community. The source node S is in community C1 , and nodes n1 and Another aspect is the destination node which is not in an n2 are ambassadors. The ambassadors are a kind of special interest community; the data message is sent out of the nodes who frequently switch between different interests interest community. The content dissemination is described communities, e.g., C1 in Figure 5. The ambassador nodes have in the next part. multiple interests and they are active most of the time. As shown in the figure, both source node S and node n2 went (1) Content Dissemination within an Interest Community. to community C3 ever before, which shows both of them When there exist connections among nodes in an interest have similar mobility trajectories. Hence, node n2 has higher community, data messages will be directly exchanged with successful delivery probability than node n1 . Node S chooses each other. Otherwise, the data messages will be delivered ambassador n2 to help forwarding the data message. After by binary spray and wait. The binary spray and wait con- the data message is carried to the community C3 , the content tent dissemination has the advantage of epidemic content dissemination within a community is enabled. Hereafter, the dissemination, such as the high delivery ratio. It is worth data message is successfully delivered to the destination D. noting that the binary spray and wait content dissemination The process for how to choose an ambassador is described as efficiently control the number of data message copies. A below. source node initially generates L copies of a data message. When the source node meets another node, it will hand over Definition 3 (position of a node at time 𝑑). Position of a node half number of data message copies to the node and keep at time t is defined as the vector (π‘₯𝑖 , 𝑦𝑖 , 𝑑𝑖 ). The symbols π‘₯𝑖 and another half for itself. The process of content dissemination 𝑦𝑖 represent the latitude and longitude of node i. The symbol will continue until a node only has one data message copy. In 𝑑𝑖 represents the current time. this way, data messages will be quickly spread to nodes in the interest community. Definition 4 (mobility area of a node during a period). 𝑑𝑠 represents the time of a node who arrives at this area and 𝑑𝑙 (2) Content Dissemination Out of an Interest Community. represents the time of the node who leaves this area. Assume When we cannot find a destination node within an interest that 𝑝(π‘₯𝑖 , 𝑦𝑖 , 𝑑𝑖 ) is the position of a node at time 𝑑𝑠 ≀ 𝑑𝑖 ≀ 𝑑𝑙 , Wireless Communications and Mobile Computing 9 Input: Source node S, GPS traces of nodes, number of nodes in a community n, number of places in a map m Output: The best ambassador (1) Initiation: set variables as zero (2) Begin (3) for (i=0, i