Genealogy

8 pages
4 views

Joint interest- and locality-aware content dissemination in social networks

of 8
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Joint interest- and locality-aware content dissemination in social networks
Transcript
  Joint Interest- and Locality-Aware ContentDissemination in Social Networks Eva Jaho and Ioannis Stavrakakis Department of Informatics and TelecommunicationsNational & Kapodistrian University of AthensIlissia, 157 84 Athens, GreeceEmail:  { ejaho, ioannis } @di.uoa.gr Abstract  —Social groups are typically formed bynodes that share common interests (interest-inducedsocialgroups), withnoimplicationonthe geographiclo-cation ofthesenodes.In additionto suchgroups, mobilenodes form groups also as they move around and cometo a locality where they can establish communicationwith other nodes (locality-induced social groups). Thispaper investigates the intermingling of these distincttypes of social groups and proposes an approach thatcan enhance content dissemination in the presence of such groups. Specifically, we introduce a framework formodelling this environment (both, the nodes’ dynamicassociation to such groups and the dynamic  usability   of the content) and explore the conditions under which aproposed cooperative strategy can enhance the contentdissemination process compared to a selfish one. Thiswork basically explores how mobility and cooperativecontent storage strategies can help bridge interest-induced social groups, or how the joint association of nodes with interest- and locality-induced social groupscan be exploited to enhance content dissemination. I. Introduction In social networks, nodes establish connections basedon their social interests, forming interest-induced socialgroups. Such groups can generally be exploited in order toenhance the dissemination of information to participatingnodes. For example, if a node is interested in music of the80’s, it may join the group“songs of the 80’s”and allow allthe members of this group to access the group’s collectiveinformation content. This example can be applicable inpublish/subscribe environments, in which the networkdelivers a published message only to the nodes whosesubscribed interests match the content of the message [1],[2].In environments where the information exchange is pos-sible  only through opportunistic encounters   (which is theone considered in this paper), the benefits of interest-basedsocial grouping can be harvested only by exploiting suchencounters. The higher the chance for a node to encounterother nodes that are strongly associated with a certain This work has been supported by the IST-FET project SOCIAL-NETS (FP7-IST-217141) and the EU funded CONTENT NoE (FP6-IST-038423). interest, the higher the probability for a node to acquirea certain content of interest.Node encounters may occur in two ways: •  Locality-induced encounters: refer to encounters thatoccur in well defined localities which nodes havea good chance of visiting, based on their be-haviour. Such localities will be considered to definelocality-induced (as opposed to interest-induced) so-cial groups. Such groups may be, for example, a coffee-break place, a train station, etc. •  Random encounters: refer to encounters not influ-enced by a particular locality (physical area) in whichthe node is found. For example, this may includeencounters a node may have when moving betweendifferent locality-induced social groups.In this paper, we explore how locality-induced nodeencounters and the nodes’ own (content) interests can be jointly exploited to improve information dissemination insocial networks.In addition to its membership to interest-induced socialgroups, a node may be attributed membership to locality-induced social groups. Such memberships are expected toboost drastically the  discoverability   of (probability of ac-quiring) a desirable content. That is, the locality-inducedsocial networking structure could direct the content dis-semination process to target nodes which are likely to beencountered by nodes desiring the specific content. Forexample, nodes that are interested in music of the 80’s maybe members of the interest-induced social group“music of the 80’s”, but they could also be members of the locality-induced social group“discotheque XYZ”, where they mayfrequently meet and thus, exchange more contents of thesame interest. Such locality-induced social groups could beuseful in enhancing content dissemination. In this paper weexplore how mobility and cooperation can enhance contentdissemination by exploiting the joint association of nodeswith interest- and locality-induced social groups.Interest- and locality-induced social grouping may betaken into account when a node decides on which typeof content to store in its memory. Clearly, the type of content that each node stores in its memory and exchangeswith other nodes, shapes the content dissemination pro-  cess. The effectiveness of this process can be measuredin terms of a quantity (to be referred to as  valuability  )that captures both the  usability   and  discoverability   of thecontent; usability refers to the extent to which content is(still) useful (e.g., just created vs outdated and irrelevantany more, etc), while discoverability refers to the chanceof succeeding in acquiring certain content by nodes thatwant it. This quantity will be clearly shaped by theadopted content dissemination strategy. The higher thevalue of this quantity, the more effective the adoptedcontent dissemination strategy would be considered to be.The paper is organized as follows. Section II refers to therelated work. In Section III, we describe the attributes of each node that help define content dissemination strategiesand the relevant attributes of a locality-induced socialgroup. A mechanism for determining which content tostore – which characterizes the content disseminationstrategy – is described in Section IV. The effectivenessof the resulting content dissemination strategy is thendetermined by deriving the  valuability   of the contentsunder the considered content dissemination strategies inSection V. Section VI presents the performance evaluationresults and finally, the paper is concluded in Section VII. II. Related work Exploiting interest-induced social groups has beenshown to improve content dissemination in variousnetworking environments. Consequently, detecting suchgroups is important and has received considerable atten-tion. Example studies include the detection of communitiesin a web graph (where a community might correspondto sets of web sites dealing with related topics [3], [4]),detection of communities of scientists connected in a co-authorship graph [5], detection of communities in Delay Tolerant networking environments [6], etc. The dynamicdetection of such groups of common interests, where usersdo not declare a priori their interests, has been studiedin [7]. In that paper, the authors show that a proactiveinformation dissemination within groups with commoninterests can reduce the search cost. Similarly, the authorsin [8] show that detecting interest-based communities inPeer-to-Peer networks improves information disseminationand helps in pruning the search space.The exploitation of both interest-induced social groupsand locality-induced social groups in order to improveinformation dissemination, has recently attracted the at-tention of researchers. For instance, a dynamic schemefor deciding which objects (content) of a certain contenttype to replicate locally based on the encounters withother nodes is introduced in [9]. In that work each nodeappends a value to each object that is a function of itsaccess probability and its availability in a locality, its sizeand the weight of the locality; this weight represents therelationship between the node and the locality (e.g., howoften a node visits this locality). In [9] the objects’ valuedoes not change over time or space (where it is stored).In our paper the problem is formulated differently thanin [9]. The associations of each node with the interest-and locality-induced social groups are described throughprobability distributions over different content types (in-terests) and localities, which express the likelihood of anode to be interested in a certain content-type, or to visita certain locality. Content exchanges are assumed to occurbetween a node visiting a locality-induced social groupand the  entire   group, as a visit to a locality implies theability to communicate with any member of that local-ity; as a result, exchanges are considered to be possiblebetween the visiting node’s storage and the collectivestorage of the group. The proposed content storage (andthus, dissemination) strategies operate on the content-type (or interest/content class) level and not on individualobject level. The proposed cooperative strategy takes intoconsideration the interests of the locality-induced socialgroups the node is likely to visit in the future, thus aimingat serving as a bridge to distinct social groups and enhancecontent dissemination; this seemingly  altruistic   behaviourbenefits the particular node as well, as the comparisonresults with a selfish counterpart to this strategy indicate.The proposed strategies are evaluated analytically withrespect to a newly introduced performance metric called valuability  ; this quantity captures jointly how probablea certain content-type is to be found and how usefulor usable it is (its  usability  ). Among other factors, the usability   may capture how fresh or novel an object is for acertain node (e.g., latest software update). Contents thatresides outside a node’s storage are considered to havehigh  usability   for this node, as such contents most likelyhave not been available to (or used by) that node in thepast. After receiving such contents upon an encounter withanother node, these contents are considered to become”old”as they are processed or utilized (if desirable) by thereceiving node and, thus, their  usability   for the node thatstores and carries them is considered to be decreased. III. Attributes of social groups In this section attributes of the interest- and locality-induced social groups are introduced that are used in theproposed framework for modelling these groups, as well asin the description of the investigated content storage and– ultimately – dissemination strategies.Consider a social network that consists of   N   mobilenodes,  C   interest-induced social groups (or, equivalently,content classes) and  L  locality-induced social groups; thevariables  n ,  c  and  l  will be used in the sequel to representan element from these sets, respectively.Network nodes are considered to belong in one ormore interest-induced social groups. The degree of theirassociation with each such group – that represents thedistribution of content class preferences of the node – iscaptured by the node’s self-interest factor. Let  I  nc  , denotethe self-interest factor of node  n  in content class  c , where0   I  nc    1 and 1    c   C  . Let the self-interest vector of 2  node  n  be the collection of all self-interest factors of thisnode associated with all the content classes, denoted by I  n = ( I  n 1  ,I  n 2  ,...,I  nC  ), where  C c =1  I  nc  = 1.In this work it is assumed that network nodes aremobile and exchange information only through encounterswith other nodes. At any point of time these nodes maybe found in a random location or in non-random, well-defined and somewhat popular locality; the latter arelocalities that are visited by a minimum number of nodesover certain periods and are, thus, considered to define alocality-induced social group. Let the self-movement factorof node  n ,  M  nl  , be equal to the probability that node n  is found in locality  l  at a random point in time, i.e.,belongs in the locality-induced social group  l , 0  M  nl   1.Let  M  n = ( M  n 1  ,M  n 2  ,...,M  nL ), denote the self-movementvector of node  n , containing the probabilities that node n  is found in the various locality-induced social groups,where  Ll =1  M  nl   1 − r n .  r n is the probability not to bein any of the locality-induced social groups. Without lossof generality and in order not to burden the presentationin this paper, we will consider that node encounters occuronly within the defined localities (and not at randomlocations) and thus,  Ll =1  M  nl  = 1 or  r n = 0.Let  A n = ( I  n ; M  n ) denote the attributes of node  n .As it will become clear later, the proposed cooperativecontent storage strategy will take into consideration cer-tain attributes associated with the locality-induced socialgroups. Such attributes are defined in the sequel.Let  g lc  denote the probability that a random member of group  l  belongs in content class  c . This probability is givenby g lc  = N   n =1 P  nl  I  nc  ,  (1)where  P  nl  denote the probability that a randomly selectednode from locality-induced social group  l  is node  n  and isgiven by P  nl  =  M  nl  N j =1  M  jl . Let  w l denote the weight of group  l , defined to be equalto the average population of locality-induced social group l  (mean number of nodes found in this group at a randominspection time), given by w l = N   n =1 M  nl  .  (2)Notice that  w l captures the ability of locality-inducedsocial group  l  to diffuse content, as a higher value of   w l would suggest a higher potential for content disseminationwithin group  l , since all the nodes within a locality-inducedsocial group are considered to communicate with eachothers. For instance, if   g lc  is the same for all the locality-induced social groups  l , it would be more effective totry to forward contents of class  c  to the group with thelargest population. An effective content storage (and, thus,content dissemination) strategy should aim at makingcontent of class  c  available to locality-induced social groupsthat are well-populated by nodes utilizing this class of content as well as have a relatively large population. IV. Content storage strategies The above introduced framework for describing interest-and locality-induced social groups is employed in thissection in order to define effective content storage strate-gies. These strategies will dictate the contents that thenodes will exchange upon encounters, so that (interest-and locality-induced) social grouping structure results indisseminating content effectively. Roughly speaking, aneffective content dissemination strategy would increase thelikelihood that a certain content type is made available toa node upon request. A specific metric for assessing theeffectiveness of these strategies is presented in the nextsection.In this paper – and in order to facilitate the presentationof the framework and show its potential for effectiveness– we restrict the consideration to the content (or interest)classes without getting into the fine resolution of thedifferent objects within each content class. Consequently,the objective here is to devise a strategy that bringsto the nodes the type of contents that are likely to berequested and not specific objects from a content class.In other words, the discussion is at the content-type leveland not the object level. In addition to facilitating makingthe important points/contributions, this content-type leveltreatment could be almost directly applicable in an envi-ronment where there is an one to one equivalence betweencontent-types and objects, while it is expected that theconclusions drawn here and the efficiencies achieved arealso expected when considering metrics associated withthe finer resolution of the object level.As the nodes are assumed here to encounter other nodeswithin the specific localities and not in random locations, anode encounter in this paper is equivalent to an encounterof the node with an entire locality-induced social group.Consequently, the incoming node is expected to be pre-sented with a (large) pool of contents and content-typesthat are stored in the storages of the nodes of this locality-induced social group. By assuming that the population of these groups is relatively large, it is reasonable to assumethat all content types are in principle available, althoughnot with the same number of objects. Consequently, theincoming node can find and place in its storage (that isconsidered to be extremely small compared to the totalstorage of all the nodes in the group) any type of content(although not necessarily any object) it desires. Whichcontent-type to actually select is dictated by the employedcontent storage strategy.Let  IPI  nc  denote the  interest priority index   ( IPI  ) of anode  n  for content class  c , to be defined below. The content3  storage strategies considered in this paper use this indexto determine the portion of the node’s storage that willbe allocated for storing content of the different contentclasses when the node is confronted with such a decision(upon entering a locality-induced social group). That is,the proportion of storage each node  n  devotes to contentsof class  c  is given by the normalized value of its  IPI   index, IPI  nc  =  IPI  nc  C c =1 IPI  nc . The first content storage strategy considered in thispaper (to be referred to as the  selfish strategy  ) utilizesthe following  IPI  : IPI  nc  =  I  nc  .  (3)That is, under this content storage strategy the nodesseek to store content-types that match completely theirown content-type (self-interests), with no provision what-soever for catering for the interests of other nodes theywill encounter in the future.The second content storage strategy considered in thispaper (to be referred to as the  cooperative strategy  ) utilizesthe following  IPI  : IPI  nc  = L  l =1 M  nl  w l g lc  = L  l =1 M  nlN   k =1 M  kl  I  kc  .  (4)That is, under this content storage strategy the nodesseek to take into account the interests of the nodes theywill most likely encounter in the future, aiming at maxi-mizing the average benefit they can generate through suchcooperative behaviour. The latter is achieved by definingthe  IPI   by considering the locality-induced social groupsthe node is expected to visit (term  M  nl  ), the number of nodes within those groups (term  w l ), and the interests of the nodes expected to visit those groups (term  g lc ). V. Measuring the effectiveness of the contentdissemination strategies As indicated earlier and in order to show the poten-tial effectiveness of the cooperative strategy without theexploding complexities of dealing with and keeping trackof a realistically immense universe of individual objects,the discussions, definitions and overall evaluation will beconfined to the content-type (as opposed to individualcontent) level. In view of the earlier discussions it is clearthat the adopted content storage strategy will shape theeffectiveness of the content dissemination process. Theeffectiveness of this process will be measured in this paperin terms of a quantity (to be referred to as  valuability  )that captures both the  discoverability   and the  usability   of the content. Discoverability   refers to the availability of a requestedcontent-type  c . This quantity will be clearly shaped bythe adopted content dissemination strategy. The higherthe value of this quantity, the more effective the adoptedcontent dissemination strategy would  potentially   be, pro-vided that the content that is made available to the node(discovered) is of high potential use, or  usability   as definednext. Usability   refers to the potential for making use of con-tent that is, or becomes, available to a node (or ultimately,how useful a certain content is to the node). It is reason-able to assume that the content that a node finds in thestorage of other nodes (upon entering a locality-inducedsocial group) is of higher potential usage than the contentthat the node has been carrying in its own storage, as thelatter content may be considered to have already been usedby the node in the past, or be somewhat outdated.Notice that it may be that the  discoverability   of acertain content may be high, but its  usability   be lowand, consequently, a strategy that ignores the contents’ usability   would not be effective; such a strategy could endup providing contents to the nodes with high probabilitybut these objects could be of small value to them. Clearly,if   discoverability   were the only criterion, the nodes wouldtend to bring to their own storage, contents of theirown interests only (since the  discoverability   of contentsstored locally is high), making them following in essencea “myopic” (or selfish) content storage behaviour. Thelatter would impact negatively on both the node itself (as it will likely end up carrying stale and largely uselesscontent) and on a wider content dissemination (as it willnot contribute to a wider circulation and refreshing of the content, benefiting all nodes). Through the introducednotion of   usability   we basically obtain a mechanism which,on one hand helps capture realistic aspects of the envi-ronment and avoid the above inefficiencies and, on theother hand, gives us a tool for stirring the behaviour of the nodes across the entire spectrum, from selfish (or even”pathologically” selfish) to cooperative (or even totallyaltruistic), depending on the  usability   values assigned tothe contents. An effective content dissemination strategywould be the strategy that yields high content  valuability  ,that is, taking into consideration both the  discoverability  and  usability   metrics.Each node is assumed to assign a  usability   value to itscontents of interest. It assigns a (relatively low) value  v l (0 ≤ v l  ≤ 1), to contents of its interest that are stored inits own storage, and it assigns a (relatively high) value  v r (0  ≤  v r  ≤  1), to contents of its interest that are storedin other nodes. To keep the analysis simple, it is assumedthat  v l  and  v r  maintain the same values for each node.The normalized  usability   values are given by  v l  =  v l v l + v r and  v r  =  v r v l + v r , for  v l  and  v r  respectively.The  discoverability   of a content-type can be expressedas the probability of acquiring content of this type. Theprobability that a node  n  finds contents of class  c  in itsown (or, local) storage is given by Pl nc  =  IPI  nc . 4  The probability that a node  n  finds contents of class  c in the storage of other nodes (or, remote storage) is givenby Pr nc  = L  l =1 M  nl  [1 − N   k =1 ,k  = n [ M  kl  (1 − IPI  kc ) + (1 − M  kl  )]] . That is, it is given by the sum for each locality-inducedsocial group  l  of the probability that node  n  is in the group l , multiplied by the probability that at least one other nodefrom this group has contents of class  c .The mean  valuability   of content class  c  for node  n can now be defined by combining the above probabilities(capturing the  discoverability   of content) with the  usability  of contents, stored locally or remotely, as follows, for thecase in which  v r  ≥ v l : V   nc  =  v r Pr nc  +  v l (1 − Pr nc  ) Pl nc  (5)When  v r  ≥ v l , a node is primarily interested in acquiringcontents that other nodes have (as they are considered tobe more fresh and not exploited yet) with  usability   v r .Otherwise, if the contents of its interest are not found inother nodes, they are acquired from its local memory (inpractice, they are kept and not moved out) with  usability  v l . That is, when  v r  ≥ v l  node  n  first searches for contentsof class  c  in other nodes (of higher  usability  ) and if noneis found, it searches its local memory. Notice that in thiscase the wider content dissemination is facilitated.Note that if the notion of   usability   is absent, the mean valuability   of content class  c  for node  n  can be calculatedfrom the previous expression by setting  v r  =  v l  andignoring the resulting constant  12 , as it does not impact onthe comparative study of the selfish and the cooperativecontent storage strategies investigated here.By weighting (5) with the self-interest factors  I  nc  of a node  n  for each content class  c  = 1 ,...,C  , the mean valuability   of contents of its interest for node  n , is derivedby V   n = C   c =1 I  nc  V   nc  . Finally, the mean  valuability   of contents of its interestfor a random node, is given by V   =  N n =1  V   n N  .  (6)In the next section we will investigate the effectivenessof the selfish and cooperative content storage (or dissemi-nation) strategies. VI. Numerical evaluation In this section we derive results on the mean  valuability  of contents of interest for a random node (as expressedin (6)) under the selfish and cooperative content dissemi-nation strategies introduced earlier. The higher the valueof   valuability  , the more effective the associated contentdissemination strategy is considered to be, according theearlier discussions. The focus of the study is on caseswhere nodes have different preferences for content classes,so that the mutual benefit of cooperation be revealed. Inall cases considered here, all nodes are either selfish or allare cooperative.The self-interest vector  I  n = ( I  n 1  ,I  n 2  ,...,I  nC  ) is drawnfrom a Zipf distribution with exponent  s C   = 5. Theprobability that each node is interested in contents of class c ,  c  = 1 ,...,C  , which is the self-interest factor of this nodein content class  c , is given by I  nc  =  f  ( c ; s C  ,C  ) = 1 /c s C  C k =1  1 /k s C .  (7)The drawn probabilities are the same for all the nodesand they result in a preference ranking for the  C   contentclasses, which are accordingly ordered as [1 , 2 ,...,C  ]. Sincewe are interested in considering the case where each nodehas different ordering of preferences for each content class,node 1 is assigned the preference order [1 , 2 ,...,C  ] and thisorder set is shifted to the left by  n − 1 positions to generatethe preference ranking for node  n  ( n  = 2 ,...,N  ). Thus, if the preference ranking of node 1 is [1 , 2 ,...,C  ], then theranking of node 2 is [2 , 3 ,...,C, 1], the ranking of node 3 is[3 , 4 ,...,C, 1 , 2], and so on.The self-movement vector  M  n = ( M  n 1  ,M  n 2  ,...,M  nL )is drawn from a Zipf distribution (that is, from (7) bysubstituting  I  nc  with  M  nl  ,  s C   with  s L  and  C   with  L ) withexponent  s L  varying from  s L  = 0 (in which case thedistribution of localities is uniform and the mobility of the nodes is considered to be high as the nodes visit withthe same probability all the locality-induced social groups)to  s L  = 5 (the mobility of the nodes is considered to below). Again, we consider the case where the preferenceranking of node 1 is [1 , 2 ,...,L ] for the  L  localities, theranking of node 2 is [2 , 3 ,...,L, 1], the ranking of node 3 is[3 , 4 ,...,L, 1 , 2], and so on.The values of   g lc  and  w l are calculated from (1) and (2),respectively. A. Results for various self-movement vectors of a node  We first consider the case for  N   =  C   =  L  = 3.In this case and in view of the earlier assumptions onthe preference ranking, it turns out that all three nodeshave different largest preferences for content classes andlocalities (for  s C   = 5 and  s L  >  0). To show the impact of  usability   on the mean  valuability   of contents of interestfor a random node (and, thus, on the effectiveness of the content dissemination process), we consider the caseswhere  v r v l = 1 , 5 , 10, or 100.Fig. 1 presents results for the different values of   v r v l .These results show that the selfish strategy outperformsthe cooperative one for any value of the parameter  s L 5
Related Documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x