# The Power of Indirect Social Ties

Xiang Zuo Jeremy Blackburn  Comp. Science & Eng.
University of South Florida
Tampa, Florida 33620
{xiangzuo<EMAIL_ADDRESS>Nicolas Kourtellis  Yahoo Labs
Barcelona, Spain
<EMAIL_ADDRESS>John Skvoretz  Sociology Department
University of South Florida
Tampa, Florida 33620
<EMAIL_ADDRESS>Adriana Iamnitchi  Comp. Science & Eng.
University of South Florida
Tampa, Florida 33620
<EMAIL_ADDRESS>
###### Abstract

While direct social ties have been intensely studied in the context of
computer-mediated social networks, indirect ties (e.g., friends of friends)
have seen little attention. Yet in real life, we often rely on friends of our
friends for recommendations (of good doctors, good schools, or good
babysitters), for introduction to a new job opportunity, and for many other
occasional needs. In this work we attempt to 1) quantify the strength of
indirect social ties, 2) validate it, and 3) empirically demonstrate its
usefulness for distributed applications on two examples.

We quantify social strength of indirect ties using a(ny) measure of the
strength of the direct ties that connect two people and the intuition provided
by the sociology literature. We validate the proposed metric experimentally by
comparing correlations with other direct social tie evaluators. We show via
data-driven experiments that the proposed metric for social strength can be
used successfully for social applications. Specifically, we show that it
alleviates known problems in friend-to-friend storage systems by addressing
two previously documented shortcomings: reduced set of storage candidates and
data availability correlations. We also show that it can be used for
predicting the effects of a social diffusion with an accuracy of up to 93.5%.

##  I Introduction

The mining of the huge corpus of social data now available in digital format
led to significant advances of our understanding of social relationships [1]
and social behavior [2], and confirmed on larger datasets long standing
results from sociology. In addition, social information (mainly relating
people via declared relationships on online social networks or via computer-
mediated interactions) has been successfully used for a variety of
applications, from spam filtering [3] to recommendations [4] and peer-to-peer
backup systems [5].

All these efforts, however, focused typically on direct ties. Direct social
ties (that is, who is directly connected to whom in the social graph) are
natural to observe and reasonably easy to classify as strong or weak [6, 7].
Indirect social ties, though, defined as a relationship between two
individuals who have no direct relation but are connected through a third
person in their social network [8], carry a significantly larger potential as
they facilitate better information dissemination then direct ties [9] and
enable significantly better opportunities [10]. Computer-mediated
applications, we conjecture, have a more significant potential in mining and
exploiting indirect ties, as the direct ties are likely to be used via the
traditional channels through which were used for thousands of years: hopefully
people will continue to talk to friends about needs and opportunities without
totally relying on online social applications.

However, not all indirect ties are valuable or usable, even at short distances
(i.e., 2 hops). For example, a distant acquaintance of a mere acquaintance is
unlikely to have the social incentives of doing a personal favor, such as
sharing his available storage on his personal computer. Moreover, the trust is
possibly too diluted in such conditions: why would that weak distant social
contact trust that the data he is asked to store is not illegal or malicious?
In addition, what works for a user or an application might not work for
another user or another application: the indirect tie $A$–$B$ may be strong
enough for $A$ to use, but not enough for $B$ to use; or it may be strong
enough to use for a backup application, but not for a distributed social
clustering application. Therefore, quantifying the strength of an indirect tie
is both necessary and non-trivial.

In this paper we propose a metric that we call _social strength_ that
numerically estimates the strength of an _indirect_ tie (Section III). Our
metric uses various observations from sociology and builds on the current
opportunities of quantifying the strength of direct ties from computer or
phone-recorded interactions. We rely on the sociology literature to define the
requirements of such a metric: first, since social relationships are
asymmetrically reciprocal [11], the social strength of an indirect tie
consequently needs to be asymmetrical as well. Second, a friend of many of
one’s friends—thus connected via multiple 2-hop paths—can potentially be more
socially “close” than the friend of a friend, connected via only one 2-hop
path. Third, the strength of an indirect tie decreases with the length of the
shortest path [12].

We partially validate the social strength metric of indirect ties (in Section
IV) using real datasets. We demonstrate the usefulness of our metric on two
proof-of-concept applications: the recruitment of storage candidates from
indirect social ties (Section V) and the prediction of information
dissemination paths (Section VI). We show experimentally that two main issues
identified in friend-to-friend storage systems, namely reduced candidate sets
[5] and low availability due to time synchronization among friends [13], are
significantly alleviated by employing our social strength metric for the
recruitment of socially close indirect contacts. Specifically, online
availability of storage resources are improved by up to 20%. We also show that
the social strength metric predicts with an accuracy of up to 93.5% diffusion
paths 2-3 steps ahead to provide more time for decision makers for containing
damaging information dissemination (i.e., damaging rumors) or accelerating
information spreading.

##  II Related Work

Since Granovetter [9] introduced the notion of strength of ties in social
networks, there have been many studies on tie strength measurement. Common
Neighbors [14] is a measure of tie strength that considers the number of
common activities or friends that two users share. Jaccard index [15] was
shown to estimate the number of phone calls between two users by considering
their shared neighborhoods [16].

Homophily, or similarity between individuals, has been shown to be a catalyst
for the formation of relationships [17] and has been leveraged to predict the
existence and strength of social ties. Gilbert and Karahalios [7] modeled tie
strength as a combination of social dimensions such as intensity, intimacy,
duration, and structure. Crandall et al. [18] investigated the existence of
social ties between people from co-occurrence in time and space on Flickr and
discovered that even a small number of co-occurrences indicate a high
probability of an existing tie between two users. Likewise, Kahanda and
Neville [6] developed a supervised learning predictor that classifies a link
in OSNs as either a weak or strong tie via features from user profiles, graph
topology, transactional connectivity and network-transactional connectivity
features. Adamic and Adar [19] introduced a log-based similarity metric to
capture tie strength between indirectly connected nodes.

However, these methods either need extra information—such as users’ profiles,
the message content or users’ geo-locations—or adopt complex models that
cannot be implemented in a decentralized fashion. More importantly, most
previous methodologies simply treat users’ relationships symmetrically.
Without asymmetric discrimination, it is difficult to accurately capture the
strength of social ties [20].

