Abstract
Finding the minimum Positive Influence Dominating Set (PIDS) is a problem arisen from the social network applications. The problem has been studied on general random graphs. However, the social networks is presented more precisely by power-law graphs. One of the most important properties of social networks is the power-law degree distribution. In this paper, we focus on the PIDS problem in power-law graphs and prove that the greedy algorithm has a constant approximation ratio. Simulation results also demonstrate that greedy algorithm can effectively select a small scale PIDS set.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 31-37 |
| Number of pages | 7 |
| Journal | Social Network Analysis and Mining |
| Volume | 2 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jan 1 2012 |
Keywords
- Greedy algorithm
- Positive influence dominating set problem
- Power-law distribution
- Social networks
ASJC Scopus subject areas
- Information Systems
- Communication
- Media Technology
- Human-Computer Interaction
- Computer Science Applications
Fingerprint
Dive into the research topics of 'Positive influence dominating sets in power-law graphs'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS