# Influence Maximization in Social Network Considering Memory Effect and Social Reinforcement Effect
## 4 Algorithms
### General Greedy Algorithm
The central idea is to compute and update the expectations of _accepted_ nodes (which is influenced nodes in the original algorithm) in each round of selection considering only one-step neighbor nodes. Once a node is chosen as a seed, we discount the potential (represented as \(dd\) in Algorithm 3) of its neighbors to be seeds. Finally, we recalculate \(P_{v}\) each round according to:\[ \begin{array}{l}P_{v}=\left(P_{v}^{in}-P_{v}^{\max}\right)\text{exps}^{-m_{1}(v) -r_{2}m_{2}(v)}+P_{v}^{\max};\\ m_{1}(v)=\sum\limits_{v^{\prime}\in N(v)}P_{vv^{\prime}};\\ m_{2}(v)=\sum\limits_{v^{\prime}\in N(v)}P_{v^{\prime}};\end{array}  \tag{4}\]

### Exchangeable Greedy Algorithm

Both _Greedy Algorithms_ and _Heuristic Algorithms_ are useful in solving _influence maximization problems_ approximately. Actually, we can further improve the result by combining greedy strategies and heuristic strategies. We use two processes to express that. The first process is to generate potential seeds using heuristic methods and the second process is to exchange some of the seeds iteratively to further approximate the optimum. If the potential seeds set are around the global optimum, we are likely to find the optimal solution finally. The algorithm is described in Algorithm 4. If \(m=1\) and \(S\) is initialized a set of NULL values of \(k\) sizes (line 2), then in the next \(k\) rounds from \(t=1\) to \(t=k\), the _Exchangeable Greedy Algorithm_ picks a _NULL_ out of \(S\) and puts a node that maximizes \(v_{t}=argmax_{v\in V\setminus S_{v-1}}\left[\sigma=\sigma_{tar}(S_{t-1}\ \cup v)-\sigma_{tar}(S_{t-1})\right]\) to \(S\) which is exactly the process done by _General Greedy Algorithm_. That means _Exchangeable Greedy Algorithm_, _which_ has better potential performance than _General Greedy Algorithm_. However, the time complexity can be very expensive. Some strategies must be used to make the algorithm practical. We find that most of nodes cannot make any improvement though they all have potentials. Experimental results in [4] showed that selecting nodes with maximum degrees as seeds results in larger influence spread than other heuristics. This is true because most nodes have less out-degrees according to power-law distribution [32] and are less likely to influence many nodes. ```
Input: network graph \(G\), initial seeds size \(k\) Output:accepted seeds \(S\)
1 Initialize \(S\leftarrow\phi\ R=10000,c=0\);
2 Initialize \(S\) with \(k\) nodes using heuristic algorithms;
3 while\(\sigma_{tar}(S)\) not converge and \(c<m\)do
4 pick one node \(u\) out of \(S\) with heuristic strategies or simply by order;
5\(S=S\backslash\{u\}\);
6 for each node \(v\in V\backslash S\)do
7\(\sigma_{v}=0\);
8 for\(i=1\)to\(R\)do
9\(\sigma_{v}+=\left|\sigma_{tar}(G,S\cup\{v\})\right|\);
10 end for
11\(\sigma_{v}=\sigma_{v}/R\);
12 end for
13\(S=S\cup\{\text{argmax}_{v\in V\backslash S}\sigma_{v}\}\);
14\(c++\);
15 end for
16 return\(S\);
```

**Algorithm 4**\(EG(G,k)\)

Heuristic strategies have lower time complexity but are less effective. Greedy strategies are just the opposite. In this paper, we propose to combine heuristic strategies and greedy strategies by two processes, namely _Sampling_ and _Verification_, to make the algorithm more practical. In each round, we only sample fixed number of candidate nodes (_Sampling_). Once the candidates are produced, we run greedy algorithm to verify the guess (_Verification_). Specially, each node is chosen as a candidate with a _Potential Probability PP_ which will be increased or decreased due to its performance. Initially, the probability \(PP\) of each node is set according to its out-degree. \[PP(v)\propto\ log\ (d_{out}(v)+1) \tag{5}\]

where \(d_{out}(v)\) is the out-degree of node \(v\). Then, \(PP\) is recalculated according to its performance in each round.