# A Hierarchical Generative Embedding Model for Influence Maximization in Attributed Social Networks
## 4 The Proposed Method
### HGE-GA Algorithm  
It has been proposed by previous work on social network influence [20] that the more equivalent the network structure of two nodes is, the more likely they make similar judgments, even without an edge between them, because these two nodes connect to other nodes more identically. It has also been revealed by previous studies on social networks that the opinions and behaviors of nodes are affected by node attributes [20], i.e., similar attributes of nodes cause similar behaviors. Therefore, the similarity of network structures and node attributes are the two factors underlying the influence probability between two nodes. We measure the similarity of node pairs and predict the influence probability of node pairs with the embedding of nodes inferred from the proposed HGE model. With the predicted influence probability of node pairs, we utilize a general greedy strategy to compute the top-K influential nodes in the network. The proposed HGE-GA algorithm is outlined in Algorithm 1, and will be detailed in this subsection.  
```
0: social network \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{A})\), the embeddings of all nodes \(\mathbf{\Phi}\), seed set size \(K\).
0: Seed node set \(\mathcal{S}\).
1: predicts influence probability of arbitrary pairwise nodes, \(p_{u,v}\);
2:for\(j=1\dots K\)do
3:\(u^{*}\leftarrow\operatorname*{arg\,max}_{u^{*}\in\mathcal{U}}\sigma(\mathcal{ S}\cup u^{*})-\sigma(\mathcal{S})\);
4:\(\mathcal{S}=\mathcal{S}\cup u^{*}\);
5:endfor
6:return\(\mathcal{S}\);
```  
**Algorithm 1** HGE-GA Algorithm  
Traditional network representation methods embed nodes into a low-dimensional vector space, and they always use the inner product to measure the similarities of node pairs. Then the relationships between node pairs can be captured. However, this method cannot capture the relationships among neighborhoods of nodes in some cases. As shown in Figure 5, for a node \(v_{1}\) and its two neighborhoods \(u_{1}\) and \(u_{2}\), two relationships are represented, as follows:  
\[v_{1}\cdot u_{1} = v_{1}\cdot u_{2},\] \[u_{1}\cdot u_{2} = 0 \tag{22}\]  
As neighbors of node \(v_{1}\), nodes \(u_{1}\) and \(u_{2}\) are similar in attributes, but the method based on the inner product cannot capture the relationship between \(u_{1}\) and \(u_{2}\) in the latent space. Similarly, the relationship between node \(v_{1}\) and \(v_{2}\) can not be captured by using the inner product.  
To avoid the case shown in Equation (26), we use the two-normal form, which satisfies the critical triangle inequality. The norm of a vector can simply be understood as its length or the corresponding distance between two points. The two-normal form is a common way to measure distance between vectors. Using the two-normal form, we define the relationship between node \(i\) and node \(j\) as follows:  
\[g(\mathbf{\Phi}_{i},\mathbf{\Phi}_{j})=\left\|\mathbf{\Phi}_{i}-\mathbf{\Phi}_{j}\right\|_{2} \tag{23}\]  
The above relationship with the two-normal form adequately captures the similarity of two nodes. We regard the similarity of two nodes as the influence probability between two nodes, since the similarity of the network structure and node attributes are the two factors underlying the influence probability between two nodes. Thus, the influence probability between node \(i\) and \(j\), i.e., \(p_{i,j}\) can be predicted as follows.  
\[p_{i,j}=g(\mathbf{\[PERSON]}_{i},\mathbf{\[PERSON]}_{j})=\left\|\mathbf{\[PERSON]}_{i}-\mathbf{\[PERSON]}_{j} \right\|_{2} \tag{24}\]  
After obtaining the influence probability of arbitrary pairwise nodes, under a general independent cascade (IC) diffusion model, we utilize a general greedy strategy to compute the top-K influential nodes, as Algorithm 1 shows.