Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Maximizing Influence-based Group Shapley Centrality   One key problem in network analysis is the so-called influence maximization
problem, which consists in finding a set $S$ of at most $k$ seed users, in a
social network, maximizing the spread of information from $S$. This paper
studies a related but slightly different problem: We want to find a set $S$ of
at most $k$ seed users that maximizes the spread of information, when $S$ is
added to an already pre-existing - but unknown - set of seed users $T$. We
consider such scenario to be very realistic. Assume a central entity wants to
spread a piece of news, while having a budget to influence $k$ users. This
central authority may know that some users are already aware of the information
and are going to spread it anyhow. The identity of these users being however
completely unknown. We model this optimization problem using the Group Shapley
value, a well-founded concept from cooperative game theory. While the standard
influence maximization problem is easy to approximate within a factor
$1-1/e-\epsilon$ for any $\epsilon>0$, assuming common computational complexity
conjectures, we obtain strong hardness of approximation results for the problem
at hand in this paper. Maybe most prominently, we show that it cannot be
approximated within $1/n^{o(1)}$ under the Gap Exponential Time Hypothesis.
Hence, it is unlikely to achieve anything better than a polynomial factor
approximation. Nevertheless, we show that a greedy algorithm can achieve a
factor of $\frac{1-1/e}{k}-\epsilon$ for any $\epsilon>0$, showing that not all
is lost in settings where $k$ is bounded.

31
The categories of this paper are: ao-sci
20
The categories of this paper are: acc-phys
22
The categories of this paper are: chao-dyn
30
The categories of this paper are: q-alg
24
The categories of this paper are: dg-ga
28
The categories of this paper are: alg-geom
0
The categories of this paper are: hep-ph
16
The categories of this paper are: stat
11
The categories of this paper are: hep-lat
35
The categories of this paper are: mtrl-th
29
The categories of this paper are: funct-an
15
The categories of this paper are: nucl-ex
3
The categories of this paper are: physics
2
The categories of this paper are: math
5
The categories of this paper are: gr-qc
25
The categories of this paper are: patt-sol