Influence Maximization Based on Backward Reasoning in Online Social Networks

Abstract

Along with the rapid development of information technology, online social networks have become more and more popular, which has greatly changed the way of information diffusion. Influence maximization is one of the hot research issues in online social network analysis. It refers to mining the most influential top-$K$ nodes from an online social network to maximize the final propagation of influence in the network. The existing studies have shown that the greedy algorithms can obtain a highly accurate result, but its calculation is time-consuming. Although heuristic algorithms can improve efficiency, it is at the expense of accuracy. To balance the contradiction between calculation accuracy and efficiency, we propose a new framework based on backward reasoning called Influence Maximization Based on Backward Reasoning. This new framework uses the maximum influence area in the network to reversely infer the most likely seed nodes, which is based on maximum likelihood estimation. The scheme we adopted demonstrates four strengths. First, it achieves a balance between the accuracy of the result and efficiency. Second, it defines the influence cardinality of the node based on the information diffusion process and the network topology structure, which guarantees the accuracy of the algorithm. Third, the calculation method based on message-passing greatly reduces the computational complexity. More importantly, we applied the proposed framework to different types of real online social network datasets and conducted a series of experiments with different specifications and settings to verify the advantages of the algorithm. The results of the experiments are very promising.

1. Introduction

With the development of the Internet, online social networks have become more and more popular, and have penetrated all aspects of human lives. We can share what we have seen and heard through online social networks, and we can also obtain the latest news and marketing information from there. Online social networks have become a new carrier for the spread of information [1]. The information transfer in online social networks is faster and more convenient, it is easier to create a popular trend, which brings new opportunities and challenges to marketing, and also attracts great attention of researchers.

Word-of-mouth marketing in the new situation can be abstractly described as an influence maximization problem, which is one of the key issues in social network analysis [2]. It refers to mining the most influential top-$K$ nodes from an online social network to maximize the final spread of influence in the network. Kempe et al. first formulated the problem of influence maximization as a discrete optimization problem, which is a milestone in the research of influence maximization [3]. They also proved that when the diffusion model is independent cascade and linear threshold models, the problem of influence maximization is an NP-hard.

As one of the important issues of online social network analysis, previous research on this issue is mainly divided into two categories: research based on greedy algorithms and heuristic algorithms. Greedy algorithms usually require Monte Carlo simulation of the propagation process, and an accurate Monte Carlo simulation often needs to be repeated many times. Although this method guarantees the accuracy of the results, it is very time-consuming. For the heuristic algorithms, they can use heuristic information to shorten the running time, but this will cause a loss of accuracy and stability. In response to this problem, researchers are constantly exploring new methods to balance the contradiction between calculation accuracy and efficiency.

In this paper, we propose a solution using backward reasoning, which is based on maximum likelihood estimation. The basic idea is to improve the efficiency of the algorithm by avoiding the Monte Carlo simulations while ensuring the accuracy of the result. We define the influence cardinality of nodes and establish rules by using backward reasoning to evaluate the probability of each node as a seed node to spread the information to the entire network. Based on these foundations, the set of seed nodes can be constructed according to given strategies. The influence cardinality considers the process of information diffusion, which provides a guarantee for the accuracy of the algorithm. In addition, to reduce the time complexity of calculating the influence cardinality, we propose an algorithm based on message-passing, which greatly reduces the computational complexity of our framework.

Summing up, the highlights of this paper are four-fold. First of all, to solve the problem to influence maximization, we propose a new framework, Influence Maximization based on Backward Reasoning, (IMBR), which achieves a balance between the accuracy of the result and the efficiency. Second, we define the influence cardinality of the node based on the information diffusion process and the network topology structure. Third, the calculation method based on message-passing reduces the number of repeated traversals of the entire network. Finally. A series of experiments with different specifications and settings were carried out on real online social network datasets to examine the advantages of the framework, which proves to be quite promising.

The rest of the paper is organized as follows. In the next section, a brief survey of the related work about influence maximization is given. The framework proposed in this paper is presented in Section 3. The experiments on real world networks are performed in Section 4. Finally, conclusions and future works are given in Section 5.

2. Related Work

