# Influence Maximization in Social Network Considering Memory Effect and Social Reinforcement Effect
## 4 Algorithms
### General Greedy Algorithm
\[\sigma=\sigma_{tar}(S\ \cup\{v\})-\sigma_{tar}(S\ \cup\{u\});\]

\[r=\frac{|\sigma|}{\sigma_{tar}(S\ \cup\{v\})};\]

\[\alpha=\frac{1}{2}\bigg{|}log\frac{1-r}{r}\bigg{|};\]

\[PP(v)\propto PP(v)e^{-\alpha};if\ \sigma<0;\]

\[PP(v)\propto PP(v)e^{-\alpha};if\ \sigma>0;\]

where \(\sigma=\sigma_{tar}\ (S\cup\{v\})-\sigma_{tar}\ (S\cup\{u\})\) is the increased or decreased _accepted_ nodes exchanging \(u\) with \(v\). The more potential a node has, the more likely it is to be selected. With enough iteration, every node has the chance to improve the result. The heuristic update strategy of \(PP\) is very important. If the strategy is good enough, then it is expected to approximate the optimal solution effectively. This is more like the idea of _boosting_ in machine learning literature which increases the weights of misclassified data and decreases the weights of correctly classified data by last classifier. The _Exchangeable Greedy with Sampling and Verification Algorithm_ is described in Algorithm 5. ```
Input: network graph \(G\), initial seeds size \(k\), number of iterations \(m\), number of nodes sampled each time \(n\) Output: accepted seeds \(S\)
1 Initialize \(S\leftarrow\phi\ R=10000,c=0\);
2 Initialize \(S\) with \(k\) nodes using heuristic algorithms;
3 Initialize \(RC\) according to (5);
4 while\(\sigma_{tar}(S)\) not converge and \(c<m\)do
5 pick one node \(u\) out of \(S\) with heuristic strategies or simply by order;
6\(S=S\{u\}\);
7 Sampling stage:
8 sample \(|RS|=n\) out of \(RC\) randomly;
9 Verification stage:
10 for each node \(v\in RS\)do
11\(\sigma_{v}=0\);
12 For\(i=1\) to \(R\)do
13\(\sigma_{v}+=\big{|}\sigma_{tar}(G,S\cup\{v\})\big{|}\);
14 end for
15\(\sigma_{v}=\sigma_{v}/R\);
16 update \(RC\) according to (6);
17 end for
18\(v^{+}=\operatorname*{argmax}_{v\in V\backslash S}\{\sigma_{v}\}\);
19\(S=S\cup\{v^{+}\}\);
20 remove \(v^{+}\) from \(RC\);
21\(c++\);
22 end for
23 return\(S\);
```

**Algorithm 5**\(EG-SV(G,k,m,n)\)Time complexities of all algorithms in this paper are summarized in Table 1 for convenience of comparison. \(N\) is the number of nodes, \(E\) is the number of edges and \(T\) is the time complexity of _Propagation Simulation_. Note that \(m|n\) is much less than \(N\) usually and the time complexity of \(EG\)-\(SV\) is independent of the size of the network which means we can apply \(EG\)-\(SV\) to large networks. Also, we can continue a terminated \(EG\)-\(SV\) until a good performance is achieved. ## 5 Experiment

In order to show the effectiveness of the algorithm proposed in this paper, experiments are carried out to improve the algorithm. We summarize our experiment results for different algorithms and discuss their performance in this section. ### Analysis of DCM4 VM

As explained in a comprehensive way, we modified the _Degree Discount_ heuristic algorithm to solve the viral marketing problem under _DCM4 VM_, described as Algorithm 3. Figure 2 shows the _accepted_ probability as a function of \(m1\) and \(m2\), given different \(r1\) and \(r2\). Larger \(r1\) and \(r2\) indicate stronger social reinforcement. And considering _accepted_ neighbors' are more influential than _interested_ neighbors', so \(r2\) should be larger than \(r1\). In this paper, \(r1\) is set to \(0.2\) and \(r2\) is set to \(0.5\). \(P_{v}^{in}\) and \(P_{v}^{max}\) are set to \(0.1\) and \(0.8\) respectively, which has been tested many times. ### Analysis of Algorithms

The networks used in this paper are _Arxiv CA-GrQc_[4] and _NetHEPT_[17] which are frequently used in current researches. We use fixed propagation probability \(P\) in the experiments. And in order to make the results more discriminative, we set \(P\) to \(0.05\) and \(0.1\) in _CA-GrQc_ and _NetHEPT_ respectively. For \(EG\)-\(SV\), \(n\) is set to \(100\), \(m\) is tried from \(1\) to \(5\). The experiment results are shown in Figure 3. \(GG\) is too complex to run in _NetHEPT_. Overall, the performance of \(EG\)-\(SV\) (\(m\geq 2\)) is almost the same as \(GG\).