A community-based algorithm for influence maximization on dynamic social networks

Abstract

The purpose of the influence maximization is to find the top $k$ influential seeds which can maximize the influence spread. Recently, some researchers address this problem through community structure. However, most of these community-based studies only consider the static social network, which ignores that social networks change frequently. In order to deal with the above problem, we present a community-based algorithm on the dynamic social network, which is divided into three phases: (i) community detection, (ii) candidate seed set on the dynamic network, and (iii) final seed set. In the first phase, we use the Louvain algorithm to obtain the community structure. In each community, we analyze the node location to judge the importance of the node. In the second phase, considering the dynamic social network, when a node is added to the network or removed from the network, we update the structure of the social network. Then, the candidate nodes are those nodes with a large influence in each community. And in the third phase, we select $k$ influential seeds from the candidate seeds by CELF algorithm. Extensive experimental results show that our algorithm obtains a better influence spread than many baseline algorithms as well as an acceptable running time while considering the dynamic social networks.

Keywords

Influence spread community structure dynamic social network three phases

1. Introduction

Nowadays, with the increasing popularity of online social networks, such as Sina Weibo, WeChat and FaceBook, the business finds that social networks play an important role in information spreading. In the studies of information spreading, one of the most popular topics is influence maximization, which selects a small number of individuals as seed set that can influence nodes as much as possible. In addition, the influence maximization has many significant applications, such as viral marketing and career predicting. Considering an application in fortune teller as an example. A people’s career path consists of several career stages. We can collect the current characteristics and topics to ensure the most influential factors that decide the proper job positions, which is crucial to the employees, employers, and headhunters.

The influence maximization, as one of the most important themes in social network analysis, is first defined by Domingos and Richardson [1]. Since then, Kempe et al. [2] propose two kinds of information spreading model: Independent Cascade (IC) model and Linear Threshold (LT) model. Meanwhile, they prove that the problem under spreading model is NP-hard and present a greedy algorithm [3] to obtain an optimal influence spread, which depends on the Monte-Carlo simulations. However, their algorithm is still impractical when facing large-scale social networks.

A large number of following works aim to deal with the context problem from efficient heuristic algorithms [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] perspective, which can improve the running time. The research [16] finds that the community structure reveals the fundamental properties of the social network. Inspired by this, studies [17, 18, 19, 20, 21, 22, 23] tackle the influence maximization problem by using the community structure. However, they ignore the reality that in general, the real-world social networks are dynamic and the community structure changes timely. Recently, studies [28, 29] mine the community from a dynamic social network. Inspired by this, based on the community structure, we deal with the influence maximization problem on the dynamic networks.

In this paper, we propose a Community-Based algorithm for Influence Maximization on Dynamic social networks, called D-CBIM algorithm. In our algorithm, we first detect the nodes community. Then, we evaluate the importance of nodes according to the nodes location analysis in each community. Moreover, we partition the dynamic node into two types: add to the social network or delete from the social network. After that, we select the influential nodes as the candidate seeds. And finally, we use the CELF (Cost Effective Lazy Forward) algorithm to obtain the final influential seed set. More specially, the major contributions of this paper are summarized in the following part:

•
Considering the dynamic networks, we propose a novel heuristic algorithm, D-CBIM algorithm, which divides the dynamic changes into two situations: add a node or delete a node.
•
We present a new method to evaluate the importance of nodes, which takes the nodes location analysis into account.
•
Extensive experiments have been carried out to estimate our algorithm on real social networks. The experimental results show that our algorithm performs better than other heuristic algorithms in both influence spread and running time and runs less time than the CELF algorithm for we consider the dynamic networks.

The rest of the paper is organized below. Firstly, we retrospect the related work on influence maximization in Section 2. Then, in Section 3, we describe the preliminaries of our paper. After that, we present our proposed D-CBIM algorithm based on community structure for influence maximization on dynamic networks in Section 4. In addition, in Section 5, we evaluate our proposed algorithm compared with many other algorithms. Finally, in Section 6 we expose our conclusions and the future directions.
2. Related work

Since Kempe et al. [2] prove the influence maximization problem is NP-hard and present a basic greedy algorithm to approximate the optimal solution, a series of studies have been proposed to deal with this problem. In general, there are mainly two categories: greedy algorithm and heuristic algorithm.

2.1 The greedy algorithm