The problem of influence maximization was first proposed by Domingos and Richardson [4]. Based on this research, Kempe et al. [3] first defined the problem as a discrete optimization problem. According to their research, the definition of the optimization problem for maximizing influence is to mine$K$seed nodes that can maximize the spread of influence on an online social network based on a given diffusion model. Besides, they also proved that the influence function satisfies the sub-module properties and the monotonicity under the most commonly used independent cascade and linear threshold models. Finally, they proposed a greedy climbing algorithm [5], which can guarantee the approximate optimal of $1-\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$e$}\right.-\epsilon$. Later, Sviridenko [6] extends the greedy framework using a non-uniform cost function for seed selection. In order to improve calculation efficiency, Leskovec et al. [7] proposed the Cost Effective Lazy Forward (CELF) schema, Goyal et al. [8] proposed CELF++, an extension of CELF. CELF and CELF++ use the sub-mode attribute of the influence function to avoid calculating the marginal gain of all non-seed nodes when selecting a seed node every time. Estevez et al. [9] presented a Set Covering Greedy (SCG) algorithm which was also the improvement of the greedy algorithm. When selecting the seed nodes, SCG discards the overlapping part with the neighbor nodes of the seed nodes. To improve the efficiency of the solution, Chen et al. [10] proposed a new algorithm called New Greedy-IC. This algorithm removes those edges that cannot successfully propagate the information in the iterative process. After these, Zhou et al. [11] used the influence function to find the upper limit of the marginal benefit of the node influence diffusion. Based on this, the Upper Bound based Lazy Forward (UBLF) algorithm was proposed. UBLF can reduce the number of repetitions of Monte Carlo simulation to improve computational efficiency by using boundaries. Unfortunately, at the beginning of selecting seed nodes, the effect of reducing the number of Monte Carlo simulations is significant. As more and more seed nodes are selected, the effect continues to decay. Lu et al. [12] proposed a cascade discount (CD) algorithm, which is based on the greedy algorithm, to solve the problem of influence maximization in the independent cascade model. Moreover, there are some other improved methods based on greedy algorithms, Ge et al. [13] extended the confidence interval estimator and proposed an end-to-end method for influence maximization, called the influence maximization based on learning automata (IMLA). Tian et al. [14] proposed a hybrid potential-influence greedy algorithm (HPG) based on the linear threshold model. The HPG algorithm uses the “influence accumulation” property of the diffusion model to heuristically select half of the seed nodes with the largest potential influence, and then greedily select the other half seed nodes. Wang et al. [15] proposed a potential-based greedy selection strategy to solve this problem, and so on [16].

Although the greedy algorithm can guarantee the best approximation, the solution process takes a huge amount of time. This is because in the process of selecting seed nodes, it is necessary to repeatedly calculate the marginal revenue of all non-seed nodes through Monte Carlo simulations. As we all know, Monte Carlo simulation is very time-consuming. Even if the number of repetitions is reduced, when the network scale becomes larger, the computational complexity is still considerable. Therefore, some researchers began to consider using heuristics to improve efficiency. Chen et al. [10] discussed the relationship between influence diffusion and the degree of nodes and proposed the Degree-Discount heuristic algorithm. This algorithm can significantly reduce the calculation time, but at the expense of some accuracy. Wang et al. [17] proposed a community-based greedy algorithm (CGA) to mine top-$K$ influential seed nodes. CGA considers the community structure in the process of influence diffusion. Furthermore, Khomanmi et al. [18] considered the spread of influence in the local community and proposed a fast and scalable algorithm named the community finding influential node (CFIN). The CFIN algorithm includes two main parts: local community spreading and seed selection. After, Kundu et al. [19] defined the diffusion degree of the node, which is a centrality measure used to indicate the influence of the node on other nodes. They used this measure to mine the influential nodes. Kim et al. [20] proposed a scalable influence approximation algorithm based on the independent cascade model, which is called the Independent Path Algorithm (IPA). IPA treated the independent influence path as an influence evaluation unit to effectively calculate the influence of the node. There are some other heuristics based on influence path like shortest path (SPIM) [21], SIMPATH [22], and LDAG [23]. Besides, Singh et al. [24] designed a new method called Influence Maximization Algorithm Based on Ant Colony Optimization (ACO-IM) to solve the problem of influence maximization in social networks. ACO-IM defined the rules for individuals to exchange and update information in the problem of influence maximization. Jung et al. [25] combined influence ranking (IR) and influence estimation (IE) to propose a novel algorithm, IRIE, to solve the problem of influence maximization. The algorithm can be used for the independent cascade model and its extended models. Tang et al. [26] proposed an algorithm, called TIM. In theory, TIM can return a ($1-\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$e$}\right.-\epsilon$) approximate solution. In practice, TIM adopts a novel heuristic method, which can significantly improve efficiency without affecting its asymptotic performance. To support massive graphs, some other different algorithms have also been proposed. Cohen et al. [27] proposed the greedy sketch-based impact maximization (SKIM) algorithm. The core of SKIM is to construct the summary structure of each node, that is, the combined reachability sketch. SKIM is a greedy algorithm in the sketch space. It has high scalability and can be easily extended to graphs with billions of edges. To improve the efficiency of calculation, Nguyen et al. [28] were inspired by the stop and stare strategy and proposed the Stop-and-Stare Algorithm (SSA), which is based on sampling technology. And they also proved that SSA is the first approximation algorithm that uses the (asymptotically) minimum number of samples. In addition, other heuristic-based algorithms are MIA [29], CIM [30], CoIM [31], and others [32,33]. These heuristic methods use the heuristic information in the influence diffusion process to improve the efficiency of seed node selection but at the expense of accuracy.