This work builds on our preliminary definitions [21, 22] of social strength
metric but significantly changes them by introducing new lessons from
sociology. Most importantly, this work contributes the validation of the
social metric and demonstrates its value via proof-of-concepts applications
that use it.

##  III Social Strength Definition

We want to define a metric that quantifies the intensity of a social
connection between indirectly connected nodes in a social network. The need
for such a metric is intuitively supported by many sociological studies and is
also well understood from daily life: friends of friends are an important
resource for information and useful social contacts.

In our attempt to quantify an indirect social tie, we use the following
observations from sociology and from recent data-driven studies on computer-
mediated social relationships:

  * O1:

The strength of a direct social relationship is influenced by the amount of
interactions, as confirmed in [9, 23]. Moreover, interactions among OSN users
were shown to represent more meaningful relations than just declared
relationships [24]. Consequently, in the quantification of an indirect social
tie, we rely on a numerical representation of the strength of a _direct_
social tie, that can be expressed as number of interactions, number of shared
interests, or other recordable outcomes, depending on the semantic of the
relationship.

  * O2:

Intuitively, the social strength of an indirect relationship on a particular
social path is limited by the strength of the weakest direct tie on that path.
Furthermore, the strength of an indirect tie decreases with the length of the
shortest path between the two individuals. This has been qualitatively
observed by Friedkin [12], who concluded that the horizon of observability is
limited to a distance of 2 hops. Without contradicting this result, in this
work we propose that instead of limiting indirect social ties to a distance of
2, we allow the calculation of social strength along longer distances, but
decrease its value as a function of distance.

  * O3:

Multiple types of social interactions (for example, both professional
collaboration and playing tennis after work) result into a stronger (direct)
relationship than only one type of interaction [25]. Furthermore, sociology
studies [12] observed that the relationship strength of indirectly connected
individuals greatly depends on the number of different direct or indirect
paths connecting them. Therefore, we consider the strength of multiple
shortest paths in our definition of the strength of an indirect social tie.

  * O4:

Typically, social ties between individuals are asymmetrically reciprocal [11].
Thus, for the directly connected users Alice and Bob, the importance of their
mutual relationship may be dramatically different. Different experiences,
psychological backgrounds and personal histories cause these asymmetries [26].
We want to preserve this asymmetry in quantifying indirect ties, such that
Alice and Charlie, indirectly connected via Bob, are entitled to have
different views about their indirect tie.

Therefore, to quantify the social strength of an indirect social tie between
users $i$ and $m$ we consider relationships at any $n$ ($n\geq 2$) social
hops, where $n$ is the shortest path between $i$ and $m$. We assume a weighted
interaction graph model that connects users with edges weighted based on the
intensity of their direct social interactions. Assuming that
$\mathcal{P}_{i,m}^{n}$ is the set of different shortest paths of length $n$
joining two indirectly connected users $i$ and $m$ and $\mathcal{N}(p)$ is the
set of nodes on the shortest path $p,p\in\mathcal{P}_{i,m}^{n}$, we define the
social strength between $i$ and $m$ from $i$’s perspective over an $n$-hop
shortest path as:

$SS_{n}(i,m)=1-\prod_{p\in\mathcal{P}_{i,m}^{n}}(1-\frac{\min\limits_{j,...,k\in\mathcal{N}(p)}{[NW(i,j),...,NW(k,m)]}}{n})$
(1)

This definition uses the normalized direct social weight $NW(i,j)$ between two
directly connected users $i$ and $j$, defined as follows:

$NW(i,j)=\frac{\sum_{\forall\lambda\in\Lambda_{i,j}}\omega(i,j,\lambda)}{\sum_{\forall
k\in N_{i}}\sum_{\forall\lambda\in\Lambda_{i,k}}\omega(i,k,\lambda)}$ (2)

Equation 2 calculates the strength of a direct relationship by considering all
types of interactions $\lambda\in\Lambda$ between the users $i$ and $j$ such
as, let’s say, phone calls, interactions in online games, and similar ratings
on Netflix (observation O3). These interactions are normalized to the total
amount of interactions of type $\lambda$ that $i$ has with other individuals.
This approach ensures the asymmetry of social weight (observation O4) in two
ways: first, it captures the cases where
$\omega(i,j,\lambda)\neq\omega(j,i,\lambda)$ (such as in a phone call graph).
Second, by normalizing to the number of interactions within one’s own social
circle, the relative weight of the mutual tie will be different for the two
users involved even in undirected social graphs (that is, when
$\omega(i,j,\lambda)=\omega(j,i,\lambda)$).

The implementation of observations O1, O3 and O4 in the definition of the $NW$
function is naturally carried over in the definition of social strength from
Eq. 1. Moreover, O3 is additionally implemented by considering the product
over all shortest paths $p$ that connect two users. O2 is implemented by
considering the weakest link (minimum normalized weight of all direct ties on
each path) and by dividing it with the distance $n$ between the users.

The proposed social strength measure can:

  * $\bullet$

Quantify the indirect tie strength for nodes indirectly connected at any
social distance.

  * $\bullet$

Treat indirect ties between two nodes as possibly asymmetric in strength
rather than constraining the values to be equal.

  * $\bullet$

Be more sensitive to strength differences because it uses both edge weights
and number of paths to calculate a value.

  * $\bullet$

Be calculated locally and so implemented on very large graphs in parallel
easily.

##  IV Social Strength Verification

Studies show that interviews meant to quantify the strength or even the
existence of social relationships are unreliable [27], as subjects do not
accurately recall [28] or are unable to objectively asses their social
relationships. To verify the social strength metric proposed in Secion III, we
thus chose to quantitatively compare social strength with other metrics, even
when the comparison can be done on a limited domain. We identified two such
metrics of relevance: the overlap of the social neighborhoods and the
frequency of interactions in online social networks. However, both have
limited applicability: The overlap of social neighborhoods is possibly non-
empty only for nodes at distance at most 2. The frequency of interaction is by
definition only possible for direct social interactions, thus directly
connected nodes.

