期刊
SOCIAL NETWORK ANALYSIS AND MINING
卷 3, 期 2, 页码 233-256出版社
SPRINGER WIEN
DOI: 10.1007/s13278-012-0067-7
关键词
Dynamic monopolies; Influence spreading; Spread of information; Viral marketing; Algorithms and complexity; Parameterized computational complexity; Fixed-parameter tractability; Data reduction
资金
- DFG [NI 369/7, NI 369/11]
We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size target set'' such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are active. Then, a vertex becomes active if the number of its active neighbors exceeds its threshold, and so on. TSS models the spread of information, infections, and influence in networks. Complementing results on its polynomial-time approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters diameter'', cluster editing number'', vertex cover number'', and eedback edge set number'' of the underlying graph on the problem's computational complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter size of the target set''. TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter treewidth''. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter cluster editing number'', yielding tractability for certain dense networks.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据