# Influence Maximization in Social Network Considering Memory Effect and Social Reinforcement Effect
## 4 Algorithms
### General Greedy Algorithm  
The _General Greedy_[4] can be extended to solve the _influence maximization problem_ under _DCM4 VM_. We consider the expected number of _accepted_ nodes when estimating the influence spread of certain seeds set. Thus, the expected number of influenced nodes \(\sigma(S)\) in the original algorithm is replaced by \(\sigma_{tar}(S)\). Then the greedy method is the same to select the node \(v_{t}\) which maximizes the marginal gain of influence spread, \(v_{t}=argmax_{v\in V\setminus S_{t-1}}\) [\(\sigma=\sigma_{tar}(S_{t-1}\ \cup v)-\sigma_{tar}(S_{t-1})\)]. The _General Greedy Algorithm_ is described in Algorithm 2. ```
Input: network graph \(G\), initial seeds \(S\) Output: accepted seeds number \(\sigma_{tar}\)
1\(o_{tar}=0\), \(t=0\);
2 foreachnode \(v\in S\)do
3\(\text{state}(u,t)=\text{accepted}\);
4\(P_{u}=1\);
5 end while
6 whileSnotemptydo
7\(t++\);
8\(\text{next}\leftarrow\phi\),\(\text{acc}S\leftarrow\phi\);
9 //assume all newly interested or accepted nodes spread immediately and simultaneously, \(N_{out}(u)\) is the out neighbors of \(u\);
10 forachnode \(v\in S\)do
11 forachnode \(v\in N_{out}(v)\)do
12 if\(\text{state}(v,t)\in\) [interested, accepted, exhausted] then
13 continue;
14 end if
15 if\(\text{state}(v,t-1)\in\) [unknown, known] then
16\(\text{P}\sim\text{Uniform}(0,1)\);
17 if\(P_{u,v}<\text{P}\)then
18\(\text{state}(v,t)=\text{interested}\);
19\(\text{new}S=\text{new}S\cup\{v\}\),\(\text{acc}S=\text{acc}S\cup\{v\}\);
20 end if
21 else
22\(\text{state}(v,t)=\text{known}\);
23 end if
24 end if
25 else
26\(\text{state}(v,t)=\text{state}(v,t-1)\);
27 end if
28 If\(\text{state}(v,t-1)=\text{interested}\)then
29\(\text{acc}S=\text{acc}S\cup\{v\}\);
30 end if
31 end if
32\(\text{state}(v,t)=\text{state}(v,t-1)\);
33 end if
34\(\text{acc}S=\text{acc}S\cup\{v\}\);
35 end if
36
37 end if
38\(\text{and}\) //whether the newly exposed interested nodes at time \(t\) will turn to accepted;
39 forach\(v\in\text{acc}S\)do
40\(P_{v}(t)\) according to (2);
41\(\text{P}\sim\text{Uniform}(0,1)\);
42 if\(P_{v}(t)<P\)then
43\(\text{state}(v,t)=\text{accepted}\);
44\(o_{tar}++\);
45 end if
46\(S=\text{new}S\);
47 end if
48 return\(\sigma_{tar}\);
```  
**Algorithm 1**Propagation Simulation \(\sigma_{tar}(G,S)\)```
Input: network graph \(G\), initial seeds size \(k\) Output:\(accepted\) seeds \(S\)
1 Initialize \(S\leftarrow\phi\) and \(R=10000\);
2 for\(t=1\) to \(k\)do
3 foreachnode \(v\in V\backslash S\)do
4\(\sigma_{v}=0\);
5 for\(i=1\) to \(R\)do
6\(\sigma_{v}+=\left\lfloor\sigma_{tar}(G,S\cup\{v\})\right\rfloor\);
7
8\(\sigma_{v}=\sigma_{v}/R\);
9
10 end for
11\(S=S\cup\left\{\operatorname{argmax}_{v\in V\backslash S}\sigma_{v}\right\}\);
12
13 end for
14 return\(S\);
```

**Algorithm 2**\(GG(G,k)\)

### Degree Discount Algorithm

Degree is frequently used for selecting seeds in _influence maximization_. [PERSON] et al. [18] propose the _Degree Discount_ heuristic to efficiently find the seed nodes. _Degree Discount_ considers only one-step neighbor nodes and selects nodes with high degree values, which tends to have higher expectations of influence, to be seeds. ```
Input: network graph \(G\), initial seeds size \(k\) Output:\(accepted\) seeds \(S\)
1 Initialize \(S\leftarrow\phi\);
2 foreachnode \(v\in V\)do
3 compute its degree \(d_{v}\);
4\(d_{v}=d_{v}\);
5 Initialize \(t_{v}\) to \(0\);
6 end for
7 for\(t=1\) to \(k\)do
8\(v^{+}=\operatorname{argmax}_{v\in V\backslash S}\)\(d_{v}\);
9\(S=S\cup\left\{v^{+}\right\}\)
10 //recalculate \(p_{V}\);
11 update \(P_{V}\) according to (4);
12 //discount degree;
13 foreachnode \(v\in N_{out}(u)\backslash S\)do
14\(t_{v}=t_{v}+1\);
15\(d_{v}=d_{v}-2t_{v}-(d_{v}-t_{v})t_{v}P_{u,v}P_{v}\);
16 end for
17
18 end for
19 return\(S\);
```

**Algorithm 3**\(DD(G,k)\)

We modified the _Degree Discount_ heuristic algorithm to solve the viral marketing problem under _DCM4 VM_, described as Algorithm 3.