# Substitute Seed Nodes Mining Algorithms for Influence Maximization in Multi-Social Networks
## 4 Substitutes Mining Algorithms for SMMNIM
### Similar-Users-Based Substitutes Mining Algorithm for SMMNIM (S_S)  
In this section, we propose another solution to find substitutes based on the idea of \"finding the most similar user of uncooperative user\". We focus on seeking the most similar users of the uncooperative nodes as the substitutes and propose a similar-users-based substitutes mining algorithm for SMMNIM (S_S), which is shown in Algorithm 4. We integrate structure similarity and neighbor attribute similarity to evaluate the similarity between two users.  
Given an aggregation graph \(G^{*}(V^{*},E^{*})\) of multi-social networks, \((u,v)\in E^{*}\) indicates the edge from node \(u\) to node \(v\). The structure of the node \(u\) is determined by the in-edges and out-edges of the node.  
\(O\_E(u)\) indicates the out-edges and be defined as  
\[O\_E(u)=\{v\in V^{*}\big{|}\left(u,v\right)\in E^{*}\}. \tag{4}\]  
\(I\_E(u)\) indicates the in-edges and be defined as  
\[I\_E(u)=\{w\in V^{*}\big{|}\left(u,v\right)\in E^{*}\}. \tag{5}\]  
The structure of the node \(u\) is defined as  
\[\Psi(u)=(O\_E(u),I\_E(u)). \tag{6}\]  
The structural similarity of node \(u\) and node \(v\) is defined as  
\[SS(u,v)=\frac{1}{2}\Bigg{(}\frac{\big{|}O\_E(u)\cap O\_E(v)\big{|}}{\sqrt{ \big{|}O\_E(u)\big{|}*\big{|}O\_E(v)\big{|}}}+\frac{\big{|}I\_E(u)\cap I\_E(v )\big{|}}{\sqrt{\big{|}I\_E(u)\big{|}*\big{|}I\_E(v)\big{|}}}\Bigg{)}. \tag{7}\]  
The self-spread of a _Bridge User_ makes it more likely to have a wider scope of influence spread than ordinary users. When choosing the most similar user of the uncooperative user, the other factor we need to consider is the similarity of neighbor attributes (_Bridge Users_ or ordinary users).  
In the neighbor node set of node \(u\), the number of _Bridge Users_ is denoted as \(B\_U(u)\), and the number of ordinary users is denoted as \(N\_U(u)\). The neighbor node attributes of node \(u\) are defined as vectors  
\[\mathbb{A}(u)=(B\_U(u),N\_U(u)). \tag{8}\]  
The Euclidean distance of the neighboring attributes of \(u\) and \(v\) is  
\[ED\_\mathbb{A}(u,v)=\sqrt{(\mathbb{A}(u)-\mathbb{A}(v))(\mathbb{A}(u)-\mathbb{ A}(p))^{T}}. \tag{9}\]  
Then we define the neighbor attributes similarity between node \(u\) and \(v\) is  
\[AS(u,v)=\frac{ED\_\mathbb{A}(u,v)-ED\_\mathbb{A}_{min}}{ED\_\mathbb{A}_{max}- ED\_\mathbb{A}_{min}} \tag{10}\]  
Finally, the similarity between node \(u\) and \(v\) is based on the similarity calculated by the structure similarity and the neighbor attributes similarity,  
\[Sim(u,v)=SS(u,v)+AS(u,v). \tag{11}\]  
```
Input:\(G^{*}(V^{*},E^{*})\), seed node set \(S\), the subset of seed nodes that can be activated \(S_{1}\), the subset of seed nodes that cannot be activated \(S_{2}\); Output: New initial seed seeds set \(S^{\prime}\); (1) \(S^{\prime}=S_{1}\); (2) \(R(\mathbb{S})\): The number of active nodes obtained by \(S\); (3) for \(i=1\) to \(|S_{2}|\) (4) for \(u\) in \(S_{2}\) (5) for \(v\) in \(V^{*}/S\) (6) select \(v=argmax(Sim(u,v))\) (7) \(S^{\prime}=S^{\prime}\cup v\) (8) end for (9) end for (10) end for (11) Output \(S^{\prime}\);
```  
**Algorithm 4**Similar-users-based Substitutes Mining Algorithm for SMMNIM (S_S).