In addition to these works, it is important to note that some variant problems based on the influence maximization problem have recently appeared. Gong et al. [34] considered the robustness assumption in the influence maximization problem and proposed the robust influence maximization problem. This problem focuses on the uncertainty factors affecting the information diffusion model and the algorithms. Seo et al. [35] changed the search target from individuals to communities and mined communities containing influential individuals in the network. They used a multi-dimensional vector to represent influence, where each dimension represents a kind of influence factor. Based on this, they proposed a search method across multiple impact criteria. Considering the dynamic behavior of online social networks, Singh et al. [36] studied the influence maximization problem in an online social network that evolves over time. In this framework, the first step is to predict the change of the network and then mine the seed nodes in the predicted network. Li et al. [37] paid attention to the problem of maximizing the positive influence in the signed social network. The formal definition of this problem is to select the top-$K$ to send nodes with the largest positive influence in a given signed social network. They proposed a greedy algorithm for maximizing net positive influence based on game theory. Wu et al. [38] combined the problem of influence maximization with the diffusion of multi-source information and proposed the problem of multiple influence maximization (MIM), in which multiple pieces of information can be spread independently in the network. The goal of the multiple influence maximization problem is to maximize the overall cumulative influence spread of different information under the constraints of the seed budget $k$. Xie et al. [39] studied the problem of influence maximization in a competitive environment and analyzed the effect of inactive nodes and community homogeneity on information diffusion. Besides, to improve the effectiveness of seed nodes, some works have extended the classic IM problem by adding contextual features, such as topic, time, location [40,41,42].

Many improvements to the problem of influence maximization have been proposed, however, the efficiency of these methods is still unsatisfactory. Most of the previous work can be divided into two categories based on greedy algorithms and heuristic algorithms. The greedy-based algorithm uses a large number of Monte Carlo simulation processes to get high accuracy, but the computation is time-consuming. The heuristic algorithm is highly efficient, but it is easy to fall into the local optimal solution. Therefore, it is a particularly critical issue to design a more efficient and more accurate scheme for evaluating the influence of nodes, which can get a higher accuracy result and avoid a large number of Monte Carlo simulations.

3. Methodology

In this section, we first give a formal definition of the influence maximization problem and describe in detail the new framework proposed in this paper.

3.1. Preliminaries

In this part, we first give a formal definition of the online social networks, then define the problem of influence maximization based on the above, and finally introduce the information diffusion model used in this paper.

Definition 1.

An Online Social network with$N$users can be represented by a graph$G\left(V,E\right)$, Set of nodes$V$represents users, where$\left|V\right|=N$and the set of edges$E$refer to the relationship between individuals. Influence can spread along the edges in the social network.

Definition 2.

The definition of the influence maximization is to select$K$seed nodes for a given online social network$G\left(V,E\right)$and an influence diffusion model$M$, which simulates how information spreads in the social network, to maximize the number of influenced nodes in$G$. Suppose$S$denotes the set of seed nodes and$R\left(S\right)$be the number of nodes influenced by the selected seed nodes based on the diffusion model$M$. The formal representation is as follows:

$$S^{*}=arg\underset{S\subset V,\left|S\right|=K}{\max }R\left(S\right).$$

(1)

The influence takes information as the carrier. For the information diffusion process, we focus on the spread of influence of the node when the process is over. Therefore, we use an Epidemic model, which is the most common model used to study information propagation as the information diffusion model. The susceptible infection (SI) model is one of the Epidemic models. In the SI model, in the beginning, the state of the seed nodes is set to the infected state, and the state of all other nodes is susceptible. A node changes from susceptible state to infected state when accepting information, and it can affect the susceptible nodes in its neighbor nodes according to probability $p$ in the future. Once a node becomes infected, it will always maintain this state. This process ends when no more new nodes are infected [43].

3.2. Proposed Method

The influence maximization framework based on backward reasoning put forth by this paper consists of two parts. First, the first stage evaluates the ability of each node as a seed node to affect the entire network. In the second stage, seed nodes are selected according to the evaluation results and strategies.

3.2.1. Evaluate the Influence of Node Based on Maximum Likelihood Estimation

Suppose that a piece of information is sent out by a seed node $v$ in an online social network $G$, and then the information continues to spread far away according to the given information diffusion model. When the process is over, we can find that $N$ nodes are infected. Since the information spreads along the edges in the graph, so these infected nodes form the influence area of node $v$, which is a connected subgraph of $G$. The goal of maximizing influence is to select the node with the greatest influence as the seed nodes. Using backward reasoning, the greater the influence of the node, the larger the influence area. After removing the isolated nodes in the online social network $G$, the remaining nodes construct the largest connectivity subgraph $G_M$, which is also the largest influence area. In an online social network, the influence area of the most influential node should be the largest, assuming that the influence area of the best seed node is $G_M$. To find out the most influential node, we evaluate the probability of each node $v$ as a seed node leading to the largest influence area $G_M$. The greater the probability, the higher the possibility that node $v$would affect the social network, that is, the greater the influence. To make this estimation, we assume that the seed node propagates information in $G$ based on the above SI model and the nodes in $G_M$ have a uniform prior probability. Based on this reasoning, a maximum likelihood estimator is constructed, which is defined as follows:

$$\widehat{v}=arg \underset{v\subset G_M}{\max }P(G_M|v)$$

(2)

where $P(G_M|v)$ represents the probability of using node $v$ as the seed node to simulate the information diffusion process according to the SI model, and the final influence area is $G_M$. Therefore, to select the seed nodes, we need to evaluate$P(G_M|v)$ for all $v\in G_M$.

However, we found that evaluation of $P(G_M|v)$ may not be computationally tractable. To solve this problem, we consider it from another perspective and transform the problem into a permutations problem, which is subject to the structure of $G_M$. As shown in Figure 1, if the seed node is the node $v_1$, it can only affect node $v_3$. After node $v_3$ is activated, the information may be transmitted to nodes $v_2,v_4,v_5$. According to this, the infected order $\left\{v_1,v_3,v_2,v_4,v_5\right\}$ and $\left\{v_1,v_3,v_5,v_2,v_4\right\}$ are permitted permutations. However, owing to the limitations of the network structure, the order of infection $\left\{v_1,v_5,v_2,v_4,v_3\right\}$ is impossible. Therefore, we need to find all these permitted permutations, where node $v$ is the beginning node, and their corresponding probabilities to evaluate $P(G_M|v)$.

Definition 3.

For a given online social network$G\left(V,E\right)$, we define$I\left(v,G\right)$as the influence cardinality of node$v$. $I\left(v,G\right)$is the total number of different permitted permutations of the nodes on$G$, which start from node$v\in G$and are subject to the structure of graph$G$.

When the problem is transformed, it becomes feasible to evaluate the$P(G_M|v)$. Assuming that $\Omega \left(v,G_M\right)$ is the set of all permitted permutations, in which source is $v$ and influence area is $G_M$. $\sigma$ represents a permitted permutation, which is also a spread path. In order to compute $P(\sigma |v)$ for every $\sigma \in \Omega \left(v,G_M\right)$, let $\sigma =\left\{v_1=v,v_2,\cdots ,v_N\right\}$, then

$$P\left(\sigma |v\right)={{\displaystyle \prod }}_{k=2}^{N}P(k^{th} \mathrm{infected} \mathrm{node}=v_k|G_{k-1}\left(\sigma \right),v)$$

(3)

where $G_k\left(\sigma \right)$ represents the subgraph of $G_M$. There are $k$ nodes in the $G_k\left(\sigma \right)$, $\left\{v_1=v,v_2,\cdots ,v_k\right\}$ for $1\le k\le N$.

Given the seed node $v$ and $G_{k-1}\left(\sigma \right)$, the next node to be infected can be any of the uninfected neighbors of the infected nodes in $G_{k-1}\left(\sigma \right)$. Since the infection probability of all individuals is independent and identically distributed in the SI model, each of these uninfected nodes has an equal probability of becoming the next infected node. Assuming $G_{k-1}\left(\sigma \right)$ has $n_{k-1}\left(\sigma \right)$ uninfected neighboring nodes, we can simplify formula 3 to

$$P\left(\sigma |v\right)={{\displaystyle \prod }}_{k=2}^N\frac{1}{n_{k-1}\left(\sigma \right)}.$$

(4)

Observing the above formula, we find that the problem of calculating $P\left(\sigma |v\right)$ has become to computing the size of the diffusion boundary $n_{k-1}\left(\sigma \right)$ for $2\le k\le N$. In general, computing this boundary is complicated, we first assume that $G_M$ is a regular tree, and then gradually change $G_M$ from a tree to a graph, which is also helpful for understanding. In this way, suppose the $k^{th}$ node added to $G_{k-1}\left(\sigma \right)$ is $v_k\left(\sigma \right)$, and the degree is $d_k\left(\sigma \right)$. Based on this, we can obtain

$$n_k\left(\sigma \right)=d_1\left(\sigma \right)+{{\displaystyle \sum }}_{i=2}^k\left(d_i\left(\sigma \right)-2\right).$$

(5)

Next, it is easy to find

$$P\left(\sigma |v\right)={{\displaystyle \prod }}_{k=2}^N\frac{1}{d_1\left(\sigma \right)+{{\displaystyle \sum }}_{i=2}^k\left(d_i\left(\sigma \right)-2\right)}.$$

(6)

According to formula 6, if $G_M$ is a $d$ regular tree, every node has the same degree $d$ in $G_M$, so for any node $v$ and permitted permutation $\sigma$.

$$P\left(\sigma |v\right)={{\displaystyle \prod }}_{k=1}^{N-1}\frac{1}{dk-2\left(k-1\right)}\equiv p\left(d,N\right).$$

(7)

Therefore, the maximum likelihood estimator becomes

$$\begin{array}{c}\widehat{v}\in arg \underset{v\in G_M}{\max }P\left(G_M|v\right)\\ =arg {\displaystyle \underset{v\in G_M}{\max }}{\displaystyle {\displaystyle \sum }_{\sigma \in \mathsf{\Omega }\left(v,G_M\right)}}P\left(\sigma |v\right)\\ =arg \underset{v\in G_M}{\max }I\left(v,G_M\right)p\left(d,N\right) \\ =arg \underset{v\in G_M}{\max }I\left(v,G_M\right)\end{array}$$

(8)

