# zbMATH — the first resource for mathematics

On the complexity of reasoning about opinion diffusion under majority dynamics. (English) Zbl 07228995
This paper studies complexity analysis of opinion diffusion problems under majority dynamics in social networks. A key problems studied in this paper is consensus problem. Given a graph $$G=(N,E)$$ and a rational number $$\alpha$$ such that $$\alpha\in(0,1)$$, this problem requires to compute a set $$S\subseteq N$$ of seeds such that $$|S|\le\alpha|N|$$ and there is a dynamic $$c$$ tends to $$1$$ with $$N_{1/c}=S$$ or check that there is no set of seeds satisfying the above conditions. Here $$N_{1/c}$$ is the set of nodes with opinion $$1$$ under a given configuration $$c:N\rightarrow\{0,1\}$$. It is shown that consensus problem is a NP-hard problem. Two other problems called double problem and plural problem are also proved to be NP-hard. Double problem refers to computing a configuration $$c$$ such that $$|N_{1/c}|\le\varepsilon|N|$$ and there exists a dynamic $$c$$ tending to $$c^*$$ with $$|N_{1/c^*}|>2\varepsilon |N|$$ or check that there is no such configuration satisfying the above conditions. Plural problem refers to computing a configuration $$c$$ such that $$c$$ is stable and $$N_{0/c}\not=\emptyset$$ and $$N_{0/c}\not=N$$ or check that there is no configuration satisfying the above conditions.
##### MSC:
 91D30 Social networks; opinion dynamics 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: