A Novel Influence Maximization Algorithm for a Competitive Environment Based on Social Media Data Analytics

As we can see from Fig. 1 , Social networks often include a large number of low-quality and invalid data and nodes. Accurately mapping all these nodes in the network generates a lot of computation overheads and further reduces the efficiency. Therefore, we propose to use the Hyperlink-Induced Topic Search (HITS) based relationship evaluation algorithm to filter out high authorities and hubs.

(1) Data preprocessing based on HITS

The algorithm based on HITS iteratively calculates the centrality of each user and the authority of each post, to obtain high authorities and hubs. Figure 2 shows the link relationship between users and posts and the iteration process. The process is described as follows:

10.26599/BDMA.2021.9020024.F002 Fig. 2Schematic diagram of the iterative process of the relationship evaluation algorithm.

(1) Initialize users’ centrality and post authority;

(2) The centrality of the users is the sum of the authority of all the linked posts, and the authority of the post is the sum of the centrality of all the linked users. Calculate users’ centrality and post authority in the follwing:

(1) $$\text{hub}=\sum \text{authority}$$

(2) $$\text{authority}=\sum \text{hub}$$

(3) The users’ centrality and post authority are normalized,

(3) $$\text{hub}=\frac{\text{hub}}{\sum \text{hub}}$$

(4) $$\text{authority}=\frac{\text{authority}}{\sum \text{authority}}$$

(4) Evaluate whether the users’ centrality degree and the post authority degree converge, the convergence will output the result; otherwise continue with Eqs. ( 2 )-( 4 ),

(5) $$\theta a=\frac{\underset{i=0}{\overset{n}{\sum }}\text{authority}}{n}$$

(6) $${\theta }_h=\frac{\underset{i=0}{\overset{n}{\sum }}\text{hub}}{n}$$

where ${\theta }_a$ and ${\theta }_h$ denote the thresholds after normalization of the posts’ authority and users’ hub, respectively.

Finally, the users’ centrality and post authority are sorted in a descending fashion (high to low) according to the numerical results, and the parameters ${\theta }_a$ and ${\theta }_h$ are defined to represent the critical value of screening, which is used to extract users’ interest labels, and other information are filtered out.

(2) Initial local community discovery

Community Dispersion (CD) is a key parameter. The higher the value of CD, the closer the community will be.

(7) $$\text{CD}=\frac{e_i}{e_o}$$

where $e_i$ represents the number of edges in the community, and $e_o$ represents the number of edges in the union of the community ( $C)$ and the neighboring nodes set ( $N)$ . Our local community discovery algorithm is described in Algorithm 1.

A very important step in the process of influence maximization is to measure the influence increment of each node. Correctly measuring the influence increment of each node is crucial to achieve the maximum influence. Highly influential nodes are usually deemed important in the network. The most important statistical measures used to denote the importance of nodes are degree centrality, intermediate centrality, compact centrality, clustering centrality, etc. After computing these statistics for each node, sorting all such nodes based on the measurement statistics is a simple strategy to measure the node importance. However, using only the aforementioned statistics during the node selection process whilst solving the influence maximization problem might not yield the best outcome. This is due to the node overlapping problem, whereby two different nodes with overlapping statistics can have varied impact on the node set. Herein, selecting nodes only based on simple metrics cannot deliver the optimal solution whilst resolving the problem of maximum impact. Thus, efficiently removing the influence of these overlaps during the selection of nodes is a key problem.

Usually, many activation paths exist between nodes, thus computing each of these paths can be a tedious process. Considering the theory of six degrees of segmentation, the connection between nodes usually does not exceed a certain value. Here, it is assumed that node $u$ can activate node $v$ only through the path with the highest activation probability between nodes. Finally, the activation probabilities of each node to all other nodes in the network are combined to approximate the influence range of the nodes.

Latent Dirichlet Allocation (LDA)^{[ 29 ]} model can be used to obtain the topic-based influence probability distribution among nodes^{[ 17 ]}. Considering the transmission of information $B$ as an example, the calculation of the probability of $p_{uv}^B$ are as follows:

(9) $$p_{uv}^B=\underset{j=1}{\overset{k}{\sum }}p({\lambda }_B|z_j)p(u,v|z_j)$$

where $p({\lambda }_B|z_j)$ represents the probability that information $B$ is the topic $z_j$ , and $p(u,v|z_j)$ represents the probability that a node influences another node under the topic.

Therefore, in the network $G(V,E)$ , calculating the influence of node $v$ under information $B$ is as follows:

(10) $${\text{Inf}}^B(v)=\underset{i=1}{\overset{k}{\sum }}\text{hub}(v)\cdot p({\lambda }_B|z_i)$$

where $\text{hub}(v)$ represents the hub of node $v$ , and $p({\lambda }_B|z_i)$ represents the probability that information $B$ is topic $z_i$ .

The formula for calculating the influence increment of node $V$ is defined as:

(11) $$\text{Δ}{\text{Inf}}^B\left(v\right)=\delta \left(S\cup \left\{v\right\}\right)-\delta \left(S\right)$$

In the process of maximization of influence, the selection of the initial node is related to the direction and scope of influence of the subsequent information communication, so it is very important to find the initial communication node with the highest influence. In some existing influence maximization algorithm^{[ 26 , 27 , 28 , 30 ]}, the initial transmission nodes are derived from the entire social network by incrementally mining the largest node. Although the influence of these nodes is high in the entire network society, their corresponding influence for a particular topic may not be necessarily higher, and the influence of each node to calculate incremental time efficiency can be low.

In the first stage, we only statically selected $\mathrm{\lceil }\beta \mathrm{\times }k\mathrm{\rceil }$ nodes with large influence as influence nodes, without considering the characteristics of information transmission in social networks. Therefore, the nodes acquired in the first stage are considered as the initial transmission nodes, and the information transmission in the social network is simulated through the model. Then, the greedy strategy is adopted to iteratively mine the $k-\lceil \beta \times k\rceil$ nodes with the largest increment of the topic influence as the remaining influence nodes. Among them, the largest increment of topic influence refers to the largest difference between the scope of influence of the current collection and the scope of influence before the addition of U. The specific algorithm flow is shown in Algorithm 2.