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.

Additional Metadata
Persistent URL dx.doi.org/10.1007/978-3-030-47358-7_2
Series Lecture Notes in Computer Science
Citation
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