Influence maximization based on network representation learning in social network

Abstract

Influence Maximization (IM), an NP-hard central issue for social network research, aims to recognize the influential nodes in a network so that the message can spread faster and more effectively. A large number of existing studies mainly focus on the heuristic methods, which generally lead to sub-optimal solutions and suffer time-consuming and inapplicability for large-scale networks. Furthermore, the present community-aware random walk to analyze IM using network representation learning considers only the node’s influence or network community structures. No research has been found that surveyed both of them. Hence, the present study is designed to solve the IM problem by introducing a novel influence network embedding (NINE) approach and a novel influence maximization algorithm, namely NineIM, based on network representation learning. First, a mechanism that can capture the diffusion behavior proximity between network nodes is constructed. Second, we consider a more realistic social behavior assumption. The probability of information dissemination between network nodes (users) is different from other random walk based network representation learning. Third, the node influence is used to define the rules of random walk and then get the embedding representation of a social network. Experiments on four real-world networks indicate that our proposed NINE method outperforms four state-of-the-art network embedding baselines. Finally, the superiority of the proposed NineIM algorithm is reported by comparing four traditional IM algorithms. The code is available at https://github.com/baiyazi/NineIM.

Keywords

Influence Maximization heuristic algorithms social netwrok network representation learning

1. Introduction

Social media platforms, e.g., Facebook and Weibo, have been playing an increasingly critical role in helping people get knowledge and information [1]. People join multiple platforms, e.g., Facebook and Weibo, to enjoy services, express opinions, and share their own stories, simultaneously. Social networks abstracted from the platform users and their relations are essential for analyzing and predicting network information propagation dynamics.

The Influence Maximization (IM) problem, which aims to recognize the influential users in a social network, has recently attracted substantial research attention due to its practical value in information propagation issues. Perfect examples can be found in such well-recognized small sets of highly influential users as the government Weibo, and opinion leaders in product marketing [2], both of which have provided faster and more effective message propagation power. These specific user sets usually maintain an orderly social network evolution, acting as the suns or moons distributed in a social network.

The goal of IM strategies is to capture the optimal seed set with maximize activated nodes around the set. The primary issue framework of IM can be depicted in a slightly formal way as follows. An initial node-set, denoted by $\mathcal{S}$ , of a social network is selected to spread information using normally information propagations models as Independent Cascade (IC), Linear Threshold (LT), etc. Second, the influence range $\sigma(\mathcal{S})$ of $\mathcal{S}$ represents the expected number of active nodes under the influence of node-set $\mathcal{S}$ . IM model intends to find a set of preset $k$ nodes, which can maximize the final influence range.

The first serious discussions and analyses of IM problems have emerged in [3], which proves that the optimization problem of IM is NP-hard. Furthermore, a greedy approximation algorithm is introduced to guarantee the optimal influence spread ( $1-1/e-\epsilon$ ), where $e$ and $\epsilon$ denote the base of the natural logarithm and a positive real number, respectively. However, this algorithm for solving IM has tended to focus on small-scale networks rather than large ones. To overcome this flaw, the sub-modularity properties are applied to optimize the solution. Leskovec et al. [4] conducted an IM algorithm called Cost-Effective Lazy Forwarding (CELF), concerning the similar sub-modularity properties of the influence function to estimate the influence diffusion. When selecting candidate seed nodes in each iteration of CELF, the re-evaluation of the influence gain for most nodes in a network is not required anymore, thus significantly reducing the influence diffusion’s computing cost. The accuracy of CELF is close to that of the greedy algorithm, yet its running speed is 700 times faster than greedy methods. Goyal et al. [5] further improved the CELF and proposed the CELF $++$ method. Compared with the CELF algorithm, CELF $++$ can reduce the running time by 30%–35%.

The improved greedy algorithm has good performance for the IM problem. Yet this updated method has given rise to a lot of heated debate. Researchers are more concerned about its disadvantages for propagation probability and large-scale social networks. Therefore, much work pays attention to heuristic algorithms. A StaticGreedy heuristic algorithm is proposed by [6], which applies the sub-modularity properties of the IM objective function to select the most influential node, reducing the time cost in candidate nodes selection. Much of the research on heuristic IM solutions has been exploratory by the topology of communities and nodes. e.g., the hybrid heuristic model TBH [7] and the structural-based heuristic algorithms CDH-Kcut and CDH-SHRINK [8]. The community structural features are adopted to avoid information overlap and reduce the number of candidate seed nodes. The excellent technique, usually called Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) [9], considers the minimum overlap and maximum coverage to select the node-set. Some challenges still exist about the data processing with large-scale and structural complexity social networks.

Recent developments in network representation learning have led to a renewed interest in IM studies by deep learning. DeepIM [10] is the first algorithm of employing deep learning techniques for IM problems, which uses the Community Aware Random walk for network Embedding (CARE) [11] to learning the node embedding of a network. A predefined cosine similarity function is offered to measure the similarity between any two nodes. Then, a group of $k$ nodes that are similar to a given node in a network can be recorded. The similarity analysis and the statistic occurrence of $k$ nodes have brought many benefits to capture a high-value seed node set (simplified as seed set). The Network Embedding for Influence Maximization (NE-IM) algorithm is proposed in [12]. The idea of NE-IM is similar to the DeepIM model, which combines the methods SDNE [13] and ASNE [14] to encode structure and attribute information of a node into low-dimensional vector representations, respectively. The integrated vector representation is obtained by contacting the two vectors with node structures and attributes. The final seed nodes set can be established according to the predefined seed node selection strategy.

This paper provides an innovative network representation approach, named Node Influence based Network Embedding (NINE), combining node influence and community factor to learning the low dimensional vector representation of nodes. Few studies have investigated the IM problem in any systematic way of representation learning with node influence. This study attempts to propose feasible local and global measurement approaches for embedding network nodes. An updated random walk strategy is applied to learn the corpus of the contextual representation of nodes in a social network. Then, the vector representation of nodes is learned through the SkipGram algorithm. Subsequently, a seed node selection strategy is performed to select the final nodes set.

The main contributions of our work are as follow:

(1)
Most previous studies have not considered the use of deep learning techniques to solve the IM problem. This paper has provided a deeper insight into applying network representation learning technology in IM issues. Then, a network embedding method NINE and a seed node selection strategy based on deep learning are introduced to fill this gap.
(2)
One of the main obstacles of existing IM solutions using deep learning is that only network structures or attributes are tacked without considering the node influence and community features. A complete understanding of combining the above multi-dimensional information to handle the IM problem is reported.
(3)
The model performance of NineIM is extensively evaluated in four real-world data sets (DBLP, FootBall, NetScience, and Ca-GrQc) with different fields. Experimental results demonstrate the effectiveness of our proposed algorithm.

The rest of the paper is organized as follows. Section 2 briefly reviews related work on IM issues and network representation learning. Section 3 introduces the proposed approach NINE and the subsequent IM model NineIM. Section 4 outlines the experimental results of the proposed method on different datasets. Finally, Section 5 presents the conclusion of this work.
2. Related work

2.1 Influence maximization

Influence maximization (IM) problem was first studied by Domingos and Richardson [2, 15]. As noted by their pioneering work, IM is concerned with probability problems. On top of that, Kempe et al. [16] found that IM can be simulated as a class of discrete optimization problems. Most existing IM algorithms are based on simple greedy computing, traversing the influence range of each node in a network and adding the nodes with greater influence to the seed set. The process is formalized as follows.