Kempe et al. [2] propose a basic greedy algorithm, which repeatedly selects the node with the largest marginal influence as the seed set. There is no doubt that it is most accurate in terms of influence spread. Unfortunately, it has a serious efficiency problem, which is inappropriate to large scale networks. In order to reduce the time complexity, taking the submodularity into account, Leskovec et al. [3] propose the CELF algorithm, which significantly reduces the running time. Since then, NewGreedy and MixGreedy are proposed in the study [4]. The NewGreedy algorithm evaluates the influence spread of nodes in the same iteration by the Monte Carlo simulations. In addition, MixGreedy combines the advantages of CELF and NewGreedy algorithm. However, although those improved greedy algorithms reduce the time complexity, they are still unsuitable for large-scale networks. In conclusion, the greedy algorithm can guarantee the accuracy of influence spread, but it is impractical in real social networks.

2.2 The heuristic algorithm

Diverging from the greedy algorithm, aiming at solving the efficiency problem, the following heuristic algorithms [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] are proposed. Chen et al. [4] propose the Degree Discount algorithm, which regards the node with the largest degree as the influential seed. In order to reduce the influence spread, if a node is selected as a seed, the neighbors will be discounted. However, this method ignores the propagation probability. In addition, they propose PMIA (Prefix Excluding Maximum Influence Arborescence) algorithm [5], which utilizes the local influence arborescences to evaluate the influence spread. And Kyomin Jung et al. [6] propose Influence Ranking Influence Estimation(IRIE), which runs two orders of magnitude faster than the PMIA algorithm. In addition, Kistak et al. [7] assume that the node who locates in the core of the network tends to have a larger influence spread. Based on this assumption, Cao et al. [8] propose the Core Covering Algorithm (CCA) algorithm, which selects the nodes with both large degree and core as seeds. However, the CCA algorithm leads to low influence spread for it may cover too many influential nodes.

Different from the above algorithms, many researchers [17, 18, 19, 20, 21, 22, 23] deal with the influence maximization problem from the community structure perspective. Cao et al. [17] are the first to deal with influence maximization based on the community structure, which assumes that different community is independent. Chen et al. [18] propose the CIM (Community-based Influence Maximization), which consists of three phases: community detection, candidate seeds, and final seeds. Basing on multi-neighbor potential in community networks, Shang et al. [19] propose an influence maximization framework, called CoFIM, which consists of two parts: seeds expansion and influence spreading. In conclusion, the heuristic algorithms based on the community structure are generally faster than the traditional algorithms. Unfortunately, we notice that a few studies focus on the dynamic social networks, ignoring the reality that the real world social networks are dynamic and community structure changes timely, which may have an effect on influence maximization problem. For example, we select $k$ influential seeds according to the static network. However, on the dynamic networks, one of the $k$ influential seeds may be removed or a new influential seed may emerge. At this time, if selecting the original $k$ influential seeds, we may obtain the inaccurate influence spread.

From the above discussion, to deal with the context situation, we should take the dynamic network into account. In this paper, we divide our algorithm into three phases: (i) community detection, (ii) candidate seed set on the dynamic network, and (iii) final seed set. In the first phase, we use the Louvain [24] algorithm to obtain the community structure. Then, we analyze the node location to judge the importance of the node. The candidate nodes are those nodes who locate in the core of the community. In addition, we consider the situation that a node may add to or delete from the social network. And in the third phase, we select $k$ influential seeds from the candidate seeds by CELF algorithm. Although our proposal performs a little worse than CELF in influence spread, it improves the running time and obtains a better influence spread compared with the other classical algorithms as the later experiments show.

3. Preliminaries

In this section, at first, we formally describe the influence maximization and diffusion model. After that, we describe the Louvain algorithm which is utilized to detect community. And finally, we present the CELF algorithm, which can optimize the final seed set.

3.1 Influence maximization problem and diffusion model

Influence maximization is aimed to specify $k$ influential nodes which can influence nodes as much as possible.

Definition 1 (Influence maximization problem): Given a social network graph $G({V,E})$ , we select $k$ influential nodes as seed set $S$ so as to the seed set $S$ can influence nodes as much as possible under the diffusion model. The maximized influence spread of seed set $S$ is called influence maximization, denoted by $\delta(S)$ .

Up to now, there are mainly two diffusion models: IC model and LT model. The IC mode not only is easy to understand but also accords with the information diffusion process. Thus, in this paper, we select the IC model as our diffusion model. The following is a simple definition of the IC model.

Definition 2 (IC model): Generally, we model a social network as a graph $G(V,E)$ , where the set of nodes $V$ represents the set of individuals. Meanwhile, $E$ is the set of edges, denoting relationships between individuals. For each edge $({u,v})\in E$ , the activated node $u$ can try activating each inactive neighbor node $v$ with a propagation probability $p({u,v})$ through this edge.

