Introduction
Related works
Contributions
Notation | Description |
---|---|
\(G=(V,E,P)\) | A social network with user set V and edge set E. P is the influence probability. \(P_e\) represents influence probability on edge e where \(0\le P_e\le 1\) |
\(G=(V,C,E,P,f)\) | A candidate seed set \(C\subseteq V\). Each user has a weight f |
\({\mathcal {U}}\) | The set of groups, b(U) is the benefit when U is activated for \(U\in {\mathcal {U}}\) |
\(c(v)\ge 0\) | c(v) is the cost to activate v |
\(n=|V|\) | The number of users |
\(m=|E|\) | The number of edges |
\(l=|{\mathcal {U}}|\) | The number of groups |
\(\beta\) | The threshold of a group being activated, \(0<\beta \le 1\) |
k | The number of seeds |
\(\beta (S)\) | The expected benefit of all activated groups with seed set S. |
\(\gamma (S)\) | The expected diffusion cost of all activated users with seed set S |
\(\rho (S)=\beta (S)-\gamma (S)\) | The expected profit with seed set S |
Problem formulation
Independent cascade model [4]
Group profit maximization
Properties of GPM
Hardness results
Modularity of objective function
Lower bound and upper bound
The upper bound
The lower bound
Algorithm
Extended reverse influence set (RIS) sampling
Submodular–modular algorithm
Group coverage maximization algorithm
Sandwich approximation framework
Comparison with different heuristic strategies
Experiments
Nodes | Edges | Groups | Average group size | |
---|---|---|---|---|
Dataset 1 | 899 | 142,760 | 522 | 14.6 |
Dataset 2 | 16,726 | 95,188 | 22,015 | 3.7 |