We can find that if $G_M$ is a regular tree, the influence of node $v$ can be evaluated simply by evaluating $I\left(v,G_M\right)$ for all $v\in G_M$. This is because the structure of the regular tree is special, and the probabilities of all permitted permutations are the same. When $G_M$ is a general tree, it becomes computationally intractable since different permitted permutations have different probabilities. Due to the exponential number of terms involved, constructing a maximum likelihood estimator for a general tree could be computationally quite expensive. Therefore, we adopted a heuristic method to resolve the heterogeneity of degrees.

If the $G_M$ is a general tree, assuming that information is transmitted between nodes in a breadth-first search (BFS) way, which is the fastest way of information diffusion.

In order to calculate the probability of BFS permitted permutations, the BFS permitted permutation with node $v$ as the seed node is denoted as ${\sigma }_v^{*}$. Then in a general tree, the maximum likelihood estimation becomes as follows after derivation

$$\widehat{v}\in arg \underset{v\in G_M}{\max }P\left({\sigma }_v^{*}|v\right)I\left(v,G_M\right)$$

(9)

Next, if $G_M$ is a general graph, calculating the probabilities of all possible permitted permutations in a given network is computationally prohibitive. Therefore, we also adopt a heuristic approach. As we all know, when a piece of information is sent out by a node, its spread path is a spanning tree of the graph. Therefore, suppose that if the node $v\in G_M$ is a seed node, after the information is sent from $v$, it will spread along a breadth first search tree rooted at $v$. This breadth first search tree, which is the fastest spread fashion of information, is denoted as $T_{bfs}\left(v\right)$. Therefore, we effectively obtain the following maximum likelihood estimator for a general graph:

$$\widehat{v}\in arg \underset{v\in G_M}{\max }P\left({\sigma }_v^{*}|v\right)I\left(v,T_{bfs}\left(v\right)\right)$$

(10)

We find that the node influence cardinality $I\left(v,G_M\right)$ plays a crucial role in evaluating whether the node $v$ is suitable as a seed node. To calculate efficiently, we convert the graph into the corresponding tree structure in the process. So, in the following, we describe in detail how to efficiently compute $I\left(v,G_M\right)$ when $G_M$ is a tree.

Let $T_u^v$ denote the subtree rooted at node $u$, with node $v$ as the seed node in a tree graph $G_M$. $\left|T_u^v\right|$ represents the number of nodes in $T_u^v$. To explain this definition clearly, an example is given in Figure 2. Figure 2 shows the spread path with node $v_1$ as the seed node. The subtree on the left has 3 nodes. It takes node $v_2$ as the root node and node $v_1$ as the seed node, so $\left|T_2^1\right|=3$. Similarly, we can obtain $\left|T_7^1\right|=1$.

In a tree graph $G_M$ with $N$ nodes, to calculate $I\left(v,G_M\right)$, we need to find the permissible permutations of $N$ nodes in the $G_M$. For a given permutation, there are $N$slots and the first of that must be the seed node $v$. Therefore, we only need to find the number of distinct ways to fill the remaining $N-1$ slots. These permutations are constrained by the structure of the graph, that is, a node $u$ must be located before all nodes in its subtree $T_u^v$. According to this constraint, the number of permissible permutations of all nodes in $T_u^v$ is $I\left(u,T_u^v\right)$. Based on this, the following relationship can be obtained.

$$I\left(v,G_M\right)=\left(N-1\right)!{{\displaystyle \prod }}_{u\in child\left(v\right)}\frac{I\left(u,T_u^v\right)}{\left|T_u^v\right|!}$$

(11)

where $child\left(v\right)$ denotes the set of all children nodes in the subtree rooted at $v$ in the graph $G_M$.

We extend this recursion to the next depth level in $G_M$, and we will get

$$\begin{array}{c}I\left(v,G_M\right)=\left(N-1\right)!{\displaystyle {\displaystyle \prod }_{u\in child\left(v\right)}}\frac{I\left(u,T_u^v\right)}{\left|T_u^v\right|!} \\ =\left(N-1\right)!{\displaystyle {\displaystyle \prod }_{u\in child\left(v\right)}}\frac{\left(T_u^v-1\right)!}{\left|T_u^v\right|!}{\displaystyle {\displaystyle \prod }_{w\in child\left(u\right)}}\frac{I\left(w,T_w^v\right)}{\left|T_w^v\right|!}\\ =\left(N-1\right)!{\displaystyle {\displaystyle \prod }_{u\in child\left(v\right)}}\frac{1}{\left|T_u^v\right|}{\displaystyle {\displaystyle \prod }_{w\in child\left(u\right)}}\frac{I\left(w,T_w^v\right)}{\left|T_w^v\right|!}\end{array}$$

(12)

A leaf node $l$only has one node and one permitted permutation, so $I\left(l,T_l^v\right)=1$. Repeat this recursion until the leaf layer of the tree graph is reached, then the number of permitted permutations rooted at the seed node $v$ in a given graph $G_M$ can be calculated by the following formula.

$$I\left(v,G_M\right)=N!{{\displaystyle \prod }}_{u\in G_M}\frac{1}{\left|T_u^v\right|}$$

(13)

