# Influence Maximization in Social Network Considering Memory Effect and Social Reinforcement Effect
## 4 Algorithms
### General Greedy Algorithm
And for both _CA-GrQc_ and _NetHEPT_, the results of \(EG\)-\(SV\) converge reasonably well for \(m\geq 2\). The results of _Degree_ and _DD_ are worse than \begin{table}
\begin{tabular}{c c} \hline \hline
**Algorithms** & **Time Complexity** \\ \hline \(GG\) & \(O(kNT)\) \\ \(EG\)-\(SV\) & \(O(knnT)\) \\ \(DD\) & \(O(kE)\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Time complexities of algorithms in this paper. Figure 2: Accepted probability of Social Reinforcements in DCM4 VM. those of _EG-SV_ and _GG_. _DD_ performs much better than _Degree_ in _CA-GrQc_ but sometime performs worse than _Degree_ in _NetHEPT_. The possible reason may be that we hope the overlaps of all seeds' propagation coverage areas to be as little as possible in traditional _influence maximization_ problem. However, the propagation coverage overlaps in the new problem may result in more _accepted_ nodes for the affection of _social reinforcement_ effect. So, we encourage propagation coverage overlaps to some extent. As a result, _Degree Discount_ heuristic is not effective anymore and is likely to work even worse than _Degree_ sometimes (see Figure 3d). From Figure 3c,d, we can explain a realistic phenomenon in viral marketing that why _microblogging marketing_ through celebrities is not as good as expected usually. Most celebrities have a lot of fans, which means the celebrity nodes in social networks have high out-degrees. Selecting them as the seeds is the same as what _Degree_ heuristic or _DD_ does. Although _Degree_ heuristic or _DD_ can influence a lot of nodes (See Figure 3c, even more than _EG-SV_), the final _accepted_ nodes of them are much less than that of _EG-SV_ (See Figure 3d). This is because the fans of a celebrity seldom know each other. Most fans only get the information once in the propagation and have less probability to turn to _accepted_ state. In other words, _social reinforcement effect_ can hardly happen during such information propagation process which lowers the number of final _accepted_ nodes. Figure 3: _Cont._

## 6 Comparison of Propagation Performance

In order to illustrate the effectiveness of the algorithm proposed in this paper in the propagation process, this part compares the DCM4 VM method proposed in this paper with the information spreading model based on relative weight in social network (RWSIR) [33]. ### Experimental Data

In this paper, three network topologies of most popular online social network are selected, such as, Twitter [34], sina microblog [35] and Epinions [36], and the relevant data are all from Internet resources [37; 38]. We assume that the edges of each network are indirect and powerless, and the relevant topological characteristic parameters of each network are shown in Table 2. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Network** & **Node** & **Side** & **Average** & **Maximum** & **Clustering** & **Correlation** \\
**Name** & **Number** & **Number** & **Node Degree** & **Node Degree** & **Coefficient** & **Coefficient of Degree** \\ \hline Epinions & 22,437 & 212,970 & 9.49 & 2031 & 0.09717 & 0.052 \\ Twitter & 145,942 & 203,152 & 1.392 & 7079 & 0.00014 & \(-\)0.1114 \\ Sina microblog & 146,091 & 205,408 & 1.406 & 2000 & 0.00024 & \(-\)0.2446 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Correlated characteristic parameters of each network. Figure 3: Interested and Accepted Nodes: (**a**) Interested Nodes P = 0.05 in CA-GrQc (**a,b**); (**b**) Accepted Nodes with P = 0.05 in CA-GrQc (**a,b**); (**c**) Interested Nodes with P = 0.1 in NetHEPT (**c,d**); (**d**) Accepted Nodes with P = 0.1 in NetHEPT (**c,d**). ### Experimental Parameters

In this section, two models, DCM4 VM and RWSIR, are simulated in the above three network topological models. A random node with low connectivity is selected as the propagation node, and the rest nodes are healthy nodes. Considering the network sizes, the connection degrees of Epinions network, Twitter network and sina microblog are 5, 10 and 10.