In the IC model, every node only has one state: active or inactive. Initially, all the seeds $S$ are active, and other nodes are inactive. Then, each active node $u$ only has one chance to try activating each of its inactive neighbors $v$ with a propagation probability $p({u,v})$ . Once a node $v$ is activated, it will stay current state any more. Notice that, all newly activated nodes will be inserted to $S$ . The influence diffusion process iteratively continues until there are no new activated nodes.

3.2 Louvain algorithm

To the best of our knowledge, the Louvain [24] algorithm is a fast and effective modularity optimization algorithm to detect community for its time complexity is $O(n\log n)$ , which contains two steps: modularity optimization and community aggregation.

1.
Modularity optimization. We assume that each node is a community firstly. Then, for each node $v$ , we compute the modularity increment of the community $u$ when adding $v$ to the community of $u$ that are the neighbor nodes of $v$ . After that, we add a node $v$ to the community $u$ with the largest modularity increment.
2.
Community aggregation. We regard the new communities as an independent node and repeat the first step. The two steps will be repeated until no movement of the node.

3.3 CELF algorithm

The main idea of CELF [3] is that using the submodularity to reduce the time complexity of the greedy algorithm.

Definition 3 (CELF algorithm): Firstly, we rank all the nodes in descending order according to the margin gain of influence spread $\delta$ . We assume that $\delta(A)>\delta(B)>\delta(C)$ . Then, we select the node A with the largest margin gain as seed. After that, in the new round, if the new margin gain of influence spread of node B and the original margin gain of node C satisfy $\delta^{\prime}(B)>\delta(C)$ , we can add node B into the seed set immediately.

4. The proposed algorithm

In this section, we introduce the implement of our algorithm, which is based on the community structure to deal with the influence maximization problem on the dynamic networks. The framework of our proposal is shown in Fig. 1. At a high level, the algorithm can be summed up in three stages blew. At first, we utilize the Louvain algorithm to detect community. Then, we conduct each community to select the influential nodes by analyzing the location. Moreover, we use the CELF algorithm to find the final seed set from the candidate seed set, which can improve both running time and influence spread.

Figure 1.

The structure of our D-CBIM algorithm.

4.1 Community detection on the static social network

Community structure [16] is characterized as a partition of network nodes into subgroups. The nodes within the community are closely connected while the nodes between the communities are sparsely connected. Newman et al. [25] propose the definition of modularity, using to access the quality of the community structure. In general, a social network is modeled as $G=(V,E)$ . We can utilize the adjacency matrix A to denote the graph.

$\displaystyle A_{ij}=\left\{\begin{array}[]{ll}w_{ij}&\text{if nodes }i\text{ % and }j\text{ are connected}\\ 0&\text{otherwise}\\ \end{array}\right.$

Where $w_{ij}$ is the weight of edge ( $i\to j$ ).

For Louvain algorithm is an effective and accuracy algorithm, we choose the Louvain algorithm to detect community. We have introduced the process of Louvain algorithm in Section 3, which is a modularity-based algorithm. The study [24] gives the description of the Louvain algorithm, whose gain in modularity is denoted following.

$\displaystyle\Delta Q=\left[{\frac{\sum\nolimits_{in}^{c}+2k_{i,in}}{2m}-\left% ({\frac{\sum\nolimits_{\textit{tot}}^{c}+k_{i}}{2m}}\right)^{2}}\right]-\left[% {\frac{\sum\nolimits_{in}^{c}}{2m}-\left({\frac{\sum\nolimits_{\textit{tot}}^{% c}}{2m}}\right)^{2}-\left({\frac{k_{i}}{2m}}\right)^{2}}\right]=\frac{1}{2m}% \left({2k_{i,in}-\frac{\sum\nolimits_{\textit{tot}}^{c}{k_{i}}}{m}}\right)$ (1)

Where $\sum\nolimits_{in}^{c}=\sum\limits_{i,j\in V}{A_{ij}}\delta(c_{i},c)\delta(c_{% j},c)$ is the sum of the weights of the edges inside $c$ , $\sum\nolimits_{\textit{tot}}^{c}=\sum\limits_{i\in V}{k_{i}}\delta(c_{i},c)$ is the sum of the weights of the edges incident to nodes in $c$ , $k_{i,in}$ is the sum of the weights of the edges from $i$ to nodes in $c$ , $k_{i}$ is the sum of the weights of the nodes connected to $i$ , $m$ is the sum of weights of all the edges in the network. The detail of the Louvain algorithm is summarized as follows.

Algorithm 1: Louvain algorithm
Input: $G=(V,E)$
Output: community structure $C$
1: Initialize each node with its own community $C_{i}$ , $\Delta Q=0$
//step1: modularity optimization
2: while $\Delta Q\geqslant 0$ do
3: for each $v\in V$
4: Put the node $v$ into its every neighbor’s community $C_{i}$
5: Calculate $\Delta Q$
6: $C_{i}=\max({\Delta Q})$
7: $C_{i}=C_{i}\cup\{v\}$
//step2: community aggregation
8: for each $C_{i}\in C$
9: each $C_{i}$ is a new node regarded as the input of step1
10: Return $C$

In order to find the most influential nodes in each community, we assign the nodes into three types:

Definition 4 (Peak node): Given a network, $\forall v\in C$ , $\delta(v)>\delta(u)$ , the node $v$ is the peak node of the community. where $C$ denotes a community, $u$ is the two neighbor nodes of $v$ . $\delta(v)$ and $\delta(u)$ represents the propagation degree of node $v$ and $u$ .

Definition 5 (Slope node): Given a network, $\exists v\in C$ , $\delta(v)>\delta(u)$ and $\exists v\in C$ , $\delta(v)\leqslant\delta(u)$ , the node $v$ is the slope node of the community. Where $u$ are the two neighbor nodes of $v$ . $\delta(v)$ and $\delta(u)$ represents the propagation degree of node $v$ and $u$ .

Definition 6 (Valley node): Given a network, $\forall v\in C$ , $\delta(v)\leqslant\delta(u)$ , the node $v$ is the valley node of the community. Where $u$ is one of the two-hop neighbor nodes of $v$ . $\delta(v)$ and $\delta(u)$ represents the propagation degree of node $v$ and $u$ .

From the above discussion, we define the propagation degree to evaluate the node influence. Degree centrality is a straightforward and significant measurement for selecting the influential nodes during information diffusion, which selects nodes with maximum degree as initial seeds [26, 27]. However, it ignores the propagation rate. Thus, in this paper, we regard the nodes with the largest propagation degree as the influential nodes, which combines the degree and propagation rate. In order to improve accuracy, we consider the two-hop neighbor nodes. The propagation degree ( $\delta$ ) of the node $v$ can be obtained as follows:

$\displaystyle Q(u)=d_{u}+\sum\limits_{w\in N(u)}{p_{uw}*d_{w}}$ (2) $\displaystyle\delta(v)=\sum\limits_{u\in N(v)}{Q(u)}$ (3)

Where $d_{u}$ and $d_{w}$ is the degree of $u$ and $w$ , $w$ is the neighbor of $u$ and $u$ is the neighbor of $v$ .

4.2 Candidate seed set on the dynamic social network

After we conduct the Louvain algorithm and identify the kinds of nodes in each community, in this section, we select the peak node as the candidate seed set for its propagation degree higher than its two-hop neighbor nodes. The Louvain algorithm performs well in detecting community on the static networks. Unfortunately, in reality, the social network is dynamic and changes every time. Due to the goal of our algorithm is to select the influential nodes, thus, based on the Louvain algorithm, we update the set of peak node when the social network changes. There could be two situations for peak node:

1.
Add node. When a node adds to the social network, we need to judge the kinds of this node. If this node is a peak node, we should add this node to the candidate seed set, which is shown in Fig. 2.

Figure 2.
Changes when adding a peak node to social network.

2.
Delete node. When a node is removed from the social network, we need to judge the kinds of this node. If this node is a peak node, we need to find another node to replace it. For the node may have a similar attribute with its neighbor nodes, thus, we select the neighbor node with the largest propagation degree replace the removed peak node as shown in Fig. 3.

Figure 3.
Changes when deleting a peak node from social network.

In conclusion, the candidate seed set consists of all the peak node although the network changes.
4.3 Final seed set

After obtaining the candidate seed set, how to find the optimal solution is the goal of this section. CELF algorithm [3] is a representational greedy algorithm, which runs 700 times faster than the basic greedy algorithm. Therefore, in this paper, we utilize the CELF algorithm to find the most influential seeds from the candidate seed set.

The D-CBIM algorithm is shown as follows:

Algorithm 2: Community based on for influence maximization
Input: network $G=({V,E})$ , and number $k$
Output: $S$
$\backslash\backslash$ community detection
1: utilize Louvain algorithm to detection community C1, C2 …Ci
$\backslash\backslash$ candidate seed set
2: for each node $v\in Ci$ (i $=$ 1, 2 …n):
3: compute $\delta(v)$ using Eqs (2) and (3)
4: identify the kinds of nodes by Function 1
5: regard all the peak node as the $C S$
$\backslash\backslash$ whether the changed node is peak node
6: if the added node $a$ is a peak node
7: $CS=CS+\{a\}$
8: if the deleted node $a$ is peak node
9: $CS=CS-\{a\}\quad a=N(a)\max\deg\textit{ree}$
10: else ignore this change
$\backslash\backslash$ CELF algorithm
11: use CELF algorithm from the $C S$
12: Return $S$

Function 1: Analysis of the kinds of nodes
1: if node $v$ satisfies Definition 4
2: $v$ is a peak node
3: else if $v$ satisfies Definition 5
4: $v$ is a slope node
5: else $v$ is a valley node

Where $C S$ represents the candidate seed set.

The goal of our algorithm is to find the most influential final seed set on the dynamic social network. Our algorithm consists of three parts. Firstly, we utilize the Louvain algorithm to detect the community (line 1). Then, we calculate the propagation rate to identify the kinds of nodes (in lines 2–4). After that, we add the peak node to the candidate seed set as shown in line 5. Considering the dynamic social network, we identify the kinds of the changed node (lines 6–10). And the last past is that we use the CELF algorithm to select the k influential seed set from the candidate seed set (lines 11–12).

Time complexity

The total calculation of Algorithm 2 mainly consists of three parts: detect community, candidate seeds calculation, and final seeds calculation.

In the first part, we utilize the Louvain algorithm to detect community, whose time complexity is $O(n\log n)$ , where $e$ is the number of edges, and $n_{C}$ is the max number of community in all the iteration. In the second part, the time consuming mainly consists of the propagation rate computing of the nodes in each community and identify the kinds of nodes. The time complexity of propagation rate computing is $O(ee_{\max})$ , where $e_{\max}$ is the largest degree in the network. Then, the computation of judging the kinds of nodes is $O(nn_{1}n_{2})$ , where n is the number of nodes. Meanwhile, $n_{1}$ and $n_{2}$ represent the number of neighbor nodes and the number of two-hop neighbor nodes respectively. And last time complexity of CELF algorithm is $O(kn^{\prime}m^{\prime})$ , where $n^{\prime}$ and $m^{\prime}$ denotes the number of nodes and edges in the subgraph composed by the candidate nodes. Consequently, the total time complexity of Algorithm 2 is $O(n\log n)+O(ee_{\max})+O(nn_{1}n_{2})+O(kn^{\prime}m^{\prime})$ .

5. Results

We carry out experiments to access the performance of our algorithm over four real-world datasets and five compared algorithms: CELF, PMIA, CoFIM, CCA, and IRIE. All the codes are implemented in Python 2.7, and all the tests are run on CPU 2.8 GHz and 128 GB memory.

5.1 Experiment setup

5.1.1 Dataset preparation

We utilize four public real-world networks downloaded from the SNAP (http://snap.stanford.edu/data/) in our experiments. We choose these networks for they contain a variety of networks with sizes ranging from 19K edges to 1M edges. The largest dataset includes 262111 nodes and 1234877 edges. In addition, the ca-astroPh and Email-Enron dataset are undirected while the NetPHY and Amazon dataset are directed, which provides theoretical assurance for the later experiment results.

•
ca-astroPh. The dataset contains scientific collaborations between authors papers submitted to Condense Matter category.
•
Email-Enron. This dataset is derived by the CALO Project, which covers about 150 users, and most of them are senior management.
•
NetPHY. This dataset is from the scientific research cooperation network of physics.
•
Amazon. The dataset is collected by crawling Amazon website, which covers product metadata, reviews, and links.

These networks are selected in our experiment for they cover various types of networks in many fields, whose statistical properties are summaried in Table 1. In addition, as to the dynamic social network, we suppose that when a node adds to the social network, it randomly connects with other nodes. And when a node removes from the social network, it will remove the connected edges.

Table 1
Basic information of the context datasets

Datasets ca-astroPh Email-Enron NetPHY Amazon

#Nodes 18772 36692 37154 262111

#Edges 198110 183831 231584 1234877

Max.Degree 427 1367 3725 366

Avg.Degree 9.377 7.384 6.934 4.505

Avg.CC 0.6306 0.4970 0.294 0.4198

5.1.2 Algorithms compared

Datasets	ca-astroPh	Email-Enron	NetPHY	Amazon
#Nodes	18772	36692	37154	262111
#Edges	198110	183831	231584	1234877
Max.Degree	427	1367	3725	366
Avg.Degree	9.377	7.384	6.934	4.505
Avg.CC	0.6306	0.4970	0.294	0.4198

We compare our algorithm with five traditional algorithms including one greedy algorithm and four heuristic algorithms, which contains the representative of the greedy algorithm – CELF algorithm, path-based heuristic algorithm – PMIA algorithm, core-based heuristic – CCA, community-based algorithm – CoFIM algorithm and two steps heuristic – IRIE algorithm. The descriptions of the implementation details of these algorithms are summarized below.

•
D-CBIM: Our algorithm contains three phases: community detection, candidate seed set on dynamic social network and CELF algorithm.
•
CELF: As a typical representative of the greedy algorithm, CELF gets higher effectiveness while not suits for large social networks.
•
PMIA: A heuristic algorithm, PMIA, based on the maximum influence arborescence, runs faster than many heuristic algorithms. In addition, we run the PMIA algorithm with a fixed $\theta=1/{320}$ .
•
CCA: Integrating the hierarchy and influence radius based on the K-shell method, CCA is not very effective in the aspect of influence spread. Here, we set influence $\textit{radius}=2$ .
•
CoFIM: CoFIM, a community-based algorithm, conducts seeds expansion between different communities firstly, then propagates on the intra-community.
•
IRIE: IRIE is an effective algorithm for influence maximization, which incorporates a new message passing and influence estimation. In addition, $\alpha$ and $\theta$ are 0.7 and $\frac{1}{320}$ .

To accurately obtain the influence spread of the above six algorithms, we run 10000 times for each targeted set as done by the previous works and then present the average of the influence spread in the following subsections.
5.2 Experiment results

In this section, we first conduct the change for the influence spread when a node adds to the social network or deletes from the social network. After that, we analyze the experimental results of our proposal on four real-world datasets from the aspects of influence spread and running time.

5.2.1 Dynamic social network

Tables 2 and 3 present the changes on ca-astroPh and NetPHY dataset when a node adds to or deletes from the social network, where the dynamic time is the time that updates the structure of the social network to find the candidate seed set. Obviously, the changes between delete and add is similar in the aspects of dynamic time and influence spread. Thus, in the following comparison with other baseline algorithms, we adopt the situation that a peak node is removed from the social network.

Table 2
Changes on ca-astrtoph dataset

ca-astroPh
Delete a node			Add a node
Candidate seed set size	Dynamic time	Influence spread	Candidate seed set size	Dynamic time	Influence spread
1471	119	407	1744	124	429

Table 3

Changes on netphy dataset

NetPHY
Delete a node			Add a node
Candidate seed set size	Dynamic time	Influence spread	Candidate seed set size	Dynamic time	Influence spread
1273	266	1630	1281	285	1672

Figure 4.

Influence spread on four different datasets.

5.2.2 Influence spread

Figure 4 shows the performance of the six algorithms introduced in Section 5.1 over four datasets under the IC model. In order to obtain a persuasive comparison, we simulate the experiments with different size of seed set, which ranges from 10 to 50.

As a whole, Fig. 4 shows that our D-CBIM algorithm outperforms other heuristic algorithms while obtains a close influence spread to CELF algorithm, which illustrates the superiority of our algorithm in tradeoff the influence spread and running time. In general, the CELF outperforms the other five heuristic algorithms for it can guarantee within ( $1-1/e$ ) of the optimal solution. However, its running time is too long, which not suits well to large scale social networks. Observing the Fig. 4a–d, we can easily notice that, CCA algorithm performs worst compared with the other five algorithms. This is mainly because it covers the neighbor nodes of the newly selected seed to reduce the overlapping of influence spread, which may cover the influential nodes. Obviously, PMIA performs greatly varies over different datasets in terms of influence spread. For example, PMIA performs well on Email-Enron showed in Fig. 4b, which only 2% less than CELF algorithm, however, it performs badly on ca-AstroPh. Thus, the PMIA may be influenced by the structures of social networks for it relies on the structure of the social network. More specially, CoFIM maintains a similar influence spread with D-CBIM algorithm on Email_Enron dataset. Fortunately, D-CBIM still 12% higher than CoFIM on this dataset. It is worth noticing that the performance of D-CBIM is 1%, 85%, 57%, 19%, and 17% higher than CELF, PMIA, CCA, CoFIM, and IRIE on as-AstroPh dataset when seed set size is 50 respectively, which owing to the consideration of dynamically adding and deleting nodes. In addition, as to the medium and large social networks, Amazon dataset, our D-CBIM can obtain 24%, 39%, 15%, and 18% higher influence spread than PMIA, CCA, CoFIM, and IRIE. In brief, D-CBIM outperforms most of the traditional heuristic algorithms for it takes the dynamic social network into account. Although on the Amazon dataset, our D-CBIM performs 2% worse than CELF when the seed size is 50, it runs 92% faster than CELF as Fig. 5 shows. Therefore, experimental studies over various real-world social networks reveal that our algorithm performs better than the baseline heuristic algorithms. Meanwhile, though our algorithm performs a little worse than CELF, our algorithm obviously improves the running time. In conclusion, considering the dynamic social network, our proposal not only provides a better practice but also explains the dynamics of social networks.

Figure 5.

Running time on different datasets for selecting 100 seed nodes.

5.2.3 Running time

The running time of the algorithms D-CBIM, CELF, PMIA, CCA, CoFIM, and IRIE are $O(n\log n)+O(ee_{\max})+O(nn_{1}n_{2})+O(kn^{\prime}m^{\prime})$ , $O(\textit{knm})$ , $O(nt_{i\theta}+kn_{o\theta}n_{i\theta}\log n)$ , $O(km)$ , $O(k^{3}n)$ , and $O\left(\sum\nolimits_{v\in V}{d_{\textit{out}}(v)}\right)$ respectively. Figure 5 presents the performance of the six algorithms in the aspect of running time over the four datasets with 100 seed nodes. In general, the CELF algorithm relies on the Monte Carlo simulations, which results in higher time complexity. For example, on Email-Enron dataset, the CELF algorithm reaches up to 13401 seconds. As shown in Fig. 5, CCA needs the shortest running time. This may be caused by too many nodes covered. Moreover, our algorithm needs to calculate the propagation degree to identify the kinds of nodes, which may cost too much time. Compared with the experiments, D-CBIM runs 76%, 9%, 17% and 53% faster than CELF, PMIA, CoFIM, and IRIE on as-astroPh respectively. It is worth noticing that the performance of our D-CBIM algorithm on Amazon dataset, a network with million edges, only consumes 764 seconds, which explains D-CBIM is more effective than most of the classical heuristic algorithms for social networks.

5.2.4 Discussion on the results

We can draw several conclusions from the experimental results. In the first place, taking the nodes location analysis into account, we present a new method to evaluate the importance of nodes that is utilized to divide the nodes into three kinds: peak node, valley node, and slope node. In addition, in order to apply to dynamic social networks, we partition the dynamic changes into two situations: add nodes or delete nodes. Moreover, empirical evaluations show that our proposed algorithm achieves a better performance on influence spread compared with the four baseline algorithms: PMIA, CCA, CoFIM, and IRIE. The reason is probably that these algorithms only consider the static social network, ignoring the dynamic of joining and deleting nodes, which leads to inaccurate results. Moreover, our algorithm obviously improves the running time of CELF and obtains a similar influence spread as CELF. Unfortunately, one limitation of D-CBIM is that it has an unsatisfactory advantage in running time.

6. Conclusions

In this paper, we propose a new community-based algorithm to address the influence maximization problem, which is applicable to dynamic social networks. Firstly, we utilize a simple and effective algorithm, call Louvain algorithm, to detect community. Then, in each community, propagation degree is utilized to identify the kinds of nodes, which can ensure the candidate seed set. Especially, considering the change of social network, we divide the dynamic nodes into two situations: delete nodes or add nodes. Finally, we adopt the CELF algorithm to optimize the solution from the candidate seed set.

In the future, we will try the best to look for a better method to deal with the influence maximization problem for the dynamic social network. As an example, we can from the aspects of the kinds of edges when a new node adds to the network.

Footnotes

Acknowledgments

This paper is supported by the Nature Science Foundation of China (No. 71772107).

References

Domingos

and Richardson

, Mining the network value of customers, in: KDD, New York, NY, USA, 2001, pp. 57–66.

Kempe

and Kleinberg

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

Leskovec

et al., Cost-effective outbreak detection in networks, in: KDD, New York, NY, USA, 2007, pp. 420–429.

Chen

Wang

and Yang

, Efficient influence maximization in social networks, in: ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA, 2009, pp. 199–208.

Chen

Yuan

and Zhang

, Scalable Influence Maximization in Social Networks under the Linear Threshold Model, in: International Conference on Data Mining. IEEE, Sydney, Australia, 2011, pp. 88–97.

Jung

Heo

and Chen

, IRIE: Scalable and Robust Influence Maximization in Social Networks, in: IEEE 12th International Conference on Data Mining, Brussels, Belgium, 2012, pp. 918–923.

Kitsak

Gallos

L.K.

Havlin

Liljeros

Muchnik

Stanley

H.E.

and Makse

H.A.

, Identification of influential spreaders in complex networks, Nat. Phys 6(11) (2010), 888–893.

Cao

J.X.

Dong

et al., A k-core based algorithm for influence maximization in social networks, Chinese Journal of Computers 38(2) (2015), 1–7.

Wang

Zhang

Lin

and Chen

, Bring Order into the Samples: A Novel Scalable Method for Influence Maximization (Extended Abstract), in: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), San Diego, CA, 2017, pp. 55–56.

10.

Huang

Wang

Bevilacqua

Xiao

and Lakshmanan

L.V.

, Revisiting the stop-and-stare algorithms for influence maximization, VLDB Endow 10(9) (2017), 913–924.

11.

Shang

Zhou

Liu

and Tang

, Effective influence maximization based on the combination of multiple selectors, in: Intel. Conf. Wireless Alg. Syst. App., Guilin, China, 2017, pp. 572–583.

12.

Yang

and Liu

, Influence maximization-cost minimization in social networks based on a multiobjective discrete particle swarm optimization algorithm, IEEE Access 6 (2018), 2320–2329.

13.

Y.-Y.

Chae

D.-K.

and Kim

S.-W.

, Influence maximization in social networks: a target-oriented estimation, J. Inf. Sci. 44(5) (2018), 016555151774828.

14.

Shi

Song

Shi

et al., A high-influence greedy maximization algorithm based on community structure, Journal of Computational Information Systems 11(2) (2015), 449–456.

15.

Shang

Liu

et al., Targeted revision: a learning-based approach for incremental community detection in dynamic networks, Physica A: Statistical Mechanics and its Applications 443 (2016), 70–85.

16.

Girvan

and Newman

M.E.J.

, Community structure in social and biological networks, Nation. Acad. Sci 12 (2002), 7821–7826.

17.

Cao

Wang

et al., OASNET: An optimal allocation approach to influence maximization in modular social networks, in: Acm Symposium on Applied Computing, Sierre, Switzerland, ACM, 2010, pp. 1088–1094.

18.

Chen

Y.C.

Zhu

W.Y.

Peng

W.C.

et al., CIM: community-based influence maximization in social networks, Acm Transactions on Intelligent Systems & Technology 5(2) (2014), 1–31.

19.

Shang

Zhou

et al., CoFIM: a community-based framework for influence maximization on large-scale networks, Knowledge-Based Systems 117(1) (2016), 88–100.

20.

Bozorgi

Haghighi

Sadegh Zahedi

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

21.

Bozorgi

Samet

Kwisthout

et al., Community-based influence maximization in social networks under a competitive linear threshold model, Knowledge-Based Systems 134(Oct.15) (2017), 149–158.

22.

Song

Zhou

Wang

et al., Influence maximization on large-scale mobile social network: a divide-and-conquer method, IEEE Transactions on Parallel and Distributed Systems 26(5) (2015), 1379–1392.

23.

Cheng

et al., Community-based seeds selection algorithm for location-aware influence maximization, Neurocomputing 275(1) (2018), 1601–1613.

24.

Blondel

V.D.

Guillaume

J.L.

Lambiotte

et al., Fast unfolding of communities in large networks, Journal of Statistical Mechanics Theory & Experiment 2008(10) (2008), 155–168.

25.

Newman

M.E.

, Fast algorithm for detecting community structure in networks, Physical Review E Statistical Nonlinear & Soft Matter Physics 69(6) (2004), 1–5.

26.

Chen

Shang

M.-S.

Zhang

Y.-C.

and Zhou

, Identifying influential nodes in complex networks, Physica A 391(4) (2012), 1777–1787.

27.

Gao

Chen

Wang

and Xing

, Ranking the spreading capability of nodes in complex networks based on local structure, Physica A 403 (2014), 130–147.

28.

Cao

et al., Local community mining on distributed and dynamic networks from a multiagent perspective, IEEE Transactions on Cybernetics 4(46) (2016), 986–999.

29.

Shang

Liu

Xie

et al., A Real-Time Detecting Algorithm for Tracking Community Structure of Dynamic Networks, in: The 6th SNA-KDD Workshopâ€™12, Beijing, China, 2014, pp. 13–21.

A community-based algorithm for influence maximization on dynamic social networks

Abstract

Keywords

1. Introduction

2.1 The greedy algorithm

2.2 The heuristic algorithm

3. Preliminaries

3.1 Influence maximization problem and diffusion model

3.2 Louvain algorithm

4. The proposed algorithm

Time complexity

5. Results

5.1 Experiment setup

5.1.1 Dataset preparation

5.2.1 Dynamic social network

Table 2 Changes on ca-astrtoph dataset

5.2.4 Discussion on the results

6. Conclusions

Footnotes

Acknowledgments

References

Table 2
Changes on ca-astrtoph dataset