To evaluate the influence of nodes, we need to compute the influence cardinality of every node in $G_M$. The computational complexity of calculating the size of subtrees $T_u^v$ for all $u$ and $v$ in a $G_M$ with $N$ nodes is $O\left(N^2\right)$. When the network scale becomes larger, the computational efficiency will be greatly reduced. To improve efficiency, we make a profound study of the relation between neighbor nodes. When node $v$ and node $u$ are two neighbor nodes in $G_M$, all their subtrees have the same size except for the subtrees rooted at $u$ and $v$. Based on this discovery, a special relationship exists between two subtrees, as follows:

$$\left|T_u^v\right|=N-\left|T_v^u\right|$$

(14)

According to this relationship, we can calculate the influence cardinality of any two neighbor nodes.

$$I\left(u,G_M\right)=I\left(v,G_M\right)\frac{T_u^v}{N-T_u^v}$$

(15)

This special relationship is the key to optimizing the algorithm for calculating the influence cardinality of each node in $G_M$. Suppose that the node $v$ is selected as the seed node in $G_M$. In order to obtain the size of all its subtrees $T_u^v$ to calculate its influence cardinality $I\left(v,G_M\right)$, every other node $u$ needs to pass two messages up to its parent node. The number of nodes in $u\prime s$ subtree is the first message, which is represented by $t_{u\to parent\left(u\right)}^{up}$. The other message includes the cumulative product of the size of the subtree of every node in $u\prime s$ subtree, expressed as $p_{u\to parent\left(u\right)}^{up}$. Then the parent node can get the size of its own subtree by adding the $t_{u\to parent\left(u\right)}^{up}$ messages together. Using these messages, the parent node can also get its cumulative subtree product by multiplying the $p_{u\to parent\left(u\right)}^{up}$ messages together. Starting from the leaf nodes, recursively pass the message upwards until the seed node receives the message. According to formula (13), the seed node multiplies the cumulative subtree products of its child nodes to obtain its influence cardinality $I\left(v,G_M\right)$. After that, we use formula (15) to evaluate the influence cardinality for the children of $v$. Each node passes its influence cardinality to its child nodes, which we call $r_{u\to w}^{down}$ for $w\in child\left(u\right)$. The complete process is as the following Algorithm 1. After optimization, the computational complexity of the algorithm that calculates the influence cardinality of all nodes is reduced from $O\left(N^2\right)$ to $O\left(N\right)$.

Algorithm 1 Calculate the influence cardinality based on message-passing

Input: An online social network $G\left(V,E\right)$

Output: Influence Cardinality of nodes in $G$

1: $G_{max}=f\left(G\right)$ //Find out the largest connectivity subgraph $G_{max}$.

2: $G_M=f\left(G_{max}\right)$ //Choose a node$v$ as the seed node and change $G_{max}$ to BFS tree graph $G_M$ with $v$ as root.

3: for $u$ in $G_M$ do

4:   if $u$ is a leaf then

5:    $t_{u\to parent\left(u\right)}^{up}=1$

6:    $p_{u\to parent\left(u\right)}^{up}=1$

7:   else

8:    if $u$ is root $v$ then

9:     $\forall w\in child\left(v\right): r_{v\to w}^{down}=\frac{N!}{N{{\displaystyle \prod }}_{j\in child\left(v\right)}{p}_{j\to v}^{up}}$

10:    else

11:     $t_{u\to parent\left(u\right)}^{up}={\displaystyle \sum }_{w\in child\left(u\right)}{t}_{w\to u}^{up}+1$

12:     $p_{u\to parent\left(u\right)}^{up}=t_{u\to parent\left(u\right)}^{up}{\displaystyle \prod }_{w\in child\left(u\right)}{p}_{w\to u}^{up}$

13:     $\forall w\in child\left(u\right): r_{v\to w}^{down}=r_{parent\left(u\right)\to u}^{down}\frac{t_{u\to parent\left(u\right)}^{up}}{N-t_{u\to parent\left(u\right)}^{up}}$

14:    end if

15:   end if

16: end for

3.2.2. Select Seed Nodes Based on Strategy

In this part, we construct the set of seed nodes according to different strategies. In the previous, we evaluated the probability that each node will affect the entire network when it is used as a seed node in $G_M$. To maximize the spread of the seed set, we use a greedy strategy to select seed nodes. This strategy aims to select $K$ most influential nodes from the candidate seed nodes. For each round, the node with the largest influence is selected to join the seed set. Algorithm 2 describes the complete process of the strategy, as follows

Algorithm 2 Construction of seed set based on greedy strategy

Input: The BFS tree subgraph $G_M$ of an online social network $G\left(V,E\right)$, the size of seed nodes set $K$

Output: the set of seed nodes $S$

1: while $\left|S\right|<K$ do

2:    $s_a=arg\underset{v\subset G_M-S}{\max }P(G_M|v)$

3:   $\mathrm{S}=\mathrm{S}{{\displaystyle \cup }}^{ }{s}_a$

4: end while

4. Experiments and Discussion

In this section, a series of experiments with different specifications are carried out for highlighting the performance and efficiency of the proposed scheme. This section is divided into two parts. The datasets used in the experiments and the baseline algorithms are introduced in the first part, and the remaining part is the analysis of the experimental results.