The strength of a relationship between two nodes in a social graph was shown
to correlate with the overlap of their social neighborhoods in various
studies. Intuitively, the more friends in common, the closer the relationship
between two subjects. This hypothesis was verified at scale by studying a who-
talks-to-whom real-world mobile phone network [16], and demonstrating that
neighborhood overlap increases with increasing tie strength.

Interaction graphs were shown to provide more accurate representation of
social ties than just the existence of declared relationships in OSNs [29,
24]. As social interactions always require some kind of investment of time and
effort from participants, the frequency of interaction is an informative
measure of tie strength. Gilbert et al. [7] classified tie strengths according
to users’ attributes on social media such as intimacy and interaction
intensity. Likewise, Marlow et at. [30] investigated users’ tweet and retweet
interactions on Twitter to distinguish a user’s strong ties from weak ties
over an observation period.

Thus, both the neighborhoods overlap and the frequency of interactions between
two users are considered quantifiers of social ties. In this section, we
compare our proposed social strength metric with these two accepted metrics.

###  IV-A Datasets

We used three social networks for the validation of the social strength metric
and for the rest of the experimental evaluations in this paper. The first two
(CA-I and CA-II) are co-authorship networks from ArnetMiner [31] and the third
(TF2) is derived from gameplay logs from a Team Fortress 2 online gaming
server.

ArnetMiner mines the academic social network to provide domain-specific search
services for researchers. From this service, Tang et. al [32] extracted a
weighted co-authorship graph of Computer Science researchers from a variety of
domains. Nodes in this graph represent authors and are labeled with the
author’s affiliation. Edges exist if the two researchers co-authored at least
one paper together and are weighted with the number of papers co-authored. The
dataset also provides the authors’ affiliations. From this dataset we
extracted two networks: _Co-authorship I (CA-I)_ is a small connected
component with 348 nodes and a relatively low density (see Table I). _Co-
authorship II (CA-II)_ is the largest connected component of the ArnetMiner
co-authorship network, comprising 1,127 nodes and having a density one order
of magnitude higher than CA-I.

Team Fortress 2 is an objective-oriented first person shooter game released in
2007. We obtained just over 10 months of gameplay traces (from April 1, 2011
to February 3, 2012) from a Team Fortress 2 server located in Los Angeles,
California [33]. The logs include game-based interactions among players, such
as teammates capturing territory together, or players from opposing teams
“killing” each other. In addition, we crawled the _Steam Community_ online
social network [34] and obtained the set of friends for each player in the
server logs [35]. We were able to tie a player on the server to an OSN profile
because Team Fortress 2 uses the Steam gaming platform, which includes Steam
Community, among other gaming specific services. The _Team Fortress 2
interacting friends network (TF2)_ is composed of edges between players who
had at least one in-game interaction while playing together on this particular
server, and also have a declared friendship in Steam Community. This dataset
has two advantages over the Steam declared OSN: First, it provides the number
of in-game interactions that quantifies the strength of a declared social tie.
Second, it provides players’ online/offline status that we use later in the
experiments in Section V. Over a pure in-game interaction network, it provides
the advantage of selecting the most representative social ties, as proven in
[33]. In this network of 2,406 nodes and over 9,000 edges, edge weights thus
represent the number of in-game interactions.

TABLE I: Characteristics of the social networks used in experiments. Networks | # Nodes | # Edges | Avg. Path Length | Density | Clustering Coef. | Assort. | Diam. | Range edge weights
---|---|---|---|---|---|---|---|---
CA-I | 348 | 595 | 6.1 | 0.0098 | 0.28 | 0.173 | 14 | [1–52]
CA-II | 1,127 | 6,690 | 3.4 | 0.0100 | 0.33 | 0.211 | 11 | [1–127]
TF2 | 2,406 | 9,720 | 4.2 | 0.0034 | 0.21 | 0.028 | 12 | [1–21,767]
Figure 1:  CDF of the three networks’ degree, weight and clustering
coefficient distributions. Edge weight distributions are normalized to allow
for comparison among the three networks.

A brief characterization of the networks appears in Table I. Figure 1 plots
the degree, edge weight, and clustering coefficient distributions for each of
our networks. In order to compare the weight distribution between different
networks, we normalized all edge weights by dividing them to the largest edge
weight in the corresponding network.

###  IV-B Social Strength vs. Neighborhood Overlap

The overlap between the social neighborhoods of two users $s$ and $r$ can be
represented by the Jaccard coefficient defined as follows:

$JC(s,r)=\frac{n_{sr}}{degree(s)+degree(r)-n_{sr}}$ (3)

where $n_{sr}$ is the number of mutual neighbors of nodes $s$ and $r$, and
$degree(s)$ and $degree(r)$ are the number of edges of nodes $s$ and $r$,
respectively.

There are some immediate observations: $JC(s,r)$ is symmetrical, that is,
$JC(s,r)=JC(r,s)$. Also, $JC(s,r)=0$ for all nodes $s$ and $r$ situated in the
network at a distance larger than 2 hops. Meanwhile, social strength is used
for quantifying the strength of indirect social ties of at least 2 hops
distance in the social graph. Therefore, for a meaningful comparison between
$JC(s,r)$ and the social strength between the same nodes $s$ and $r$,
$SS_{n}(s,r)$, we select only those nodes $s$ and $r$ for which $n=2$.

Table II shows the Pearson correlation coefficient between $JC(s,r)$ and
$S_{2}(s,r)$ for all pairs of nodes $(s,r)$ situated at distance 2 in the
social graphs (all p-values $\leq 2.2\times 10^{-16}$). All three datasets
present positive correlations. In the CA-II network the correlation is the
highest ($0.41$), while TF2 shows only a weak positive correlation. Because
TF2 is extracted from an online gaming social network, players establish
connections according to their gaming interests or to the requirements of the
game, rather than according to genuine social phenomena. For example, many
players add others as their social connections to satisfy the minimum number
of participants required for playing the game, but end up having few
interactions. Thus, in this scenario, the overlap of neighborhoods may not
accurately capture meaningful social ties without considering the frequency of
users interactions.

In contrast, social strength evaluates social closeness by including both
shared paths and interactions between users, which calibrates social ties more
meaningfully.

TABLE II: Pearson correlation coefficients (PC) between the Jaccard coefficient and social strength over 2-hop paths. Networks | PC(JC, $SS_{2}$)
---|---
CA-I | 0.255
CA-II | 0.410
TF2 | 0.137

###  IV-C Social Strength vs. Number of Interactions

A common measure of the strength of a direct social tie is the
number/frequency/duration of interactions [9, 36]. In order to compare social
strength (a measure of the strength of an indirect social tie) with the
strength of a direct tie as given by the number of direct social interactions,
we do the following: for closed triads in the social graph (such as depicted
in Figure 2(a)), we calculate the correlation between the social strength of
$A$ and $B$ along the path $A-C-B$ by ignoring the direct tie $A-B$ (as
depicted in Figure 2(b)) and the number of interactions between $A$ and $B$.
Because the overlap of the social neighborhoods of directly connected nodes
$A$ and $B$ is also a measure of the intensity of the social tie [16], we also
include the Jaccard coefficient of the direct tie $A-B$ in our comparison.
(Note that this time we apply the Jaccard coefficient to direct ties, not to
2-hop distant nodes, as in the previous section).

(a)

(b)

(c)

(d)

Figure 2: Using 2-hop social strength metrics to infer 1-hop social strength
values: (a) original graph (b) remaining graph after removing edge AB (c)
graph without 2-hop length paths (d) graph with only one shared edge between A
and B.

The intuition for this experiment is the following: if the social strength
metric indeed captures the strength of an indirect tie between $A$ and $B$,
then this metric should correlate with measures of strength on the direct tie
$A-B$. In Table III, column 2 to 4 present the Pearson correlation among the
number of direct interactions, 1-hop Jaccard coefficient, and the social
strength value along n-hop (n is the shortest path length) paths for pairs of
directly connected users. The results show that all correlations are positive
(with p-values $\leq 8.8\times 10^{-8}$). Moreover, it results that social
strength is a better predictor of the intensity of a social relationship than
the Jaccard index: social strength has higher positive correlation with edge
weights than the Jaccard coefficient in all three datasets, with the highest
positive correlation value in the CA-II network. This result is mainly due to
the fact that the Jaccard coefficient metric does not takes edge weights into
consideration, while social strength considers both edge weights and shared
paths for quantifying users’ social closeness.

However, removing edges such as $A$–$B$ could lead to situations such as those
in Figures 2(c) and 2(d), where $A$ and $B$ get disconnected or remain
connected by shortest path of 3 or more. In the case of Figure 2(c), the
Jaccard coefficient becomes $0$ while the social strength can still be
computed as $SS_{3}(A,B)$ along the path $A$–$C$–$D$–$B$. In the case of
Figure 2(d), both social strength and the Jaccard coefficient become $0$,
which might bias the results. Column 5 to 7 in Table III present the
correlations among the three metrics after removing all such zero values in
each dataset (all p-values $\leq 0.01$). The percentage of removed data is
presented in the 8th column. Even in this case when we remove all the special
zero values and re-calculate the Pearson coefficient, social strength values
rarely change and have higher correlation with edge weights than the Jaccard
coefficient has.

TABLE III: Pearson coefficient (PC) among edge weights, Jaccard coefficient and the social strength over 1-hop paths and the same correlations by removing zeros in special cases. Networks | PC(weight, JC) | PC(weight, $SS_{1}$) | PC(JC, $SS_{1}$) | PC_nonzero(weight, JC) | PC_nonzero(weight, $SS_{1}$) | PC_nonzero(JC, $SS_{1}$) | % of Removed Zeros
---|---|---|---|---|---|---|---
CA-I | 0.179 | 0.238 | 0.655 | 0.173 | 0.244 | 0.530 | 24.7%
CA-II | 0.211 | 0.394 | 0.591 | 0.210 | 0.396 | 0.580 | 2%
TF2 | 0.173 | 0.267 | 0.554 | 0.135 | 0.245 | 0.492 | 13.2%

To conclude, the above experiments show that our definition of social strength
$SS_{n}$ among indirectly connected individuals in a social graph is
positively correlated to both neighborhood overlaps and the frequency of
interactions. Consequently, since the neighborhood overlap and the frequency
of interactions are considered to accurately estimate the strength of social
ties, then $SS_{n}$ can also be used for indicating the closeness of social
relationships among people. The difference is that the neighborhood overlap
and the frequency of interactions are limited to quantifying the intensity of
direct or at most 2-hop away social ties, while the social strength can
estimate the intensity of ties between people who are n-hop distant in the
social graph.

##  V Using Social Strength in Friend-to-Friend Storage Systems

A Friend-to-Friend (F2F) storage system is a distributed system where users
use incentives to get access to the available storage resources or services of
their friends’ machines. While a promising alternative to cloud-based data
backup, F2F storage systems were shown to suffer from two significant
limitations. First, users with a small set of friends are penalized by lack of
available storage for their needs [5]. Second, friends are typically in close
geographical proximity, and thus their online times are synchronized, leading
to high unavailability to their friends’ data [13]. These concerns can
intuitively be addressed by leveraging social strength $SS_{n}$ (where $n\geq
2$) to expand the set of storage resources while still using a measure of
social incentives.

In this section we verify whether $SS_{n}$ can improve the service performance
in F2F storage systems. To maintain a meaningful value of social incentives,
we restrict our evaluations to $n=2$ and $n=3$. Our objectives are:

  * $\bullet$

To understand if $SS_{n}$ expands the size of candidate sets.

  * $\bullet$

To evaluate the benefits of using $SS_{n}$ to improve data availability in F2F
systems.

###  V-A Experimental Setup

Details of algorithmic and empirical assumptions made in our experiments are
presented in the following.

####  V-A1 Expansion algorithm

A user is not expected to trust all his friends of friends to store his or her
data: some of them can be just weak connections of his weaker direct social
ties, for example. We use the quantitative power of $SS$ to select the
reasonably strong indirect connections and guarantee comparable social
strength with the user’s 1-hop friends.

The expansion algorithm follows two steps:

  * $\bullet$

For each user $i$, find the weakest direct social contact $p$ such that
$NW(i,p)=\min\limits_{j\in Neigh(i)}{[NW(i,j)]}$. Let this minimum normalized
weight be referred to as $\theta_{i}$.

  * $\bullet$

