The study of information spread in social networks has applications in viral marketing, rumour modelling, and opinion dynamics. Often, it is crucial to identify a small set of influential agents that maximize the spread of information (cases which we refer to as being budget-constrained). These nodes are believed to have special topological properties and reside in the core of a network. We introduce the concept of nucleus decomposition, a clique based extension of core decomposition of graphs, as a new method to locate influential nodes. Our analysis shows that influential nodes lie in the k-nucleus subgraphs and that these nodes outperform lower-order decomposition techniques such as truss and core, while simultaneously focusing on a smaller set of seed nodes. Examining different diffusion models on real-world networks, we provide insights as well into the value of the degree centrality heuristic.
Lecture Notes in Computer Science
School of Computer Science

Agarwal, R.R. (Rishav Raj), Cohen, R. (Robin), Golab, L. (Lukasz), & Tsang, A. (2020). Locating Influential Agents in Social Networks: Budget-Constrained Seed Set Selection. In Lecture Notes in Computer Science. doi:10.1007/978-3-030-47358-7_2