4.1. Experiment Setup

We compare the performance of five different algorithms on four real social network datasets. These four datasets are crawled from real online social networks, and the compared algorithms include classic algorithms and the latest algorithms. To avoid randomness in the process of selecting seed nodes, each algorithm was run 50 times independently.

4.1.1. Dataset Description

To verify the performance of our framework, we conduct experiments on four different online social network datasets. These datasets are detailed in

Table 1. The description of datasets.

No.	Name	Edges	Nodes	Average Degree	Average Clustering Coefficient	Diameter
1	Facebook	88,234	4039	43.7	0.61	8
2	ca-HepTH	25,998	9877	5.3	0.47	17
3	Epinions	508,837	75,879	6.7	0.14	14
4	Twitter	1,768,149	81,306	43.5	0.57	7

. The second column represents the name of the online social network dataset. The number of edges and nodes of the dataset are shown in the third and fourth columns. It can be found from the table that we use different scale datasets to make the experiment more convincing. The average degree of nodes in the online social network is listed in the fifth column. The last two columns of the table respectively show the average clustering coefficient and diameter of the network.

4.1.2. Baseline Algorithms

To demonstrate the superior performance of the framework IMBR, our algorithm is compared with several existing algorithms. The algorithms to be compared are summarized below.

Degree-Discount [10]: This is a heuristic algorithm based on node degree, which selects the nodes with the largest out-degree as the seed nodes. Besides, it considers the influence of neighbor nodes. If its neighbor is selected as the seed node, the out-degree of the node will decrease by one.

Upper Bound based Lazy Forward (UBLF) [11]: This is a greedy algorithm, it uses the upper bound based lazy forward to mine the top-$K$ influential nodes in an online social network. UBLF has the same accuracy and less running time than other greedy algorithms such as CELF and CELF++.

Influence Maximization Algorithm Based on Ant Colony Optimization (ACO-IM) [24]: This algorithm uses ant colony optimization to maximize the influence of the set of seed nodes. According to the fitness function, the best solution is selected in the iterative process and added to the seed set.

Community-based Greedy Algorithm (CGA) [17]: This algorithm first detects the structure of the community, and then exploits a dynamic programming algorithm to find influential nodes in these communities.

Sketch-based Impact Maximization Algorithm (SKIM) [27]: This is a greedy algorithm in the sketch space. The key of the algorithm is per-node summary structures.

Stop-and-Stare Algorithm (SSA) [28]: This is a sampling-based framework for the influence maximization problem, which is faster than other sampling algorithms.

4.1.3. Evaluation Measure

According to the previous analysis, the goal of influence maximization is to mine $k$ seed nodes with the greatest influence to maximize the final influence range. In order to measure the performance of the algorithm, we applied each algorithm to different datasets and get$k$seed nodes respectively. Then, the seed nodes are used as the information source, and the process of information spreading on the corresponding network is simulated based on the SI model. When the information spreading process is over, the number of affected nodes is used as the influence spread of the seed nodes. We use the influence spread of the seed nodes as a measure of the effectiveness of the algorithm.

In the experimental part, the probability of an individual changing from the susceptible state to the infected state in the SI model is set to$p=0.08,$ and each propagation process goes through 1000 iterations. The range of $k$ranges from 5 to 50, with 5 as an interval.

4.2. Result and Discussion

To show the performance of our IMBR algorithm, we applied IMBR to different datasets and compared it with six rival benchmark algorithms from different aspects. The first measure to be evaluated is the influence spread of the seed nodes selected by different algorithms, which is the most important in the problem of influence maximization. We use the seed nodes obtained in the experiment to perform 1000 Monte Carlo simulations and take the average of the simulation results as the final influence spread of the set of seed nodes. Applying IMBR and other algorithms to different real online social network datasets, the results are shown in Figure 3.

Analyzing these figures carefully, we can find that as the size of the seed nodes set K increases, the influence spread becomes larger in all datasets. Greedy algorithm UBLF performed best, and the results of SSA and SKIM were close to that of UBLF. At the same time. Another important result is that our algorithm IMBR has achieved similar results to SKIM, which provides a piece of evidence for the accuracy of our algorithm. The idea of the maximum likelihood estimator is to evaluate the influence of nodes in the diffusion process based on the entire network structure. It considers the entire process of information diffusion, which leads to higher accuracy of the results. In addition, the seed nodes set selected by Degree-Discount has a poor result in different situations. This is because it considers less node information in the process of selecting, which improves efficiency at the expense of accuracy. Moreover, the stability of Degree-Discount is not good. As the size of the datasets increases, the gap between Degree-Discount and other algorithms gradually becomes larger. The performance of the ACO-IM algorithm is second only to our algorithm. The seed nodes selected by the CGA algorithm are not good, which is due to the CGA algorithm mines influential seed nodes in different communities while ignoring information dissemination between communities. It is worth noting that the gap on the ca-HepTH and Epinions datasets between other algorithms and the UBLF, which is based on the greedy algorithm are larger than that on the Facebook and Twitter datasets. Through the analysis of the datasets, we found that owing to the sparse network structure of the datasets, the average node degree in the ca-HepTH and Epinions datasets is only 5.3 and 6.7, respectively, while the average node degree in the Twitter and Facebook datasets is 43.7 and 43.5, respectively.