For each $m$ of $i$’s $n$-hop friends, if $SS_{n}(i,m)\geq\theta_{i}$, the
user $m$ is inserted in the candidate peer set of $i$. Intuitively, this
ensures that the social strength between $i$ and $m$, located at distance $n$
in the social graph, is at least as strong as $i$’s weakest direct tie.

We note that the algorithm expands each candidate-set using a user-specific,
thus local, threshold. Such local thresholds are needed in the distributed
setting of a F2F system.

####  V-A2  Online Presence Behavior

To estimate peer availability, we augmented each network with online presence
empirically deduced from various real traces. For CA-I and CA-II, we fit a
distribution to online presence information extracted from empirical Skype
traces presented in [13]. The distribution was applied to each author by
shifting it to match the timezone of his or her affiliation. As seen in Figure
3, which plots the percentage of users online per hour of the day, at least
25% of nodes are online at any given time, with the peak and valley occurring
at about 1:00 AM and noon, respectively.

For the TF2 network, we used one month of the empirical playing times of the
gamers. We plot the corresponding aggregate distribution in Figure 4, which
shows each week’s online presence per hour for May 2011. The distribution
shows clear diurnal and domain-specific activity patterns. As noted in [33],
gaming is not an activity conducive to multi-tasking. Therefore, we see an
elevated level of presence on weekends and during non-working hours. Although
peak presence occurs consistently in the early morning with more than 20% of
users online, there are almost no users online at noon.

Figure 3:  Online behavior of nodes in empirical traces of Skype. Figure 4:
Online behavior of players per hour of the week in May for TF2.

To determine whether the social strength selection mechanism improves the
potential availability of storage resources, we measure the percentage of a
node’s selected candidates available throughout the day, by binning online
presence into 1-hour time slots. If a user was online at some point during a
time slot, we mark him as available for that time slot. Methods that store
files in a distributed fashion such as erasure codes require $k$ storage sites
to be available for retrieving a file. Thus, we also vary the number of
friends necessary for a node’s storage needs to be met under such storage
schemes. We then measure the fraction of nodes who have enough candidates
online to meet their needs when selected by either the 1-hop or social
strength mechanisms.

####  V-A3 Data placement

Replicating data at all friends allows a user to get maximum achievable data
coverage but results in high costs for storing and transferring data to
multiple copies, in particular for users with a large number of friends. So we
adapt the greedy heuristic data placement algorithm proposed in [37] to backup
files with a subset of friends who can cover the maximum online time. In this
heuristic, to get maximum possible time slots coverage (e.g., 24 hours), users
first pick the friend who is able to cover as many time slots as possible,
then pick the second friend to maximum cover the remaining not covered time
slots, and keep doing this until all the possible time slots are covered.

###  V-B Results

####  V-B1 Expanding Peer Sets

Since the most intuitive advantage of our mechanism is an increase in the
number of storage candidates, we begin by evaluating _how much_ the candidates
set is expanded. We thus implemented $SS_{n}$ presented in Eq. 1 and report
the size of the candidate set selected based on the expansion algorithm
presented in Section V-A1 on the three networks described in Section IV-A.

Table IV shows high level statistics on how candidate sets are expanded with
2- and 3-hop social distance respectively in each of our three networks. For
2-hop expansion, 63.6% users in CA-II and 36.6% of players in TF2 expanded
their candidate sets. Even in the sparse CA-I, 34.2% users augmented their
peer-set.

When using only the 3-hop neighborhood to recruit peer candidates $p$ who
satisfy the requirement that $SS_{3}(i,p)\geq\theta(i)$ the expansion is still
taking place in all three networks: even in the sparse network CA-I, 10.6%
users augment their friendsets and about 1% users have expanded their
candidates with more than five friends. The denser network CA-II has more than
50% users expanding their candidate sets, and TF2 has 27.2% (with the number
of expanded 3-hop friends being 1,032). As expected, 3-hop augmentation is not
as strong as 2 hops’ since as the social distance increases, the social
strength weakens. Yet a number of users can still recruit more peers when
increasing the social distance. Thus, using social strength for recruiting
resources indirectly connected in the social graph can successfully augment
users’ peer-sets and potentially solve problems caused by the limited number
of friends in F2F systems.

TABLE IV: Candidate set expansion via $SS_{2}$ and $SS_{3}$: percentage of expanded users, expansion nodes and rate. | % expanded users | expansion: med, max | expansion rate: med, avg, max
---|---|---|---
Net. | n=2 | n=3 | n=2 | n=3 | n=2 | n=3
CA-I | 34.2 | 10.6 | 0, 19 | 0, 19 | 0, 0.2, 1.6 | 0, 0.1, 1.1
CA-II | 63.6 | 51.2 | 3, 459 | 1, 474 | 0.5, 1.3, 6.1 | 0.1, 3.1, 23.3
TF2 | 36.6 | 27.2 | 0, 988 | 0, 1032 | 0, 2.5, 36 | 0, 1.8, 116.5

Figure 5 examines the effects of the social strength mechanism from a
different perspective. It plots the degree of a user vs. the size of her
expanded candidate set. For the most part, all users expand their candidate
set, with CA-II showing linear growth in 2-hop distance as the user’s degree
increases. As expected, the number of expanded friends is positively
correlated to users’ social degrees in both 2- and 3-hop expansion.

Figure 5: Expanded candidate set size as a function of node degree.

####  V-B2 Online Storage Availability

Figures 6 and 7 plot the average fraction of users whose storage needs are met
with the requirement that at least $k\in\\{1,3,6\\}$ candidates are online at
a given time for the co-authorship networks and TF2, respectively. For CA-I
and CA-II, each data point is the average of 10 times iterations. Error bars
represent the 95% confidence interval. Three scenarios are compared: storage
candidates are selected only from direct social contacts; and storage
candidates are selected from those located at least $n$ hops away with a
strong enough social strength $SS_{n}$, where $n=2$ and $n=3$.

Figure 6: Average fraction of available candidates per hour for CA-I and CA-
II. Figure 7: Average fraction of available candidates per hour of the week
for TF2.

