=Paper=
{{Paper
|id=Vol-356/paper-2
|storemode=property
|title=Setting Access Permission through Transitive Relationship in Web-based Social Networks
|pdfUrl=https://ceur-ws.org/Vol-356/paper2.pdf
|volume=Vol-356
|dblpUrl=https://dblp.org/rec/conf/www/HongS08
}}
==Setting Access Permission through Transitive Relationship in Web-based Social Networks==
https://ceur-ws.org/Vol-356/paper2.pdf
Setting Access Permission through Transitive Relationship
in Web-based Social Networks
Dan Hong Vincent Y. Shen
Department of Computer Science and Engineering
Hong Kong University of Science and Technology
Hong Kong
{csdhong,shen}@cse.ust.hk
ABSTRACT 1. INTRODUCTION
The rising popularity of Web 2.0, such as blogs, forums, online cal- With the increasing popularity of Web 2.0 services, more and
endars/diaries, etc., makes users more interested in keeping their more Web users post their articles, pictures, comments on the Web
data on the Web. Sharing of such data could make life more enjoy- through blogs, forums or other Web applications. Based on the
able and convenient. For example, posting new photos about activ- “State of the Blogosphere” report [19], 120,000 new weblogs are
ities or sharing views about an event can let friends know what a being created worldwide each day. Many online communities have
user cares about. However, some of these data (such as a person’s been established when users create accounts at those website hosts.
location during a particular time, opinion about a political event, In these communities users share their beliefs, opinions and in-
etc.) are private and should not be accessed by unauthorized users. terests. Communities on these websites are set up based on the
Although Web 2.0 facilitates sharing, the fear of forwarding sen- “common interest" page their members marked. Each person can
sitive data to a third party without knowledge of the data owners be members of several different communities and private data (e.g.
discourages people from using certain applications due to privacy identification, financial record, location, calendar, Web content) are
concerns. We take advantage of the existing relationships on social commonly shared along community connections. However, these
networks and build a “trust network” with transitive relationship to data sharing activities through Web-based social networking bring
allow data sharing while respecting the privacy of data owners. The serious privacy concerns since users do not have control over who
trust network linking private data owners, private data requesters, can access their personal data.
and intermediary users is a directed weighted graph. The permis- Nowadays, many users use a Web-based calendar, such as Google
sion value for each private data requester is automatically assigned Calendar [9], to arrange their appointment schedules. It is possible
in this network based on the transitive relationship. Experiments to provide a feature to let users define activity categories, such as
were conducted to confirm the feasibility of constructing the trust “family activity”, “work activity”, “church activity”, etc. Figure
network from existing social networks, and to assess the appropri- 1(a) shows such a calendar which has several different categories.
ateness of permission value assignments in the query process. This When a visitor of the website clicks on an item of the calendar,
privacy scheme can make private data sharing manageable by data detailed information (such as location, contact person, etc.) about
owners, who only need to define the access rights of their closest the event is displayed. It is also possible to provide a feature for
contacts once. the owner to define different groups (user context) who may access
different categories of the calendar. For example, assuming Alice is
Categories and Subject Descriptors the owner of such a calendar. As a family member, her sister Karen
can see “family activity” in detail but not the detailed information
K.4.1 [Computers and society]: Public Policy Issues—Privacy; of events in other categories. This strict definition of groups is use-
H.3.5 [Information storage and retrieval]: Online Information ful, but it does not fully satisfy Alice’s needs. To make the calendar
Services—Data sharing; H.1.2 [Models and principles]: User/Ma- more useful, some undefined visitors should also be allowed to see
chine Systems—Human factors part of her calendar. Consider the following two scenarios:
General Terms • Bob, who is one of Alice’s colleagues, can check her sched-
ule and see the details of her “work activity”. Carl, who is
Design, Human Factors
Bob’s friend, hopes to make an appointment with Alice for
some business discussion.
Keywords
Data Privacy, Trust Network, Transitive Relationship, P3P, Social • Donald, who is Alice’s travel agent, can check her sched-
Network ule for the arrangement of a family vacation. Edward, who
works for the car rental company which is a business part-
ner of Donald’s agency, needs the information regarding the
family’s arrival time.
The normal action for Carl is to ask his friend Bob to make the
Copyright is held by the Authors. Copyright transfered for publishing on-
appointment for him. He may also write to Alice directly. This
line and a conference CD ROM. requires some amount of interactions between Carl and Bob, and
SWKM’2008: Workshop on Social Web and Knowledge Manage- may also involve Alice directly or indirectly. It will be more conve-
ment @ WWW 2008, April 22, 2008, Beijing, China. nient if Carl can inherit some access right from Bob, who is Alice’s
.
(a) Without Privacy Management (b) With Privacy Management
Figure 1: Web Calendar Example
colleague, and can check Alice’s calendar directly for her “work ac- data access permission values when there is an existing social net-
tivity" items when he visits her website. Donald (the travel agent) work. The contributions of this paper include the construction of a
and Edward (the car rental agent) are in a similar situation; they trust network from existing social networks. This network can be
should have the right to see the “family activity” category, but not used to manage the sharing of private data in the Web environment.
the “work activity” category. Moreover, Alice’s calendar can be This trust network concept may be applied to data sharing in other
checked by Donald and Edward based on additional context: Alice ubiquitous computing environments.
might only allow Donald to check her calendar after the final ar- The rest of the paper is organized as follows. Section 2 describes
rangement of her trip is settled and before the end of her trip (time the related effort in improving privacy management. Section 3 de-
context); and Edward is only allowed to check Alice’s calendar in- scribes how to bootstrap the trust network from an existing social
formation related to Edward’s city (location context) and during the network. Using the Web calendar as a case study, Section 4 demon-
trip (time context, inherited from Donald). strates the process of trust network initialization and data sharing
It is hard for Alice to assign a special group and access right with obfuscation rules. A framework on how the components of
to every potential user for different calendar categories. It is not the system to manage private data sharing can be implemented
possible to assign an access right to someone whom Alice does not is given in Section 5. Section 6 summarizes the experiments we
even know, such as Carl and Edward. But a “trust network" can have done using an existing social network (MSN.com) to study
be used to derive specific access rights when needed. The network the characteristics and significant issues of the trust network. Sec-
is a directed graph which represents the trust relationship among tion 7 discusses possible refinements for the permission assignment
users in it. During the query process, some private data owners techniques. Section 8 contains the conclusions and future work.
(PDOs) might be willing to share their private data with private
data requesters (PDRs) through the network. We note that the trust
relationship is transitive; i.e., Alice trusts Bob and Bob trusts Carl 2. RELATED WORK
implies Alice trusts Carl to a certain extent. It is also directional; In order to identify Web users and their relationship with others,
i.e., although Alice trusts Carl by implication, Carl may not trust the Friend of a Friend (FOAF) [2] project creates a set of machine-
Alice regarding his private data. Since the trusted PDR through readable pages describing people, the links between them, and the
transitive trust relationship might have less access right (Edward things they create and do. This could be the basis to construct trust
does not have the same right as Donald has in the above example), networks by bootstrapping from existing social networks.
the information released to indirectly-trusted PDRs may need to Much of the fundamental work in the analysis of social networks
be obfuscated according to the level of trust. The trust network and the major advances in the past century have been carried out in
therefore requires: the fields of sociology, psychology, and communications [8, 22].
The first step to facilitate social networking is to have a definition
1. Trust relationship defined by PDOs of trust that captures the social features for both local and global
scopes [24]. Trust management is quite well studied in P2P sys-
2. Obfuscation (Web data annotation) rules defined according tems and semantic Web [13,14,16,23,24]. In [14], a definition that
to the nature of private data captures the nature of social trust relationships and an algorithm
are proposed for computing the trust value in social networks using
With the help of obfuscation rules, the access right is no longer default logic. Kamvar et al. proposed EigenTrust for reputation
binary (“yes" or “no"). The access right for a private data item is management for file sharing in P2P systems [13]. Richardon pro-
considered a PERMISSION VALUE, which represents how much de- posed a trust value computation method using probability theory in
tail the private data item can be given to the PDR based on the level global belief combination which can provide each user a personal-
of trust. Figure 1(b) shows the result when Carl looks at Alice’s ized set of trust values [16]. Trust propagation is another important
calendar when he visits the website. From the figure we can find research topic. Guha et al. proposed a method for predicting trust
out that Carl can only see the “work activity” and for the “family between users [10]. The trust acquisition and propagation model is
activity” Carl only knows that Alice is busy. The ability to con- discussed in [5, 6, 25]. However, the relationship between trust and
trol the sharing of private data makes life easier since Carl does not online private data is not well addressed.
need to ask Bob, who is Alice’s colleague, to help checking Alice’s The online data privacy problem has been noticed for quite a
calendar. long time. The Platform for Privacy Protection (P3P) Project [21]
In this paper, we are not focusing on how to define Web data in of the World Wide Web Consortium (W3C) is a method for web-
various levels of obfuscations. We solve the problem of assigning sites to publish their privacy policies. The APPEL language [20]
works with P3P and enables users to exchange privacy preferences
according to published privacy policies. P3P has not yet received
much acceptance from Web users mainly due to its lack of en-
forcement, since current implementations do not include compli-
ance of user preferences. Kolari et al. have pointed out that an
enhanced P3P based on the Rei language can provide an improved
trust model [15].
A lot of research has also been done on statistical databases
to protect privacy through query restriction, data perturbation and
output perturbation [1]. Such research focuses on hiding the re-
lationship between the identity of the PDO and relevant private
data [11, 18]. An example is that instead of giving the applica-
tion an exact location, a regional context is used to satisfy the K-
anonymity requirement. A list of candidates is returned to obfus-
cate private data [17]. There has not been much attempt to connect Figure 2: Facebook Network Example (1190 nodes). The data
this approach with access control rules. includes friends of ID 655183482 and friends of friends.
Since P3P does not provide any mechanism to ensure that these
promises are consistent with internal data processing at the web-
site, a purpose-based access control method can be used as an ex-
tension of P3P [4]. To address this issue we have proposed to ex- permission = trust(a, g, c)
tend the P3P protocol, which is a W3C recommendation for Web
applications. We have successfully applied this extension to some Where a is the PDO involved, g is a member within a group of
context-aware applications [12]. But the extension did not consider contacts that the PDO has defined, and c is the context where the
transitive trust relationships. PDOs still need to specify every po- permission value applies. The context in Definition 1 provides the
tential PDR’s access right based on the categories defined by P3P, application developer and the PDOs the ability to set the constrains
which makes management of private data cumbersome. in data sharing. Context may be related to the time, location, nature,
etc. of an event. For example, Alice only allows Bob to view his
calendar on her “working” activity. The event type "working" in the
calendar can be considered as one context. It is extensible based on
3. FROM SOCIAL NETWORK TO TRUST the needs of the application or the PDOs.
NETWORK PDOs are requested to define data access permissions for all the
In the Web-based social network, the PDOs need to have some direct users using their privacy preferences. The permission value
control on the management of their private data. However, it is not can be a decimal number ranging from [0,1], where 1 represents
practical for a PDO to set a particular permission value for each total trust and 0 represents no trust at all. The 0 permission value
private data category for every potential PDR. The role-based ac- is seldom used in online social networks because a PDO joins the
cess control (RBAC) has partially solved the problem [7]. In this network for the purpose of sharing data with friends there. The
approach, it is required to define all the potential users’ into some context in Definition 1 refers to the particular situation a permis-
groups. For example, in the UNIX file system, the file owner (user) sion value is assigned. The context includes time context, location
can give each role (user, group, and other users) some specific per- context, and query context (such as purpose, retention, etc.) When
missions (read, write, execute). With the role-based access control, Web data annotation is available in the social network, the annota-
a PDO needs to define the permissions based on the roles of PDRs. tion can also be part of the query context. For each kind of private
But it still may be difficult to define the role of every potential PDR. data, the PDO can define several permission values to fit different
Therefore it will be very nice if a transitive trust relationship exists contexts. A GROUP represents a group of PDOs who share the same
among the potential PDRs. permission value. A group can either be defined by a third party or
It turns out that the transitive relationship does exist in our daily by a PDO. One of the most popular Web-based social networks,
life. For example, if Carl wants to know how much is the toll to Facebook, allows users to create private groups or to join the ex-
travel through the Cross Harbor Tunnel in Hong Kong, he may ask isting regional or alumni networks. Figure 2 shows “my friends”
his friend Bob about it. If Bob does not have the answer, he may and “friends of my friends” relationship on Facebook for one of
continue asking his friends by phone calls or by emails. Later from the authors. We can see that the relationship has been defined be-
Alice, Bob finds out the toll charge and passes the information to tween Facebook users through the profile. When a PDO assigns
Carl. Formally speaking, this transitive query continues until a sat- his friends the permission which can be written in a preference file,
isfactory answer is obtained and returned to the originator along the the network becomes the trust network. The preference file can be
query path. stored as a single document or attached to the private FOAF doc-
When each person who is willing to share data in the community ument [2]. The trust relationship described above only supports
is represented by a vertex, and when how much a PDO trusts a the direct relationship. In the Web calendar application, the tran-
PDR is represented by an edge, the whole community becomes a sitive trust relationship also needs to be considered. Carl, who is
trust network. When users share private data in a community, the not directly connected with Alice, links to Alice through Alice’s
access decision is based on the trust relationship between the PDO colleague Bob. In order to achieve this, we define a new operation
and the PDR in the trust network. JOIN .
D EFINITION 2. T RANSITIVITY determines whether a trust re-
D EFINITION 1. The TRUST relationship between a PDO and lationship can be extended outside of the directly-connected PDRs.
one of its contacts is a permission value assigned by PDO to a A propagated trust (Ptrust) relationship based on transitivity can
potential PDR: be used to extend the relationship to other users. The JOIN opera-
tion shows that the trust relationship is transitive; that is, if PDO
A trusts PDR B, who in turn trusts PDR C, it implies that PDO A
Ptrusts PDR C .
∀a : PDO, i, j : GROUP, c : CONTEXT, ∃interim ∈ i
trust[a, i, c] = p1 , trust[interim, j, c] = p2 ⇒
P trust[a, j, c] = trust[a, i, c] ⊲⊳ trust[interim, j, c] = min(p1 , p2 )
With the JOIN operation, the permission propagates along the
trust network with the maximum possible value. Every potential
PDR can be assigned a permission value automatically if he is
within the community or from a related community. In a real ap-
plication a PDO might set more restricted access. Additional oper-
ations will be proposed in the future.
4. TRUST NETWORK AND OBFUSCATION Figure 3: FaceBook Multiple Relationship Example.
Privacy management is separated into four steps: context prun-
ing, transitive trust network initialization, permission value com-
putation and data obfuscation. The four steps are applied when ap- relationships together to build the trust network. For the example
propriate. In this section, we use the example when Edward sends discussed in 1, after context pruning we know the direct trust rela-
a query on Alice’s “family activities” in the calendar application to tionships form a tree. Figure 4 shows the result after merging all
demonstrate these four steps. direct trust relationship trees of Alice, Bob, Edward and Donald.
4.1 Context Pruning
In a Web-based social network, users are allowed to define a lot
of relationships with other users. For example, in Facebook users
can define every relationship with all friends, such as “We went
to school together” or “We took the course together”. Moreover, a
user can further specify which school and which course to establish
the link between two users. As a result, group definition is quite
complicated. Each PDO might need to define permission values
for an individual person or a group based on different contexts.
The goal for context pruning is that trust relationship only prop-
agates within the same group of people. For example, Alice would
like to share her “work activity” with Bob. But she may not wish to
share the information with Bob’s family doctor, whom Bob trusts
totally. Therefore the trust network should be restricted by context. Figure 4: Trust Network- Transitive Relationship
We zoom in Figure 2 and extract part of the real Facebook network
as shown in Figure 3. The church events in the calendar can be
D EFINITION 3. In a trust network, the hops of a PDR is the
exchanged among all members of this network since all these five
number of vertices to traverse along the shortest path from the PDO
people are from the same church "CBIBC". But the work event is
to this PDR.
just shared between Michelle and Cammy since they “worked to-
gether" and no other user in the network has a similar context. Here Even if the complexity of privacy preference files has been de-
“church” or “work”, which might be an attribute of the event, can creased by using group-based permission assignments, to define the
be considered a context. permission values of every potential PDR is still plenty of work.
Suppose there are two groups of users trusted by a PDO and a With the transitive relationship, a PDO only needs to define the
PDR is in both of the groups. If the PDR requests information permission values of those PDRs who have a “close” relationship,
from the PDO then it might be reasonable for the PDO to provide or are directly connected in the trust network. Based on the privacy
the larger permission value derived from each of the two groups. preferences defined for each of these PDRs, the trust relationship
Another task for context pruning is to find out the maximum per- can be computed and propagated to the rest of the trust network.
mission value for every direct trust relationship on the condition of Since there are various types of private data on the Web, we need
satisfying the context requirement. to consider the data categories, sharing contexts during the trust
In the previous example, during the trip time the travel agent network merging process.
Donald is trusted by Alice based on RECIPIENT “ours”(see the
definition in [21]). For other times, since the query context is not 4.3 Permission Value Computation
satisfied, Donald is not trusted. Note that to apply the transitive relationship, all the trust rela-
tionships during the propagation process need to have the same
4.2 Transitive Trust Network Initialization context. Before computation of the permission value for a PDR,
Even if a PDO defines only a small portion of the whole commu- context pruning will ensure the network initialized in 4.2 is extend-
nity, data can still be shared based on the PDO’s preferences. The able.
users a PDO trusts may also have their own trust relationships (e.g., Algorithm 1 can be applied to implement the JOIN operation in
Donald trusts Edward due to partnership). We need to merge all the order to compute the shortest path from the PDO (source) to a PDR
(destination). Given a social network graph G(V, E), where V is control factors:
the vertices set and E is the trust relationship set. p(u, v) is user v’s
permission value given by user u. Extract_M AX(Q) is used to 1. Maximum propagation hops, hopmax : how many hops pri-
extract the vertex with the maximum permission value which is not vate data can be passed along the network. This is helpful to
in the finished set S. Through Algorithm 1, a user can get the most stop data propagation to PDRs who are too far away.
private data from a PDO based on the permission value assigned.
Algorithm 1 is only one simple and possible solution to compute 2. Damping factor, ̟: How much data is obfuscated through
the permission value. The pageRank [3] or Max-Flow might be every hop. This method gradually reduces the information
used to defined and compute the Ptrust. available and makes sure that an unknown PDR cannot get
too much detailed information through several trustable in-
termediary users.
Algorithm 1 Permission Value Computation
Input:A weighted directed graph G(V,E) Therefore we can replace line 15-18 of Algorithm 1 by:
edge weight, p(u,v), is the permission from u to v
PDO, PDR
Output:Permission Value if min(permission[u], p(u, v)) × ̟ > permission[v]
1: for all vertex v in V do hop[v] ≤ hopmax ∧ u is not PDO then
2: permission[v]=0 permission[v] = min(permission[u], p(u, v)) × ̟
3: previous[v]=undefined previous[v] = u
4: end for end if
5: permission[PDO]= 1
6: S= empty set With the help of hopmax and the damping factor ̟, the private
7: Q= V[G]
8: while Q is not an empty set do data is controlled to spread only within a certain number of hops.
9: u= Extract_MAX(Q) Moreover, the farther a PDR is away from a PDO, the less private
10: if u equals PDR then data he receives. For the previous example, Edward can know Alice
11: return permission[u] is in HKUST without the damping factor. And if the ̟ = 0.7,
12: end if then permission for Edward is 0.42. Edward can only know that
13: S= S union u Alice is in Hong Kong. The permission values might be hard for
14: for all edge (u,v) outgoing from u do
15: if min(permission[u], p(u, v)) > permission[v] PDO to understand. It is helpful to visualize the social network by
then painting users in the network with colors of different shades based
16: permission[v] = min(permission[u], p(u, v)) on the permission values assigned as shown in Figure 8. And it
17: previous[v] = u is also very helpful to assign the critical person, who has lots of
18: end if connection the PDO are not familiar with, a sharp ̟ in order to
19: end for keep the data private.
20: end while
When Algorithm 1 is applied to Figure 4, it first puts Donald
5. FRAMEWORK OVERVIEW
and Bob into the waiting queue Q. Then the Extract_M AX In the Web calendar example, we use the Privacy Server frame-
function extracts Donald from the queue and puts Edward and Un- work as shown in Figure 5. The PDOs define their private data
known1 into Q. Then Bob is extracted and Carl is put into Q, too. through the PDO Preference Manager and store their preferences
The Extract_M AX function processes Unknown1 and Edward in the PDO Preference Database. When there is a data query ini-
in order. When Edward is handled, the algorithm knows Edward’s tiated by a PDR, the Private Data Query Adapter acts as an inter-
permission value. Therefore the trust is propagated from Alice to preter for the query and sets up the trust network based on PDO’s
Donald and finally to Edward. We compute the permission value of preference definition. The data query should include all the context
every potential user (all users except Alice herself), and use a gra- information (e.g., the reason to access the data, how to forward data
dient color to represent the value as shown in Figure 4. The darker to third parties and application user name). With the PDO informa-
the vertex’s color, the higher permission value it holds. We can see tion from Context Database, the Adapter computes the permission
the effects of trust propagation by the changing color shades. value based on PDO’s preference and passes the value to the Ob-
fuscation Manager. A fuzzy result is returned based on applicable
4.4 Data Obfuscation obfuscation rules and the permission value.
There are lots of data items that can be represented in a hierarchi-
cal way. For example, the “current location" is a frequently-used
private data in different applications. Room 4208, Floor 4, HKUST,
Hong Kong, China is a common address to define a location pre- Private Data PDO
Data Query Query Adaptor Preference
cisely. To protect privacy, for some PDRs in some applications, a Database PDO
Preference
PDO may want different information shown on the PDR’s screen. PDR Manager PDO
Obfuscation
Detailed information (room number, etc.) is given to close friends Result
Manager
and general information (Hong Kong) is given to unknown PDRs.
Based on the transitive relationship, the permission value can be Context
Database
used to control the degree of obfuscation for a certain private data
item based on either the default value or the user’s preference.
From Figure 4, we see that when the trust network becomes com- Figure 5: Privacy Server Implementation Framework
plex it is quite possible for an unknown PDR to obtain private data
after several data passing actions. In order to make sure the pri- A trust network is set up based on the transitive relationship de-
vate data passing scale is controllable, a PDO needs to set up some fined by each PDO, which is derived from the online community
information. Users in a whole community who are willing to share
private data become vertices in the network while the trust relation-
ship between each other becomes edges. The strength of the trust
relationship becomes private date permission value which denotes
the edge weight in the trust network. Since the trust relationship
is asymmetric, the whole trust network is a directed graph. When
there is a private data query, the problem becomes the checking
of whether there is a path from a vertex (PDO) to another vertex
(PDR) in a directed graph.
After the permission value is obtained, the Obfuscation Manager
blurs the private data according to the value and still returns some
information to the PDR (unless the permission value is zero, indi-
cating that the PDR is forbidden from accessing the data). Context
data can often be represented in many ways and forms. For ex-
ample, the location context can be represented at a particular point
geographically, or in regions of various sizes which contain that
point. Alice’s location, in the previous example, could be repre-
sented as , (a) Random Permission Value Assignment
showing that Alice’s location information at a certain time is one of
Cross Harbor Tunnel, Hong Kong and China depending on the per-
mission value. The Obfuscation Manager returns different results
for different queries based on the relationship between the PDO
and the PDR.
The transitive relationship and obfuscation rules break the cur-
rent binary private data access characteristic and make context shar-
ing easier. We modify the Web calendar component, JEvent, and
build the Privacy Management Framework for it as shown in Figure
1. Figure 1(a) is the original JEvent service. Users are allowed to
check all the detailed calendar information by clicking on the event.
With the privacy management as shown in Figure 1(b) only the reg-
istered users can check the calendar and the “Family activities” is
not available based on the data category the calendar owner (PDO)
has defined. The successful hacking of the code for JEvent shows
that the transitive trust relationship does work in a real application.
This framework is not specially defined for the Web calendar;
other applications can also connect to the Privacy Server through (b) Assign High Permission value for Relationship
an HTTP connection for the current CGI version.
Figure 6: Transitive Network Efficiency
6. EXPERIMENT
6.1 General Characteristics of the Trust Net- than random assignments in the range of [0,1). By changing the
work range to [0.6,1), the results are shown in Figure 6(b). Compare
Figure 6(a) and Figure 6(b), we see that the colors in Figure 6(b)
Our study is focused on the “trust network” where edge (u, v)
are darker, which means that the permission values are higher after
means u trusts v with a labeled permission value. There are lots of
trust propagation when higher permission values are assigned ini-
online communities available currently, such as MSN, Facebook,
tially. Therefore the permission values defined by PDOs are indeed
Blogger, etc. We picked MSN due to its popularity to test the imple-
affecting the private data propagation process.
mentation of permission value assignment scheme. Starting from
one of the authors’ friends who posts her friends list on the Web1 ,
we used a crawler to trace the friends lists. We visited 187 users
6.2 Control Factors
who are connected with the friend within four hops and obtained Figure 6 demonstrates that it is possible to construct a trust net-
other 1,181 related users. None is more than four hops away from work from an existing social network for managed data sharing,
the friend. Since there was no permission value currently supported if the social network supports the setting of permission levels. We
by MSN, we randomly assigned different permission values for ev- then explore how a PDO can control the transitive relationship with
ery relationship. partial trust.
Figure 6 contains the trust propagation results after we randomly The maximum number of hops hopmax can be set by a PDO
assigned permission values using Math.random (range [0,1)). The in order to control how far the private data can be forwarded. We
permission values became very small after four hops as shown in again use the MSN social network as a test base. We randomly
Figure 6(a), since most peripheral nodes are in light color. If these assigned permission values to every trust relationship and then kept
peripheral nodes wish to see the central node’s information, their this directed graph unchanged in the following experiment.
requests will not be successful. Since friend lists on MSN are de- When no transitive relationship was allowed (hopmax = 0),
fined by the users manually, the trust relationships should be higher 1,350 queries got no permission during data sharing in Figure 7(a).
When the transitive relationship was allowed, the non-empty query
1
MSN URL:http://rp20040619.spaces.live/friends number was dramatically increased when hopmax = 3. This is
because there are few users on the first one or two hops of the trust ⇀ Unknown3. However, Unknown3 is directly defined in Alice’s
network. The bigger hopmax was, the more detailed result could trust tree with permission value 0.4 (green line). There is now a
be obtained. Moreover, we noted that blanket permission was not conflict between the direct trust and trust derived from transitive
granted since only a small number of queries could get access to relationships. Since trust based on multiple recommendations from
the private data. We can also see that even if the friend has only a single source should not be higher than that from independent
defined three close friends, if she allows three hops of data sharing, sources, if the PDR is one of the directly-connected vertices with
then around 700 users can see her obfuscated data. the PDO then the permission for this PDR cannot be higher than
the permission value originally assigned by the PDO.
1400
permission=0
1200 permission=0.2
permission=0.4
permission=0.6
1000
permission=0.8
Number of Users
permission=1
800
600
400
200
0
0 1 2 3 4
Maximum Trust Propatation Hops
(a) Max Hop Number Affects Permission
1400
permission=0
permission=0.2
1200 permission=0.4
permission=0.6
Figure 8: Trust Priority: Directed vs. Transitive
1000 permission=0.8
permission=1
Number of Users
800
600
7.2 Standardized Private Data Levels
It is often hard for users to assign accurate decimal permission
400
values to others. Therefore, we should provide a visualization of
200
the data. The user can directly select the data level they would like
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 to share and the program can easily convert the level into a decimal
Damping Factor
number.
(b) Damping Factor Affects Permission
Figure 7: Control Factors
Figure 7(b) demonstrates how the damping factor discussed in
section 4.4 affected the permission value. If the damping factor
̟ is zero, it meant that there was no transitive relationship. If
̟ is very small (e.g., 0.1 or 0.2), it strongly restricted the access The levels of a private data item are either defined by a PDO
permission of private data. Even when ̟ became 0.6, most users or by a public ontology. Then different PDOs might have different
got permission value less than 0.2. When ̟ became bigger, the data levels in real applications. For example, Alice defines her loca-
influence of ̟ significantly affected the permission value to access tion in 5 levels, such as “Room 4208, Floor 4, HKUST, Hong Kong,
private data. China". Her secretary only uses “HKUST, Hong Kong, China”.
We understand that the number of users who get permission might When the secretary grants Bob with permission value 0.67, Bob
be different due to different social network topologies. For exam- can only know “Hong Kong”. If Alice gives a 0.8 permission value
ple, if the PDO defines a lot of close friends, there will be a num- to her secretary, then with the transitive relationship Bob gets 0.67
ber of users who get permission to access private data even when (the maximum of 0.8 and 0.67) permission value and consequently
hopmax = 0,. The selection of ̟ and hopmax will indeed affect a more specific area name (HKUST) of Alice’s location. This could
the topology of the trust network. But the trend of trust propagation be a big privacy hole.
will not change too much. In practice the damping factor should be A possible solution is that for each category a standardized pri-
used with maximum hop number together in order to achieve the vate context data level is set up and shared by all PDOs through a
desired access control. Moreover, the PDO can set up different separate central information directory which provides all kinds of
damping factors to different groups or specific users if he wishes. information level descriptions. The PDO Preference Manager con-
nects to that directory and automatically helps users to search what
other preferences the PDO has defined. Initially, there are only a
7. DISCUSSIONS few default levels for the data. When a PDO wants to have more
specific context levels, he can insert a level himself and record the
7.1 Trust Priority new level in the central information directory. For example, if Al-
In a trust network, it is possible that a PDR may obtain more ice wants to identify the current building as a new context level,
private data through transitive relationships. For example Figure 8 she finds that this information is between the floor information and
is the result after running Algorithm 1. The gray line represents the area name. Alice can then insert the building name between
the trust propagation path when Unknown3 queries Alice’s infor- them and set the permission value for this new context level to be
mation. Through a full transitive relationship, Unknown3 can get ( 0.6+0.8
2
= 0.7). When other PDOs define their location informa-
0.6 permission value through the path: Alice ⇀ Donald ⇀ Edward tion, this new level can also be used by them. Since the permission
value is a decimal number between 0 and 1, an infinite number of the Fourth Workshop on Deception, Fraud and Trust in Agent
context levels can be supported. Another advantage of using stan- Societies 2001, pages 27–34, 2001.
dard levels is that a PDO can see and directly choose the informa- [7] D. F. Ferraiolo, J. F. Barkley, and D. R. Kuhn. A role-based
tion level he wishes to share with other users instead of assigning a access control model and reference implementation within a
corporate intranet. ACM Transactions on Information and
permission value which may not be meaningful to the PDO. System Security, 2(1):34–64, 1999.
[8] L. Garton, C. Haythornthwaite, and B. Wellman. Studying
7.3 Other Applications online social networks. Journal of Computer-Mediated
With the development of ubiquitous computing, more and more Communication, 3(1), June 1997.
private data is available to the public either on the Web or through [9] Google. Google calendar. www.google.com/calendar.
other applications. For example, a mobile service provider has al- [10] R. Guha, R. Kumar, P. Raghavan, and A. Tomkins.
ready started friend location service. Users can dial a special num- Propagation of trust and distrust. In WWW ’04: Proceedings
ber to trace friends’ location. Users might lose privacy control in of the 13th international conference on World Wide Web,
pages 403–412, New York, NY, USA, 2004. ACM Press.
that situation because he may not know what information about
[11] A. Y. Halevy, A. Rajaraman, and J. J. Ordille. Data
him is shared, compared with the social network situation that the integration: The teenage years. In VLDB, pages 9–16, 2006.
user is the publisher of his own data on the Web. It is possible that [12] D. Hong, M. Yuan, and V. Y. Shen. Dynamic privacy
through such a service, a thief can find out a user’s regular sched- management: a plug-in service for the middleware in
ule, such as the time to go home, by tracking the user’s location for pervasive computing. In MobileHCI 2005, pages 1–8,
a period of time before breaking into his home when he is not there. Salzburg, Austria, September 2005. ACM.
The convenience of ubiquitous computing applications will not be [13] S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The
enjoyed unless users can control what private data to share with eigentrust algorithm for reputation management in p2p
networks. In WWW ’03: Proceedings of the 12th
whom at what time. Our privacy server framework can be helpful international conference on World Wide Web, pages
in these applications. 640–651, New York, NY, USA, 2003. ACM Press.
[14] Y. Katz and J. Golbeck. Using social network-based trust for
8. CONCLUSIONS AND FUTURE WORK default reasoning on the web. Submitted to Journal of Web
Semantics, 2007.
In this paper we propose a transitive trust network for private [15] P. Kolari, L. Ding, S. G. A. Joshi, T. Finin, and L. Kagal.
data sharing in social networks. Private information can be shared Enhancing web privacy protection through declarative
through the trust network. We use a Web calendar application to policies. In POLICY ’05: Proceedings of the Sixth IEEE
show the process of using trust network algorithms to share data. International Workshop on Policies for Distributed Systems
We finally demonstrate the feasibility of constructing the trust net- and Networks (POLICY’05), pages 57–66, Washington, DC,
USA, 2005. IEEE Computer Society.
work from an existing social network. The characteristics of such
[16] R. Matthew, R. Agrawal, and P. Domingos. Trust
a trust network are analyzed which may be applied to data shar- management for the semantic web. In Proceedings of the
ing in ubiquitous computing environments. We plan to launch the Second International Semantic Web Conference, 2003.
Web calendar service with trust network and collect data for further [17] M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new casper:
development. We shall also develop plug-ins and propose to own- Query processing for location services without
ers of social networks that users be allowed to use them to assign compromising privacy. In VLDB, pages 763–774, 2006.
permission values to their contacts. [18] L. Sweeney. k-anonymity: a model for protecting privacy.
International Journal on Uncertainty, Fuzziness and
Knowledge-based Systems, 10(5):557–570, 2002.
Acknowledgement [19] Technorati. State of the blogosphere / state of the live web.
This research is supported in part by Hong Kong Research Grant http://www.sifry.com/stateoftheliveweb/, 2007.
Council Project 619507. [20] W3C. A p3p preference exchange language 1.0 (appel1.0).
http://www.w3.org/TR/P3P-preferences/.
[21] W3C. Platform for privacy preferences (p3p) project.
9. REFERENCES http://www.w3.org/TR/P3P/, April 2002.
[1] N. R. Adam and J. C. Worthmann. Security-control methods [22] S. Wasserman and K. Faust. Social Network Analysis :
for statistical databases: a comparative study. ACM Methods and Applications (Structural Analysis in the Social
Computing Survey, 21(4):515–556, 1989. Sciences). Cambridge University Press, 1994.
[2] D. Brickley and L. Miller. Foaf project. [23] C.-N. Ziegler and G. Lausen. Analyzing correlation between
http://www.foaf-project.org/, 2007. trust and user similarity in online communities. In C. Jensen,
[3] S. Brin and L. Page. The anatomy of a large-scale S. Poslad, and T. Dimitrakos, editors, Proceedings of the 2nd
hypertextual web search engine. In WWW7: Proceedings of International Conference on Trust Management, volume
the seventh international conference on World Wide Web 7, 2995 of LNCS, pages 251–265, Oxford, UK, March 2004.
pages 107–117, Amsterdam, The Netherlands, The Springer-Verlag.
Netherlands, 1998. Elsevier Science Publishers B. V. [24] C.-N. Ziegler and G. Lausen. Spreading activation models
[4] J.-W. Byun, E. Bertino, and N. Li. Purpose based access for trust propagation. In EEE ’04: Proceedings of the 2004
control of complex data for privacy protection. In SACMAT IEEE International Conference on e-Technology,
’05: Proceedings of the tenth ACM symposium on Access e-Commerce and e-Service (EEE’04), pages 83–97,
control models and technologies, pages 102–110, New York, Washington, DC, USA, 2004. IEEE Computer Society.
NY, USA, 2005. ACM Press. [25] C.-N. Ziegler and G. Lausen. Spreading activation models
[5] M. Conrad, T. French, W. Huang, and C. Maple. A for trust propagation. In EEE ’04: Proceedings of the 2004
lightweight model of trust propagation in a multi-client IEEE International Conference on e-Technology,
network environment: To what extent does experience e-Commerce and e-Service (EEE’04), pages 83–97,
matter? In ARES ’06: Proceedings of the First International Washington, DC, USA, 2004. IEEE Computer Society.
Conference on Availability, Reliability and Security
(ARES’06), pages 482–487. IEEE Computer Society, 2006.
[6] B. Esfandiari and S. Chandrasekharan. On how agents make
friends: mechanisms for trust acquisition. In Proceedings of