Next, we analyze the impact of network type and network properties on the results of our algorithm. From the above analysis, it is found that the greedy algorithm UBLF has the highest accuracy. To facilitate the analysis, we normalize the accuracy of the algorithm according to the following formula:

$$Ac{c}_{IMBR}=\frac{IS{P}_{IMBR}}{IS{P}_{UBLF}}.$$

(16)

where $Ac{c}_{IMBR}$ represents the normalized accuracy of our algorithm IMBR, and $IS{P}_{IMBR}$ denotes the influence spread of the seed node selected by the IMBR algorithm. Similarly, $IS{P}_{UBLF}$ represents the influence spread of the seed nodes selected by the UBLF algorithm.

The following table shows the normalized accuracy of our algorithm under different data sets. The second to tenth columns of

Table 2. Normalized accuracy of IMBR algorithm on different datasets.

	5	10	15	20	25	30	35	40	45	50	Average
Facebook	0.94	0.92	0.95	0.96	0.99	0.98	0.96	0.97	0.98	0.98	0.96
ca-HepTH	0.67	0.54	0.82	0.8	0.8	0.87	0.85	0.89	0.9	0.93	0.81
Epinions	0.88	0.9	0.87	0.88	0.89	0.88	0.87	0.91	0.95	0.94	0.9
Twitter	0.93	0.96	0.97	0.97	0.98	0.98	0.97	0.96	0.97	0.97	0.97

indicates the normalized accuracy of the IMBR algorithm when $k$ takes different values. The last column of Table 2 represents the average of the normalized accuracy under different datasets.

With further analysis of the experimental results, it is found that the IMBR algorithm has the highest accuracy on the Twitter dataset and the worst performance on the ca-HepTH dataset; when $k$is larger, the accuracy of the IMBR algorithm is higher. Moreover, to explore the relationship between the results and network properties, a comparative analysis of Table 1 and Table 2 shows that the smaller the diameter of the network, the higher the accuracy of the IMBR algorithm. This is because the smaller the network diameter, the shorter the path for each individual to receive information. The IMBR algorithm evaluates the influence of nodes based on the spread path. The shorter the spread path, the smaller the evaluation error.

In the last part of the experiment, we compared the running time between our algorithm and the other six rival algorithms on different online social network datasets. We fixed the size of seed nodes to 50 and compared the cost time of different algorithms. The result is shown in Figure 4.

The result in Figure 4 reveals that the running time of the IMBR proposed in this paper is similar to the running time of CGA. UBLF has the longest running time, followed by ACO-IM, and Degree-Discount has the shortest running time. Degree-Discount algorithm saves time at the expense of accuracy. In addition, it can be found that the running time of our algorithm IMBR is faster than SSA and SKIM. Our algorithm IMBR avoids Monte Carlo simulations, and the calculation method based on message-passing greatly reduces the computational complexity. Compared with the greedy algorithm UBLF, IMBR significantly improves computational efficiency.

Based on the experimental results, we conclude that our proposed scheme based on the maximum likelihood estimator has found an optimal solution in the trade-off between time and accuracy. In terms of running time and influence spread, IMBR is not the best among all algorithms. However, compared with the UBLF based on the greedy algorithm, IMBR achieves a higher running speed. Compared with the Degree-Discount algorithm, which is the fastest algorithm, IMBR maintains a higher accuracy. Compared with the CGA and ACO-IM algorithms, IMBR has a great accuracy improvement. Compared with SKIM and SSA, IMBR has improved efficiency while maintaining accuracy close to SKIM. Considering the computational efficiency and accuracy, IMBR strikes a better balance between efficiency and accuracy.

5. Conclusions

With the rapid development of the Internet, online social networks have greatly changed human lives. This change has attracted many researchers to devote themselves to studying online social networks. Influence maximization is one of the hot research issues in this field. To solve this problem, many algorithms have been proposed. These works are mainly divided into two categories: algorithms based on greed and algorithms based on heuristic information. Greedy algorithms have high accuracy, but poor efficiency. The reason is that the Monte-Carlo simulations used by greedy algorithms are time-consuming. The heuristic algorithms are efficient, but the accuracy is not high. To find a better balance between efficiency and accuracy, we continued to study this issue in depth.

In this paper, we propose a framework of influence maximization based on backward reasoning in online social networks. Using this new framework, it is possible to estimate the ability of each node as a seed node to affect the entire network, which can measure the influence of nodes. The seed nodes can be selected based on this estimation using a greedy strategy. A series of experiments were conducted on real online social network datasets to explore the advantages of our framework. The results show that our method significantly shortens the running time under the premise of ensuring the accuracy of the results. In other words, the proposed framework achieves a good balance between efficiency and accuracy.

In future work, we intend to conduct in-depth research based on this work. One potential extension is based on this work to study the problem of maximizing marketing revenue under budget constraints. Another potential direction is to delve into the problem of influence maximization when the entire network structure cannot be obtained.