iDocSlide.Com

Free Online Documents. Like!

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

Tags

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. Speciﬁcally, 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 selﬁsh 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 beneﬁts 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 deﬁned localities which nodes havea good chance of visiting, based on their be-haviour. Such localities will be considered to deﬁnelocality-induced (as opposed to interest-induced) so-cial groups. Such groups may be, for example, a coﬀee-break place, a train station, etc.
•
Random encounters: refer to encounters not inﬂu-enced by a particular locality (physical area) in whichthe node is found. For example, this may includeencounters a node may have when moving betweendiﬀerent 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 speciﬁc 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 eﬀectiveness 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 eﬀective 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 deﬁne 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 eﬀectivenessof 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 ﬁnally, 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 diﬀerently thanin [9]. The associations of each node with the interest-and locality-induced social groups are described throughprobability distributions over diﬀerent 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
behaviourbeneﬁts the particular node as well, as the comparisonresults with a selﬁsh 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-deﬁned and somewhat popular locality; the latter arelocalities that are visited by a minimum number of nodesover certain periods and are, thus, considered to deﬁne 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 deﬁned 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 deﬁned 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
, deﬁned 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 diﬀuse 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 eﬀective totry to forward contents of class
c
to the group with thelargest population. An eﬀective 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 deﬁne eﬀective 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 eﬀectively. Roughly speaking, aneﬀective content dissemination strategy would increase thelikelihood that a certain content type is made available toa node upon request. A speciﬁc metric for assessing theeﬀectiveness 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 eﬀectiveness– we restrict the consideration to the content (or interest)classes without getting into the ﬁne resolution of thediﬀerent 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 speciﬁc 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 eﬃciencies achieved arealso expected when considering metrics associated withthe ﬁner resolution of the object level.As the nodes are assumed here to encounter other nodeswithin the speciﬁc 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 ﬁnd 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 deﬁned 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 diﬀerent 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 ﬁrst content storage strategy considered in thispaper (to be referred to as the
selﬁsh 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 beneﬁt they can generate through suchcooperative behaviour. The latter is achieved by deﬁningthe
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 eﬀectiveness of the cooperative strategy without theexploding complexities of dealing with and keeping trackof a realistically immense universe of individual objects,the discussions, deﬁnitions and overall evaluation will beconﬁned 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 theeﬀectiveness of the content dissemination process. Theeﬀectiveness 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 eﬀective 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 deﬁnednext.
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 ﬁnds 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 eﬀective; 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 selﬁsh) 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, beneﬁting 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 ineﬃciencies and, on theother hand, gives us a tool for stirring the behaviour of the nodes across the entire spectrum, from selﬁsh (or even”pathologically” selﬁsh) to cooperative (or even totallyaltruistic), depending on the
usability
values assigned tothe contents. An eﬀective 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
ﬁnds contents of class
c
in itsown (or, local) storage is given by
Pl
nc
=
IPI
nc
.
4
The probability that a node
n
ﬁnds 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 deﬁned 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
ﬁrst 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 selﬁsh 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 eﬀectivenessof the selﬁsh 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 selﬁsh and cooperative content dissemi-nation strategies introduced earlier. The higher the valueof
valuability
, the more eﬀective the associated contentdissemination strategy is considered to be, according theearlier discussions. The focus of the study is on caseswhere nodes have diﬀerent preferences for content classes,so that the mutual beneﬁt of cooperation be revealed. Inall cases considered here, all nodes are either selﬁsh 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 diﬀerent 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 ﬁrst 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 diﬀerent 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 eﬀectiveness of the content dissemination process), we consider the caseswhere
v
r
v
l
= 1
,
5
,
10, or 100.Fig. 1 presents results for the diﬀerent values of
v
r
v
l
.These results show that the selﬁsh strategy outperformsthe cooperative one for any value of the parameter
s
L
5

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