This is the accepted version of the article: Borrego Iglesias, Carlos; Borrell i Viader, Joan; Robles Martínez, Sergi. Hey, Influencer! Message Delivery to Social Central Nodes in Social Opportunistic Networks. 2019. DOI 10.1016/j.comcom.2019.02.003 This version is avaible at https://ddd.uab.cat/record/203043 under the terms of the license Hey, Influencer! Message Delivery to Social Central Nodes in Social Opportunistic Networks Carlos Borregoa,∗, Joan Borrella , Sergi Roblesa a Department of Information and Communications Engineering Universitat Autònoma de Barcelona Barcelona, Spain Abstract This paper presents a new strategy to efficiently deliver messages to influencers in social opportunistic networks. An influencer node is an important node in the network with a high social centrality and, as a consequence, it can have some characteristics such as high reputation, trustfulness and credibility, that makes it an interesting recipient. Social network analysis has already been used to improve routing in opportunistic networking, but there are no mechanisms to efficiently route and deliver messages to these network influencers. The delivery strategy proposed in this article uses optimal stopping statistical techniques to choose among the different delivery candidate nodes in order to maximise the social centrality of the node chosen for delivery. For this decision process, we propose a routing-delivery strategy that takes into account node characteristics such as how central a node is in terms of its physical encounters. We show, by means of simulations based on real traces and message exchange datasets, that our proposal is efficient in terms of influencer selection, overhead, delivery ratio and latency time. With the proposed strategy, a new venue of applications for opportunistic networks can be devised and developed using the leading figure of social influencers. Keywords: OppNet, Opportunistic Social Networks, Optimisation, centrality 1. Introduction privacy. As explained in studies like [44], Internet service providers are using packet inspection techniques to read The global deployment of computer networks has per- and store users’ messages and personal data. Opportunis- mitted the creation of a wide range of different social tic social networks, in contrast with traditional connected network-based applications. These social applications al- ones, can provide their users with a way of socialising with- low collaborative behaviour among users to share their out renouncing to their privacy since OppNet nodes do not personal interests or hobbies, for example [17]. rely on a network infrastructure that identifies their users. As mobile devices get smarter, Opportunistic Network- When OppNet is seen from a social perspective, new net- ing (OppNet) [18] has emerged as a solid network solution work roles come into view. For example, OppNet nodes that allows mobile nodes to communicate with each other can be characterised in terms of how socially connected when no end to end connection is possible. they are. In social networks, an influencer node [31] is an In the context of OppNet, research is directed towards important node in the network with a high social central- a new network paradigm that evolves from the traditional ity and, as a consequence, can have interesting character- node-to-node scheme to a more person-centric one. Under istics such as high reputation, trustfulness, and credibil- different terms, such as Proximity-Based Applications [46], ity. Having the possibility of communicating with influ- Mobile Ad Hoc Social Networks (MASNs) [47], Offline So- encer nodes in an OppNet and make them send a message cial Networks [49], or SmartPhone Adhoc Networks [49], with a given information may improve the social accep- the research community is pointing at the human social tance of this information. For example, in an emergency characteristics such as mobility patterns or personal in- scenario with damaged network infrastructure, a critical terests, to provide new social applications and to improve advise from the emergency coordination to the population networking decisions such as the message routing. will have more chances of being followed when it comes There are many reasons why these opportunistic social (not just forwarded) from a trusted influencer. networks can be a useful alternative to traditional con- nected ones. One example for this is to preserve users’ However, finding strongly connected nodes in OppNet is far from being easy to achieve due to OppNet’s dynamic ∗ Corresponding change of topology and the lack of a global view of the author Email addresses: cborrego@deic.uab.cat (Carlos Borrego), network [30]. In this article, we propose a routing-delivery joan.borrell@uab.cat (Joan Borrell), sergi.robles@uab.cat mechanism that allows to deliver messages to influencers (Sergi Robles) of a network in an optimal way, statistically speaking. 6 Influencer 5 focusing on the two key concepts of SNA: community 7 2 and centrality. Social-based forwarding schemes outper- 1 4 Virtual Layer form traditional schemes based on epidemic approaches 3 or mobility-based predictions. Moreover, other proposals 6 5 [15, 49] consider the existence of two levels of social net- 7 2 1 4 works in opportunistic environments. As depicted in Fig- Hub 3 Electronic Layer ure 1, there is a first level, an electronic (also called off- line) social network, which refers to the physical wireless Social interaction Physical interaction network in which users mobility and proximity are con- sidered. Secondly, a virtual or online social network that Figure 1: Two levels of the relationship of nodes in an OppNet: reflects users friendships and influences [49]. That study electronic and virtual. also encourages the combination of the social awareness in both electronic and virtual social networks, in order to The optimality of this mechanism is achieved by making, improve the efficiency of new data forwarding protocols in on one hand, optimal delivery decisions and, on the other, OppNets. optimal routing decisions. Optimal delivery decisions in- Under different terms such as Proximity-Based Applica- volves deciding whether a node should be considered an in- tions [46], Mobile Ad Hoc Social Networks (MASNs) [47], fluencer or not, whilst optimal routing decisions deals with Offline Social Networks [49], or SmartPhone Adhoc Net- deciding the optimal message path to discover influencers. works [49], the scientific community proposes a natural To obtain this optimality, the routing-delivery strategy evolution of OppNet where users, using mobile devices, proposed in this article uses optimal stopping statistical are connected using opportunistic contacts to form vir- techniques [6] to choose among the different delivery can- tual communities of similar personal interests. We use all didate nodes in order to maximise the social centrality of along this article the term Opportunistic Social Network the delivered node. For the routing decision process, we (OSN) to refer to this type of networks. There are some propose a routing algorithm that takes into account other OppNet studies that propose that social network applica- node’s characteristics such as their physical centrality, that tions can become a driver for the proliferation of OppNet is, how central a node is in terms of its physical encounters. [28]. OSN is not merely for research: some recent propos- The paper starts with all the relevant state of the art in- als have developed solutions to build local mobile ad-hoc formation, in Section 2, paying special attention to Oppor- social networks on top of Android-based mobile terminals tunistic Social Networks, centrality metrics, and optimal [48]. These solutions make opportunistic social networks stopping techniques in OppNet. Next, we provide a full de- a feasible network paradigm with promising social appli- scription of our routing-delivery strategy in Section 3. The cations as pointed out in studies like [21]. paper follows with Section 4, where a simulation-based ex- 2.2. Centrality in Opportunistic Networks perimentation is presented. Finally, Section 5 contains the conclusions we have drawn from this work. When OppNet is seen from a social perspective, as de- scribed in the previous section, nodes can be characterised in terms of how socially connected they are. In order to 2. Related Work measure this sociability, Graph Theory can be very help- ful. In Graph Theory in general, the term centrality iden- In this section, we study the state of the art of Op- tifies the most important vertices within a graph. Users portunistic Social Networks. We make a summary of the in OppNet in particular, are structured in communities, different ways of studying the centrality of a node in clas- and inside these communities, there are some more popu- sical networks and in ego networks. Additionally, a brief lar and influential than others. This influence is commonly survey on articles that use Optimal Stopping statistical measured using centrality indicators. techniques for improving OppNet is presented. Finally, Many research studies [40, 41] have proposed to use the we present how to include complex routing and delivery centrality of OppNet nodes to influence in the routing de- algorithms in OppNet within the messages. cision. The basic idea behind this concept is to choose nodes with high centrality to forward the custodied mes- sages to increase the probability of delivering the message 2.1. Opportunistic Social Networks to its destination: centrality defines a node’s ability to act Opportunistic Networking [18, 51] is a network as a communication hub. paradigm where end-to-end connection is not guaranteed. There a many different centrality metrics proposed in Messages in OppNet use intermediate nodes to be routed the literature to measure the structural importance of a from their source to their destination in an opportunistic node in the network. There are many centrality metrics way. proposed by the scientific community [22]. The three most Social Network Analysis (SNA) has been applied to important are degree centrality, betweenness, and close- OppNet to improve routing algorithms [35, 16, 29, 37, 26], ness centrality. Degree centrality [39] measures the num- 2 ber of direct edges that reach a given node. Betweenness apply optimal stopping theories to make network decisions centrality [2], instead, calculates the number of shortest such as routing or node searching. However, these optimal paths connecting other nodes that use the node being mea- stopping theories are difficult to be directly implemented sured as a hop. Finally, closeness centrality [38] studies in OppNet using traditional protocols because these pro- the length of the shortest path connecting the rest of the tocols are not able to implement optimal strategies. The nodes. reason for this limitation is that optimal strategies need Additionally, there has been a large effort in proposing special delivery conditions that require keeping an inter- social metrics to define network centrality from an egocen- nal state of the message with the purpose of remembering tric point of view [23]. Ego networking is a network metric preceding events. In [6], the authors present Software- where that consists of defining a node together with the cast, a general delivery scheme for group communications nodes to which this node is connected to and the links based on mobile code that helps to solve this limitation. among those nodes. Some studies [36] show that ego net- In Softwarecast, messages carry a software code and a de- work centrality is highly correlated to traditional central- livery state that permit them to perform refined delivery- ity. This paradigm is very useful in Ad Hoc networks be- decision-making methods based on optimal stopping the- cause of the lack of a central entity capable of calculating ories to implement complex delivery decisions. Software- nodes’ centrality. cast uses Active-DTN [8], an OppNet solution that con- sists in extending the messages being communicated by 2.3. Optimal stopping in OppNet incorporating software code for forwarding, delivery, life- In this article, we propose a routing-delivery mechanism time control and prioritisation purposes. Active-DTN has that allows, in an optimal way, to deliver messages to in- been applied in different DTN scenarios such as oppor- fluencers, that is, to highly social-connected nodes in the tunistic computing infrastructures [7], multi-application network. This problem can be seen as the optimisation mobile node sensor networks [5] and disconnected emer- problem of deciding when to make a delivery decision. gency scenarios [8]. Probabilistically speaking, early delivery decisions will not We base our proposal on the study OppNet Profile-cast guarantee optimal results, that is, messages will be de- scheme [27]. In OppNet Profile-cast, message destinations livered to poor socially connected nodes. Late decisions, are users defined by certain profiles. These profiles pro- moreover, will also fail since it is probable that good can- vide very effective ways of characterizing nodes in terms didates will be discarded. Optimal Stopping Theory [43] of nodes’ attributes. More concretely, we use a Profile-cast deals exactly with this type of problems. It is a statistical model [9] that allows messages to be sent to profiles defined solution for the problem of choosing the best moment to in terms of relative delivery functions such as best, maxi- make a particular decision to maximise a certain reward. mum or over-the-average. Additionally, in [9], the authors One of the most popular problems in Optimal Stopping present Explore and Wait, a composite routing-delivery Theory is the secretary problem [20]. In this problem, a scheme that uses Optimal Stopping Theory-based deliv- person must interview a group of n candidates, that can ery strategies to route messages to these special profiles. be ranked from best to worse, with the aim of selecting Even though there has been a substantial number of pro- the best one. The difficulty of this problem lies in the fact posals to solve routing and delivery problems in OppNet, that once a candidate is not selected he/she can not be re- there is not yet any proposal that gives a solution to the called again. The solution to this problem, as presented in complex problem of sending messages to highly connected [20], is a selection strategy that discards the first n/e can- nodes in OppNet. In this article, we open a new avenue for didates interviewed (being e the mathematical constant) creating new applications in OppNet by proposing a novel and selects the first one, if found, that is better than all of routing-delivery strategy that allows messages to be deliv- the previous ones. ered to influencers. This strategy uses optimal stopping There are different extensions of the secretary problem. delivery techniques strategies on the basis of the studies A complete survey can be found in [24]. In this article, we presented in this section. will use a concrete variation of the secretary problem called the rank-based selection and cardinal payoffs variation of the secretary problem [3, 4]. This variation is more flexible 3. Influencer message delivery than the traditional problem because it allows the selection In this section, we define the influencer message deliv- of a candidate that is not necessarily the best, while trying ery problem and we describe an optimal routing-delivery to maximise the quality of the candidate. The solution to strategy based on optimal stopping theory to solve this this problem is a similar strategy √ to the classical secretary problem. problem: it discards the first n nodes instead of the first n/e, and then, as in the traditional problem, selects the next one, if found, that is better than all of the previous 3.1. Influencer Nodes in OppNet ones. In network theory, nodes (vertex) are connected to one There are some proposals in literature that are using op- another in a symmetric or asymmetric way forming con- timal stopping in OppNet. In [30], the authors propose to nections (edges). In OppNet, as introduced in Section 2, 3 Variable Description is increased whenever two nodes A and B meet, in the vc Virtual centrality. following way: ec Electronic centrality. ecnewA = ecoldA + 1 (1) ms Message scope. tlimit Time limit for message delivery. iet Inter-Explore Time. ecnewB = ecoldB + 1 (2) xp Number of nodes a message has explored. This action allows frequently-contacted nodes to have a siet EWMA of iet. high electronic centrality. α siet EWMA weight factor. On the other hand, in order to make this centrality met- lastxp List of nodes recently explored. ric more adaptive to dynamical networks such as OppNet, lastxpvc List of nodes considered for the trend nodes automatically age their values of their electronic cen- evaluation. trality in order to decrease the impact of old physical con- mvc Median of the values in lastxpvc. tacts. A node A will update its electronic centrality using svc EWMA of the explored vc. an exponentially decaying function in the following way: β svc EWMA weight factor. vctrend The trend of the virtual centrality. ecnewA = ecoldA × γ k (3) Table 1: Description of the acronyms used in Section 3. where γ[0, 1] is an ageing constant and k is the number of time units that have passed since the last ageing update. this relationship among nodes can be seen from two dif- ferent perspectives: virtual and electronic, following the 3.2.2. Virtual Centrality Metric terminology presented in [15]. For the virtual centrality, we have chosen to maintain on A first perspective is a virtual one. Two nodes in an every node its ego network. An ego network, as introduced OppNet are virtually connected if they virtually interact in Section 2, is a network that consists of the single studied with each other by, for example, exchanging messages or by node together with the nodes this node is connected to and explicitly being defined as friends in a given social network. the links among those nodes. We have chosen to use ego A second perspective is an electronic one. In OppNet, two networks to study social node’s virtual centrality because nodes are electronically connected if they physically come it can be performed locally by individual nodes without in contact with one another. complete knowledge of the entire network. As explained in There are many proposals in literature for metrics that [19], this betweenness calculation is very efficient in terms quantify how strongly connected two nodes are in a net- of CPU utilization. Additionally, as introduced in Section work. These metrics can be applied to both virtual and 2, some studies show that ego network centrality is highly electronic planes [17]. Examples of these metrics in- correlated to traditional centrality [36]. The calculation of clude frequency of the virtual/electronic contacts, their all the ego betweenness values for a given network would longevity, their duration, reciprocity, etc. be one order of magnitude lighter rather than calculating An influencer node in OppNet is a node that has a high the real betweenness scores. virtual centrality in comparison to the rest of the nodes In an ego network, nodes’ virtual contacts are repre- from the network. As introduced in Section 1, an influ- sented by an adjacency symmetric matrix where its rank, encer node is a special role in the network that has inter- n, is the number of messages a given node has sent and re- esting characteristics such as high reputation, trustfulness ceived. Note that this virtual metric considers both send- and credibility. Following, we define the centrality metrics ing and receiving messages. For these purposes, every node we will use for the virtual and electronic social network. keeps a contact matrix (CM ) that represents the node’s virtual ego perspective of the network. In this contact ma- trix, the first row and the first column (CM0,j and CMi,0 ) 3.2. Centrality Metrics defines virtual contacts from the local node. Any other We need to define two different centralities metrics, the generic value CMi,j , instead, defines virtual contacts be- electronic centrality —how physically connected a node is tween two nodes i and j. To obtain this, for every message —and the virtual centrality —how socially connected a m(f rom: A, to: B) sent, received or forwarded, the matrix node is. CM is updated in the following way: CMa,b = 1 (4) 3.2.1. Electronic Centrality Metric For the electronic centrality, we have chosen to use a where a and b are the row position in matrix CM for nodes degree centrality metric. The degree centrality of a node A and B. [39] represents the number of physical encounters a node We propose to use the betweenness egocentric central- has made. We define two functions to update the electronic ity as virtual centrality. This metric is calculated by com- centrality metric. On one hand, the electronic centrality puting the number of nodes that are indirectly connected 4 through the ego node. This calculation is done by obtain- rank-based selection and cardinal payoffs variation of the ing a new adjacency matrix, (CM 0 ), where every value secretary problem [4]. This variation of the secretary prob- 0 CMi,j is set to CMi,j if both CMi,j and CMj,i are set to lem fits better to the influencer message delivery problem 0 1, otherwise CMi,j is set to 0. Then, the betweenness ego- than the traditional one because, as explained in Section centric centrality is obtained by summing the reciprocals 2, it includes the flexibility of allowing the selection of a of the following matrix, as introduced in [19]: candidate that is not necessarily the best, while trying to maximise the quality of the candidate in terms of its vir- CM 02 [1 − CM 0 ] (5) tual centrality. In the influencer message delivery problem, we do not aim to send the message to the most influential 3.3. Influencer Message Delivery Problem node, but to a node which has a high virtual centrality The influencer message delivery problem can be formu- (not necessarily the highest). lated as a set of the following constraints: The influencer message delivery problem is extremely challenging. A straightforward solution would be to broad- • The goal of this problem is to deliver a message to a cast an influencer discovery message to the network and node with a high virtual centrality. The higher this afterwards send the influencer message to the most social virtual centrality is, the better. node found. However, this solution could fail because once the potential influencer is discovered, it could not receive • There is a limited and known time to deliver the mes- the influencer message due to the low delivery ratios ob- sage. tained in OppNet. Besides, this solution would have a high network overhead. • There is an unknown number of nodes in the network. Instead, if we allow just one message to perform both • At a given time, at the hypothetical situation of hav- the exploration and the delivery action some other prob- ing all the nodes in the network together, they can be lems may be found. First of all, the number of candidate ordered from best to worst according to their virtual nodes a message can explore in a period of time is difficult centrality. to estimate. Additionally, nodes have a dynamic value for their virtual centrality since it changes overtime. Also, in- • When a node has accepted the custody of a message, it fluencer messages can be forwarded to one node more than allows the message to explore its virtual centrality and once. Finally, the exploration action implies the necessity the one from every neighbor not selected for routing. of storing information within the message that should be light in terms of storage and accurate in terms of the ex- • As a message is being routed from one node to an- ploration. other, it can be determined the relative ranks of the In the following two sections, we explain our strategy to explored candidate nodes but it cannot be observed solve the influencer message delivery problem that covers the absolute ranks of all of the nodes in the network. all of these issues. We give a network oriented explana- • Once a candidate is rejected, it can be found again in tion for this strategy. First, in Section 3.4, we explain the future. the message delivery decision process, that is, the decision on which node should be the destination of the influencer While in connected networks this delivery action can be message. Secondly, in Section 3.5, we explain the message very easy to perform since network searches are easily con- routing decision process, that is, the decision on whether ducted, in OppNet, this is not an easy task to accomplish or not to forward an influencer message to a certain con- because of the idiosyncrasy of the network. The search tacted node. In Algorithm 1, the complete strategy is problem in OppNet is quite difficult to conduct, as de- presented. scribed in proposals like [30]. This relative decision of delivering or not a message to 3.4. Delivery Protocol a contacted node is a similar problem to optimal stopping In this section, we propose a delivery strategy for the problems [43]. As introduced in Section 2, optimal stop- influencer message delivery problem, as defined in the pre- ping theories deal with problems that aim to choose the vious section. optimal moment to take a particular action. The solu- The influencer message delivery problem delivery strat- tion to these problems are complex strategies that, from a egy consists of creating a single message that operates in statistical point of view, offer an optimal result. two different phases: the Explore Phase and the Wait The influencer message delivery problem is very similar Phase, following the delivery scheme terminology pre- to the standard secretary problem. The main difference is sented in [9]. During the Explore phase, the influencer that in the influencer message delivery problem, the payoff message is routed from a node to another. Messages dur- obtained when making a decision is equal to the selected ing this phase are not delivered. Instead, the maximum node virtual centrality value, whereas in the classical sec- value retrieved for the virtual centrality is kept within the retary problem it is just 1 if the best overall candidate is message. This phase ends when the message has explored selected or 0 otherwise. This problem can be seen as the more than a certain number of nodes. During the Wait 5 Phase, the message will still be routed from one node to Input Variable Description another, and it will be delivered to the first node found msg Message to be delivered. that has a greater virtual centrality than all of the previ- tlimit Time limit for message delivery. ous ones. swapmetric() A function that changes a metric The key issue in this delivery problem, as in all optimal from electronic to virtual and vice stopping problems, is to decide when to stop exploring the versa. network and switch to the Wait phase. As introduced in getvc() A function returning the virtual Section 2, we follow the variation of the secretary problem centrality. called the rank-based selection and cardinal payoffs varia- getec() A function that returns the tion electronic centrality. √ [4]. This variation of the secretary problem considers n as the optimal value for the phase transition, being n neighbours The list of current neighbour nodes. the number of candidates. However, in OppNet, the num- lastxpT A message state variable with the ber of nodes a message can explore in a given time can not time of the last explored node. be known in advance. lastxp A fixed-size unique-value LIFO Accordingly, our optimal delivery strategy for the influ- array with the last explored nodes. encer message delivery problem is the following: lastxpvc A fixed-size LIFO array with the last vc values of explored nodes. • Within the message, keep: xp The number of explored nodes. CurrentM etric The routing metric to use. – xp, the number of already explored nodes (up- maxvc The maximum vc explored. dated in line 14 of Algorithm 1). α,β siet and svc EWMA weights. – ms, an estimation of the total number of nodes this message could explore in the remaining time Table 2: Description of the input variables from Algorithm 1. to be delivered (updated in line 7 of Algorithm 1). – maxvc, the maximum virtual centrality (vc) ex- plored so far (updated in lines 8 and 9 of Algo- Algorithm 1 Routing-Delivery strategy. rithm 1). 1: procedure sendToInfluencer 2: for all remote in neighbours do • Allow the influencer message to be routed from node 3: svc = svc + β × (svc - getvc(remote)) to node following the routing protocol that will be 4: mvc = median(lastxpvc) presented in Section 3.5 and reject for delivery the 5: iet = getTime - lastexploretime √ 6: siet = siet + α × (iet − siet) , α ∈ [0, 1] first xp + ms nodes a message has explored (line 19 of Algorithm 1). 7: ms = (tlimit − getT ime )/siet . nodes to explore 8: if getvc(remote) > maxvc then • Select the first node (if found) that is better than all 9: maxvc=getvc(remote) . Update maxvc of the previous explored nodes in terms of its virtual 10: end if centrality (line 20 of Algorithm 1). 11: if mvc < svc then . negative trend, swap metric 12: swapMetric(CurrentM etric) In order to calculate the estimation of the number of 13: end if nodes an influencer message can explore at a give time, 14: xp = xp + 1 15: lastxpT = getTime() a statistic of the time between explored nodes is kept 16: lastxp.add(local) within the message. We call this statistic the Smooth 17: lastxpvc.add(getvc(local)) Inter-Explore Time (siet). To prevent recently forwarded 18: end for nodes to distort this estimation, messages keep a list of the √ 19: if xp > xp + ms and getvc(local) > maxvc then last nodes the message has explored. We call this list last 20: deliver(msg); exit . End of Wait phase explored node list (lastxp). In Section 4, the size of this 21: else list is studied to understand its impact on the influencer 22: for all remote in neighbours do delivery performance. 23: if CurrentMetric == electronic then Every time a node containing an influencer message con- 24: if getec(remote) > getec(local) then tacts another node not included in the lastxp list, the ob- 25: forward(msg,remote); break served Inter-Explore Time (iet) is calculated (line 5 of Al- 26: end if 27: else if getvc(remote) > getvc(local) then gorithm 1): 28: forward(msg,remote); break 29: end if iet = time.now() − lastexploretime, (6) 30: end for 31: end if where time.now is the current time and lastexploretime is 32: end procedure the last time the influencer message explored a node. 6 The siet statistic is updated using an EWMA (Exponen- a message is upward (in this case the trend value is 1), tial Weighted Mobile Average) in the following way (line or downward (trend value of -1). To calculate this trend, 6 of Algorithm 1): the algorithm uses two variables: another EWMA of the virtual centralities of the explored nodes that we call the sietnew = sietold + α × (iet − sietold ), α ∈ [0, 1], (7) smooth virtual centrality (svc) and the median of the met- where sietold is the historical iet, α is a weight factor and ric considering the last n updates (mvc). These two values iet the last iet time measured. are stored in the message, and are updated every time step Finally, the estimation of the number of nodes an influ- by the node, as seen in lines 3-4 and 12 of Algorithm 1: encer message could explore in a given time t is calculated using the following expression (line 7 of Algorithm 1): svcnew = svcold + β × (vc − svcold ), β ∈ [0, 1] (9) ms = t/siet. (8) 3.5. Routing Protocol In this section, we introduce a routing algorithm that mvc = median(vct , vct−1 , vct−2 , . . . , vct−n ) (10) makes use of both electronic and virtual centrality metrics to drive information in social OppNets toward nodes with ( a high virtual connectivity (influencers). 1 svc 6 mvc vctrend = (11) This algorithm uses the electronic centrality (in what −1 svc > mvc extent a node is physically connected to others) and the virtual centrality (in what extent a node is socially con- We define currentmetric as an element in the set nected to others). One may think that because the sought electronic, virtual. It is first intitialised to virtual and destination (the influencer) is the best social connected will be changed when vctrend is negative. node in the network, exclusively taking into consideration In the routing process, a neighbour is selected for for- the virtual centrality would suffice for the sake of the rout- warding if its ec or vc, depending on the currentmetric, ing. Unfortunately, virtual and electronic centrality are is higher than the local one. This routing decision can be not necessarily correlated. A physically highly-connected seen in lines 23-28 of Algorithm 1. node is a good candidate to forward messages to other nodes (whatever their virtual connectivity, which might 4. Evaluation be null). On the other hand, a socially highly-connected node looks like a good candidate to forward messages to- The routing-delivery strategy presented in Section 3 is wards influencers, although this last forwarding might not our approach for delivering messages to socially influencers take place due to a lack of physical connectivity. There- in an OppNet. We have conducted several experiments us- fore, an on-the-fly detection of the current trend towards ing simulations based on real mobility traces and real so- nodes with high virtual centrality is going to be considered. cial interaction behaviour in three different scenarios. In If there is an upward trend of the virtual centrality (the these scenarios, we prove that our approach, in comparison message is progressing towards an influencer), the routing to state of the art proposals, improves the influencer grade algorithm will keep using the same centrality (virtual or of the selected node for delivery, the network latency, and electronic) as a selection criterion for choosing the next for- the delivery ratio. We claim that our approach is highly warding node. Otherwise, it will use the other centrality performant to solve the influencer message delivery prob- (the trend has to be reverted to get closer to influencers). lem in OppNet as presented in Section 3.3. In this section, To make this routing possible, there are three required we describe the evaluation experimentation in detail. elements: the current virtual centrality in a node, its elec- tronic centrality, and the general trend of virtual centrality considering all nodes, updated periodically and stored in the message. The algorithm will use these three values to make the routing decision for a particular message. The electronic centrality of a node in a given time can be easily calculated, for example, by counting how many neighbour nodes are at physical reach during a window of time. Every node keeps this metric, and can be accessed from the routing algorithm. The virtual centrality of a node at a given time can be worked out by ascertaining (a) Info5. (b) Cambridge. (c) Taxis. the number of social contacts during the same window of time. Figure 2: Electronic social network for Info5, Cambridge and Taxis The trend of the virtual centrality, vctrend , indicates scenarios. whether the tendency of this metric along the journey of 7 General Value Transmission Speed 250Kb/s Transmit Range 10-50m # Nodes (Info5) 41 # Nodes (Cambridge) 51 # Nodes (Taxis) 370 # Messages 1000 # random seeds 50 Buffer Size 1GB (a) Info5. (b) Cambridge. (c) Taxis. Electronic layer Trace duration (Info5) 2.97 days Figure 3: Virtual social network for Info5, Cambridge and Taxis Trace duration (Cambridge) 6 days scenarios. Trace duration (Taxis) 30 days # Contacts (Info5) 22459 # Contacts (Cambridge) 10641 4.1. Simulation Environment # Contacts (Taxis) 449226 The experiment has been conducted over the Oppor- Virtual layer tunistic Network Environment (TheONE) simulator [32]. Message Payload 100 KB For the sake of simulation accuracy, we have performed # Message Events 18600 the simulations presented in this sections following the be- tlimit 20’-180’ haviour and performance of a real Bundle Protocol im- Active-DTN Settings plementation capable of reproducing the influencer deliv- Mobile Code Extension Size 300 bytes ery strategy. We base our simulations on Active-DTN [8], Compilation Time 54884 ns an OppNet solution1 that consists in an extension of the Delivery Execution Time 360 ns Bundle Protocol where the messages being communicated Routing/Delivery Settings incorporate software and message state for forwarding, de- livery, lifetime control and prioritisation purposes. γ (electronic ageing constant) 0.98 Time unit size 30 s In the following simulations, the routing-delivery strate- α (siet EWMA weight factor) 0.75 gies presented in Section 3 are included in messages as β (svc EWMA weight factor) 0.75 bundle forwarding and/or delivery extensions following the bundle extension introduced in [8]. We simulate messages Table 3: Simulation settings default values for all scenarios. sent to influencers as messages that carry a delivery ex- tension with a software mobile code. The simulator is programmed to allow messages, when carrying the deliv- work, as defined in Section 3, of all proposals are defined by ery extensions, to be delivered in terms of mobile software physical contacts obtained from real mobility traces from codes that are included in these delivery extensions. the Crawdad database2 , a community resource for collect- As introduced in Section 3, there are several variables ing wireless data at Dartmouth College, United States. that the message must keep to implement the Influencer The first scenario, the Info5 scenario, is based on real delivery strategy: the Smooth Inter-Explore Time (siet), mobility traces, as published in [42]. These traces were the last explored node list (lastxp), the number of ex- retrieved during the 2005 edition of the Infocom conference plored nodes (xp) and the last vc values explored values in the course of 2.97 days. Contacts from this mobility list (lastxpvc). These variables must be kept when being traces represent 41 students carrying iMote platforms . forwarded from one node to another and represent histor- The total of physical encounters provided in these traces ical information that allows our delivery strategy to be is 22459. capable of performing appropriately upon arriving at new The second scenario, the Cambridge scenario, is based nodes. For these purposes, we have adapted the simulator on real Bluetooth traces from students from the System to extend its messages to include these variables. Research Group of the University of Cambridge carrying In Table 3, details related to Active-DTN considered small devices for six days [33]. Additionally, some station- for the simulations such as the mobile code extension size, ary nodes were placed in various points of interest such as delivery mobile code compilation and execution time are grocery stores, pubs, market places, and shopping centers listed. all around the city of Cambridge, UK. A stationary device was also placed at the reception of the Computer Lab, in 4.2. Simulation Model and scenarios which most of the experiment participants were students. We have chosen three different scenarios to analyse the The number of contacts provided in these traces is 10641. performance of our proposal. The electronic social net- Info5 and Cambridge are long-established scenarios which have been used in many papers in the area of Op- 1 Active-DTN source code can be found at https://github.com/SeNDA-UAB/aDTNPlus. 2 http://crawdad.org/keyword-DTN.html. 8 Maximum value (node=3, time=1101, ec=15.9) Maximum value (node=23, time=4412, ec=5.1) Maximum value (node=214, time=1126, ec=10.9) 5 15 10 4 8 Cen Cen Cen 10 3 6 trali trali trali ty v ty v ty v 2 4 alue alue alue 5 No 2 e No e 1 No e m m m de de Ti de Ti Ti 0 0 0 (a) Info5: electronic centrality. (b) Cambridge: electronic centrality. (c) Taxis: electronic centrality. Maximum value (node=6, time=1288, vc=321) Maximum value (node=34, time=135143, vc=190) Maximum value (node=10, time=500, vc=276) 200 250 150 200 Cen 150 Cen Cen trali trali trali 100 150 ty v ty v ty v 100 100 alue alue alue 50 No 50 50 e No e No e m m m de de de Ti Ti Ti 0 0 0 (d) Info5: virtual centrality. (e) Cambridge: virtual centrality. (f) Taxis: virtual centrality. Figure 4: Evolution of the electronic centrality (contact degree centrality) and virtual centrality (betweenness ego centrality) of the different nodes in the network every time two nodes connect as a function of the simulation time for the scenarios Info5, Cambridge and Taxis, respectively. portunistic Networking to compare the performance of dif- All three scenarios run applications with the same ap- ferent algorithms. Nevertheless, there are other more re- plication traffic based on real message exchange from real cent and realistic scenarios which consider larger tempo- communication datasets taken from the Stanford Large ral and spatial scales, and with a larger number of par- Network Dataset Collection3 . We have simulated appli- ticipants, which are ordinary people instead of volunteer cation messages that define the virtual social network, as students. An interesting example is the mobile phone lo- explained in Section 3, with real dataset collections. The cation dataset provided by the company Airsage to the virtual social network was generated based on anonymised MIT’s SENSEable City lab [13], which contains 200 mil- real message exchange from different users belonging to a lion anonymous location measurements of one million mo- large European research institution as presented in [34]. bile phones, collected in 2009 in East Massachusetts. From These real message exchange social network has been this dataset, [11] constructs a scenario of 1900 users in a adapted to be integrated into the three above-mentioned Boston area of 150 km2 during 29 days of October 2009, scenarios4 . very interesting to explore the human mobility properties In Figure 2(a), Figure 2(b), Figure 2(c), Figure 3(a), from a networking point of view. Also from this dataset, Figure 3(b), and Figure 3(c) the electronic and virtual [12] focuses on the Boston Independence Day Celebration social network for all scenarios are represented using the on the evening of July 4th 2009, in the Boston city area Fruchterman-Reingold [25] algorithm to improve the place- (15 km2 , 700 users), as a crowded event where to anal- ment of neighbouring nodes. yse the feasibility of disseminating emergency information In Figure 4(a), Figure 4(b) and Figure 4(c) we show the among the mobile phones in absence of network infrastruc- evolution of the electronic centrality (contact degree cen- tures. trality) of the different nodes in the network as a function Therefore, in addition to Info5 and Cambridge, we anal- of the simulation time for the scenarios Info5, Cambridge yse the performance of our proposal on a third scenario, and Taxis, respectively. As it can be seen, the overall elec- which is larger in time, space and number of participants, tronic social network, from the point of view of the nodes, and which is also publicly available from the Crawdad is different from a scenario to another. In the Info5 sce- database. The Taxis scenario, as published in [10], con- nario the contacts are more frequent, and the electronic tains mobility traces from the ordinary activity of 370 taxi cabs in the city centre of Rome over 30 days (February- 3 Datasets https://snap.stanford.edu/data/ March 2014), covering an area of 64 km2 . The number of 4 TheOneEvents for this Datasets can be found at contacts provided in these traces is 449226. https://senda.uab.cat/wiki/aDTN in Section “TheOne resources”. 9 Info5 Scenario Cambridge Scenario Taxis Scenario Delivery Ratio 1.000 0.99 0.99 0.975 0.96 0.96 0.950 0.93 0.93 0.925 0.90 0.90 0.900 4000 8000 12000 4000 8000 12000 4000 8000 12000 9000 10000 Latency(s) 3000 7000 8000 2500 Routing 5000 6000 2000 Adaptive 3000 4000 1500 Electronic 4000 8000 12000 2000 4000 8000 12000 4000 8000 12000 FirstContact 500 300 Random Virtual Overhead 400 7500 300 200 5000 200 100 2500 100 0 0 0 4000 8000 12000 4000 8000 12000 4000 8000 12000 Centrality Value 90 80 80 150 70 60 60 100 40 50 40 20 50 30 4000 8000 12000 4000 8000 12000 4000 8000 12000 Maximum Delivery Time (s) Figure 5: Routing performance for the metrics delivery ratio, latency time, overhead and centrality value for the scenarios Info5, Cambridge and Taxis using different routing algorithms: random routing, first contact routing, electronic routing, virtual routing and adaptive routing. centrality values are very dynamical. In the Cambridge routing proposal, three well-known ones and a random pro- scenario the contacts are less frequent, and the electronic tocol. These routing protocols are: centrality values do not vary so much. Finally, in Taxis we can see the diversity that comes from such a complex • Our routing protocol presented in Section 3.5 (Adap- scenario. tive Routing in the figures). If there is an upward Additionally, in Figure 4(d), Figure 4(e) and Figure 4(f) trend of the virtual centrality, the routing algorithm we show the evolution of the betweenness social ego cen- will keep using the same centrality as a selection cri- tric centrality of the different nodes in the network as a terion for choosing the next forwarding node and it function of the simulation time for the scenarios Info5, will user the other centrality, otherwise. Cambridge and Taxis, respectively. In this case, even if • Virtual Routing. Messages are forwarded to a con- the social interaction defined for the three scenarios fol- tacted node if its virtual centrality is bigger than the lows the same social trace, it can be seen that the social custodian of the message. This routing behaviour has centrality perception is different for the three scenarios. been used in recent proposals like [6]. 4.3. Experimentation Results • Electronic Routing. Messages are forwarded to a con- tacted node if its electronic centrality is bigger than In this section, we describe the results of the different the custodian of the message. This routing behaviour simulations performed. We have included two types of has been applied in many proposals such as [1] fol- experimentations: routing experimentation and delivery lowing the principle that hubs are good candidates experimentation. for message relays. • First Contact Routing. A very popular routing pro- 4.3.1. Routing Experimentation Results tocol used in studies like [50] where messages are for- We have performed a series of simulations where we have warded to the first available contact for routing. studied the performance of our routing protocol. As pre- sented in Section 3.5, our routing protocol aims to forward • Random Routing. Messages are forwarded to a con- messages delivered to influencers. The following exper- tacted node following a random criterion as used in imentations compare five different routing protocols: our [45]. 10 175 Virtual Centrality Value Virtual Centrality Value Virtual Centrality Value 80 150 140 70 125 Scenario Scenario Scenario 120 Cambridge Cambridge Cambridge 60 Info5 Info5 Info5 100 Taxis 100 Taxis Taxis 50 75 80 40 50 0 10 20 30 40 5 10 15 20 0.00 0.25 0.50 0.75 1.00 lastexplored value lastexplored value γ (a) Impact of the size of the last (b) Impact of the size of the last (c) Impact of γ ec ageing constant. explored node list (lastxp). virtual centrality updates (lastxpvc). Figure 6: lastxp, lastxpvc and γ impact on the virtual centrality performance. 80 70 Virtual Centrality Value Virtual Centrality Value Virtual Centrality Value 70 60 60 Scenario Scenario 60 Scenario Cambridge Cambridge Cambridge Info5 Info5 Info5 50 Taxis Taxis 50 Taxis 40 40 40 20 0.00 0.25 0.50 0.75 1.00 0 100 200 300 0.00 0.25 0.50 0.75 1.00 Time unit α β (a) Impact of the time unit size for ec (b) Impact of α (siet EWMA (c) Impact of β (svc EWMAweight factor). ageing. weight factor). Figure 7: Time unit size, α and β impact on the virtual centrality performance. We have simulated the behaviour of 1000 messages sent for the Info5 scenario this impact is much more clear than to influencers in the Info5, Cambridge and Taxis scenar- for the other two scenarios. ios. We study in this experimentation the virtual cen- Additionally, in Figure 6(b), we show the impact of the trality value obtained, the delivery ratio, the latency time size of the list of the nodes considered for trend evaluation and its overhead. In Figure 5, the results for these experi- (lastxpvc) on the virtual centrality value obtained on av- mentations are depicted. As it can be seen, our proposal, erage. We see that, for the three scenarios, the maximum for all scenarios, improves the virtual centrality value ob- value on average for the virtual centrality is obtained when tained and the latency time. Messages for the four routing this list has a small size. However, for the Cambridge and algorithms have very similar and very high delivery ratio the Taxis scenarios, this variable has a smaller effect on performance. The reason for this high delivery ratio not the performance. related to any routing scheme lies in the fact that Active- DTN, the OppNet solution in which the simulations are Moreover, in Figure 6(c) and Figure 7(a), we study the based on, is capable of evaluating the delivery conditions performance impact of γ, the electronic centrality ageing of the custodied messages even if the OppNet node has not constant and the size of its time unit, as presented in Equa- contacted any new node. As a consequence of this, the de- tion 3 from Section 3.2.1. As it can be seen in Figure 6(c), livery strategy, independently from the routing protocol, the best performances for the three scenarios are obtained will eventually decide to locally deliver the message, even when γ values are greater than 0.9. Concerning the size if there are no new contacts. As it can be seen in Figure of the time unit, there is no general value that fits well for 5, messages are almost always delivered. The ones that the three scenarios. However, only in the Taxis scenarios, they are not delivered, then, are the ones being dropped. this parameter seems to have a high impact on the virtual Finally, concerning the overhead, the best results are ob- centrality value obtained, on average. tained by the First Contact routing protocol. Our routing Finally, we study in Figure 7(b) and 7(c), the impact protocol instead has a very similar overhead performance of the two EWMA weight factors for siet and svc (α and to the Virtual Router and Electronic Router. β). As it can be seen in these figures, giving a weight of In Figure 6(a), we show the impact of the last explored 70% to new measured information and the remaining 30% node list (lastxp) size on the virtual centrality value ob- to the old measured one seems to be a good compromise tained on average. As it can be seen, for the three scenar- value that performs well for the three scenarios and both ios, the evolution of this performance is similar. However, exponential moving averages. 11 150 2000 Node Virtual Centrality Value Latency Time (s) 1500 100 Scenario Scenario Cambridge Cambridge 1000 Info5 Info5 Taxis Taxis 50 500 0 0 OptStop Pub/Subs OptStop Pub/Subs Scheme Scheme (a) Latency average. (b) Virtual centrality value average. 1.00 20 Delivery Ratio Performance Overhead Performance 0.75 15 Scenario Scenario Cambridge Cambridge 0.50 10 Info5 Info5 Taxis Taxis 0.25 5 0.00 0 OptStop Pub/Subs OptStop Pub/Subs Scheme Scheme (c) Delivery ratio average. (d) Network overhead average. Figure 8: Delivery Performance of 1000 influencer messages in 4 hours of time for two different strategies: Influencercast and Publish/Subscribe strategies. 4.3.2. Delivery Experimentation Results and network overhead. As far as we know, this paper is the only publication that studies the problem of sending messages to influencers in 5. Conclusions OppNet. However, we still wanted to compare our pro- posal with another scheme that could also implement this To pave the way for new social applications in OppNet, delivery problem. We compare our proposal (OptStop in in this paper, we analysed the possibility of contacting the figures) with a publish/subscribe paradigm called the influencer nodes in such networks. Finding strongly con- Onside algorithm [14]. This proposal is a message dis- nected nodes in OppNet is far from being easy to achieve semination algorithm that takes advantage of node’s so- due to OppNet’s dynamic change of topology and the lack cial connections, its interests and the history of contacts, of a global view of the network. Therefore, we had to use in order to decrease congestion and required bandwidth. optimal stopping statistical techniques to devise a novel In this publish/subscribe paradigm, nodes willing to send routing-delivery strategy to allow messages to be delivered messages to influencers are subscribed to virtual centrality to influencers in OppNet. values from other nodes that have already published their We firstly formulated the influencer message delivery virtual centrality values. Messages sent to influencers are problem, whose goal is to deliver a message to a node sent to nodes whose centrality is the highest received. with a high virtual centrality, along with all its restric- We analyse the latency time, delivery ratio and virtual tions. In particular, the fact that there is an unknown centrality value obtained as a function of the maximum number of nodes in an OppNet. Our strategy to solve the time for delivery (tlimit) when 1000 messages to influ- influencer message delivery problem follows an adaptation encers are sent to the two different scenarios using the two of the variation of the well-established secretary problem different ways of solving the influencer message delivery known as the rank-based selection and cardinal payoffs. problem. As it can be seen in Figure 8(a), Figure 8(b), Our solution to this problem operates in in two differ- Figure 8(c) and Figure 8(d), our strategy performs better ent phases: the Explore Phase and the Wait Phase. In than the publish/subscribe one in terms of latency time, the Explore Phase, the influencer message is routed from delivery ratio, virtual centrality value obtained on average node to node while estimating the number of nodes this 12 message could explore. Our routing is adaptive as it takes [10] Lorenzo Bracciale, Marco Bonola, Pierpaolo Loreti, Giuseppe into account three different elements: both the virtual and Bianchi, Raul Amici, and Antonello Rabuffi. CRAW- DAD dataset roma/taxi (v. 2014-07-17). Downloaded from electronic centralities in each explored node, and the gen- https://crawdad.org/roma/taxi/20140717, July 2014. eral trend of the virtual centrality considering the last ex- [11] Angela Sara Cacciapuoti, Francesco Calabrese, Marcello Caleffi, plored nodes. After exploring the first square root of the Giusy Di Lorenzo, and Luigi Paura. Human-mobility enabled estimated number of nodes for exploration, our strategy networks in urban environments: Is there any (mobile wire- less) small world out there? Ad Hoc Networks, 10(8):1520 – enters the Wait Phase, where the message is delivered to 1531, 2012. Special Issue on Social-Based Routing in Mobile the first node that is better than all the previous explored and Delay-Tolerant Networks. nodes in terms of its virtual centrality. [12] Angela Sara Cacciapuoti, Francesco Calabrese, Marcello Caleffi, Giusy Di Lorenzo, and Luigi Paura. Human-mobility enabled We evaluated our strategy using three scenarios based wireless networks for emergency communications during special on real mobility traces with real message exchange from events. Pervasive and Mobile Computing, 9(4):472 – 483, 2013. real communication datasets. In our experimentation we [13] F. Calabrese, G. Di Lorenzo, and C. Ratti. Human mobility proved that our routing protocol performs better than prediction based on individual and collective geographical pref- erences. In 13th International IEEE Conference on Intelligent state of the art ones in terms of latency time and vir- Transportation Systems, pages 312–317, Sept 2010. tual centrality obtained with very similar delivery ra- [14] Radu-Ioan Ciobanu, Radu-Corneliu Marin, Ciprian Dobre, tios. Additionally, we compared our general strategy Valentin Cristea, and Constandinos X Mavromoustakis. ON- with a publish/subscribe scheme. The simulation re- SIDE: Socially-aware and interest-based dissemination in op- portunistic networks. In Network Operations and Management sults showed that our proposal performs better than the Symposium (NOMS), 2014 IEEE, pages 1–6. IEEE, 2014. publish/subscribe one in terms of latency time, virtual cen- [15] Marco Conti, Mohan Kumar, et al. Opportunities in oppor- trality value, delivery ratio and network overhead. tunistic computing. Computer, 43(1):42–50, 2010. [16] Elizabeth M Daly and Mads Haahr. Social network analysis for routing in disconnected delay-tolerant manets. In Proceed- ings of the 8th ACM international symposium on Mobile ad hoc Acknowledgements networking and computing, pages 32–40. ACM, 2007. [17] Elizabeth M Daly and Mads Haahr. Social network analysis for information flow in disconnected delay-tolerant manets. IEEE This work was partly supported by the Catalan AGAUR Transactions on Mobile Computing, 8(5):606–621, 2009. 2017 SGR 00463 project and the Spanish Ministry of Sci- [18] Mieso K Denko. Mobile Opportunistic Networks: Architectures, ence and Innovation TIN2017-87211-R project. Protocols and Applications. CRC Press, 2016. [19] Martin Everett and Stephen P Borgatti. Ego network between- ness. Social networks, 27(1):31–38, 2005. [20] Thomas S Ferguson. Who solved the secretary problem? Sta- References tistical science, pages 282–289, 1989. [21] Mohamed Amine Ferrag, Leandros Maglaras, and Ahmed Ah- mim. Privacy-preserving schemes for ad hoc social networks: A [1] Shabbir Ahmed and Salil S Kanhere. HUBCODE: hub-based survey. arXiv preprint arXiv:1610.06095, 2016. forwarding using network coding in delay tolerant networks. [22] Linton C Freeman. Centrality in social networks conceptual Wireless Communications and Mobile Computing, 13(9):828– clarification. Social networks, 1(3):215–239, 1978. 846, 2013. [23] Linton C Freeman. Centered graphs and the structure of ego [2] Marc Barthelemy. Betweenness centrality in large complex net- networks. Mathematical Social Sciences, 3(3):291–304, 1982. works. The European Physical Journal B-Condensed Matter [24] PR Freeman. The secretary problem and its extensions: A and Complex Systems, 38(2):163–168, 2004. review. International Statistical Review/Revue Internationale [3] MohammadHossein Bateni, Mohammadtaghi Hajiaghayi, and de Statistique, pages 189–206, 1983. Morteza Zadimoghaddam. Submodular secretary problem and [25] Thomas MJ Fruchterman and Edward M Reingold. Graph extensions. ACM Transactions on Algorithms (TALG), 9(4):32, drawing by force-directed placement. Software: Practice and 2013. experience, 21(11):1129–1164, 1991. [4] J Neil Bearden. A new secretary problem with rank-based selec- [26] Wei Gao, Qinghua Li, Bo Zhao, and Guohong Cao. Social- tion and cardinal payoffs. Journal of Mathematical Psychology, aware multicast in disruption-tolerant networks. IEEE/ACM 50(1):58–59, 2006. Transactions on Networking (TON), 20(5):1553–1566, 2012. [5] Carlos Borrego, Sergio Castillo, and Sergi Robles. Striving for [27] Wei-jen Hsu, Debojyoti Dutta, and Ahmed Helmy. Profile-cast: sensing: Taming your mobile code to share a robot sensor net- Behavior-aware mobile networking. In Wireless Communica- work. Information Sciences, 2014. tions and Networking Conference, 2008. WCNC 2008. IEEE, [6] Carlos Borrego, Gerard Garcia, and Sergi Robles. Softwarecast: pages 3033–3038. IEEE, 2008. A code-based delivery manycast scheme in heterogeneous and [28] Xiping Hu, Terry HS Chu, Victor CM Leung, Edith C-H Ngai, opportunistic ad hoc networks. Ad Hoc Networks, 55:72–86, Philippe Kruchten, and Henry CB Chan. A survey on mobile 2017. social networks: Applications, platforms, system architectures, [7] Carlos Borrego and Sergi Robles. A store-carry-process-and- and future research directions. IEEE Communications Surveys forward paradigm for intelligent sensor grids. Information Sci- & Tutorials, 17(3):1557–1581, 2015. ences, 222(0):113 – 125, 2013. [29] Pan Hui, Jon Crowcroft, and Eiko Yoneki. Bubble rap: Social- [8] Carlos Borrego, Sergi Robles, Angela Fabregues, and Adrián based forwarding in delay-tolerant networks. IEEE Transac- Sánchez-Carmona. A mobile code bundle extension for tions on Mobile Computing, 10(11):1576–1589, 2011. application-defined routing in delay and disruption tolerant net- [30] Esa Hyytiä, Suzan Bayhan, Jörg Ott, and Jussi Kangasharju. working. Computer Networks, 87:59–77, 2015. Searching a needle in (linear) opportunistic networks. In Pro- [9] Carlos Borrego, Adrián Sánchez-Carmona, Zhiyuanand Li, and ceedings of the 17th ACM international conference on Model- Sergi Robles. Explore and wait: A composite routing-delivery ing, analysis and simulation of wireless and mobile systems, scheme for relative profile-casting in opportunistic networks. pages 187–196. ACM, 2014. Computer Networks, 123:51–63, 2017. 13 [31] Zsolt Katona, Peter Pal Zubcsek, and Miklos Sarvary. Network Experience, 27(8):1900–1912, 2015. effects and personal influences: The diffusion of an online social [42] James Scott, Richard Gass, Jon Crowcroft, Pan Hui, network. Journal of marketing research, 48(3):425–443, 2011. Christophe Diot, and Augustin Chaintreau. CRAWDAD [32] Ari Keränen, Jörg Ott, and Teemu Kärkkäinen. The ONE dataset cambridge/haggle (v. 2006-01-31). Downloaded simulator for DTN protocol evaluation. In Proceedings of from http://crawdad.org/cambridge/haggle/20060131, January the 2nd international conference on simulation tools and tech- 2006. niques, page 55. ICST (Institute for Computer Sciences, Social- [43] Albert N Shiryaev. Optimal stopping rules, volume 8. Springer Informatics and Telecommunications Engineering), 2009. Science & Business Media, 2007. [33] Jérémie Leguay, Pan Hui, Jon Crowcroft, James Scott, [44] Sophie Stalla-Bourdillon, Evangelia Papadaki, and Tim Chown. Anders Lindgren, and Timur Friedman. CRAWDAD From porn to cybersecurity passing by copyright: how mass dataset upmc/content (v. 2006-11-17). Downloaded from surveillance technologies are gaining legitimacy the case of deep http://crawdad.org/upmc/content/20061117, November 2006. packet inspection technologies. Computer Law & Security Re- [34] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph view, 30(6):670–686, 2014. evolution: Densification and shrinking diameters. ACM Trans- [45] Sergio Martı́nez Tornell, Carlos Miguel Tavares Calafate, Juan- actions on Knowledge Discovery from Data (TKDD), 1(1):2, Carlos Cano, and Pietro Manzoni. DTN Protocols for Vehicular 2007. Networks: An Application Oriented Overview. IEEE Commu- [35] Anders Lindgren, Avri Doria, and Olov Schelén. Proba- nications Surveys and Tutorials, 17(2):868–887, 2015. bilistic routing in intermittently connected networks. ACM [46] Sacha Trifunovic, Sylvia T Kouyoumdjieva, Bernhard Distl, SIGMOBILE Mobile Computing and Communications Review, Ljubica Pajevic, Gunnar Karlsson, and Bernhard Plattner. A 7(3):19–20, 2003. decade of research in opportunistic networks: Challenges, rele- [36] Peter V Marsden. Egocentric and sociocentric measures of net- vance, and future directions. IEEE Communications Magazine, work centrality. Social networks, 24(4):407–422, 2002. 55(1):168–173, 2017. [37] Mehul Motani, Vikram Srinivasan, and Pavan S. Nuggehalli. [47] Jie Wu and Yunsheng Wang. Opportunistic Mobile Social Net- Peoplenet: Engineering a wireless virtual social network. In works. CRC Press, 2014. Proceedings of the 11th Annual International Conference on [48] Daqiang Zhang, Daqing Zhang, Haoyi Xiong, Ching-Hsien Hsu, Mobile Computing and Networking, MobiCom ’05, pages 243– and Athanasios V Vasilakos. BASA: Building mobile Ad-Hoc 257, New York, NY, USA, 2005. ACM. social networks on top of android. IEEE Network, 28(1):4–9, [38] Kazuya Okamoto, Wei Chen, and Xiang-Yang Li. Ranking of 2014. closeness centrality for large-scale social networks. In Interna- [49] Yanru Zhang, Lingyang Song, Chunxiao Jiang, Nguyen H Tran, tional Workshop on Frontiers in Algorithmics, pages 186–195. Zaher Dawy, and Zhu Han. A Social-Aware Framework for Effi- Springer, 2008. cient Information Dissemination in Wireless Ad Hoc Networks. [39] Tore Opsahl, Filip Agneessens, and John Skvoretz. Node cen- IEEE Communications Magazine, 55(1):174–179, 2017. trality in weighted networks: Generalizing degree and shortest [50] Haojin Zhu, Suguo Du, Zhaoyu Gao, Mianxiong Dong, and paths. Social networks, 32(3):245–251, 2010. Zhenfu Cao. A probabilistic misbehavior detection scheme [40] Jiho Park, Junyeop Lee, Sun-Kyum Kim, Kiyoung Jang, and toward efficient trust establishment in delay-tolerant net- Sung-Bong Yang. A forwarding scheme based on swarm in- works. IEEE Transactions on Parallel and Distributed Systems, telligence and percolation centrality in opportunistic networks. 25(1):22–32, 2014. Wireless Networks, 22(8):2511–2521, 2016. [51] Haojin Zhu, Xiaodong Lin, Rongxing Lu, Yanfei Fan, and [41] Florin Pop, Radu-Ioan Ciobanu, and Ciprian Dobre. Adaptive Xuemin Shen. Smart: A secure multilayer credit-based incen- method to support social-based mobile networks using a pager- tive scheme for delay-tolerant networks. IEEE Transactions on ank approach. Concurrency and Computation: Practice and Vehicular Technology, 58(8):4628–4639, 2009. 14