Font Size:

Preventing Unraveling in Social Networks Gets Harder

Last modified: 2013-06-29

#### Abstract

The behavior of users in social networks is often observed to be affected by the actions of their friends. Bhawalkar et al. (ICALP '12) introduced a formal mathematical model for user engagement in social networks where each individual derives a benefit proportional to the number of its friends which are engaged. Given a threshold degree

*k*the equilibrium for this model is a maximal subgraph whose minimum degree is at least*k*. However the dropping out of individuals with degrees less than*k*might lead to a cascading effect of iterated withdrawals such that the size of equilibrium subgraph becomes very small. To overcome this some special vertices called "anchors" are introduced: these vertices need not have large degree. Bhawalkar et al. considered the*Anchored k-Core*problem: Given a graph*G*and integers*b, k*and*p*do there exist sets of vertices*B, H*such that*B*is a subset of*H*, size of*B*is at most*b*and size of*H*is at least*p*, and every vertex*v*which is in*H*but not in*B*has degree at least*k*in the induced subgraph*G[H]*. They showed that the problem is NP-hard for all*k*greater equal 2, and gave some inapproximability and fixed-parameter intractability results. In this paper we give improved hardness results for this problem. In particular we show that the*Anchored k-Core*problem is W[1]-hard parameterized by*p*, even for*k*=3. This improves the result of Bhawalkar et al. (who show W[2]-hardness parameterized by*b*) as our parameter is always bigger since*p*is greater equal than*b*. Then we answer a question of Bhawalkar et al. by showing that the*Anchored k-Core*problem remains NP-hard on planar graphs for all*k*greater equal 3, even if the maximum degree of the graph is*k*+2. Finally we show that the problem is FPT on planar graphs parameterized by*b*for all*k*greater equal 7.
Full Text:
PDF