Top-K Influential Nodes in Social Networks: A Game Perspective
Influence maximization, the fundamental of viral marketing, aims to find top-$K$ seed nodes maximizing influence spread under certain spreading models. In this paper, we study influence maximization from a game perspective. We propose a Coordination Game model, in which every individuals make their decisions based on the benefit of coordination with their network neighbors, to study information propagation. Our model serves as the generalization of some existing models, such as Majority Vote model and Linear Threshold model. Under the generalized model, we study the hardness of influence maximization and the approximation guarantee of the greedy algorithm. We also combine several strategies to accelerate the algorithm. Experimental results show that after the acceleration, our algorithm significantly outperforms other heuristics, and it is three orders of magnitude faster than the original greedy method.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionMarketingSimilar Papers 제목 키워드 기반
Influential Node Detection in Implicit Social Networks using Multi-task Gaussian Copula Models
Influential node detection is a central research topic in social network analysis. Many existing methods rely on the assumption that the network structure is completely known \textit{a priori}. However, in many applicati…
Time SeriesTime Series AnalysisTime Series PredictionNetwork Inference from a Mixture of Diffusion Models for Fake News Mitigation
The dissemination of fake news intended to deceive people, influence public opinion and manipulate social outcomes, has become a pressing problem on social media. Moreover, information sharing on social media facilitates…
parameter estimationDynamics of node influence in network growth models
Many classes of network growth models have been proposed in the literature for capturing real-world complex networks. Existing research primarily focuses on global characteristics of these models, e.g., degree distributi…
Influence Maximization in Hypergraphs Using A Genetic Algorithm with New Initialization and Evaluation Methods
Influence maximization (IM) is a crucial optimization task related to analyzing complex networks in the real world, such as social networks, disease propagation networks, and marketing networks. Publications to date abou…
MarketingA graph neural network based on feature network for identifying influential nodes
Identifying influential nodes in complex networks is of great importance, and has many applications in practice. For example, finding influential nodes in e-commerce network can provide merchants with customers with stro…
Graph Neural Network