$\displaystyle u\leftarrow\textit{arg}\max_{u\in(V\backslash\mathcal{S})}\sigma% (\mathcal{S}\cup{u})-\sigma(\mathcal{S})$ (1)

The final seed set $u$ can be obtained by continuously selecting the nodes with a maximal influence range. However, Previous greedy methods are limited to low efficiency and high time complexity, which are not suitable for large-scale networks. Hence, subsequent studies addressed the scalability and efficiency of the IM problem.

Some heuristic algorithms have gradually entered people’s field of vision on node selections, such as degree analysis [17], PageRank [18], and Distance Centrality [19]. Kimura et al. [20] consider the shortest path between two nodes for measuring the influence degree of each user. Gong et al. [21] designed the IM algorithm PTMA based on the probability transition matrix, which primarily uses the greedy idea to find the first $k$ nodes with greater influence. PTMA improves operating efficiency in a shorter time due to avoid the calculation of the marginal revenue for inactive nodes at every moment.

Recently heuristic algorithms have examined the effects of community structure on solving IM issues. Bozorgi et al. [22] exploit the community structures to find the influential communities in a network. They combine local and global influences of a node to capture the influence nodes in the communities. The method FSIM [23] chooses a limited number of communities as important ones containing the candidate seeds by a measure of betweenness centrality. Wang et al. [24] presented Weighted LeaderRank with Neighbors (WLRN) to rank users in a single community. An Optimal Budget Allocation (OBA) strategy is applied for multiple communities. Heuristic factors found to be influencing IM problems have also been explored in the three studies [25, 26, 27].

Some of the recent IM research has focused on identifying and evaluating the user influences of a social network by using deep learning techniques. Classical examples include DeepIM [10], NE-IM [12], and reinforcement learning-based IM model [28]. The common process of these models is transforming the structure or attribute features of a social network into a low-dimensional vector representation. Using the vector representation of nodes can obtain the final node-set through a predefined seed selection strategy or a vector-specific location tag update strategy.

2.2 Community detection

Community structure is one of the important characteristics of social networks. Community discovery algorithms have been widely used in many fields such as personalized interest recommendation [29] and social network analysis [30]. Notable applications of community discovery include finding user groups with similar interests and detecting academic groups with similar research interests, etc.

Louvain community discovery algorithm [31] has become popular with social network analysis for its simplicity and excellent accuracy. This study set out to use the Louvain algorithm to deal with the IM issues. The primary creative concept of the algorithm is the modularity that can be used to estimate the modularity gain of each node joining other communities. We can determine the community to which the node belongs. Modularity can be formalized as:

$\displaystyle Q=\frac{1}{2m}\sum_{uv}\left(A_{uv}-\frac{k_{u}k_{v}}{2m}\right)% \delta_{uv}$ (2)

where, $m$ represents the sum of edge weights in a social network. $u$ and $v$ are two arbitrary nodes. $A$ is the weighted adjacency matrix of the network. $A_{uv}=0$ denotes that there is no edge between $u$ and $v$ , and vice versa. $k_{u}$ and $k_{v}$ depict the summation of edge weights of node $u$ and node $v$ , respectively. If node $u$ and node $v$ belongs to same community, we have $\delta_{uv}=1$ , otherwise $\delta_{uv}=0$ .

2.3 Network representation learning

Network representation learning, also known as network embedding [32, 33], has attracted great attention in recent years. The central to the entire discipline of social network analysis using deep learning is the technologies of network representation learning. The purpose of the learning is to transform network characteristics into a low-dimensional continuous representation matrix that serves as the algorithm input of machine learning approaches. The learning intention is to preserve network structure and inherent properties to the greatest extent.

Some social network studies are devoted to applying deep learning techniques to learn node embeddings, including DeepWalk [34], LINE [35], and node2vec [36], etc. Sampling random walk makes an important contribution to preserve the features of network structure. The sampling sequences of a social network can be generated through a predefined random walk strategy to obtain a corpus that represents the network structural relationships. Then, the SkipGram model [37] is used for the corpus to learn the node vector representation of the network. Finally, a low-dimensional embedding representation of the nodes in a network is obtained. Although these random walk methods have been proven to achieve better performance in network embedding, these methods neglect the global structure information and the properties of nodes. Therefore, some researchers have begun to combine network exploration strategies with other node properties.

Some scholars have begun to combine node community factors in the process of random walk. Keikha et al. [11], introduced a network embedding algorithm named CARE, trying to preserve the node’s local neighborhood and community information of a network. They apply the SkipGram model to learn the representation vector of network nodes in the corpus obtained by random walks. Gao et al. in [38] proposed a community-oriented attributed network embedding method, which designed a margin-based random walk procedure coupled with flexible margins among communities to limit the scope of random walks. However, they only recognize community information to preserve the global network structure and do not utilize the critical feature, i.e., node structure influence bias. Furthermore, these methods are unstable when the sampling frequency or the number of node sequences changes.

Some scholars consider the process of random walk and information diffusion in social networks. Shi et al. [39] used a diffusion-driven process to capture both depth and breadth information in networks. They stochastic sampling in the process of information cascades diffusion procedure to get an approximation of a network structure information. Zhang et al. [40] achieve a network representation according to a degree-biased random walk method that can well extract network information with much less redundancy. This new type of walk strategy with a high-degree biased backtracking mechanism has given rise to better capture the local and global network structure. The research has tended to focus only on the immediate neighborhood of nodes rather than community information. In addition, no study has been reported that both global network structure and node structure influence bias are preserved in a social network.

Node influence and community factor will be two critical interactive supplements to the network representation learning. Inspired by the above research, this paper establishes a novel random walk algorithm, combining node influence and community factor to obtain the node context corpus. Community structures will be applied, which also play a significant role in random walk processes. The recommended method can preserve both micro-structure and community characteristics to learn more meaningful and differentiated network representations.

3. Methodology

3.1 Measurement of node influence

The studies of IM issue have benefited a lot from a systematic measurement of node influence in a social network. This paper recommends to obtain the influence of an arbitrary node $i$ on node $j$ from its local neighbor information and the global network information. The global information of node $i$ on node $j$ can be calculated by the increment of the shortest path length from node $j$ to all nodes except for node $i$ . The formal definition of global information can be represented as follows:

$\displaystyle\textit{gInf}_{ij}=\frac{|P(G_{j})-P(G_{j}^{\prime})|}{P(G_{j})}$ (3)

where notation $\textit{gInf}_{ij}$ represents the global influence of node $i$ on node $j$ . The parameter $P(G_{j})$ in the numerator and denominator of $\textit{gInf}_{ij}$ denotes the average shortest path length from node $j$ to all nodes except node $i$ in a network $G$ . $P(G_{j})$ can be calculated by the following equation:

$\displaystyle P(G_{j})=\frac{1}{N}\sum_{k\notin\{i,j\},k\in G}s_{jk}$ (4)

where, $N$ is the number of nodes in network $G$ . Notation $s_{jk}$ represents the Dijkstra shortest path length from node $j$ to node $k$ . The edge weight of $G$ is initialized to 1 if not specified. Correspondingly, the parameter $P(G_{j}^{\prime})$ in Eq. (3) denotes the average shortest path length from node $j$ to all nodes except for node $i$ . There exist some nodes in $G$ , which may become isolate after removing the node $i$ . The path value from a node to an isolated one is set to 0 by reflecting the zero probability of information transmission between the nodes.

The calculation of global information $\textit{gInf}_{ij}$ can be illustrated briefly by the example network shown in Fig. 1. We have $\textit{gInf}_{1,10}=0$ and $\textit{gInf}_{10,1}=\frac{6}{7}$ according to Eqs (3) and (4). The values illustrate that the global influence of node 1 on node 10 (resp. node 10 on node 1) is 0 (resp, $\frac{6}{7}$ ). However, the global information result $\textit{gInf}_{1,10}=0$ on the effect between nodes 1 and 10 is not appropriate. There are two common neighbors, i.e., nodes 2 and 3, between nodes 1 and 10. The influence of node 1 on node 10 should be greater than that of other nodes on node 10 by comparing real-life character relationships. This has aroused concern about the local influence of nodes to capture the information of network structure more appropriately. The local information of node $i$ in a social network can be recognized from the comprehending two aspects:

•

People tend to communicate with others who have direct connections. These connected users often referred to as direct neighbors or 1-hop neighbors;

•

People tend to share with people who have common friends.

Some literature regards 2-hop neighbors of nodes as the global information, which are limited to small-scale social networks. The global information of a node should contain full structural features from the node to other ones. This paper believes that both 1-hop and 2-hop neighbors should be recognized as the local information of a node. The novel local information connotation can be exemplified in work undertaken by the example shown in Fig. 1.

Figure 1.

Case network.

Node 10 can be considered as a real role, i.e., a big $V$ user in a microblog network, according to its rich user links. On the other hand, node 1 has a direct 1-hop neighbor relationship with node 10. If we measure the 1-hop relationship between nodes 1 and 10, they are similar. However, node 10 has more optional 1-hop neighbors to deliver messages. 1-hop neighbor measure can not uniquely identify the local information of a node. This study integrates 1-hop and 2-hop features to obtain the local structure information metric of nodes as follows:

$\displaystyle\textit{lInf}_{ij}=D(i)+\frac{|\textit{Nei}(i)\cap\textit{Nei}(j)% |}{|\textit{Nei}(i)\cup\textit{Nei}(j)|}$ (5)

where, $\textit{lInf}_{ij}$ represents the local influence of node $i$ on node $j$ . $D(i)$ is the probability of the information propagation from node $i$ to its 1-hop neighbors. $\textit{Nei}(i)$ denotes the direct neighbors, i.e., 1-hop neighbors, of node $i$ . $\frac{|\textit{Nei}(i)\cap\textit{Nei}(j)|}{|\textit{Nei}(i)\cup\textit{Nei}(j% )|}$ is the Jaccard’s Coefficient with two neighbor sets $\textit{Nei}(i)$ and $\textit{Nei}(j)$ , which value describes the neighbor similarity between nodes $i$ and $j$ . $D(i)$ can be calculated by

$\displaystyle D(i)=\frac{\textit{Nei}(i)}{\sum_{k\in G}\textit{Nei}(k)}$ (6)

The local influence $\textit{lInf}_{ij}$ of a node $i$ on node $j$ is hence evolved to the correlation measure of 2-hop according to Eq. (5).

This study integrates the global and local structure information to get the influence $\textit{Inf}_{ij}$ of node $i$ on node $j$ in the whole network.

$\displaystyle\textit{Inf}_{ij}=\alpha_{1}\textit{gInf}_{ij}+\alpha_{2}\textit{% lInf}_{ij}$ (7)

Mathematical symbols $\alpha_{1}$ and $\alpha_{2}$ are hyper-parameters of $\textit{Inf}_{ij}$ , adjusting the proportion of global and local influences of nodes, respectively. The influence value of a node $i$ on an arbitrary node $j$ in a network can be quickly calculated according to Eq. (7). To get the influence value of node $i$ on its neighbors, we have the following influence-gathering equation:

$\displaystyle\textit{Inf}_{i}=\frac{1}{|N(i)|}\sum_{j\in N(i)}\textit{Inf}_{ij}$ (8)

where $N(i)$ is the neighbor set of node $i$ . The influence value of all nodes in a network can be obtained. Then, these values are normalized using

$\displaystyle\textit{Inf}^{\prime}_{i}=\frac{\textit{Inf}_{i}}{\max(\textit{% Inf}_{i})}$ (9)

We select the degree centrality (DC), closeness centrality (CC), betweenness centrality (BC), and eigenvector centrality (EC) to evaluate the comparative values of our influences by the example shown in Fig. 1. Table 1 shows the results with $\alpha_{1}=0.3$ and $\alpha_{2}=0.2$ , in which all the methods can effectively identify the importance order of nodes to a certain extent. It is apparent from this table that the BC algorithm fails to capture the importance of node 2 or node 3 to other single-degree nodes. As Fig. 1 shows, the structural complexity of node 10 indicates its importance. However, the approaches of DC, CC, and EC can not quantify the whole structural relationship of node 10. Our method contributes to solving this inadequacy.

Table 1

A case study of comparison of calculation results of node influence

Node	DC	CC	BC	EC	Ours
1	0.1364	0.1017	0.0147	0.1349	0.0181
2	0.0909	0.0953	0.0000	0.1096	0.013
3	0.0909	0.0953	0.0000	0.1096	0.013
4	0.0455	0.0897	0.0000	0.0692	0.0022
5	0.0455	0.0897	0.0000	0.0692	0.0022
6	0.0455	0.0897	0.0000	0.0692	0.0022
7	0.0455	0.0897	0.0000	0.0692	0.0022
8	0.0455	0.0897	0.0000	0.0692	0.0022
9	0.0455	0.0897	0.0000	0.0692	0.0022
10	0.4091	0.1694	0.9853	0.2307	0.9425

To combine the node influences with network representation learning, this paper redefines the random-walk sampling strategy for network nodes and then learns the vectorized representation of the network.

3.2 Optimization

As previously stated, the global information of a node $i$ on node $j$ can be calculated by $\textit{gInf}_{ij}$ (Eq. (3)). $P(G_{j})$ is the average shortest path length from node $j$ to other nodes except node $i$ in the network. We must traverse the whole network to get the global influence measure of all nodes. The time complexity of Dijkstra algorithm between two nodes is $O(n^{2})$ . Hence, the time complexity of calculating $\textit{gInf}_{ij}$ will be $O(n^{3})$ for all pair of nodes. This kind of calculations is not suitable for large networks. Therefore, a more detailed of optimizing the calculation of $\textit{gInf}_{ij}$ is given in this section.

Inspired by the PageRank model, we use a similar method to capture the global structure information of the graph. Let $G(V,E)$ be a social network, and $A$ be its adjacency matrix. The diagonal element in each row of the diagonal matrix $D$ represents the degree of every node in $G$ . The first-order probability transition matrix is

$\displaystyle S=D^{-1}A$ (10)

Matrix $S$ can be considered as neighbor nodes that contribute to the representation of a target node through edges. This section introduces a row vector $p_{k}$ , in which the $j$ th entry indicates the probability of reaching the $j$ th vertex after $k$ steps of transitions. The calculation of $p_{k}$ is defined as follows:

$\displaystyle p_{k}=\alpha\cdot p_{k-1}S+(1-\alpha)p_{0}$ (11)

where, $p_{0}$ is the initial 1-hot vector with the value of the $j$ th entry being 1 and all other entries being 0. $p_{k}$ will continue to be updated with the probability of $\alpha$ , and with the probability of $1-\alpha$ to return the original vertex $p_{0}$ . For each node in the network, we can calculate the corresponding $p_{k}$ , representing the global propagation probability for the current node to all network nodes. Let matrix $M$ be the splicing of these $p_{k}$ vectors in the column direction. $M_{ij}$ can be recognized as the global influence of node $i$ on node $j$ . Hence, the equivalent approximation of Eq. (7) can be obtained, i.e.,

$\displaystyle\textit{Inf}_{ij}=\alpha_{1}M_{ij}+\alpha_{2}\textit{lInf}_{ij}$ (12)

3.3 Sampling strategy

Having discussed how to optimize $\textit{Inf}_{ij}$ , turning now to the sampling strategy on random walk. The central purpose of random walk in a network is to learn a node sequence of predetermined sampling schemes and the deliberate length from the starting node $i$ according to specific rules. For example, we can obtain a vertex sequence with the form: $i_{1}\lx@stackrel{{\scriptstyle s}}{{\rightarrow}}i_{2}\lx@stackrel{{% \scriptstyle s}}{{\rightarrow}}i_{3}\lx@stackrel{{\scriptstyle s}}{{% \rightarrow}}\ldots\lx@stackrel{{\scriptstyle s}}{{\rightarrow}}i_{\textit{len}}$ , where $s$ and len represent predetermined sampling strategy and the walk length, respectively.

This paper combines node influence with a random sampling strategy. If a random walk starts from a node $i$ in a network, one of its neighbors (node $j$ ) can be selected, satisfying the probability $P(i,j)=\textit{Inf}_{i,j}$ . At the next step, node $j$ will be a new start node and repeat the walking process until the predefined walk length is satisfied; otherwise, the walk process will be terminated. In other words, the rejection probability of a random walk process can be computed by $1-P(i,j)$ .

It is now well established of a novel backtracking mechanism [40] to simplify the biased sampling strategy of the random walk. First, the approach randomly selects a neighbor $j$ of node $i$ and transit to node $j$ directly. Second, if the rejection condition is satisfied, the mechanism can perform backtracking from node $j$ to node $i$ . As a result, node $i$ will randomly choose from its direct neighbors with probability $1-\textit{Inf}_{i,j}$ and add the current node repeatedly. The node influence-based random walk sampling is emphasized in Alg. 3.3.

[h] : NodeInfRW(G, $v_{i}$ , $\textit{Com}_{v_{i}}$ , $\_\textit{len}$ , $p\_g$ , $p\_l$ ) Input: Network: $G(V,E)$ Start node: $v_{i}$ Node set belonging to the same community with $v_{i}$ : $\textit{Com}_{v_{i}}$ Maximum length of random walk: $\_\textit{len}$ Coefficient of node global influence: $p\_g$ Coefficient of node local influence: $p\_l$ Output: Node sequence of current random walk: walk[1] Initialize the list variable walk to $[\textit{start\_node}]$ $\textit{len}(\textit{walk})<\_\textit{len}$ $i=\textit{walk}[-1]$ Get current node’s neighbors $\textit{len}(\textit{neighbors})>0$ Select $j$ from $i$ ’s neighbors by alias sample Append $j$ to walk $\textit{random}(0,1)<(1-\textit{Inf}_{i,j}(p\_g,p\_l))$ Append $i$ to walkSelect $j$ from members of $i$ ’s community walk $=$ [ $\textit{str}(w)$ for $w$ inwalk] walk

Another critical factor associated with the node influence may be focused on the communities of a social network since users’ interests are different in distinctive communities. The objective is to associate the user’s community information in the process of network embedding. First of all, a random walk sampling based on the node influence is performed. On top of that, the resulting sampling sequences will be input into the SkipGram model for training. Finally, we can obtain the embedding representation of the network structure. The community solution of user influence is already represented in Alg. 3.3. $\textit{Com}_{v_{i}}$ depicts a dictionary type data that maps the community information of each node in a network. The parameter $\alpha$ controls whether the current random walk samples from node $v_{i}$ ’s community. At every step of the walk, sampling is done based on alias sampling, which can be completed in $O(1)$ time complexity.

3.4 Node embedding based on random walk

Algorithm 3.3 generates the training corpus of network nodes by using the biased random walk recommenced in this paper. SkipGram model is applied to learn a representation of nodes, which can predict the co-occurrence conditional probability of the remaining words in a predefined window size. The vector representation of words in the corpus can be obtained by maximizing the probability. Specifically, given a sequence of training words $w_{1}$ , $w_{2}$ , $w_{3}$ , …, $w_{T}$ , the objective of the SkipGram model is to maximize the average log probability as below.

$\displaystyle\max\frac{1}{T}\sum_{t=1}^{T}\sum_{-\textit{win}\leqslant j% \leqslant\textit{win},j\neq 0}\log p(w_{t+j}|w_{t})$ (13)

where win indicates a predefined window size. A greater value of win results in more additional training examples and thus can lead to a higher accuracy. Softmax function is used to approximate the probability distribution of $p(w_{t+j}|w_{t})$ , i.e.,

$\displaystyle p(w_{O}|w_{I})=\frac{\exp{(v_{w_{O}}^{{}^{\prime}T}v_{w_{I}})}}{% \sum_{w=1}^{W}\exp{(v_{w}^{{}^{\prime}T}v_{w_{I}})}}$ (14)

where $v_{w}$ and $v^{\prime}_{w}$ are the word representations of “input” and “output” data, respectively. $W$ is the total number of words in the vocabulary. The detailed procedure of node embedding based on our node influence is given in Alg. 3.4. In addition, Louvain method is applied to detect communities.

[h] : NINE( $G$ , wNum, wLen, win, $d$ ) Input: Network: $G(V,E)$ Maximum length of random walk: wLen Number of nodes in truncated walk: wNum Window length: win Final representation size: $d$ Output: Matrix of node representations: $\Phi\in R^{|V|\times d}$ [1] Initializer walks to empty Initializer parameter $p\_g$ and $p\_l$ Com $=$ $\textit{community\_detection}(G)$ node $u$ in $V$ $\textit{iter}=1$ towNumwalk $=$ NodeInfRW(G, $u$ , $\textit{Com}_{u}$ , wLen, $p\_g$ , $p\_l$ ) Append walk to walksSkipGram( $\Phi$ , walks, win) $\Phi$

3.5 Seed set selection

As explained in Algs 3.3 and 3.4, it is clear that the vector representation, i.e., $\Phi\in R^{|V|\times d}$ , of entire nodes in a network can be obtained. Correspondingly, we can recognize the representation of any node with the shape $1\times d$ . Furthermore, the pearson correlation coefficient between two vectors benefits to measure the relationship between any two nodes. Let $X$ and $Y$ be two random variables and $\rho_{XY}$ be their pearson correlation coefficient. Then, the greater the absolute value of $\rho_{XY}$ , the higher the correlation between $X$ and $Y$ . The detail of $\rho_{XY}$ can be depicted as

$\displaystyle\rho_{XY}=\frac{\textit{Cov}(X,Y)}{\sqrt{D(X)}\sqrt{D(Y)}}=\frac{% E((X-E(X))(Y-E(Y)))}{\sqrt{D(X)}\sqrt{D(Y)}}$ (15)

where $\textit{Cov}(X,Y)$ is the covariance. $\sqrt{D(X)}$ and $\sqrt{D(Y)}$ indicate the standard deviations of $X$ and $Y$ , respectively. Let $\rho_{ij}$ denote the score of the relationship between $v_{i}$ and $v_{j}$ . We denote the average of $\rho_{ij}$ as the integrated influence of $v_{i}$ :

$\displaystyle\rho_{i}=\frac{\sum_{j=0}^{n-1}\rho_{ij}}{n}$ (16)

Finally, the influence of each nodes in the network can be achieved and denoted by $\Psi=\{\rho_{0},\rho_{1},\rho_{2},\ldots,\rho_{n-1}\}$ . According to the predefined $k$ value, this study selects the top- $k$ node list from $\Psi$ as the final seed set $\mathcal{S}$ . The process of seed set selection can be represented by Alg. 3.5.

[h] : NineIM( $G$ , embeddings, $k$ ) Input: Network: $G(V,E)$ The matrix of graph node embedding: embeddings Number of nodes selected: $k$ Output: Node list: seeds[1] Initializer seeds to empty Calculate the correlation by Eq. (15) Get the node final score by Eq. (16) Sort the node by score Get top $k$ node seeds

The connection between the three algorithms proposed in this paper is illustrated as follows. First, the influence matrix Inf of a network should be calculated. Its subscript representation $\textit{Inf}_{ij}$ indicates the influence of node $i$ on node $j$ , which is a probability value from $0-1$ . Then, we perform a biased random walk in the network according to the NodeInfRw proposed in Algorithm 3.3, and obtain the sampling sequence, i.e., training corpus, of the network node. According to the NINE proposed by Algorithm 3.4, the corpus is fed into the SkipGram model for training. Consequently, the vector representation of each node in the network is achieved. Finally, the NineIM algorithm screens top $k$ nodes to get the final set of seed nodes.

4. Experimental evaluation

Aiming to verify the feasibility and effectiveness of the proposed NINE approach, this section mainly conducts the performance comparison experiments with the current state-of-the-art approaches, including DeepWalk [34], node2vec [36], LINE [35], and GraRep [41]. Four public real-world datasets are applied to evaluate our proposed NINE method. This section also conducts extensive evaluations on the proposed seed node selection algorithm. We use the SIR model to simulate the information propagation process and then compare it with the existing evaluations of Degree, Connected Components Heuristic (CCHeuristic) [3], Betweenness Centrality [42], and PageRank [43].

4.1 Dataset description

The following is a brief introduction to the dataset used in this article:

•
DBLP [44].1
¹
http://snap.stanford.edu/data/com-DBLP.html.

DBLP is the computer science bibliography that provides a comprehensive list of research papers in computer science. There are many relationships in this network, such as citation relationships, collaboration relationships, etc. This experiment employs the citation relationship between papers to build social networks that contains 317 thousand nodes and 1.04 million edges.
•
FootBall [45].2
²
http://www-personal.umich.edu/∼mejn/netdata/.

FootBall social network is Newman created based on the American College Football League. The network contains 115 nodes and 1226 edges.
•
NetScience [46]. ${}^{2}$ The NetScience dataset contains a coauthorship network of scientists working on network theory and experiments. A figure depicting the largest component of this network can be found at the URL.3
³
http://www-personal.umich.edu/ mejn/centrality/.

This network contains 1589 nodes and 5484 edges.
•
Ca-GrQc [47].4
⁴
http://snap.stanford.edu/data/ca-GrQc.html.

Ca-GrQc is a collaboration network of Arxiv General Relativity and Quantum Cosmology which is from the e-print arXiv and covers scientific collaborations between authors’ papers submitted to the General Relativity and Quantum Cosmology category. The data covers papers in the period from January 1993 to April 2003. There are 5242 nodes and 14496 edges in this dataset.

Before proceeding to experiments, it is necessary to data pre-processing. First, the size of DBLP is enormous, which is reduced by discovering network communities and repeatedly deleting leaf nodes. The result data set is labeled with DBLP-S that also enjoy the characteristics of the power-law distribution and the high aggregation coefficient. Second, NetScience has many isolated nodes or communities. This work has combined these isolated elements. The largest connected subgraphs are captured. On top of that, we randomly add an edge between any remaining isolated element and its largest connected subgraph to form the final dataset. Third, we extract the maximum interconnection subgraph of Ca-GrQc directly as the final experimental data set. To make the structure of the network closer to the real network structure, the experiment needs first to remove the abnormal value of high node degree in the network. The network structure has typical social network characteristics such as power-law distribution and high aggregation coefficient. The statistics of these data sets are displayed in Table 2.

Table 2
Statistics of datasets used in the experimental, showing the number of nodes #Node, the number of edges #Edge, modularity of graph #Modularity, and the number of community #Com

Dataset #Node #Edge #Modularity #Com

DBLP-S 593 1341 0.875 34

FootBall 115 1226 0.603 9

NetScience 1589 5879 0.931 56

Ca-GrQc 4158 26850 0.844 38

4.2 Evaluation tasks of node embedding

Dataset	#Node	#Edge	#Modularity	#Com
DBLP-S	593	1341	0.875	34
FootBall	115	1226	0.603	9
NetScience	1589	5879	0.931	56
Ca-GrQc	4158	26850	0.844	38

As mentioned in the previous section, this paper proposes a biased random walk sampling strategy based on node influence. Then the SkipGram algorithm is used to learn the embedding representation of a network. This section will evaluate the performance of the NINE embedding algorithm.

4.2.1 Baseline methods

The following baseline methods are introduced to evaluate the comparative performance of the proposed NINE model.

•
DeepWalk [34]. DeepWalk is a representative embedding method to learn the low-dimensional vector representation of social network structure. The algorithm inputs the sequence into the SkipGram model and applies the truncated random walks to learn the vector representation of words through the word co-occurrence relationship.
•
LINE [35]. LINE is the abbreviation of Large-scale information network embedding. The network’s local and global structure information are preserved by using the first-order similarity and the second-order similarity, respectively. The final low-dimensional vector is obtained by simply splicing the representations learned by the two similarities.
•
node2vec [36]. Node2vec is a derivative model of Deepwalk. Through random walk sampling, node2vec combines Depth-First Search (DFS) and Breadth-First Search (BFS) to calculate the transfer probability of nodes to their neighbors. Then, the sequence is also input into the SkipGram model to learn a low-dimensional vector representation for network nodes.
•
GraRep [41]. GraRep is the abbreviation of Learning Graph Representations with Global Structural Information, which uses the idea of matrix factorization to solve the network embedding problem. The procedure applies sparse truncated SVD to learn embeddings for the powers of the PMI matrix that are computed from powers of the normalized adjacency matrix.

4.2.2 Overall performance of node embedding

To validate the performance of NINE, its learned low-dimensional representations of nodes are used to solve a node classification problem. The node label is the same as the tag of the community to which it belongs. The validity of the model can be verified by predicting these node labels. In this section, a popular community discovery algorithm Louvain [31] is performed to calculate the community tags. We consider the following performance metrics: Micro-F1 and Macro-F1 and compare NINE with the four baselines on the node classification task. The proportion of the training set to the data sets varies from 5% to 80%, and the rest of the data is used as a test set. Their values of baseline evaluation metrics on four data sets DBLP-S, FootBall, NetScience, and Ca-GrQc are recorded in Tables 3–6, respectively.

Table 3
The experiment of node classification result on DBLP-S

Metrix	Method	5%	10%	20%	30%	40%	50%	60%	70%	80%
Macro-F1	DeepWalk	0.1661	0.3031	0.5425	0.7029	0.8448	0.8253	0.8579	0.8632	0.8716
	node2vec	0.2312	0.4071	0.6564	0.7437	0.8097	0.8291	0.8477	0.8445	0.8828
	LINE	0.1296	0.1620	0.2560	0.3498	0.4168	0.3995	0.4845	0.4918	0.4575
	GraRep	0.2064	0.3728	0.6012	0.7125	0.7759	0.8101	0.8541	0.8466	0.7348
	NINE	0.3676	0.6155	0.8425	0.9188	0.9372	0.9789	0.9787	0.9708	0.9789
Micro-F1	DeepWalk	0.3262	0.4419	0.6000	0.7379	0.8426	0.8316	0.8529	0.8820	0.8991
	node2vec	0.3191	0.4662	0.6715	0.7379	0.7977	0.8215	0.8277	0.8202	0.8235
	LINE	0.1861	0.2172	0.2778	0.3533	0.3988	0.3939	0.4454	0.4550	0.4621
	GraRep	0.2712	0.4344	0.6168	0.7355	0.7865	0.8181	0.8403	0.8371	0.8403
	NINE	0.4379	0.6910	0.8505	0.9086	0.9325	0.9764	0.9747	0.9679	0.9775

Table 4

The experiment of node classification results on Football

Metrix	Method	5%	10%	20%	30%	40%	50%	60%	70%	80%
Macro-F1	DeepWalk	0.1585	0.5996	0.9270	0.9019	0.9346	0.9410	0.9426	1.0000	1.0000
	node2vec	0.1762	0.3005	0.5062	0.7241	0.7768	0.7801	0.891	0.8746	0.8380
	LINE	0.0835	0.3631	0.4294	0.5505	0.5566	0.7413	0.8404	0.8066	0.7896
	GraRep	0.1758	0.5049	0.8464	0.9212	0.9229	0.9840	0.9654	0.9481	0.9507
	NINE	0.1484	0.4984	0.8342	0.8464	0.8984	0.9627	0.9852	1.0000	1.0000
Micro-F1	DeepWalk	0.3272	0.6923	0.9130	0.9275	0.9275	0.9310	0.9547	1.0000	1.0000
	node2vec	0.3067	0.4119	0.5832	0.7356	0.7669	0.7576	0.8529	0.8652	0.8824
	LINE	0.1636	0.5192	0.5434	0.6049	0.5652	0.7413	0.8043	0.8214	0.8261
	GraRep	0.3818	0.6442	0.8478	0.9135	0.9130	0.9827	0.9565	0.9428	0.9565
	NINE	0.3091	0.6346	0.8261	0.8395	0.8841	0.9483	0.9783	1.0000	1.0000

Table 5

The experiment of node classification results on NetScience

Metrix	Method	5%	10%	20%	30%	40%	50%	60%	70%	80%
Macro-F1	DeepWalk	0.2308	0.3502	0.5476	0.6823	0.7466	0.7895	0.8081	0.8042	0.8309
	node2vec	0.2485	0.3713	0.5842	0.6862	0.7364	0.7821	0.8103	0.8037	0.8032
	LINE	0.1126	0.1377	0.2624	0.3401	0.3938	0.4176	0.4061	0.3953	0.3813
	GraRep	0.3722	0.5546	0.7095	0.8213	0.8621	0.8969	0.9128	0.8930	0.8972
	NINE	0.4812	0.6090	0.7509	0.8343	0.8825	0.9125	0.9342	0.9288	0.9353
Micro-F1	DeepWalk	0.2774	0.4486	0.5943	0.6936	0.7505	0.7861	0.8113	0.8322	0.8522
	node2vec	0.3092	0.4451	0.6218	0.7161	0.7421	0.7849	0.8034	0.8071	0.8176
	LINE	0.1072	0.1467	0.2193	0.2740	0.3134	0.3308	0.3396	0.3732	0.3962
	GraRep	0.4980	0.6925	0.8003	0.8625	0.8909	0.9169	0.9339	0.9350	0.9402
	NINE	0.5901	0.7316	0.8231	0.8796	0.9035	0.9358	0.9512	0.9517	0.9779

Table 6

The experiment of node classification results on CA-GrQc

Metrix	Method	5%	10%	20%	30%	40%	50%	60%	70%	80%
Macro-F1	DeepWalk	0.3690	0.4704	0.6265	0.6617	0.7297	0.7399	0.7415	0.767	0.7656
	node2vec	0.3692	0.4722	0.6278	0.6911	0.7277	0.7435	0.7598	0.7681	0.7412
	LINE	0.2231	0.3027	0.3734	0.4094	0.4388	0.4544	0.4768	0.4843	0.4845
	GraReprap	0.4357	0.5193	0.6822	0.7345	0.7682	0.8202	0.8310	0.8467	0.8482
	NINE	0.6723	0.7459	0.8477	0.8833	0.8947	0.9037	0.9148	0.9246	0.9046
Micro-F1	DeepWalk	0.3639	0.4843	0.5912	0.6410	0.6841	0.6945	0.6989	0.7147	0.7283
	node2vec	0.3556	0.4603	0.5906	0.6458	0.6765	0.6902	0.7007	0.7163	0.7103
	LINE	0.1946	0.2428	0.2876	0.3246	0.3386	0.3458	0.3593	0.3758	0.3882
	GraRep	0.4593	0.5776	0.7003	0.7540	0.7799	0.8177	0.8329	0.8373	0.8497
	NINE	0.6555	0.7528	0.8253	0.8601	0.8769	0.8864	0.8906	0.9030	0.9074

First of all, the results in Table 3 show that NINE outperforms other baseline algorithms in all data divisions at the Micro-F1 and Macro-F1 metrics, which illustrate the effectiveness of our model. On top of that, as can be seen from Table 4, the approaches of DeepWalk and node2vec perform well on the dataset Football. However, when the dataset is divided into 60%, 70%, and 80%, NINE offers excellent performance in the node classification task. All the methods have reliable performance improvements with increased proportions of the training set. Among them, DeepWalk and NINE are more prominent.

Tables 5 and 6 show the results of classification experiments on datasets NetScience and CA-GrQc, respectively. The most striking result from the tables is that adding node influences to the network embedding can achieve optimal performance compared with the state-of-art methods in the node classification task.

This section outlines the experimental parameter setting. Specifically, the node global and local influence parameters are $\alpha_{1}=0.3$ and $\alpha_{2}=0.2$ , respectively. The dimension of output representation is $d=128$ . The random walk max length satisfies $\textit{wLen}=80$ . The walk number serves $\textit{wNum}=10$ . The window lenght size is $d=5$ .

4.3 Evaluation tasks of node influences

The benefits of node influences are clearly supported by the proposed seed set selection algorithm based on NINE. As discussed above, we can get the vector representation of each node’s predefined dimensions through the random walk sampling and the SkipGram model. The final score of the nodes in a network can be calculated by vector correlation computing. The predefined number of seed nodes can be placidly selected by Alg. 3.5. This section chooses the Degree, CC-Heuristic, Betweenness Centrality, and PageRank Centrality algorithms as the baselines to evaluate the propagation influence capacity of the final seed set obtained by Alg. 3.5.

Figure 2.

The number of node influence on seed set under different datasets.

Figure 3.

The number of influence propagation of seed set in different datasets.

4.3.1 Baseline methods

•
Degree. Degree method sorts the nodes based on the node’s degree in a graph and returns the top $k$ nodes with the maximal degree.
•
CC-Heuristic [3]. CC-Heuristic is a heuristic-based algorithm to obtain connected components for an undirected graph. The main idea of the CC-Heuristic is to remove an edge from the original graph with a certain probability and calculate the connected components of the graph. Then, the method updates the node weight values with the reciprocal 1/2 power of the component size. The update process is repeated $R$ times to get the node scores. Consequently, we can select the top $k$ nodes.
•
Betweenness Centrality [42]. Betweenness centrality is one of the essential measurement parameters of network centrality in social networks. The betweenness centrality of a particular node is the statistics of shortest paths between all node pairs in a network through the node. A higher betweenness centrality value indicates a further quantity of the shortest paths through the node.
•
PageRank Centrality [43]. PageRank centrality measures the features of a network structure, which is initially developed to evaluate the importance of web pages by their link structures. Subsequently, various study fields such as social network analysis, link prediction, and recommendation benefit from the technology of PageRank.

4.3.2 Overall performance of node influences

NineIM algorithm (Alg. 3.5) achieves the correlation degree calculations between node pairs and an immeasurable selection of a seed set. This part evaluates the performances of the NineIM algorithm concerning the choice of a seed set. SIR model and the well-established seed set are applied to illustrate the algorithm performance with respect to the simulation of information propagation processes.

Figure 4.

The number of influence propagation of seed set in NetScience dataset under different parameters of the SIR model.

In a SIR model, the initial state of the seed nodes and the rest nodes of a network in the influence maximization problem is denoted by the capital $I$ (Infected) and $S$ (Susceptible), respectively. These nodes evolve according to the rules of the SIR model during the propagation process. The number of nodes belonging to the $R$ (Recovered) state in the final network is used as the influence propagation measurements of the initial seed set. The SIR process has been run 500 times for a more accurate evaluation, and the average number of $R$ nodes is reported as the influence range of the seed set.

We select Degree, CC-Heuristic, Betweenness Centrality, and PageRank Centrality on four date sets, including DBLP-S, FootBall, NetScience, and Ca-GrQc as baseline methods to assess the comparative performance of the proposed NineIM. Figure 2 depicts the number of node influences on seed set under different datasets. The proposed NineIM achieves the optimal performance at the datasets DBLP and FootBall, which possesses the sub-optimal performance compared with the traditional IM algorithm in the datasets NetScience and CA-GrQc.

This section also uses Alg. 3.5 to capture the seed set in the baseline network embedding methods. The infection and recovery coefficients of the SIR simulation propagation process are set to 0.07 and 0.136, respectively. The experimental results shown in Fig. 3 illustrate that the network representation learning algorithm proposed in this paper has a broader influence propagation in the final SIR simulation and has achieved excellent results.

Moreover, we compare the network coverage of seed sets which are obtained by NineIM under different infection and recovery coefficients of the SIR model in NetScience dataset. In the experiment, the number of seed nodes is set at 50, and the influence propagation under different infection and recovery coefficients is tested. As shown in Fig. 4, the influence spread of NineIM algorithms has risen with the growth of infection coefficient or decrease of recovery coefficient. In the lower infection coefficient or higher recovery coefficient, there is less opportunities to diffuse influence because each edge has small chances to an active destination node, whereas, in higher lower recovery coefficient or higher infection coefficient, a considerable number of users can be affected by the seed set which is chosen by NineIM.

5. Conclusion

Finding a group of users with a significant influence in a social network has been playing an increasingly important role in helping people transfer particular information or promote specific products. A growing number of prestigious sociologists and artificial intelligence scholars around the world have started to post their excellent ideas on the IM problem. The present study was designed to solve the IM problem by introducing a novel influence maximization algorithm NineIM based on network representation learning. NineIM applies network representation learning technologies to obtain the low-dimensional vector representations of nodes in a social network. Local and global influences of network nodes are combined, and the community structure information is also added and tackled to enrich the embedding features of the nodes. As a result, a seed set selection algorithm with good performance can be deduced according to the idea of the proposed NINE. Extensive experiments conducted on four real-world networks show that NINE and NineIM have an excellent performance on both tasks. The Macro-F1 and Micro-F1 scores of NINE in the data sets increase by at least 3% or equal at the complete data sets compared with existing state-of-the-art NE baselines. As the result, the influence spread score of NineIM is better than or similar to the baseline method in the article.

This study still has some limitations worthy of future research. First, NINE is designed to capture the structural characteristics of nodes. We will extend this research to attribute networks in the future because users usually have rich attribute characteristics in social networks. Second, NINE is designed for static network settings. However, social networks in real life are constantly changing, and we will consider the support of dynamic networks in the future. Finally, In the NineIM algorithm ignores the competition problems in reality. In the end, we will consider using the feature of node attributes to enhance NINE performance and study how to apply NineIM to consider competitors.

Footnotes

Acknowledgments

This work is supported by the National Natural Science Foundation (Nos. 61902324, 11426179, and 61872298), the Social Science Planning Project of Sichuan Province (No. SC20TJ020), the Xihua University Graduate Innovation Fund 2020 (Grant Nos. ycjj2020098, YCJJ2020023), the Science and Technology Program of Sichuan Province (nos. 2021YFQ0008, 2020JDRC0067, 2019GFW131), the Foundation of Cyberspace Security Key Laboratory of Sichuan Higher Education Institutions (no. sjzz2016-73), the Scientific Research Fund of Sichuan Provincial Education Committee (nos. 15ZB0134 and 17ZA0360), and the Open Fund Project of Xihua University (Nos. 20170410143123, szjj2015-059).

References

Gong

Chen

Wang

and Zhou

, Structural hole-based approach to control public opinion in a social network, Engineering Applications of Artificial Intelligence 93 (2020), 103690.

Domingos

and Richardson

, Mining the network value of customers, in: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 57–66.

Kempe

Kleinberg

and Tardos

É.

, Maximizing the spread of influence through a social network, in: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, pp. 137–146.

Leskovec

Krause

Guestrin

Faloutsos

VanBriesen

and Glance

, Cost-effective outbreak detection in networks, in: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007, pp. 420–429.

Goyal

and Lakshmanan

L.V.

, Celf

++

: optimizing the greedy algorithm for influence maximization in social networks, in: Proceedings of the 20th International Conference Companion on World Wide Web, 2011, pp. 47–48.

Cheng

Shen

Huang

Zhang

and Cheng

, Staticgreedy: solving the scalability-accuracy dilemma in influence maximization, in: Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, 2013, pp. 509–518.

Hao

and Yitong

, Threshold-based heuristic algorithm for influence maximization, Journal of Computer Research and Development 49(10) (2012), 2181.

Cao

Wang

and Hu

, OASNET: an optimal allocation approach to influence maximization in modular social networks, in: Proceedings of the 2010 ACM Symposium on Applied Computing, 2010, pp. 1088–1094.

Zareie

Sheikhahmadi

and Khamforoosh

, Influence maximization in social networks based on TOPSIS, Expert Systems with Applications 108 (2018), 96–107.

10.

Keikha

M.M.

Rahgozar

Asadpour

and Abdollahi

M.F.

, Influence maximization across heterogeneous interconnected networks based on deep learning, Expert Systems with Applications 140 (2020), 112905.

11.

Keikha

M.M.

Rahgozar

and Asadpour

, Community aware random walk for network embedding, Knowledge-Based Systems 148 (2018), 47–54.

12.

Zhan

Zhuo

and Liu

, Social Influence Maximization for Public Health Campaigns, IEEE Access 7 (2019), 151252–151260.

13.

Wang

Cui

and Zhu

, Structural deep network embedding, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 1225–1234.

14.

Liao

Zhang

and Chua

T.-S.

, Attributed social network embedding, IEEE Transactions on Knowledge and Data Engineering 30(12) (2018), 2257–2270.

15.

Richardson

and Domingos

, Mining knowledge-sharing sites for viral marketing, in: Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002, pp. 61–70.

16.

Kempe

Kleinberg

and Tardos

, Maximizing the Spread of Influence through a Social Network, Association for Computing Machinery, New York, NY, USA, 2003, 137–146. ISBN 1581137370. doi: 10.1145/956750.956769.

17.

Rachman

Z.A.

Maharani

et al., The analysis and implementation of degree centrality in weighted graph in Social Network Analysis, in: 2013 International Conference of Information and Communication Technology (ICoICT), IEEE, 2013, pp. 72–76.

18.

Langville

A.N.

and Meyer

C.D.

, Google’s PageRank and beyond: The science of search engine rankings, Vol. 30, Princeton university press, 2011, 68–69.

19.

Vega-Oliveros

D.A.

Gomes

P.S.

E. Milios

and Berton

, A multi-centrality index for graph-based keyword extraction, Information Processing & Management 56(6) (2019), 102063.

20.

Kimura

and Saito

, Tractable models for information diffusion in social networks, in: European Conference on Principles of Data Mining and Knowledge Discovery, Springer, 2006, pp. 259–271.

21.

Zhang

P.Y.

and Gong

X.W.

, Influence Maximization Algorithm in Social Network Based on Probability Transfer Matrix, Computer Engineering, 2013, 41–45.

22.

Bozorgi

Haghighi

Zahedi

M.S.

and Rezvani

, INCIM: A community-based algorithm for influence maximization problem under the linear threshold model, Information Processing & Management 52(6) (2016), 1188–1199.

23.

Bagheri

Dastghaibyfard

and Hamzeh

, FSIM: A fast and scalable influence maximization algorithm based on community detection, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 26(03) (2018), 379–396.

24.

Wang

Tong

Fan

Wang

and Wang

, Multi-Community Influence Maximization in Device-to-Device social networks, Knowledge-Based Systems 221 (2021), 106944.

25.

Gong

Liu

and Bai

, Efficient parallel computing on the game theory-aware robust influence maximization problem, Knowledge-Based Systems 220 (2021), 106942.

26.

Aldawish

and Kurdi

, A modified degree discount heuristic for influence maximization in social networks, Procedia Computer Science 170 (2020), 311–316.

27.

Kianian

and Rostamnia

, An efficient path-based approach for influence maximization in social networks, Expert Systems with Applications 167 (2021), 114168.

28.

Tian

Wang

and Peng

, Deep reinforcement learning-based approach to tackle topic-aware influence maximization, Data Science and Engineering 5(1) (2020), 1–11.

29.

Qian

Feng

Zhao

and Mei

, Personalized recommendation combining user interest and social circle, IEEE Transactions on Knowledge and Data Engineering 26(7) (2013), 1763–1777.

30.

Camacho

, Ángel Panizo-LLedot Bello-Orgaz

Gonzalez-Pardo

and Cambria

, The four dimensions of social network analysis: An overview of research methods, applications, and software tools, Information Fusion 63 (2020), 88–120.

31.

Blondel

V.D.

Guillaume

J.-L.

Lambiotte

and Lefebvre

, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment 2008(10) (2008), P10008. doi: 10.1088/1742-5468/2008/10/p10008.

32.

Cui

Wang

Pei

and Zhu

, A survey on network embedding, IEEE Transactions on Knowledge and Data Engineering 31(5) (2018), 833–852.

33.

Cai

Zheng

V.W.

and Chang

K.C.-C.

, A comprehensive survey of graph embedding: Problems, techniques, and applications, IEEE Transactions on Knowledge and Data Engineering 30(9) (2018), 1616–1637.

34.

Perozzi

Al-Rfou

and Skiena

, Deepwalk: Online learning of social representations, in: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014, pp. 701–710.

35.

Tang

Wang

Zhang

Yan

and Mei

, Line: Large-scale information network embedding, in: Proceedings of the 24th International Conference on World Wide Web, 2015, pp. 1067–1077.

36.

Grover

and Leskovec

, node2vec: Scalable feature learning for networks, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 855–864.

37.

McCormick

, Word2vec tutorial-the skip-gram model, Apr-2016. [Online]. Available: http://mccormickml.com/ 2016/04/19/word2vec-tutorial-the-skip-gram-model, 2016.

38.

Gao

Gong

Xie

and Zhong

, Community-oriented attributed network embedding, Knowledge-Based Systems 193 (2020), 105418.

39.

Shi

Lei

Yang

and Niu

, Diffusion network embedding, Pattern Recognition 88 (2019), 518–531.

40.

Zhang

Shi

Feng

and Zhan

X.-X.

, Degree-biased random walk for large-scale network embedding, Future Generation Computer Systems 100 (2019), 198–209.

41.

Cao

and Xu

, Grarep: Learning graph representations with global structural information, in: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 2015, pp. 891–900.

42.

Grobelny

B.T.

London

Hill

T.C.

North

Dugan

and Doyle

W.K.

, Betweenness centrality of intracranial electroencephalography networks and surgical epilepsy outcome, Clinical Neurophysiology 129(9) (2018), 1804–1812.

43.

Gleich

D.F.

, PageRank beyond the Web, Siam REVIEW 57(3) (2015), 321–363.

44.

Yang

and Leskovec

, Defining and evaluating network communities based on ground-truth, Knowledge and Information Systems 42(1) (2015), 181–213.

45.

Girvan

and Newman

M.E.

, Community structure in social and biological networks, Proceedings of the National Academy of Sciences 99(12) (2002), 7821–7826.

46.

Newman

M.E.

, Finding community structure in networks using the eigenvectors of matrices, Physical Review E 74(3) (2006), 036104.

47.

Leskovec

Kleinberg

and Faloutsos

, Graph evolution: Densification and shrinking diameters, ACM Transactions on Knowledge Discovery from Data (TKDD) 1(1) (2007), 2-es.

48.

Chen

Fang

Wang

and Huang

, A Node Embedding-Based Influential Spreaders Identification Approach, Mathematics 8(9) (2020), 1554.

Influence maximization based on network representation learning in social network

Abstract

Keywords

1. Introduction

2.1 Influence maximization

3. Methodology

3.1 Measurement of node influence

3.4 Node embedding based on random walk

4.1 Dataset description

4.2.1 Baseline methods

Table 3 The experiment of node classification result on DBLP-S

Footnotes

Acknowledgments

References

Table 3
The experiment of node classification result on DBLP-S