as those edges that, after dividing up
the network into communities (thus
obtaining so-called “community
structure”), connect vertices belonging to different communities. Finally,
we classify intra-community edges as
One of the most important features
of our weak ties is that those that are
bridges (in the Granovetter sense) create more, and shorter, paths; their deletion would indeed be more disruptive than the removal of a strong tie,
from a community-structure perspective. This may even be the reason weak
ties (albeit defined in a slightly different fashion) have proved effective in
the diffusion of information.
Benefits of our definition. Our definition of weak tie has four appealing
Weaker than Granovetter. The fact
that vertices linked by a weak tie belong to different communities does
not imply the edge between them is a
bridge; its deletion may not disconnect
its vertices, and, in practice, almost
Based on topological information.
It enables weak/strong classification
on the basis of only topological information. Zhao et al.
21 used topological
information but only locally, on the
neighbors of the two terminal vertices,
whereas our definition handles global
information, as it relies on the partitioning of the whole network;
Binary. It labels each edge in the
network as either weak or strong; as a
consequence, there is no need to need
to “tune” any threshold, below which
edges are classified as weak, the upshot
being we cannot compare two edges on
the basis of their strength; and
Accuracy of community discovery.
Our experiments show our definition
of weak tie is robust with respect to
the choice of a particular community-detection algorithm.
Several research projects have examined the strength of weak ties in
terms of nontopological information.
A nontopological approach to deter-
mining degrees of strength or weak-
ness requires researchers to choose
some measurable variables by which
the strength of the relation binding
two users can be deduced. In such a
scenario, weak ties are intended in a
relational sense; that is, they connect
acquaintances who do not interact fre-
quently and therefore do not influence
each another strongly. For “offline”
social networks, Marsden and Camp-
bell17 identified some variables (such
as communication reciprocity and the
presence of at least one mutual friend)
as indicators of a weak tie.
In the context of the social Web,
Gilbert and Karahalios9 and Petroczi
19 studied small OSNs— 35 participants and 56 participants, respectively—assigning weights to the relationships on the basis of several measures
of strength (such as intimacy/close-ness, reciprocity, and sociability/
conviviality) assessed through direct
questions to participants. Gilbert
and Karahalios9 extended Marsden-Campbell’s method to Facebook by
identifying as many as 74 variables as
potential predictors of strength. They
then modeled strength as a linear
combination of the variables, computing the weights by means of a variant of ordinary least-square regression. To validate their model, Gilbert
and Karahalios9 recruited 35 users
and asked them to rate their Facebook friends. They achieved accuracy
of approximately 85%, but their performance is difficult to replicate on
large OSN fragments. Their method
requires collecting a large amount of
information on user behavior; due to
privacy concerns and the limitation
on use of proprietary data, most such
required data is unlikely to be available for academic studies.
Zhao et al.
21 formalized the
strength of ties with a weight wij
assigned to the edge connecting vertices
i and j as follows
where ki and kj are the degrees of i and j
and cij are the numbers of their mutual
acquaintances. Numerical simulations
by Zhao et al.
21 showed that by gradually deleting ties with lower w values,
information coverage drops sharply.
Zhao et al.’s results corroborate the
hypothesis that weak ties are in fact the
key to information diffusion. A 2012
paper on weak ties in Facebook due
to Bakshey et al.
2 considered four pa-
rameters to measure the strength of a
connection: frequency of private mes-
sages; frequency of public comments
left on each other’s posts; number of
times they jointly appear in a photo;
and number of times they jointly com-
mented on a third-party post.
Unlike us, Bakshy et al.
2 did not
consider, at least not explicitly, the topological aspects of Facebook social
connections; moreover, their analysis
requires access to proprietary data
and records of user activity, so the
methodologies are not easily compared. Our work is more like Blondel
2 and Zhao21 in that weak ties are
understood to be useful connectors
favoring the spread of information
and was (as in Blondel et al.
However, one difference emerges:
Blondel et al. and Zhao et al. both assigned scores to ties and classified
them according to a threshold value.
In contrast, we classify ties as weak
or strong, depending on whether or
not they connect vertices located in
different communities; our classification scheme is binary and does not
use scores and threshold, which may
be difficult to set up and tune properly. Another approach is due to Grabowicz et al.,
12 who, like us, used information about network topology to
identify weak ties. However, they focused on Twitter, which can be modeled as a directed network where user
relationships are mostly asymmetric.
The Twitter “retweet” and “mention”
functions have a major effect on identification of weak ties; the studies are
thus not easily compared.
The results of the tests we carried out
highlight the pros and cons of our definition of a weak tie. For the preliminary community-detection phase we
deployed two popular algorithms: LM3
20 We considered two
testbeds, comparing them with a fragment of the Facebook network collected by Gjoka et al.
10 with 957,000 users
and 58. 4 million friendship connectionsa and “null-model” networks consisting of Erdös-Rényi random graphs
with up to 2,048 vertices; we varied the
a For a complete description of the dataset, see
supplementary material at http://informatica.