Using social strength results in a higher fraction of candidate sets meeting
the storage requirements: in our experiments, social strength lead up to 20%
improvements on data availability. In particular, when 6 friends are needed to
cooperate on completing a storage task, at least 5% higher data availability
can be reached. Further, the social strength mechanism does not degrade as
quickly as the 1-hop selection when increasing the number of friends that are
required to be online simultaneously. We also see that for sparse networks
like CA-I, social strength over larger distance $n$ significantly improves
data availability, especially when larger number of friends are required to be
online simultaneously.

Finally, CA-II shows higher levels of availability than CA-I under the same
conditions. This is likely because CA-II has more users with larger expanded
candidate sets under the social strength mechanism than CA-I (Figure 1).
Moreover, we note that CA-I shows better performance than TF2 under the same
requirements. In the scenario that requires at least one friend online, 73% of
users in CA-I have candidates available at midnight, compared to only 20% of
TF2 users. One explanation could be due to the limited number of concurrent
players the gaming server supports (at most 32 simultaneous players). Another
explanation is that CA-I users are spread out over multiple timezones, while
most of the TF2 users are geographically close to the server to minimize
latency, and thus are time synchronized in their gaming patterns.

To conclude, using datasets from co-authorship networks and a video gaming
community, we show that the social strength-based mechanism more than doubles
the set of storage candidates potentially motivated by social incentives, and
improves the data availability of storage resources by up to 20% with 3-hop
social strength.

##  VI Using Social Strength for Predicting Information Diffusion Paths

The diffusion of information is a fundamental process in OSNs. Our social
strength metric can be used to infer information diffusion paths between
indirectly connected users in the social graph. I.e., if we know someone who
received the information at $t_{0}$, then we can directly predict the infected
users at $t_{n}$ ($n\geq 2$) instead of step-wise, e.g., at $t_{1}$.

Predictions over such longer intervals could help OSN providers customize
strategies for preventing or accelerating information spreading. For example,
to contain rumors, OSN providers could block related messages sent to the
susceptible users several time steps before the rumor arrives, or disseminate
official anti-rumor messages in advance. Similarly, advertisers could
accelerate their advertisements spreading in the network by discovering who
will be the next susceptible to infection. This n-hop long paths prediction
can supply more time for decision makers to contain harmful disseminations,
and to choose users who are pivotal in information spreading for targeted
advertisements.

This section describes our experiments of applying the social strength metric
to information diffusion path prediction.

###  VI-A Experimental Setup

For simplicity, we focus on predicting diffusion paths at 2- and 3-hop
distance with a single seed source. A single node is chosen as the original
source of information at $t_{0}$. We then predict the nodes that will accept
the information at $t_{n}$ with the knowledge from $t_{0}$. All other n-hop
($n\geq 4$) paths and multiple seeds can be extended from 2 and 3 hops.

####  VI-A1 Diffusion simulation

As ground truth, we used the widely accepted Susceptible-Infected (SI) model
[38] to simulate the diffusion process and recorded the diffusion paths, i.e.,
which nodes are affected during each time step. The SI model is a probability-
based diffusion model where nodes can be in one of two states: susceptible or
infected. We say a node has accepted the information if it is infected, and
once infected, can never return to the susceptible state. The input of the
simulation is a weighted graph where weights represent a quantification of the
social ties between two directly connected nodes.

For simplicity, we set the spreading probability from an infected node $v_{i}$
to its nearest neighbor $v_{j}$ proportional to the edge weight $w_{i,j}$.
Introducing a constant of proportionality $\beta$, the time-independent
probability of passing information from $v_{i}$ to $v_{j}$ can be written as
$P_{i,j}$ = $\beta w_{ij}$, where increasing $\beta$ results in an overall
increased probability of infection. We set $\beta=\frac{1}{max(w_{ij})}$
(inversely proportional to the global maximum edge weight in the graph), in
which case $P_{i,j}=1$ for the globally strongest link, and $P_{i,j}<1$ for
all others. We set a threshold $p_{0}$, which is in the range between the
minimum $P_{min}$ and the maximum $P_{max}$. When $p_{0}=P_{min}$, the
information will disseminate to all the nodes in the graph. Conversely, if
$p_{0}=P_{max}$, almost no diffusion will occur. If $P_{ij}$ $\geq p_{0}$,
information will spread through the edge (i, j), and not spread otherwise. The
initial seed, i.e., the node infected at $t_{0}$, is randomly selected at the
beginning of the simulation.

####  VI-A2 Predicting diffusion paths via social strength

Once we generate the ground truth from the SI model, we then use social
strength to predict the path of diffusion. We calculate social strength values
between the seed and its n-hop friends, then convert the social strength
values to a social rank. Each user has a rank list for all his or her friends
according to the social strength value between said user and the friend.
Because of the asymmetric characteristic of the social strength metric, the
converted social ranks are also asymmetric.

After obtaining social ranks, we need a cut-off threshold to decide whether or
not a node’s n-hop friends will be infected at $t_{n}$. The strategy we adopt
here is that the social ranks from both perspectives must be high, e.g.,
$socialrank_{n}(A,B)$ and $socialrank_{n}(B,A)$ both rank among the top 10% of
both user A and B’s friends. Then, the cut-off threshold can classify a node’s
n-hop friends into two categories: information-accepted (infected) or
information-denied nodes at $t_{n}$. The intuition of this cut-off is that
users will both prefer to send information to their “closest” social ties and
will likely believe the information from their “closest” social ties.

####  VI-A3 Prediction evaluation

We compare the prediction results with the ground truth obtained from the
diffusion simulation to verify the effectiveness of the social strength in
predicting diffusion paths. We evaluate our method using three metrics.

  * $\bullet$

_A_ ccuracy is the proportion of true results in the population.

