Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Inferring the strength of social ties: a community-driven approach   Online social networks are growing and becoming denser. The social
connections of a given person may have very high variability: from close
friends and relatives to acquaintances to people who hardly know. Inferring the
strength of social ties is an important ingredient for modeling the interaction
of users in a network and understanding their behavior. Furthermore, the
problem has applications in computational social science, viral marketing, and
people recommendation.
  In this paper we study the problem of inferring the strength of social ties
in a given network. Our work is motivated by a recent approach [27], which
leverages the strong triadic closure (STC) principle, a hypothesis rooted in
social psychology [13]. To guide our inference process, in addition to the
network structure, we also consider as input a collection of tight communities.
Those are sets of vertices that we expect to be connected via strong ties. Such
communities appear in different situations, e.g., when being part of a
community implies a strong connection to one of the existing members.
  We consider two related problem formalizations that reflect the assumptions
of our setting: small number of STC violations and strong-tie connectivity in
the input communities. We show that both problem formulations are NP-hard. We
also show that one problem formulation is hard to approximate, while for the
second we develop an algorithm with approximation guarantee. We validate the
proposed method on real-world datasets by comparing with baselines that
optimize STC violations and community connectivity separately.

2
The categories of this paper are: math
21
The categories of this paper are: adap-org
9
The categories of this paper are: nlin
11
The categories of this paper are: hep-lat
35
The categories of this paper are: mtrl-th
37
The categories of this paper are: supr-con
27
The categories of this paper are: comp-gas
17
The categories of this paper are: q-fin
18
The categories of this paper are: econ
34
The categories of this paper are: chem-ph
26
The categories of this paper are: bayes-an
3
The categories of this paper are: physics
32
The categories of this paper are: atom-ph
22
The categories of this paper are: chao-dyn
4
The categories of this paper are: cond-mat
24
The categories of this paper are: dg-ga