${\textstyle
accuracy=\frac{\\#~{}of~{}true~{}positives+~{}\\#~{}of~{}true~{}negatives}{population~{}size}}$

  * $\bullet$

_S_ ensitivity, also called the true positive rate, measures the proportion of
actual positives that are correctly predicted.

${\textstyle
sensitivity=\frac{\\#~{}of~{}true~{}positives}{\\#~{}of~{}true~{}positives+\\#~{}of~{}false~{}negatives}}$

  * $\bullet$

_S_ pecificity evaluates the proportion of negatives which are correctly
identified.

${\textstyle
specificity=\frac{\\#~{}of~{}true~{}negatives}{\\#~{}of~{}true~{}negatives+\\#~{}of~{}false~{}positives}}$

###  VI-B Results and Evaluation

We used the three datasets (CA-I, CA-II and TF2) as described in the previous
section. Results are presented as the average of 100 iterations. We varied the
threshold $p_{0}$ to examine the effect of prediction results in scenarios
ranging from complete propagation to nearly none. The threshold ranges we
chose are based on the edge probability distribution plotted in Figure 8. For
example, in CA-II, 49.3% of edge probabilities are smaller than 0.007. Thus,
setting $p_{0}<$ 0.007 results in complete diffusion in the network.
Conversely, 94.1% edge probabilities are smaller than 0.07, so setting
$p_{0}>$ 0.07 leads to almost no propagation. Therefore, we test the power of
social strength for predicting diffusion paths when the threshold varied from
0.007 to 0.07. Similarly, we choose 0.01 and 0.1 as the range of thresholds of
CA-I and 0 and 0.018 for CA-II.

The prediction results via $SS_{2}$ and $SS_{3}$ are shown in Figure 9. We see
that for 2-hop social strength prediction, besides complete infection
scenarios, the sensitivities are above 0.64, reaching a maximum of 0.887 in
CA-II. Also, the specificities and the accuracies in all cases are always
higher than 0.74, with the highest accuracy ($0.935$) occurring in TF2 when
$p_{0}=$ 0.018. Although 3-hop predictions show decreased sensitivity,
specificity, and accuracy compared to 2-hop results, they remain above 0.5.

Figure 8: The frequency distribution of edge probability of CA-I, CA-II and
TF2.

To better demonstrate social strength’s effective power on inferring diffusion
processes, we consider the following baseline method: assume all of a user’s 2
and 3-hop friends accept the information in $t_{2}$ and $t_{3}$. We compare
our prediction results via $SS_{2}$ and $SS_{3}$ with the baseline in Figures
10 and 11.

The baseline performance is very low when networks are not completely diffused
while the social strength predictive method achieves peak performance at
around 0.89, 0.79, and 0.82 for sensitivity, specificity, and accuracy,
respectively. It is important to note that these three networks have very
different network structure (from sparse to dense), yet the performance of
social strength is consistently higher than the baseline in all three
networks.

From all these results, we conclude that social strength is useful to predict
who will be infected, or along which paths information propagates, at least
2-3 steps before a susceptible node is even in contact with an infected node.
Even if the accuracy of the prediction decreases with distance for $n=3$,
there are significant benefits in being 3 time steps ahead of the infection.

Figure 9: Sensitivity, specificity and accuracy when using social strength to
predict information dissemination in CA-I, CA-II and TF2. Figure 10:
Comparison between the performances of prediction using 2-hop social strength
($SS_{2}$)) and the baseline. Figure 11: Comparison between the performances
of prediction using 3-hop social strength ($SS_{3}$)) and the baseline.

##  VII Summary and Discussion

We introduced a social strength metric to measure the strength of indirect
social ties by considering both the intensity of interactions and the number
of connected paths. We showed that our metric is positively correlated with
the Jaccard index and with the interaction frequency along direct social ties,
indicating that it is an accurate quantification of the intensity of a(n
indirect) social relationship.

We proved its applicability to two socially informed applications: friend-to-
friend storage sharing systems and predicting information diffusion in a
social graph. Based on empirical data, our experimental evaluations
demonstrate that using the social strength metric is beneficial in both cases.
First, for the average user in the social graph, it helps identify indirectly
connected peers with whom the user has a significant social strength that
could act as social incentive in a resource sharing environment, thus
significantly increasing the pool of resources available to the user. Second,
because indirect ties diversify the pool of users (in this case, by covering
more time zones), resource availability increases significantly. Third, social
strength accurately predicts information diffusion paths at least 2 steps
ahead, which enables intervention mechanisms for rumor squelching and targeted
information injection.

A variety of socially aware applications can benefit from the social strength
metric. For example, link prediction based on social strength could discover
more potentially useful contacts and improve link recommendation accuracy.
Automatically setting default privacy controls based on social strength is
likely to be more accurate than using graph distance alone. Employing social
strength in graph partitioning will have the benefits of relying on local
computation, thus allowing for more decentralized and scalable algorithms.
Finally, in decentralized OSNs, users’ augmented social strength-based
friendsets could provide a more efficient and privacy-guaranteed technique to
propagate updates in the presence of churn.

This work is a first step in understanding the value of and the methodology
for quantifying the strength of indirect social ties. In addition to exploring
the applicability space, there are aspects related to privacy and security
that need to be understood. Intuitively, because of the local exploration of
one’s social neighborhood for computing social strength, the risks are
contained, especially compared to approaches that require the global graph.
However, a formal study of this topic is required for building a practical
framework that enables the implementation and adoption of the social strength
metric for indirect ties.

## References

  * [1] T. C. Antonucci, “Social supports and social relationships,” _Handbook of aging and the social sciences_ , vol. 3, pp. 205–226, 1990.
  * [2] G. C. Homans, “Social behavior: Its elementary forms.” 1961.
  * [3] H. Shen and Z. Li, “Leveraging social networks for effective spam filtering,” _Computers, IEEE Transactions on_ , vol. PP, no. 99, pp. 1–1, 2013.
  * [4] C. Basu, H. Hirsh, and W. Cohen, “Recommendation as classification: Using social and content-based information in recommendation,” in _AAAI/IAAI_ , 1998, pp. 714–720.
  * [5] J. Li and F. Dabek, “F2f: reliable storage in open networks,” in _Proceedings of the 4th International Workshop on Peer-to-Peer Systems_ , ser. IPTPS ’06, 2006.
  * [6] I. Kahanda and J. Neville, “Using transactional informa- tion to predict link strength in online social networks,” in _Proceedings of the 3rd Conference on Weblogs and Social Media, ICWSM_ , 2009.
  * [7] E. Gilbert and K. Karahalios, “Predicting tie strength with social media,” in _Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, CHI’09_ , 2009.
  * [8] R. S. Burt, “Social contagion and innovation: cohension versus structural equivalence,” _The American Journal of Sociology_ , vol. 92, no. 6, pp. 1287–1335, 1987.
  * [9] M. Granovetter, “The strength of weak ties,” _American Journal of Sociology_ , vol. 78, no. 6, pp. 1360–1380, 1973.
  * [10] ——, _Getting a job A study of contacts and careers_ , 2nd ed. University Chicago Press, 1995.
  * [11] B. Wellman, “Structural analysis: From method and metaphor to theory and substance,” _Social structures: A network approach._ , pp. 19–61, 1988.
  * [12] N. E. Friedkin, “Horizons of observability and limits of informal control in organizations,” _Social Forces_ , vol. 62, no. 6, pp. 54–77, March 1983\.
  * [13] G. T. Raúl, M. Sánchez Artigas, and P. García López, “Analysis of Data Availability in F2F Storage Systems: When Correlations Matter,” in _Peer-to-Peer Computing_ , 2012, pp. 225–236.
  * [14] M. Gupte and T. Eliassi-Rad, “Measuring tie strength in implicit social networks,” in _In Proceedings of the 3rd Annual ACM Web Science Conference, WebSci’12_ , 2012.
  * [15] P. Jaccard, “Distribution de la flore alpine dans le bassin des drouces et dans quelques regions voisines,” _Bulletin de la Société Vaudoise des Sciences Naturelles_ , vol. 37, no. 140, pp. 241–272, 1901.
  * [16] J.-P. O. andJ. Saramäki, J. Hyvönen, G. Szabó, D. Lazer, K. Kaski, J. Kertész, and A.-L. Barabási, “Structure and tie strengths in mobile communication networks,” _PNAS_ , vol. 104, no. 7332, 2007.
  * [17] M. McPherson, L. Smith-Lovin, and J. Cook, “Birds of a feather: Homophily in social networks,” _Annual Review of Sociology_ , vol. 27, pp. 415–444, 2001\.
  * [18] D. Crandall, L. Backstrom, D. Cosley, S. Suri, and D. Huttenlocher, “Inferring social ties from geographic coincidences,” _National Academy of Sciences_ , vol. 107, no. 52, 2010.
  * [19] L. Adamic and E. Adar, “Friends and neighbors on the web. social networks,” _Social Networks_ , vol. 25, no. 3, pp. 211–230, 2003.
  * [20] D. J. Brass, K. D. Butterfield, and B. C. Skaggs, “Relationships and unethical behavior: A social network perspective,” _Academy of Management Review_ , vol. 23, no. 1, pp. 14–31, 1998.
  * [21] P. Anderson, N. Koutellis, J. Finnis, and A. Iamnitchi, “On managing social data for enabling socially-aware applications and services,” in _3rd Workshop in Social Network Systems_ , 2010.
  * [22] N. Kourtellis, “On the design of socially-aware distributed systems,” Ph.D. dissertation, University of South Florida, 2012.
  * [23] R. Xiang, J. Neville, and M. Rogati, “Modeling relationship strength in online social networks,” in _19th International Conference on World Wide Web_ , Raleigh, NC, USA, 2010, pp. 981–990.
  * [24] C. Wilson, B. Boe, A. Sala, K. P. N. Puttaswamy, and B. Y. Zhao, “User interactions in social networks and their implications,” in _Proceedings of the 4th ACM European conference on Computer systems_ , 2009\.
  * [25] L. Pappalardo, G. Rossetti, and D. Pedreschi, “”how well do we know each other?” detecting tie strength in multidimensional soical networks,” in _In ASONAM_ , 2012, pp. 1040–1045.
  * [26] J. Golbeck and J. Hendler, “Inferring binary trust relationships in web-based social networks,” _ACM Transactions on Internet Technology_ , vol. 6, no. 4, 2006.
  * [27] P. D. Killworth, E. C. Johnsen, H. Bernard, G. A. Shelley, and C. McCarty, “Estimating the size of personal networks,” _Social Networks_ , vol. 12, no. 4, pp. 289 – 312, 1990. [Online]. Available: http://www.sciencedirect.com/science/article/pii/037887339090012X
  * [28] H. R. Bernard, P. Killworth, D. Kronenfeld, and L. Sailer, “The problem of informant accuracy: The validity of retrospective data,” _Annual Review of Anthropology_ , vol. 13, pp. pp. 495–517, 1984. [Online]. Available: http://www.jstor.org/stable/2155679
  * [29] B. A. Huberman, D. M. Romero, and F. Wu, “Social networks that matter: Twitter under the microscope,” _First Monday_ , vol. 14, no. 1, 2009.
  * [30] “Economist 2009 primates on facebook: Even online, the neocortex is the limit,” http://www.economist.com/node/13176775/, February 2009.
  * [31] http://arnetminer.org/.
  * [32] J. Tang, J. Sun, C. Wang, and Z. Yang, “Social influence analysis in large-scale networks,” in _International Conference on Knowledge Discovery and Data Mining (SIGKDD’2009)_ , 2009.
  * [33] J. Blackburn and A. Iamnitchi, “Relationships under the microscope with interaction-backed social networks,” in _In 1st International Conference on Internet Science_ , 2013.
  * [34] http://steamcommunity.com/.
  * [35] J. Blackburn, R. Simha, N. Kourtellis, X. Zuo, M. Ripeanu, J. Skvoretz, and A. Iamnitchi, “Branded with a scarlet ”c”: cheaters in a gaming social network,” in _Proceedings of the 21st International conference on World Wide Web_ , 2012.
  * [36] B. Gonalves, N. Perra, and A. Vespignani, “Modeling users’ acitivity on twitter networks: validation of dunbar’s number,” _PLoS ONE_ , vol. 6, no. 8, 2011.
  * [37] R. Sharma, A. Datta, M. Dell’Amico, and P. Michiardi, “An empirical study of availability in friend-to-friend storage systems,” in _Peer-to-Peer Computing_ , 2011, pp. 348–351.
  * [38] M. Newman, _Networks: an introduction_. Oxford University Press, 2009.