Recent years have witnessed a rapid development of social network services (SNS), such as Twitter^{1}, Facebook^{2}, and Sina Weibo^{3}. More and more users are taking them to share information with friends. For example, in Facebook, there are over 2.01 billion monthly active users all over the world during June 2017^{[1]}. These social networks have the characteristics of openness (i.e., every one can join and keep in touch with the outside world), interaction (i.e., users can interact with friends about a movie or an accident by replying or reposting) and timeliness (i.e., a user can update status messages at any time)^{[2, 3]}.
Users′ participations generate tremendous data in social networks. In Twitter, on average, 500 million tweets are posted per day^{4}. This data contains various informations. For example, people may tweet their opinions on breaking news; or may just update messages to tell friends what have happened in their daily life. Companies may hire influential users to promote new products such as movies and electronic goods. Besides, those information are flowing and can diffuse among users. Once users see something interesting, they can repost or forward these contents to their friends. If their friends also like the contents, they can further share them with their own friends, which thus causes information diffusion in the network, i.e., the socalled effect of wordofmouth. Those users who adopt the information are called influenced or active.
^{4}http://www.internetlivestats.com/twitterstatistics/1108.
However, how the information diffuses through networks is usually unknown. Understanding the diffusion mechanism behind massive information is important for a wide range of applications, such as viral marketing^{[4–6]}, social behavior prediction^{[7–9]}, social recommendation^{[10–12]}, and community detection^{[13–15]}. This issue has attracted researchers from various fields including epidemiology, computer science, and sociology. They proposed different kinds of information diffusion models to describe and simulate this process, such as the independent cascade (IC) model^{[16]}, linear threshold (LT) model^{[17, 4]} and epidemic models^{[18]}. Most models are contagious and assume that the information starts to diffuse from a source (or seed) node set, and other nodes can access the information only from their neighbors.
The discovered diffusion models have been applied to many practical applications. For example, first, by evaluating users′ influence, we can identify influential spreaders^{[19, 20]} and find experts^{[21–23]}. Second, by choosing seed users and solving the socalled influence maximization problem^{[4]}, we can maximize the number of influenced users. This is significant to promote new products through the wordofmouth effect^{[4]} or place sensors to quickly detect contaminants in the water distribution network in a city^{[24, 25]}. Third, after the information diffuses from a set of source nodes for a period of time, it will influence more nodes. We can infer the source nodes according to these observed influenced nodes, which is called information source detection. It can help to prevent the outbreak of an epidemic^{[26–28]} and trace the rumor source in social networks^{[29, 30]}.
Therefore, we will review the recent development of information diffusion analysis in social networks and its applications. Fig. 1 gives an overview of this paper. The rest parts are organized as follows. We start with some preliminaries of social networks in Section 2. Section 3 introduces three basic kinds of information diffusion models. Then we list methods which are used to evaluate the authority and influence in Section 4. Sections 5 and 6 show the solutions to influence maximization and information source detection, respectively. Finally, we conclude some possible directions for further study in Section 7.
Download:


Fig. 1. Overview of recent advances on information diffusion analysis included in this paper 
2 Preliminaries
A social network can be denoted as
Download:


Fig. 2. A toy social network where edges indicate the directions of information flows 
1) Microblogging networks. Nodes represent users or organizations. For example, in Twitter, if user v is a follower of user u, there will be an edge from u to v, and
2) Citation networks. Nodes represent papers and edge
3) Collaboration networks. Nodes represent authors and
4) Email networks. Edge
Different kinds of information can spread in a social network, such as innovations, contagion, opinions about specific events. Note that a node is influenced if it adopts the information. An influenced node will further propagate the information to its neighbors, i.e., wordofmouth, which causes information diffusion in the network. Thus, except for specific explanation, every node has two states: active (i.e., infected/influenced) and inactive. For example, in Twitter, users reposting a funny tweet are active, while others are inactive.
Datasets. There are many websites providing open datasets of social networks for research. Here we list some of them for easy reference.
1) Stanford large network dataset collection^{5}. It is a collection of more than 50 large network datasets from tens of thousands of nodes and edges to tens of millions of nodes and edges, including social networks, web graphs, road networks, Internet networks, citation networks, collaboration networks, and communication networks.
^{5}https://snap.stanford.edu/data/
2) Aminer^{6}. It provides a repository of external datasets for social network analysis, including microblogging networks, patent dataset from Patentminer.org, knowledge linking dataset, mobile dataset and other online social networks.
^{6}https://cn.aminer.org/datasna
3) Social computing data repository^{7}. It hosts datasets from many different social media sites, most of which have blogging capacity, such as BlogCatalog, Twitter, MyBlogLog, Digg, StumbleUpon, del.icio.us, MySpace, LiveJournal, The Unofficial Apple Weblog (TUAW), Reddit, etc.
^{7}http://socialcomputing.asu.edu/pages/home
4) KONECT^{8}. Koblenz Network Collection (KONECT) is a project to collect large network datasets for researching in network science and related fields. It includes several hundred network datasets of various types, including directed, undirected, bipartite, weighted, unweighted, signed and rating networks.
^{8}http://konect.unikoblenz.de/
3 Information diffusion modelsHow the information diffuses through networks is unknown and has been studied by researchers from various fields including epidemiology^{[18]}, computer science^{[16]}, and sociology^{[32]}. They proposed different kinds of information diffusion models to describe and simulate this process. Most of them are contagious and follow two rules below:
Rule 1. Every piece of information diffusion starts from several source nodes.
For example, John is a movie star and posts a tweet on Twitter to promote his new movie. This may cause a hot discussion among his fans, and thus he is the source node initializing this diffusion.
Rule 2. Every disseminator can access the information only from its neighbors.
In the above example, Alice is a fan of John, and she can only read the tweet from John or other fans′ retweeting.
All information diffusion models are consistent with Rule 2, but achieve Rule 2 in different ways. They can be divided into two categories: 1) progressive models where nodes can switch from being inactive to being active, but do not switch in the other direction and 2) non progressive models where nodes can switch in both directions and allow to be activated for many times. In the next part, we will introduce three basic information diffusion models, namely independent cascade (IC) model, linear threshold (LT) model and Epidemic models, which are widely used and are fundamental for personal influence evaluation, influence maximization, etc. More diffusion models can be found here^{[33]}.
3.1 Independent cascade modelIndependent cascade (IC) model was proposed by Goldenberg et al.^{[16]} in 2001. It describes a diffusion like Domino and assumes the information starts from a set of active seed nodes
As time goes by, inactive nodes can receive information from active ones. Specifically, at time t,
Linear threshold (LT) model was proposed by Granovetter^{[17]} in 1978. It assumes that each node v has a specific threshold
$\sum_{u\in N_{in}(v)} w_{uv} \ge \theta_v $  (1) 
where
In summary, there are two main differences between LT and IC models. First, active nodes in the LT model have more than one chance to affect their inactive neighbors. Second, node v′s active neighbors will affect v together in the LT model, while v′s active neighbors only have one chance to independently affect v in the IC model. However, Kempe and McKendrick^{[18]} proposed a general threshold model and a general cascade model, and have proven their equivalence. Besides, both LT and IC models are special cases of the triggering model^{[18]}, where each node v independently chooses a random triggering set
Some researchers adopt the epidemic models to simulate the infection and recovery processes of nodes in networks^{[34, 35]}, which are originally describing how a disease spreads within a population in epidemiology^{[18]}. The information or disease also starts from a set of infected seed nodes
Susceptibleinfectedrecovered (SIR) model^{[18]} generalizes the SI model, and assumes a node has three states: susceptible, infected and recovered. When a node u is infected, it has a probability of
Download:


Fig. 3. Node state transition diagrams for four epidemic models: (a) SI, (b) SIS, (c) SIR, (d) SIRS, where

Indeed, there are other epidemic models, such as susceptible exposed infected recovered (SEIR)^{[37]}, maternal susceptible infected recovered (MSIR)^{[38]}, susceptible exposed infected recovered susceptible (SEIRS)^{[39]}. Readers can refer to the work^{[40]} for more details. How to exploit these models for information diffusion analysis is underexplored.
4 Authority and influence evaluationBased on the above diffusion models, we can evaluate the influence or authority of an individual in social networks, which is important for influential spreader identification^{[19, 20, 41]} and expert finding^{[42, 21, 22]}. A user′s influence and authority seem to be different at a first glance, because “influence” measures the impact that it has on others through outlinks (e.g., persuading them to buy a product) while “authority” is the endorsement received from its followers through inlinks. However, some works^{[43, 44]} have realized that they have a close relationship because an individual earns its authority by influencing others. In the next, we will show how to evaluate the influence and authority.
4.1 Authority evaluationIn this subsection, we focus on the solutions to authority evaluation which only exploit the network structure, such as centrality based and PageRank. Readers can find other methods by referring to the work^{[45]}.
4.1.1 Centrality basedThere are many ways to compute the centrality of a node and its larger value means more influential. The first and simplest way is degree centrality, which equals to the number of links upon a node. In a directed network, we can use outdegree and indegree to measure the centrality, respectively. For a node u, outdegree can evaluate its importance as information senders, while indegree measures its gregariousness. That′s to say, the larger u′s outdegree is, the more users u will affect. While the larger u′s indegree is, the closer u is to others.
For degree centrality, it considers nodes with more connections to be more influential. In fact, the influence of a node should be determined by its neighbors. Eigenvector centrality provides another way to measure individual influence with this fact. Let
$c_e(u) = \frac{1}{\lambda}\sum_{v\in V}a_{v, u}\times c_e(v) $  (2) 
where
$\lambda {{c}}_e = {{A}}^{\rm T}{\bf{c}}_e $  (3) 
where
The third way to compute centralities is based on the distance between nodes. 1) Node u′s closeness centrality^{[46]},
$c_c(u) = \frac{1}{\sum\limits_{v\in V}d(u, v)} $  (4) 
where
$c_b(u) = \sum_{s\ne u \ne t\in V}\frac{\sigma_{st}(u)}{\sigma_{st}} $  (5) 
where
$c_j(u) = \frac{1}{\max\{d(u, v)v\in V\}}.$  (6) 
Note that the closeness and Jordan centralities assume authoritative nodes can send information to others as fast as possible, while betweenness centrality shows how important a node is in connecting others as a pivot.
When comparing nodes of graphs with different sizes, we can normalize the aforementioned centralities by things like the number of nodes. Readers can find more details in the work^{[36]}.
4.1.2 PageRankPageRank^{[49]} is originally used for evaluating authorities of Web pages and as the cornerstone of Google′s search engine^{9}. It is also an extension of the normal eigenvector centrality discussed above. The general PageRank values
${{x}}=d{{W}}{{x}} +\frac{1d}{n}{{e}}$  (7) 
where
The random surfer model^{[49]} can explain PageRank vividly. A user starts surfing on a web page and then clicks current links randomly. He will continue clicking until stopping at a desired page. PageRank assumes that the surfer is more likely to stop at important pages. When d = 1,
Haveliwala^{[51]} considered more personalized knowledge and proposed a topicsensitive PageRank. The uniform personalization vector
Due to its simplicity and effectiveness, PageRank has been applied to complete many tasks, such as influential spreaders identification^{[19]} and link prediction^{[11]} in social networks, item recommendation^{[54]} and expert finding^{[22]}.
4.2 Influence evaluationSomeone′s influence can be considered as the ability to affect others. Kempe et al.^{[4]} defined the influence of a node set A to be the expected number of active nodes at the end of the process, which is also named influence spread, given that A is the initial active set. Many methods have been designed to compute this value efficiently and effectively.
4.2.1 Monte Carlo simulationKempe et al.^{[4]} proposed to run Monte Carlo (MC) simulations to estimate the influence spread under the IC model or LT model. The MC simulation is a process: under the IC or LT model, we diffuse a piece of information from a node set A in the network, and can get the number of active nodes at the end of this diffusion. Therefore, the influence spread of a node set A, denoted as
$f(A) = \frac{1}{R}\sum_{v\in V}\delta(v) $  (8) 
where R is the count of MC simulations, and
Chen et al.^{[55]} further studied this problem, and got the following depressing result. Given a node set A, computing its influence spread
$\pi (i) = \left\{ {\begin{aligned}& 1, & {{\rm{if }} \; i \in A}\quad\,\, \\& {1  \prod\limits_{j \in V} {(1  {w_{ji}}\pi (j))} }, & \quad {{\rm otherwise}.}\end{aligned}} \right.$  (9) 
That means in order to let node i assimilate the information, it must receive the information from at least one of its neighbors. Then, the sum of steadystate assimilation probabilities of all nodes can reach the desired influence spread.
Yang et al.^{[58]} noted that (9) is not strictly applied to some situations. For example, it is invalid when the network has structuraldefect node pairs. More importantly, there are some difficulties in solving systems of nonlinear equations, such as convergence and multiple solutions. They illustrated an observation that influence propagation probabilities in realworld social networks are usually quite small. Then, they represented the steadystate probability approximation by a linear system defined as
$\pi (i) = \sum_{j\in V}w_{ji}\pi (j).$  (10) 
They also proposed a simple iterative algorithm to solve the linear system problem. We can see (10) is similar to (2). This indicates that the influence and authority should have a latent relationship, which we will discuss in the next subsection.
However, in many scenarios, the network where diffusions take place is in fact implicit or even unknown. For example, in viral marketing settings, we only observe people purchasing products without explicitly knowing who was the influencer that caused the purchases. Thus, Yang and Leskovec^{[59]} studied modeling information diffusion in implicit networks. They focused on modeling the global influence of a node on the rate of diffusion through the (implicit) network over time. Every node u has a particular nonnegative influence function
$V(t) = \sum_{u\in A(t)}I_u(tt_u) $  (11) 
where
More methods to estimate the influence spread when dealing with the influence maximization problem will be introduced in Section 5.2.
4.2.3 PageRank with priorXiang et al.^{[44, 60]} further understood PageRank from the perspective of influence propagation to explore the relationship between authority and influence. Specifically, they first proposed a linear social influence computation model as follows.
Definition 1. Denote the influence from node i to j by
${f_{i \to i}} = {\alpha _i}, \quad {\alpha _i} > 0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$  (12) 
${f_{i \to j}} = \frac{1}{{1 + {\lambda _j}}}\sum\limits_{1 \le k \le n} {{w_{kj}}} {f_{i \to k}}, \quad {\rm{ for }} \; j \ne i $  (13) 
where
Equestion (13) shows that the influence from node i to j is proportional to the linear combination of its influence on j′s neighbors. That′s to say, if i wants to affect j, he can successfully affect k and then k will affect j with a probability of
The authors noticed that PageRank is actually a special case of the linear social influence model in Definition 1 with an appropriate priority. This shows the reasonableness of taking PageRank as a baseline in social influence related applications^{[57, 54, 61]}. Moreover, the authors found individual influence
Actually, influences of different nodes may have overlaps that affect the same part of other nodes. For instance, in a social network, users u and v are adjacent, and u is one of the most influential users. If affecting u successfully, v can affect more others with the help of u, and thus its observed influence is much larger than the real value. Liu et al.^{[62]} noted this scenario and tried to compute the independent social influence based on the linear model in Definition 1. They introduced the following definition of independent social influence.
Definition 2. Denote the influence from node
$f_{i\to i}^{S\backslash i}= 1\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$  (14) 
$f_{i\to j}^{S\backslash i}= 0, \quad j \in S\backslash i\quad\quad\quad\quad\quad\quad$  (15) 
$f_{i \to j}^{S\backslash i} = d\sum\limits_{1 \le k \le n} {{w_{kj}}} {f_{i \to k}}, \quad j \notin S $  (16) 
where
From the difference with Definition 1, we can see that
Liu et al.^{[63]} provided a bounded linear approach for influence computation, called Group PageRank. They first extended Definition 1 of influence to a set on another node.
Definition 3. Denote the influence from a node set S to node j by
$\hspace{75pt}f_{S\to j}= 1, \quad {\rm if} \,j\in S $  (17) 
$f_{S\to j}= d\sum_{1\le k\le n}w_{kj} f_{S\to k}, \quad {\rm otherwise}$  (18) 
where
Then they found that the influence from S to T,
$f_{S\to T} \le \frac{T}{1d}\sum_{i\in S}(1  d\sum_{k\in S}t_{ki})fPR_i \overset{\bigtriangleup}{=} GPR(S, T) $  (19) 
where
In summary, getting the exact value of influence is hard, and thus many approximate methods have been proposed to simplify the computation process and improve the efficiency.
5 Influence maximizationIn this section, we will show how to solve the influence maximization problem based on information diffusion models and influence evaluation.
In a social network such as Twitter, which users should be selected to offer discounts and then let them promote a new product through the wordofmouth effect? Given the water distribution network in a city, where should we place sensors to quickly detect contaminants? Both of them can be formalized as the influence maximization (IM) problem that selects a set of seed nodes to maximize the expected number of active nodes at the end of diffusion process. It was first noted by Richardson and Domingoes^{[6]} when they mined knowledgesharing sites for viral marketing. Then Kempe et al.^{[4]} formulated it as the following discrete optimization problem.
Problem 1 (Influence manimization).
In a social network
$S = \arg \max_{S\subset V} f(S), \qquad {\rm s}.{\rm t}. \quad S = K $ 
where
There are two intuitive solutions: one is enumerating and selecting the subset with the maximal influence spread. This will lead to combinatorial explosion and is not applicable to largescale networks. The other is selecting topK nodes with maximal influences, but different individual influences may overlap with each other so that their collective influence is not the maximal. Kempe et al.^{[4]} claimed that influence maximization is NPhard under the independent cascade (IC) model and linear threshold (LT) model. Therefore, many researchers focus on this problem due to its wide applications and propose various approximation methods to speed up the solutions, which can be divided into four categories: greedy, heuristic, reverse sampling and other algorithms.
5.1 Greedy algorithmsKempe et al.^{[4]} noted that the influence spread function f under the IC and LT model is monotone and submodular.
Definition 4 (Monotonicity). A set function
Definition 5 (Submodularity). A set function
$f(S\cup \{u\})f(S) \geq f(T\cup \{u\})f(T)$ 
for any u and
For a nonnegative, monotone and submodular function f, let S be a set of size k obtained by selecting elements one at a time which provides the maximal marginal increase of the function value. Let
$f(S)\ge (1\frac{1}{e})f(S^\ast) $  (20) 
i.e., S provides a (1 –
Algorithm 1. Framework of the greedy algorithm
Input:
K – the number of seed nodes
Output:
S – the seed set
1)
2) while
3)
4)
5) end while
6) return S
Therefore, Kempe et al.^{[4]} proposed a framework of the greedy algorithm to select seed nodes one by one and its pseudo codes are listed in Algorithm 1. It starts with an empty seed set. In each iteration, we compute the marginal influence gain for each node, and then the node which provides the largest marginal influence gain is selected into the set (i.e., Lines 3 and 4).
Definition 6 (Marginal influence gain). Given a node set, the marginal influence gain of node u,
This simple algorithm provides an amazing performance guarantee that it can approximate the problem with a ratio of
We can see the bottleneck of Algorithm 1 is to evaluate the influence spread of a seed set (i.e., the value of f). Kempe et al. ran Monte Carlo (MC) simulations for R times to estimate its value under the IC or LT model, as described in Section 4.2.1. Thus, the Monte Carlo simulation will be executed
Leskovec et al.^{[24]} exploited the submodularity to avoid unnecessary recalculations of the marginal influence gains in each iteration, and developed an efficient algorithm, namely costeffective lazy forward (CELF) selection. It is based on the diminishing returns property that the earlier a node is selected into the seed set, the larger marginal influence gain it can achieve. That means for a node
$\Delta_{u}(S_k)\ge \Delta_{u}(S_{k+1}) $  (21) 
where
Algorithm 2. Costeffective lazy forward (CELF)^{[33]}
Input:
K – the number of seed nodes
Output:
S–the seed set
1)
2) for
3)
4)
5) add u to Q in the decreasing order of
6) end for
7) while
8) u = the first element in Q
9)
10) if
11)
12) else
13)
14)
15) add u to Q again in the decreasing order of
16) end if
17) end while
18) return S
Its pseudo codes are shown in Algorithm 2. Specifically, it initializes each node′s marginal influence gain (i.e.,
Eventually, CELF not only keeps the performance with a ratio of
Besides, Liu et al.^{[63]} explored Group PageRank in Section 4.2.5 as the influence spread and adopted the greedy framework to solve this problem. In the (k+1)st iteration, node u′s marginal influence gain is
Although aforementioned methods exploit the lazy evaluation to speed up the greedy algorithm, their running time on largescale networks is still very high. Therefore, many researchers start to develop heuristic algorithms to further improve the efficiency of influence spread evaluation according to properties of specific diffusion models.
5.2.1 Shortest pathDue to the hardness of getting an exact calculation or a good estimate of influence spread, Kimura and Saito^{[67]} proposed two models, shortestpath model (SPM) and shortestpath1 model (SP1M), to simplify the IC model and to efficiently obtain good approximate solutions to the influence maximization problem, when the propagation probabilities through links are small. In SPM, each node v has the chance to become active only at step
More importantly, adopting the greedy framework in Algorithm 1 can guarantee the output with a ratio of
When selecting the seed nodes one by one, Chen et al.^{[68]} explored the effect of the selected seed nodes on the rest nodes. They adopted the node degree to estimate its influence and proposed two degree discount heuristics to diminish that effect.
1) SingleDiscount: Each neighbor of a newly selected seed will discount its degree by one. This heuristic can be applied to all information diffusion models.
2) DegreeDiscountIC: This is a more accurate degree discount heuristic for the IC model with a small propagation probability p. When selecting v into the seed set, the increase of the expected number of active nodes is
$1+(d_v  2t_v  (d_v  t_v)t_vp+o(t_v))\times p$  (22) 
where
They have shown that the above degree discount heuristics achieve much larger influence spread than classic degree and centralitybased heuristics. What′s more, DegreeDiscountIC achieves almost equal influence thread with the greedy algorithm when tuned for a specific influence cascade model. However, they have no performance guarantee for general graphs.
5.2.3 Maximum influence pathChen et al.^{[55]} extended SPM and SP1M by considering maximum influence paths (MIP) instead of shortest paths, to approximate the actual expected influence within the social network. Its main idea is to use local arborescence structures of each node to approximate the influence propagation.
Specifically, a maximum influence path between node u and v is the path with the maximum propagation probability from u to v. They first computed maximum influence paths between every pair of nodes in the network via a Dijkstra shortestpath algorithm, and ignore MIPs with probabilities smaller than an influence threshold
When the graph is sparse and the propagation probabilities on edges are small, to improve the efficiency, they provided a variant of MIA, called prefix excluding MIA (PMIA) with a batch update^{[55]}. When selecting the next seed, for every node v, PMIA recomputes its inarborescence so that every seed candidate
Moreover, they have proved that the influence spreads in the MIA and PMIA models are submodular and monotone^{[55]}. Therefore, adopting the greedy algorithm in previous subsection under the MIA and PMIA model can also approximate the problem with a ratio of
After that, many works try to further extend the above algorithm, e.g., IRIE^{[66]}, local directed acyclic graph (LDAG)^{[56]} and simple path (SIMPATH)^{[69]}. IRIE integrates a new message passing based influence ranking (IR), and influence estimation (IE) methods for influence maximization in both the independent cascade (IC) model and its extension ICN that involves negative opinion propagations. In each round of selecting a seed node, the greedy algorithm uses Monte Carlo simulations while PMIA uses more efficient local arborescence based heuristics to estimate the influence spread of every possible candidate. This is especially slow for the first round where the influence spread of every node needs to be estimated. Therefore, Jung et al.^{[22]} proposed a novel global influence ranking (IR) method derived from a belief propagation approach, which uses a small number of iterations to generate a global influence ranking for the nodes and then selects the highest ranked node as the first seed. To avoid the overlapping influence, they integrated IR with a simple influence estimation (IE) method, so that after one seed is selected, they can estimate additional influence impact of this seed to other nodes in the network, and then use the results to adjust next round computation of influence ranking. IE is much faster than directly estimating marginal influence gain of many seed candidates. When combining IR and IE together, we obtain the fast IRIE algorithm.
On the other hand, LDAG^{[56]} and SIMPATH^{[69]} are tailored for the LT model. LDAG exploits the fact that computing influence spread in directed acyclic graphs (DAGs) can be done in linear time. It constructs a local DAG surrounding every node v in the network, and restricts the influence to v within the local DAG structure. This makes influence computation tractable and fast on a small DAG. Then the authors combine the greedy algorithm with a fast scheme that updates the incremental influence spread of every node. While SIMPATH builds on the fact that the spread of a set of nodes can be calculated as the sum of spreads of each node in the set on appropriate induced subgraphs under the LT model. It iteratively selects seeds in a lazy forward manner like CELF. Instead of using expensive MC simulations to estimate the spread, it can be computed by enumerating the simple paths starting with the seed nodes within a small range of neighborhood, where the majority of the influence flows since probabilities of paths diminish rapidly as they get longer.
In general, these heuristic algorithms are more efficient for largescale networks through properties of specific diffusion models, but few of them can keep the performance guarantees under the standard IC and LT models described in Section 3.
5.3 Reverse sampling algorithmsRecently, Borgs et al.^{[70]} made a theoretical breakthrough and inspired many researchers to solve the influence maximization problem from a quite different perspective of reverse sampling, which has approximation guarantees and is even more efficient than the above heuristic algorithms.
We first introduce two concepts for better explanation.
Definition 7 (Reversa reachable set). Let v be a node in G, and g be a graph obtained by removing each edge e in G with
Definition 8 (Random RR set). Let
Borgs et al.^{[70]} proposed a reverse influence sampling (RIS) method under the IC model. It runs in two steps:
1) Generate a certain number of random RR sets from G.
2) Use the standard greedy algorithm for the maximum coverage problem^{[72]} to select k nodes to cover the maximum number of RR sets generated.
Its main idea is if a node u appears in a large number of RR sets, then it should have a high probability to activate many other nodes under the IC model; in that case, u′s influence spread should be large. More importantly, RIS can return a (
However, RIS has a large hidden constant factor in its time complexity so that its practical efficiency is rather unsatisfactory. Tang et al.^{[71]} borrowed ideas from RIS and proposed a twophase influence maximization (TIM) algorithm. It first computes a lowerbound of the maximum expected influence spread among all sizek node sets and then uses the lowerbound to derive a parameter
Nguyen et al.^{[75]} designed two novel sampling algorithms SSA and DSSA, aiming to achieve minimum number of RIS samples. However, Huang et al.^{[76]} revised their work and discovered inaccuracies in previously reported technical results on the accuracy and efficiency of SSA and DSSA, which was set right by then. They presented a revised version of SSA, dubbed SSAFix that restores
There are various other algorithms for influence maximization, and here we demonstrate four typical methods which may bring us new perspectives.
First, now that evaluating influence spread on the whole network is timeconsuming, can we just deal with it on the communitylevel? A community is a densely connected subset of nodes that are only sparsely linked with the remaining network^{[15]}. Wang et al.^{[77]} noted this idea and proposed a communitybased greedy algorithm (CGA), for mining topK influential nodes in mobile social networks, following the divideandconquer principle. Specifically, they first extended a community detection method so that it can divide the network into communities based on information diffusion models. Then they proposed a dynamic programming method to incrementally choose the communities to be processed. Within a community, we can adopt any existing algorithm to detect influential nodes, such as PageRank and CELF. Besides, they have proved that CGA obtains a (
Second, Wang et al.^{[78]} noticed that influence maximization finds some influential nodes whose influences can cover the whole network, which is similar to selecting some informative rows to reconstruct a matrix. Thus, they proposed a novel framework, named data reconstruction for influence maximization (DRIM), from the perspective of data reconstruction. They first constructed an influence matrix, each row of which is the influence of a node on other nodes. Instead of using timeconsuming Monte Carlo simulations to estimate the influence spread, they turn to the linear social influence model in Definition 1, which gives us a closedform solution to the influence of each node. Then, they selected the most informative k rows to reconstruct the matrix and their corresponding nodes are the seed nodes which could maximize the influence spread. The experimental results show that the proposed framework is at least as effective as the traditional greedy algorithm^{[4]}. However, this framework has no performance guarantee and its time complexity is too high.
Third, Jiang et al.^{[79]} proposed a totally different approach based on simulated annealing (SA) to the influence maximization problem. Simulated annealing simulates the process of metal annealing and optimizes the solutions to a number of NPhard problems. The proposed SA based algorithm for influence maximization problem will converge towards optimum as the iteration number grows larger. SA can escape the local optimum and is able to learn to improve the influence spread of solution set automatically. They also designed two heuristic methods to accelerate the convergence process of SA, and a new method of computing influence to speed up the proposed algorithm.
Finally, indeed, users′ influences and the network structure are dynamic over time. The previous works are done only in static networks. Rodriguez and Schölkopf^{[80]} focused on influence maximization in continuous time diffusion networks. They described how continuous time Markov chains allow us to analytically compute the average total number of nodes reached by a diffusion process starting in a set of seed nodes. They also showed that selecting a set of most influential source nodes in the continuous time influence maximization problem is NPhard, and developed an efficient approximation algorithm with provable nearoptimal performance. Wang et al.^{[81]} studied the incremental influence maximization for dynamic social networks. They designed an incremental algorithm, dynamic influence maximization (DIM), for the linear threshold model. It consists of two phases: initial seeding and seeds updating. They also proposed two pruning strategies for the seeds updating phase to further reduce the running time. While Wang et al.^{[81]} tried to track the influential nodes in dynamic networks. They modeled a dynamic network as a stream of edge weight updates, which embraces many practical scenarios as special cases, such as edge and node insertions, deletions as well as evolving weighted graphs. Their key idea is to use the pollingbased methods and maintain a sample of random RR sets so that we can approximate the influence of nodes with provable quality guarantees.
5.5 Variants of influence maximizationThere have been many variants of the classical influence maximization for different applications. Here we will briefly discuss some of them and hope to attract more readers for further study.
First, try to generalize the influence maximization problem or add more constrains to the original formulation in Problem 1. For example, budgeted influence maximization (BIM) is identifying a small set of influential individuals who can influence the maximum number of members within a limited budget. It was formally described by Kempe et al.^{[4]} and attracted much attention later^{[82, 83]}. While Yang et al.^{[84]} took a step further and proposed the continuous influence maximization (CIM) problem. It deals with a realworld scenario: Imagine we are introducing a new product through a social network, in which we can get the purchase probability curve with respect to discount for each user in the network. Based on that, it can be decided what discount should be offered to those social network users so as to maximize purchases under a predefined budget. We can see CIM is a generalization of influence maximization (IM) and BIM. Besides, Aslay et al.^{[85]} studied the revenue maximization problem in incentivized social advertising. It is to allocate advertisements to influential users with the rational goal of maximizing its own revenue. They consider the propensity of advertisements for viral propagation, and carefully apportion the monetary budget of each of the advertisers between incentives to influential users and adengagement costs.
Second, in many realworld cases, marketers usually target certain products at particular groups of customers. For example, a cosmetic company would want its products to attract more women than men. Li et al.^{[86]} formulated the above as a labeled influence maximization problem, which aims to find a set of seed nodes to trigger the maximum spread of influence on the target customers in a labeled social network. The label information is widely available in current social networks, by which users describe their personal interests, graduated colleges, hometown, age, skills, etc. Tang et al.^{[87]} considered the magnitude of influence and the diversity of the influenced crowd at the same time, and formulated it as the diversified influence maximization problem. An obvious case is that this could reduce the risk of marketing campaigns, as the proverb goes: “Don′t put all your eggs in one basket”. Besides, Liu et al.^{[88]} combined targeted marketing with viral marketing to build a better and stronger marketing business. Targeted marketing identifies typical customers and concentrates marketing efforts on these customers, which could make the promotion of items much easier and more costeffective. They studied the problem of maximizing information awareness in viral marketing with constrained targets.
Third, Wang et al.^{[89]} considered both active nodes and informed nodes that are aware of the information when they study the coverage of information propagation in a network. They proposed a new problem called information coverage maximization that aims to maximize the expected number of both active nodes and informed ones, and showed this problem is NPhard and submodular in the IC model. After that, they further studied the activity maximization problem^{[90]} which selects a set of seed users to maximize the expected total amount of excitements for a piece of new information. It is substantially different from the renowned influence maximization problem and cannot be tackled with the existing approaches. In a social network, the excitements among different users even at the same information are different. They aim to find an optimal set of seed users under a given budget, and start information propagation from the seed users so as to gather the maximum sum of activity strengths among the influenced users.
Finally, sometimes, more than one type of information such as different information about competitive products is spreading in social networks. He et al.^{[91]} focused on the blocking maximization problem under the competitive linear threshold (CLT) model, which states that one entity would try to block the influence propagation of its competing entity as much as possible by strategically selecting a number of seed nodes that could initiate the propagation by themselves. They extended LDAG^{[56]} and designed an efficient algorithm competitive local directed acyclic graph (CLDAG) which utilizes the properties of the CLT model, to address this issue. Besides, it is supposed that one of the competitors could enhance its influence by creating new links. A natural question is, when the number of new links is limited due to limited resource, how to add these links so as to maximize the influence of the given competitor over the others (called competitiveness). Zhao et al.^{[92]} formulated it as a competitiveness maximization problem on complex networks. They take two cases into consideration: maximize the number of supporters of the competitor and maximize the total supporting degree of normal agents toward the competitor. Besides, many individuals also care about the influence of themselves and want to enhance the influence. Thus, Ma et al.^{[93]} considered an individual influence maximization problem that maximizing the target individual influence by recommending new links.
6 Information source detectionThe purpose of influence maximization is to find a small set of seed nodes to maximize the expected number of activated users. But when observing which nodes are active after a piece of information has diffused in the network, can we infer the source or seed nodes triggering this observed diffusion result? For example, after a rumor has spread among the network, we want to find the rumor source nodes to stop its dissemination. This problem is called information source detection (or patientzero), which can be considered as the reverse process of information diffusion. It also has attracted many researchers to study, due to its wide range of applications such as epidemic outbreak prevention^{[26–28]} and rumor source tracing in social networks^{[30, 29]}.
After the information starts to spread in the network G from an unknown source node set
Problem 2 (Information source detection). Given graph
For example, in Fig. 4, we observe seven infected nodes and want to identify the source node. This problem is challenging due to many aspects. First, we often observe only one snapshot of the network and get the states of some nodes, which is just a part of the whole diffusion process. That means we just know which nodes are infected, but cannot distinguish the propagation paths that indicate who infects who and when they are infected. Second, the actual information diffusion laws are unknown, which cannot be comprehensively described by the models in Section 3. Third, information diffusion is highly dynamic and has a great variety of patterns when initiated from different sources. For instance, a photo will be shared for many times if it is posted by a celebrity in social networks. Forth, there are usually multiple source nodes in realworld scenarios, while the number is unknown. Finally, the timestamp
Download:


Fig. 4. Information diffusion in a toy social network, where the orange node 5 is the source node and gray nodes are infected, while others are susceptible. Edges indicate the directions of information flows. Color versions of the figures in this paper are available online. 
Shah and Zaman^{[35]} are among the first to consider this problem. After that, many efforts have been devoted to different cases, which can be divided into three categories^{[94]} according to the observed node states: complete observation partial observation sensor observation. Fig. 5 shows three examples of observed diffusion results for each category. In the next part, we will briefly describe the corresponding solutions to detect the source nodes of the observed three categories in recent years.
Download:


Fig. 5. Three examples^{[94]} of observed diffusion results corresponding to three categories of observation for information source detection in a network, whose edges between nodes are hidden for brevity 
6.1 Detection with complete observation
In this subsection, we introduce some detection methods with the complete observation. It means when observing the diffusion at time t after the information has spread, we will get the complete states of all nodes in the whole network. That′s to say that we can identify which nodes are infected, and which are recovered or still susceptible.
6.1.1 Rumor centerWhen noticing the source detection problem in their seminal work, Shah and Zaman^{[35]} provided a systematic study on finding the source of a computer virus in a network. They assumed there is only one source node and described the virus spreading in a network with the SI model, a variant of the popular SIR model. Then they constructed the following maximum likelihood estimator for the virus source.
$\hat{v} = \arg\max_{v\in V_I} P(G_Iv^\ast = v)$  (23) 
where
Luckily, they found the rumor centrality
$R(v, G_I) = V_I\prod_{u\in V_I} \frac{1}{T_u^v} $  (24) 
where
Their method has several limitations in some aspects. First, it is only applicable for the case when there is one source node. Second, it only considers the infected subgraph and neglects other uninfected nodes which are also important for detecting the source. Third, rumor centrality assumes that the probabilities of all permitted permutation are equal for general graphs.
After that, some researchers tried to improve this method. Dong et al.^{[95]} constructed a maximum a posteriori (MAP) estimator to detect a single source from many suspect nodes under the SI model. A priori knowledge will indicate the set of suspect nodes
Besides, Wang et al.^{[96]} addressed the problem of single rumor source detection with multiple independent observations under the SI model by joint rumor center. Suppose k different rumors originate from a common node in the network, which can be regarded as k times independent rumor spreading with the same rumor source. For each rumor spreading, we can observe a corresponding infected subgrpah. For regular tree graphs, they showed the detected source is a node that maximizes the product of its rumor centralities in each infected subgrpah. They found even with two observations, the detection probability at least doubles that of a single observation. Luo et al.^{[97]} considered the problem of estimating the multiple infection sources and the infection regions (subsets of nodes infected by each source) in a network. They exploited the Voronoi partition to estimate the infection regions and combined two regions to find two source nodes with their source estimation method, an extension of rumor centrality. They proved that if there are at most two infection sources in a geometric tree, their estimator identifies the true source nodes with a probability going to one as the number of infected nodes increases. However, this method can hardly be used in the real world, especially on largescale networks due to its high time complexity.
6.1.2 Eigenvector centerThe second kind of source detection methods is based on the eigenvector center, which exploits the adjacent matrix analysis. For example, Fioriti and Chinnici^{[27]} predicted the multiple sources of an outbreak with a spectral technique. They proposed to use the node dynamical importance (DI) which is the reduction of the largest eigenvalue of the adjacency matrix after a node has been removed, to assess the most prominent nodes of a network. They noted that a large reduction after the elimination of a node implies the node is relevant to the aging of an infection network. Dynamical importance (i.e., dynamic age) of node v is defined by
$DI_v = \frac{\lambda_m^{new}\lambda_m}{\lambda_m}$  (25) 
where
Besides, based on the minimum description length (MDL) principle, Prakash et al.^{[28]} proposed a novel method, NETSLEUTH, under the SI model. The total description length of a diffusion consists of two parts: cost of the model to identify the source nodes S and cost of describing the infected subgraph
The third kind of source detection methods is based on sampling to estimate the likelihood of observing the infected subgraph for each node. Different with previous methods, they focus on the stochastic diffusion models, such as the independent cascade (IC) model and linear threshold (LT) model. For example, Zhai et al.^{[98]} designed a Markov chain Monte Carlo (MCMC) algorithm to find the single source of a cascade given the snapshot under the IC model. They formulated the detection as a source inference problem with maximum likelihood estimation like Problem 2, and proved its #Pcompleteness. Note that the generation of infected subgraphs corresponds to a specific distribution
Besides, Nguyen et al.^{[100]} proposed a new approach to identify multiple infection sources by searching for a seed set S that minimizes the symmetric difference between the cascade from S and
A diffusion kernel can represent diffusion processes in a given network, but computing this kernel is computationally challenging in general. Feizi et al.^{[101]} proposed a pathbased network diffusion kernel which considers edgedisjoint shortest paths among pairs of nodes in the network, and can be computed efficiently for both homogeneous and heterogeneous continuoustime diffusion models. They used this network diffusion kernel to solve the inverse diffusion problem, named network infusion (NI) with both likelihood maximization and error minimization. They applied this framework to both singlesource and multisource diffusion, and singlesnapshot and multisnapshot observations, using both uninformative and informative prior probabilities for candidate source nodes.
Pena et al.^{[102]} casted the problem of source localization on graphs as the simultaneous problem of sparse recovery and diffusion kernel learning (SRDKL). A
Zhu and Ying^{[103]} presented a new source localization algorithm under the independent cascade (IC) model, called the shortfat tree (SFT). Loosely speaking, the algorithm selects a node as the source such that the breadthfirst search (BFS) tree from the node has the minimum depth but the maximum number of leaf nodes. They also established the performance guarantees of SFT for both tree networks and the ErdosRenyi (ER) random graph. On tree networks, SFT is the maximum a posterior (MAP) estimator.
6.2 Detection with partial observationIn some scenarios, we can only observe the states of partial nodes at a given time t. Jiang et al.^{[94]} summarized them as four cases.
1) Nodes reveal their states with probability
2) We can identify all infected nodes, but cannot distinguish susceptible or recovered nodes, because some infected nodes may recover from the disease with a probability such as in the SIR model.
3) Only the nodes infected at time t are observed, while the states of other nodes infected before time t are missing. For example, the observed black nodes in the ring in Fig. 5 are infected at time t.
4) We only observe a part of nodes at time t due to some limitations such as financial and human resources. Note that some observed nodes may be infected before time t.
In the next part, we will introduce some typical solutions to different cases.
6.2.1 Jordan centerThis kind of methods selects a Jordan center as the detected source node, which has the maximal Jordan centrality defined in (6). That means Jordan center is a node minimizing the maximum distance with other nodes. Zhu and Ying^{[104]} studied the source detection problem under the popular SusceptibleInfectedRecovered (SIR) model. Given a snapshot of the network, we know all infected nodes but cannot distinguish the susceptible nodes and recovered nodes. The network is assumed to be an undirected graph and each node in the network has three possible states: susceptible (S), infected (I), and recovered (R). Nodes in state S can be infected and change to state I, and nodes in state I can recover and change to state R.
They formalized this problem with maximum likelihood estimation (MLE). To solve it, we need to consider all possible infection sample paths, which is impossible for largescale networks with unknown initial infection time
Zhu and Ying^{[105]} further extended this method for source detection under the heterogeneous SIR model with sparse observations. They assumed that a small subset of infected nodes are reported. The heterogeneous SIR model allows different infection probabilities along edges and different recovery probabilities at different nodes. Besides, Luo et al.^{[106, 107]} explored the sample path based approach for source detection under SI and SIS models. They obtained the same conclusion as under the SIR model: the detected source is a Jordan center. However, the Jordan center method is designed for treelike networks, which are very different from realworld networks.
6.2.2 Message passing methodsThe second kind of methods is based on message passing. Lokhov et al.^{[108]} took the infected and uninfected nodes to detect the source node under the SIR model. They introduced an effective inference algorithm based on dynamic message passing (DMP) equations. Let
$\begin{split}& P_S^i(t + 1) = P_S^i(0)\prod\limits_k {{\theta ^{k \to i}}} (t + 1) \\& P_R^i(t + 1) = P_R^i(t) + {\mu _i}P_I^i(t) \\& P_I^i(t + 1) = 1  P_S^i(t + 1)  P_R^i(t + 1)\end{split}$  (26) 
where
As noted by the authors, DMP has two drawbacks. First, the space of initial conditions considered must be explored exhaustively. Second, DMP relies on a further assumption of singlesite factorization of the likelihood function, which is not necessarily consistent with the more accurate underlying approximation. Altarelli et al.^{[110]} realized these and conducted Bayesian inference for this problem on a factor graph under the SIR model. They derived belief propagation (BP) equations for the probability distribution of system states conditioned on some observations, which is more accurate than DMP. Besides, BP can be used to identify the origin of an epidemic outbreak in the SIR, SI, and similar models, even with multiple infection seeds and incomplete or heterogeneous information. They further generalized the analysis to more realistic cases in which observations are imperfect^{[111]}. They said it also can give accurate predictions about the future evolution of an outbreak from which only a partial observation (noisy and/or incomplete) of the current state is available.
DMP and BP have been shown to perform better than centrality based methods, such as Jordan center and rumor center in previous sections. However, DMP and BP are too timeconsuming for largescale networks, because they need to run on the whole network which may have large number of nodes.
6.2.3 Diffusion reconstructionSome methods are based on diffusion reconstruction which recover the states or propagation paths of unknown nodes. For example, Zang et al.^{[112]} presented a multisource locating method based on a given snapshot of partially and sparsely observed infected nodes in the network. They first introduced a reverse propagation method to detect recovered and unobserved infected nodes in the network, and then used community cluster algorithms to change the multisource locating problem into a bunch of single source locating problems. At the last step, they identified the nodes with the largest likelihood as the source nodes in the infected clusters.
Gundecha et al.^{[29]} tried to seek the provenance (i.e., sources or originators) of information for a few known recipients by recovering the information propagation paths in social media. The proposed method exploits easily computable node centralities of a large social media network. Feng et al.^{[113]} studied the problem of recovering other unknown recipients and seeking the provenance of information based on a few known recipients. They exploited the property of frequent pattern and node centrality measures to find important nodes.
6.2.4 OthersKaramchandani and Franceschetti^{[114]} extended the rumor centrality for source detection under probabilistic sampling, i.e., each node reports its status with probability p. They computed the centralities of each node in the reported rumor subgraph which is the minimum subgraph that connects all infected nodes. Besides, Brockmann and Helbing^{[115]} proposed a novel concept of effective distance, which can be used to reconstruct the origin of outbreaks. Shi et al.^{[116]} proposed a twostage method under the SI model that first locates a set of suspected source nodes and then identifies the infection source from the candidate source nodes by the Markov random field method. Zhang et al.^{[117]} studied the diffusion sources locating problem by learning from information diffusion data collected only from a small subset of network nodes. They presented a new regression learning model that can detect anomalous diffusion sources by jointly solving five challenges: unknown number of source nodes, few activated detectors, unknown initial propagation time, uncertain propagation path and uncertain propagation time delay.
6.3 Detection with sensor observationSometimes, due to the large quantity of nodes in a network, we have to select some specific nodes as sensors to monitor the information diffusion, such as choosing some users in a social network and many computers in the Internet to stop the spread of wrong information. That means at time t, we can observe the states of these selected sensors. More importantly, sensor nodes also provide the state transition time (i.e., when they are infected) and infection directions (i.e., which adjacent nodes the information comes from). In the next part, we will show how to use those data to detect the source nodes.
6.3.1 Delay distance estimatorPinto et al.^{[118]} estimated the location of the source from measurements collected by k sparsely placed sensors. Every edge has a deterministic propagation time, which is independent and identically distributed with a Gaussian distribution. The information diffusion follows the continuous SI model, where an infected node will retransmit the information to all of its other neighbors in propagation delays. To minimize the scale of seeking sources, they first determined a unique subtree
$\hat{s} = \arg\max_{s\in T_a} { {\mu}}_s^{\rm T}{{\varLambda}}^{1}({{d}}\frac{1}{2}{ {\mu}}_s)$  (27) 
where
Agaskar and Lu^{[119]} described an alternate representation for the susceptibleinfected (SI) infection model based on geodesic distances on a randomlyweighted version of the graph. This representation allows us to exploit fast Monte Carlo (MC) algorithms to compute geodesic distances and to estimate the marginal distributions for each observer, and then compute a pseudolikelihood function that is maximized to find the source.
Besides, Shen et al.^{[120]} developed a timereversal backward spreading (TRBS) algorithm to locate the source of a diffusionlike process efficiently. Sensors
${{T}}_i=[t_{o_1}\hat{t}(i, o_1), t_{o_2}\hat{t}(i, o_2), \cdots, t_{o_k}\hat{t}(i, o_k)]^{\rm T} $  (28) 
where
Seo et al.^{[122]} followed the intuition that the source node must be close to the infected sensors but far from the negative monitors, and proposed four metrics (FM): 1) Reachability to all positive monitors. It calculates how many positive monitors are reachable from each node. 2) Distance to positive monitors. They sorted the suspected sources by increasing total distances from positive monitors. 3) Reachability to negative monitors. For each sorted node v, they counted the number of negative monitors that are not reachable from v and preferred larger counts. 4) Distance to negative monitors. It is more natural that negative monitors are far from rumor sources, so nodes with larger distance to negative monitors are preferred.
Offline learning models do not meet the needs of early warning, realtime awareness, and realtime response of malicious information spreading in social networks. Therefore, Wang et al.^{[123]} combined online learning and regressionbased detection (OLRD) methods for realtime diffusion source detection with sensors. They proposed a new
Sometimes, some sensors may fail to report their states. Louni et al.^{[124]} noted this and addressed the problem of locating the source of a rumor in large social networks where some of these sensor nodes have failed. They estimated the missing information about the sensors by doubly nonnegative matrix completion and compressed sensing (DNMCCS) techniques. It first used the compressed sensing method to recover sporadically missing measurements and the doubly nonnegative (DN) completion to recover measurements missing in bursts. Then it detects the rumor source based on the recovered measurements with a maximum likelihood (ML) estimator.
In conclusion, we compare some typical methods for different scenarios in Table 1 and have several findings. First, most current methods are detecting the information sources under epidemic models, such as SI and SIR. While other models such as IC and LT are more widely used for information diffusion analysis in social networks. Under these models, it is promising to solve the source detection problem, like [100]. For example, we can extend current methods to more diffusion models according to the difference among them. Second, current methods have no performance guarantee with respect to generic graphs, except for SISI^{[100]}. Many of them can only provide guarantees in some specific cases. For example, the basic rumor center ensures that the probability of correct detection is bounded uniformly away from 0 under the SI model for regular expander trees and geometric trees^{[35]}. Zhu and Ying^{[104]} proved that Jordan center can output a node within a constant distance from the actual source with a high probability for regular trees. Therefore, we can follow SISI and propose more effective methods with performance guarantees based on reverse sampling algorithms for influence maximization in Section 5.3. Third, detection methods with both partial and sensor observations are running on the whole graph, which is unsatisfactory for largescale graphs. Therefore, reducing their time complexities is necessary.
6.4 Similar problems
In literature, there are some problems similar to information source detection defined in Problem 2. For example, Lappas et al.^{[34]} defined the problem of keffectors, which selects a set of k active nodes that can best explain the observed activation states,
$C(S) = \sum_{v\in V}{{a}}(v)\alpha(v, S)$  (29) 
is minimized, where
To conclude, we have reviewed recent advances on information diffusion analysis in social networks and its applications in this paper. Specifically, we first introduced three typical information diffusion models, namely independent cascade (IC) model, linear threshold (LT) model and epidemic models, which can be used to describe how the information diffuses in a network. Then, we showed three practical problems: authority and influence evaluation, influence maximization, and information source detection. Authority and influence evaluation in social networks is important for influential spreaders identification and expert finding, while influence maximization contributes to viral marketing and sensor placement. Information source detection has a wide range of applications such as epidemic outbreak prevention and rumor source tracing in social networks. Although many efforts have been devoted to these problems, there are still some rooms for improvement. Here we will list several possible directions for further study.
First, current information diffusion models have perfect theoretical properties for further analysis, but simplify realworld scenarios which are actually very complicated. Users can access the information from external sources such as TV, newspaper and other websites, not only from its neighbors in a social network. Besides, there may be multiple types of information spreading in the network at the same time, such as information of competitive products. Therefore, it is promising to model multiple types of information diffusion in heterogeneous social networks with external influence. For example, Myers et al.^{[127]} presented a model in which information can reach a node via the links of the social network or through the influence of external sources. Besides, Zhan et al.^{[128]} studied the influence maximization problem in multiple partially aligned heterogeneous in online social networks.
Second, large scalability is one of the biggest challenges to apply influence maximization and information source detection in realworld applications, especially for largescale networks. Solutions to influence maximization have achieved a great improvement after reverse sampling algorithms are proposed by Borgs et al.^{[70]}, and thus we can bring in the experience to accelerate solutions to information source detection, like Nguyen et al.^{[100]} Besides, implementing these solutions in distributed programming is another practical direction.
Third, most current solutions are applicable for static networks, and they neglect that networks are dynamic and evolving. For example, a user may unfollow some of his friends in some time and his personal interests may change on different topics. That′s to say, the tie strengths among different users are varying over time. We should take this fact into account so as to analyze the information diffusion in social networks better.
Forth, deep learning has been applied to many tasks of social network analysis recently, such as network embedding^{[129, 130]} and link prediction^{[131]}. The real process of information diffusion in social networks is complicated and sometimes unobserved. Can we design deep learning methods for analyzing the information diffusion? For example, when we input the network structure and a user′s attributes such as the age, gender, posts, into a deep learning based model, we can output this user′s influence. Bourigault et al.^{[132]} proposed a representation learning approach for information source detection in social networks. It relies neither on a known diffusion graph nor on a hypothetical diffusion law, but directly infers the source from diffusion records.
Finally, it is attractive to incorporate the information diffusion analysis with other practical problems, such as behavior prediction for social users^{[8, 133, 134]}. For example, social users are usually affected by multiple companies at the same time, and not only the user interests but also these social influences will contribute to the user consumption behaviors. Ma et al.^{[135]} proposed a general approach to figure out the targeted users for social marketing, taking both user interests and multiple social influences into consideration. Valuable users should have the best balanced influence entropy (being “Hesitant”) and utility scores (being “Interested”). Wu et al.^{[133]} took the underlying social theories to explain and model the evolution of users′ two kinds of behaviors: users′ preferences (reflected in useritem interaction behavior) and the social network structure (reflected in useruser interaction behavior). Xu et al.^{[8]} tried to reveal how the social propagation affects the prediction of cab drivers′ future behaviors.
AcknowledgementsThis research was supported by National Natural Science Foundation of China (Nos. 61703386, U1605251 and 91546103), the Anhui Provincial Natural Science Foundation (No. 1708085QF140), the Fundamental Research Funds for the Central Universities (No. WK2150110006), and the Youth Innovation Promotion Association of Chinese Academy of Sciences (No. 2014299).
[1] 
Zephoria. The top 20 valuable Facebook statisticsupdated April 2018. [Online], Available: https://zephoria.com/top15valuablefacebookstatistics/, October 1, 2017.

[2] 
H. Kwak, C. Lee, H. Park, S. Moon. What is Twitter, a social network or a news media? In Proceedings of the 19th International Conference on World Wide Web, New York, USA, pp. 591–600, 2010.

[3] 
H. P. Zhang, R. Q. Zhang, Y. P. Zhao, B. J. Ma. Big data modeling and analysis of microblog ecosystem. International Journal of Automation and Computing, vol.11, no.2, pp.119127, 2014. DOI:10.1007/s1163301407749 
[4] 
D. Kempe, J. Kleinberg, É. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Washington DC, USA, pp. 137–146, 2003.

[5] 
J. Leskovec, L. A. Adamic, B. A. Huberman. The dynamics of viral marketing. ACM Transactions on the Web, vol.1, no.1, pp.5, 2007. DOI:10.1145/1232722.1232727 
[6] 
M. Richardson, P. Domingos. Mining knowledgesharing sites for viral marketing. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Edmonton, Canada, pp. 61–70, 2002.

[7] 
C. Ma, C. Zhu, Y. J. Fu, H. S. Zhu, G. Q. Liu, E. H. Chen. Social user profiling: A socialaware topic modeling perspective. In Proceedings of the 22nd International Conference on Database Systems for Advanced Applications, Springer, Suzhou, China, pp. 610–622, 2017.

[8] 
T. Xu, H. S. Zhu, X. Y. Zhao, Q. Liu, H. Zhong, E. H. Chen, H. Xiong. Taxi driving behavior analysis in latent vehicletovehicle networks: A social influence perspective. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, San Francisco, USA, pp. 1285–1294, 2016.

[9] 
X. Y. Zhao, T. Xu, Q. Liu, H. Guo. Exploring the choice under conflict for social event participation. In Proceedings of the 21st International Conference on Database Systems for Advanced Applications, Springer, Dallas, USA, pp. 396–411, 2016.

[10] 
L. Backstrom, J. Leskovec. Supervised random walks: Predicting and recommending links in social networks. In Proceedings of the 4th ACM International Conference on Web Search and Data Mining, ACM, Hong Kong, China, pp. 635–644, 2011.

[11] 
D. LibenNowell, J. Kleinberg. The linkprediction problem for social networks. Journal of the American Society for Information Science and Technology, vol.58, no.7, pp.10191031, 2007. DOI:10.1002/asi.v58:7 
[12] 
T. Xu, H. S. Zhu, E. H. Chen, B. X. Huai, H. Xiong, J. L. Tian. Learning to annotate via social interaction analytics. Knowledge and Information Systems, vol.41, no.2, pp.251276, 2014. DOI:10.1007/s1011501307178 
[13] 
S. Fortunato. Community detection in graphs. Physics Reports, vol.486, no.3, pp.75174, 2010. DOI:10.1016/j.physrep.2009.11.002 
[14] 
S. Fortunato, M. Barthlemy. Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, vol.104, no.1, pp.3641, 2007. DOI:10.1073/pnas.0605965104 
[15] 
M. Girvan, M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America, vol.99, no.12, pp.78217826, 2002. 
[16] 
J. Goldenberg, B. Libai, E. Muller. Talk of the network: A complex systems look at the underlying process of wordofmouth. Marketing Letters, vol.12, no.3, pp.211223, 2001. DOI:10.1023/A:1011122126881 
[17] 
M. Granovetter. Threshold models of collective behavior. American Journal of Sociology, vol.83, no.6, pp.14201443, 1978. DOI:10.1086/226707 
[18] 
W. O. Kermack, A. G. McKendrick. Contributions to the mathematical theory of epidemics – II. The problem of endemicity. Bulletin of Mathematical Biology, vol. 53, no. 1–2, pp. 57–87, 1991.

[19] 
M. Cataldi, L. Di Caro, C. Schifanella. Emerging topic detection on Twitter based on temporal and social terms evaluation. In Proceedings of the 10th International Workshop on Multimedia Data Mining, ACM, Washington DC, USA, 2010.

[20] 
M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, H. A. Makse. Identification of influential spreaders in complex networks. Nature Physics, vol.6, no.11, pp.888893, 2010. DOI:10.1038/nphys1746 
[21] 
J. Zhang, J. Tang, J. Z. Li. Expert finding in a social network. In Proceedings of the 12th International Conference on Database Systems for Advanced Applications, Springer, Bangkok, Thailand, pp. 1066–1069, 2007.

[22] 
H. S. Zhu, E. H. Chen, H. Xiong, H. H. Cao, J. L. Tian. Ranking user authority with relevant knowledge categories for expert finding. World Wide Web, vol.17, no.5, pp.10811107, 2014. DOI:10.1007/s1128001302175 
[23] 
H. S. Zhu, E. H. Chen, H. H. Cao. Finding experts in tag based knowledge sharing communities. In Proceedings of the 5th International Conference on Knowledge Science, Engineering and Management, Springer, Irvine, USA, pp. 183–195, 2011.

[24] 
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Costeffective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, San Jose, USA, pp. 420–429, 2007.

[25] 
L. Zou, Z. D. Wang, D. H. Zhou. Eventbased control and filtering of networked systems: A survey. International Journal of Automation and Computing, vol.14, no.3, pp.239253, 2017. DOI:10.1007/s1163301710778 
[26] 
B. Chang, F. D. Zhu, E. H. Chen, Q. Liu. Information source detection via maximum a posteriori estimation. In Proceedings of IEEE International Conference on Data Mining, IEEE, Atlantic City, USA, pp. 21–30, 2015.

[27] 
V. Fioriti, M. Chinnici. Predicting the sources of an outbreak with a spectral technique. Applied Mathematical Sciences, vol.8, pp.67756782, 2014. DOI:10.12988/ams.2014.49693 
[28] 
B. A. Prakash, J. Vreeken, C. Faloutsos. Spotting culprits in epidemics: How many and which ones? In Proceedings of the 12th International Conference on Data Mining, IEEE, Brussels, Belgium, pp. 11–20, 2012.

[29] 
P. Gundecha, Z. Feng, H. Liu. Seeking provenance of information using social media. In Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, ACM, San Francisco, USA, pp. 1691–1696, 2013.

[30] 
D. Shah, T. Zaman. Rumors in a network: Who′s the culprit?. IEEE Transactions on Information Theory, vol.57, no.8, pp.51635181, 2011. DOI:10.1109/TIT.2011.2158885 
[31] 
A. Goyal, F. Bonchi, L. V. S. Lakshmanan. Learning influence probabilities in social networks. In Proceedings of the 3rd ACM International Conference on Web Search and Web Data Mining, ACM, New York, USA, pp. 241–250, 2010.

[32] 
B. Ryan, N. C. Gross. The diffusion of hybrid seed corn in two Iowa communities. Rural Sociology, vol.8, no.1, pp.1524, 1943. 
[33] 
H. Y. Zhang, S. Mishra, M. T. Thai. Recent advances in information diffusion and influence maximization in complex social networks. Opportunistic Mobile Social Networks, J. Wu, Y. S. Wang, Eds., USA: CRC Press, 2014.

[34] 
T. Lappas, E. Terzi, D. Gunopulos, H. Mannila. Finding effectors in social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Washington DC, USA, pp. 1059–1068, 2010.

[35] 
D. Shah, T. Zaman. Detecting sources of computer viruses in networks: Theory and experiment. In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, ACM, New York, USA, pp. 203–214, 2010.

[36] 
R. Zafarani, M. A. Abbasi, H. Liu. Social Media Mining: An Introduction, Cambridge, UK: Cambridge University Press, 2014.

[37] 
Y. Yao, X. R. Luo, F. X. Gao, S. L. Ai. Research of a potential worm propagation model based on pure P2P principle. In Proceedings of International Conference on Communication Technology, IEEE, Guilin, China, 2006.

[38] 
H. W. Hethcote. The mathematics of infectious diseases. SIAM Review, vol.42, no.4, pp.599653, 2000. DOI:10.1137/S0036144500371907 
[39] 
K. L. Cooke, P. van den Driessche. Analysis of an SEIRS epidemic model with two delays. Journal of Mathematical Biology, vol.35, no.2, pp.240260, 1996. DOI:10.1007/s002850050051 
[40] 
Y. Xiang, X. Fan, W. T. Zhu. Propagation of active worms: A survey. International Journal of Computer Systems Science and Engineering, vol.24, no.3, pp.157172, 2009. 
[41] 
H. S. Zhu, E. H. Chen, H. H. Cao, J. L. Tian. Contextaware expert finding in tag based knowledge sharing communities. International Journal of Knowledge and Systems Science, vol.3, no.1, pp.4863, 2012. DOI:10.4018/jkss.2012010104 
[42] 
H. S. Zhu, H. H. Cao, H. Xiong, E. H. Chen, J. L. Tian. Towards expert finding by leveraging relevant categories in authority ranking. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, ACM, Glasgow, UK, pp. 2221–2224, 2011.

[43] 
B. A. Prakash, C. Faloutsos. Understanding and managing cascades on large graphs. Proceedings of the VLDB Endowment, vol.5, no.12, pp.20242025, 2012. DOI:10.14778/2367502.2367567 
[44] 
B. Xiang, Q. Liu, E. H. Chen, H. Xiong, Y. Zheng, Y. Yang. PageRank with priors: An influence propagation perspective. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, pp. 2740–2746, 2013.

[45] 
S. Y. Lin, W. X. Hong, D. D. Wang, T. Li. A survey on expert finding techniques. Journal of Intelligent Information Systems, vol.49, no.2, pp.255279, 2017. DOI:10.1007/s1084401604405 
[46] 
A. Bavelas. Communication patterns in taskoriented groups. The Journal of the Acoustical Society of America, vol.22, no.6, pp.725730, 1950. DOI:10.1121/1.1906679 
[47] 
L. C. Freeman. A set of measures of centrality based on betweenness. Sociometry, vol.40, no.1, pp.3541, 1977. DOI:10.2307/3033543 
[48] 
C. Jordan. Sur les assemblages de lignes. Journal fr die reine und angewandte Mathematik, vol.1869, no.70, pp.185190, 1869. DOI:10.1515/crll.1869.70.185 
[49] 
L. Page, S. Brin, R. Motwani, T. Winograd. The PageRank citation ranking: Bringing order to the web, Technical Report SIDLWP19990120, Stanford University, USA, 1999.

[50] 
P. Berkhin. A survey on PageRank computing. Internet Mathematics, vol.2, no.1, pp.73120, 2005. DOI:10.1080/15427951.2005.10129098 
[51] 
T. H. Haveliwala. Topicsensitive PageRank. In Proceedings of the 11th International Conference on World Wide Web, ACM, New York, USA, pp. 517–526, 2002.

[52] 
J. M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, vol.46, no.5, pp.604632, 1999. DOI:10.1145/324133.324140 
[53] 
J. S. Weng, E. P. Lim, J. Jiang, Q. He. TwitterRank: Finding topicsensitive influential twitterers. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining, ACM, New York, USA, pp. 261–270, 2010.

[54] 
Q. Liu, B. Xiang, E. H. Chen, Y. Ge, H. Xiong, T. F. Bao, Y. Zheng. Influential seed items recommendation. In Proceedings of the 6th ACM Conference on Recommender Systems, ACM, Dublin, Ireland, pp. 245–248, 2012.

[55] 
W. Chen, C. Wang, Y. J. Wang. Scalable influence maximization for prevalent viral marketing in largescale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Washington DC, USA, pp. 1029–1038, 2010.

[56] 
W. Chen, Y. F. Yuan, L. Zhang. Scalable influence maximization in social networks under the linear threshold model. In Proceedings of the 10th International Conference on Data Mining, IEEE, Sydney, Australia, pp. 88–97, 2010.

[57] 
C. C. Aggarwal, A. Khan, X. F. Yan. On flow authority discovery in social networks. In Proceedings of SIAM International Conference on Data Mining, SIAM, Mesa, USA, pp. 522–533, 2011.

[58] 
Y. Yang, E. H. Chen, Q. Liu, B. Xiang, T. Xu, S. A. Shad. On approximation of realworld influence spread. In Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, Bristol, UK, pp. 548–564, 2012.

[59] 
J. Yang, J. Leskovec. Modeling information diffusion in implicit networks. In Proceedings of the10th International Conference on Data Mining, IEEE, Sydney, Australia, pp. 599–608, 2010.

[60] 
Q. Liu, B. Xiang, N. J. Yuan, E. H. Chen, H. Xiong, Y. Zheng, Y. Yang. An influence propagation view of PageRank. ACM Transactions on Knowledge Discovery from Data, vol.11, no.3, pp.30, 2017. DOI:10.1145/3046941 
[61] 
J. Tang, J. M. Sun, C. Wang, Z. Yang. Social influence analysis in largescale networks. In Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, ACM, Paris, France, pp. 807–816, 2009.

[62] 
Q. Liu, B. Xiang, L. Zhang, E. H. Chen, C. Tan, J. Chen. Linear computation for independent social influence. In Proceedings of the 13th International Conference on Data Mining, IEEE, Dallas, USA, pp. 468–477, 2013.

[63] 
Q. Liu, B. Xiang, E. H. Chen, H. Xiong, F. S. Tang, J. X. Yu. Influence maximization over largescale social networks: A bounded linear approach. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, ACM, Shanghai, China, pp. 171–180, 2014.

[64] 
G. L. Nemhauser, L. A. Wolsey, M. L. Fisher. An analysis of approximations for maximizing submodular set functionsI. Mathematical Programming, vol.14, pp.265294, 1978. 
[65] 
A. Goyal, W. Lu, L. V. S. Lakshmanan. CELF++: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference Companion on World Wide Web, ACM, Hyderabad, India, pp. 47–48, 2011.

[66] 
K. Jung, W. Heo, W. Chen. IRIE: Scalable and robust influence maximization in social networks. In Proceedings of the 12th International Conference on Data Mining, IEEE, Brussels, Belgium, pp. 918–923, 2012.

[67] 
M. Kimura, K. Saito. Tractable models for information diffusion in social networks. In Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Springer, Berlin, Germany, pp. 259–271, 2006.

[68] 
W. Chen, Y. J. Wang, S. Y. Yang. Efficient influence maximization in social networks. In Proceedings of the 15th ACM International Conference on Knowledge Discovery and Data Mining, ACM, Paris, France, pp. 199–208, 2009.

[69] 
A. Goyal, W. Lu, L. V. S. Lakshmanan. SIMPATH: An efficient algorithm for influence maximization under the linear threshold model. In Proceedings of the 11th International Conference on Data Mining, IEEE, Vancouver, Canada, pp. 211–220, 2011.

[70] 
C. Borgs, M. Brautbar, J. Chayes, B. Lucier. Maximizing social influence in nearly optimal time. In Proceedings of the 25th Annual ACMSIAM Symposium on Discrete Algorithms, Illinois, USA, pp. 946–957, 2014.

[71] 
Y. Z. Tang, X. K. Xiao, Y. C. Shi. Influence maximization: Nearoptimal time complexity meets practical efficiency. In Proceedings of ACM SIGMOD International Conference on Management of Data, ACM, Snowbird, USA, pp. 75–86, 2014.

[72] 
V. V. Vazirani. Approximation Algorithms, Berlin Heidelberg, Germany: Springer, 2013.

[73] 
Y. Z. Tang, Y. C. Shi, X. K. Xiao. Influence maximization in nearlinear time: A martingale approach. In Proceedings of ACM SIGMOD International Conference on Management of Data, ACM, Melbourne, Australia, pp. 1539–1554, 2015.

[74] 
E. Cohen, D. Delling, T. Pajor, R. F. Werneck. Sketchbased influence maximization and computation: Scaling up with guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, ACM, Shanghai, China, pp. 629–638, 2014.

[75] 
H. T. Nguyen, M. T. Thai, T. N. Dinh. Stopandstare: Optimal sampling algorithms for viral marketing in billionscale networks. In Proceedings of International Conference on Management of Data, ACM, San Francisco, USA, pp. 695–710, 2016.

[76] 
K. K. Huang, S. B. Wang, G. Bevilacqua, X. K. Xiao, L. V. S. Lakshmanan. Revisiting the stopandstare algorithms for influence maximization. Proceedings of the VLDB Endowment, vol.10, no.9, pp.913924, 2017. DOI:10.14778/3099622.3099623 
[77] 
Y. Wang, G. Cong, G. J. Song, K. Q. Xie. Communitybased greedy algorithm for mining topK influential nodes in mobile social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Washington DC, USA, pp. 1039–1048, 2010.

[78] 
Z. F. Wang, H. Wang, Q. Liu, E. H. Chen. Influential nodes selection: A data reconstruction perspective. In Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval, ACM, Gold Coast, Australia, pp. 879–882, 2014.

[79] 
Q. Y. Jiang, G. J. Song, G. Cong, Y. Wang, W. J. Si, K. Q. Xie. Simulated annealing based influence maximization in social networks. In Proceedings of the 25th AAAI Conference on Artificial Intelligence, AAAI, San Francisco, USA, pp. 127–132, 2011.

[80] 
M. G. Rodriguez, B. Schölkopf. Influence maximization in continuous time diffusion networks. https://arxiv.org/abs/1205.1682, 2012.

[81] 
Y. K. Wang, J. H. Zhu, Q. Ming. Incremental influence maximization for dynamic social networks. In Proceedings of the 3rd International Conference of Pioneering Computer Scientists, Engineers and Educators, Springer, Changsha, China, pp. 13–27, 2017.

[82] 
E. Güney. On the optimal solution of budgeted influence maximization problem in social networks. Operational Research, to be published.

[83] 
H. Nguyen, R. Zheng. On budgeted influence maximization in social networks. IEEE Journal on Selected Areas in Communications, vol.31, no.6, pp.10841094, 2013. DOI:10.1109/JSAC.2013.130610 
[84] 
Y. Yang, X. B. Mao, J. Pei, X. F. He. Continuous influence maximization: What discounts should we offer to social network users? In Proceedings of International Conference on Management of Data, ACM, San Francisco, USA, pp. 727–741, 2016.

[85] 
C. Aslay, F. Bonchi, L. V. S. Lakshmanan, W. Lu. Revenue maximization in incentivized social advertising. Proceedings of the VLDB Endowment, vol.10, no.11, pp.12381249, 2017. DOI:10.14778/3137628.3137635 
[86] 
F. H. Li, C. T. Li, M. K. Shan. Labeled influence maximization in social networks for target marketing. In Proceedings of the 3rd International Conference on Privacy, Security, Risk and Trust and the IEEE 3rd International Conference on Social Computing, IEEE, Boston, USA, pp. 560–563, 2011.

[87] 
F. S. Tang, Q. Liu, H. S. Zhu, E. H. Chen, F. D. Zhu. Diversified social influence maximization. In Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE, Beijing, China, pp. 455–459, 2014.

[88] 
Q. Liu, Z. Dong, C. R. Liu, X. Xie, E. H. Chen, H. Xiong. Social marketing meets targeted customers: A typical user selection and coverage perspective. In Proceedings of IEEE International Conference on Data Mining, IEEE, Shenzhen, China, pp. 350–359, 2014.

[89] 
Z. F. Wang, E. H. Chen, Q. Liu, Y. Yang, Y. Ge, B. Chang. Maximizing the coverage of information propagation in social networks. In Proceedings of the 24th International Conference on Artificial Intelligence, AAAI, Buenos Aires, Argentina, pp. 2104–2110, 2015.

[90] 
Z. F. Wang, Y. Yang, J. Pei, L. Y. Chu, E. H. Chen. Activity maximization by effective information diffusion in social networks. IEEE Transactions on Knowledge and Data Engineering, vol.29, no.11, pp.23742387, 2017. DOI:10.1109/TKDE.2017.2740284 
[91] 
X. R. He, G. J. Song, W. Chen, Q. Y. Jiang. Influence blocking maximization in social networks under the competitive linear threshold model. In Proceedings of SIAM International Conference on Data Mining, SIAM, Anaheim, USA, pp. 463–474, 2012.

[92] 
J. H. Zhao, Q. P. Liu, L. Wang, X. F. Wang. Competitiveness maximization on complex networks. IEEE Transactions on Systems, Man, and Cybernetics: Systems, to be published.

[93] 
G. W. Ma, Q. Liu, E. H. Chen, B. Xiang. Individual influence maximization via link recommendation. In Proceedings of the 16th International Conference on Webage Information Management, Springer, Qingdao, China, pp. 42–56, 2015.

[94] 
J. J. Jiang, S. Wen, S. Yu, Y. Xiang, W. L. Zhou. Identifying propagation sources in networks: Stateoftheart and comparative studies. IEEE Communications Surveys & Tutorials, vol.19, no.1, pp.465481, 2017. DOI:10.1109/COMST.2016.2615098 
[95] 
W. X. Dong, W. Y. Zhang, C. W. Tan. Rooting out the rumor culprit from suspects. In Proceedings of IEEE International Symposium on Information Theory, IEEE, Istanbul, Turkey, pp. 2671–2675, 2013.

[96] 
Z. X. Wang, W. X. Dong, W. Y. Zhang, C. W. Tan. Rooting our rumor sources in online social networks: The value of diversity from multiple observations. IEEE Journal of Selected Topics in Signal Processing, vol.9, no.4, pp.663677, 2015. DOI:10.1109/JSTSP.2015.2389191 
[97] 
W. Q. Luo, W. P. Tay, M. Leng. Identifying infection sources and regions in large networks. IEEE Transactions on Signal Processing, vol.61, no.11, pp.28502865, 2013. DOI:10.1109/TSP.2013.2256902 
[98] 
X. M. Zhai, W. L. Wu, W. Xu. Cascade source inference in networks: A Markov chain monte Carlo approach. Computational Social Networks, vol.2, no.1, pp.17, 2015. DOI:10.1186/s4064901500174 
[99] 
L. Zhang, T. Y. Jin, T. Xu, B. Chang, Z. F. Wang, E. H. Chen. A Markov chain monte Carlo approach for source detection in networks. In Proceedings of the 6th National Conference on Social Media Processing, Springer, Beijing, China, pp. 77–88, 2017.

[100] 
H. T. Nguyen, P. Ghosh, M. L. Mayo, T. N. Dinh. Multiple infection sources identification with provable guarantees. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, ACM, Indianapolis, USA, pp. 1663–1672, 2016.

[101] 
S. Feizi, K. Duffy, M. Kellis, M. Médard. Network infusion to infer information sources in networks, Technical Report MITCSAILTR2014028, Computer Science and Artificial Intelligence Laboratory, USA, 2014.

[102] 
R. Pena, X. Bresson, P. Vandergheynst. Source localization on graphs via L_{1} recovery and spectral graph theory. In Proceedings of the 12th Image, Video, and Multidimensional Signal Processing Workshop, IEEE, Bordeaux, France, 2016.

[103] 
K. Zhu, L. Ying. Information source detection in networks: Possibility and impossibility results. In Proceedings of the 35th Annual IEEE International Conference on Computer Communications, IEEE, San Francisco, USA, 2016.

[104] 
K. Zhu, L. Ying. Information source detection in the SIR model: A samplepathbased approach. IEEE/ACM Transactions on Networking, vol.24, no.1, pp.408421, 2016. DOI:10.1109/TNET.2014.2364972 
[105] 
K. Zhu, L. Ying. A robust information source estimator with sparse observations. Computational Social Networks, vol.1, no.1, pp.3, 2014. DOI:10.1186/s4064901400032 
[106] 
W. Q. Luo, W. P. Tay. Finding an infection source under the sis model. In Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE, Vancouver, Canada, pp. 2930–2934, 2013.

[107] 
W. Q. Luo, W. P. Tay, M. Leng. How to identify an infection source with limited observations. IEEE Journal of Selected Topics in Signal Processing, vol.8, no.4, pp.586597, 2014. DOI:10.1109/JSTSP.2014.2315533 
[108] 
A. Y. Lokhov, M. Mézard, H. Ohta, L. Zdeborová. Inferring the origin of an epidemic with a dynamic messagepassing algorithm. Physical Review E, vol 90, no. 1, Article number 012801, 2014.

[109] 
W. H. Hu, W. P. Tay, A. Harilal, G. X. Xiao. Network infection source identification under the SIRI model. In Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing, IEEE, Brisbane, Australia, pp. 1712–1716, 2015.

[110] 
F. Altarelli, A. Braunstein, L. Dall′Asta, A. LageCastellanos, R. Zecchina. Bayesian inference of epidemics on networks via belief propagation. Physical Review Letters, vol. 112, no. 11, Article number 118701, 2014. DOI: 10.1103/PhysRevLett.112.118701.

[111] 
F. Altarelli, A. Braunstein, L. Dall′Asta, A. Ingrosso, R. Zecchina. The patientzero problem with noisy observations. Journal of Statistical Mechanics: Theory and Experiment, vol. 2014, no. 10, Article number 10016, 2014. DOI: 10.1088/17425468/2014/10/P10016.

[112] 
W. Y. Zang, P. Zhang, C. Zhou, L. Guo. Discovering multiple diffusion source nodes in social networks. Procedia Computer Science, vol.29, pp.443452, 2014. DOI:10.1016/j.procs.2014.05.040 
[113] 
Z. Feng, P. Gundecha, H. Liu. Recovering information recipients in social media via provenance. In Proceedings of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, IEEE, Niagara Falls, Canada, pp. 706–711, 2013.

[114] 
N. Karamchandani, M. Franceschetti. Rumor source detection under probabilistic sampling. In Proceedings of IEEE International Symposium on Information Theory, IEEE, Istanbul, Turkey, pp. 2184–2188, 2013.

[115] 
D. Brockmann, D. Helbing. The hidden geometry of complex, networkdriven contagion phenomena. Science, vol.342, no.6164, pp.13371342, 2013. DOI:10.1126/science.1245200 
[116] 
C. Y. Shi, Q. Zhang, T. G. Chu. Source identification of network diffusion processes with partial observations. In Proceedings of the 36th Chinese Control Conference, IEEE, Dalian, China, pp. 11296–11300, 2017.

[117] 
P. Zhang, J. He, G. D. Long, G. Y. Huang, C. Q. Zhang. Towards anomalous diffusion sources detection in a large network. ACM Transactions on Internet Technology, vol.16, no.1, pp.24, 2016. DOI:10.1145/2806889 
[118] 
P. C. Pinto, P. Thiran, M. Vetterli. Locating the source of diffusion in largescale networks. Physical Review Letters, vol. 109, no. 6, Article number 068702, 2012. DOI: 10.1103/PhysRevLett.109.068702.

[119] 
A. Agaskar, Y. M. Lu. A fast Monte Carlo algorithm for source localization on graphs. In Proceedings of SPIE 8858, Wavelets and Sparsity XV, SPIE, San Diego, USA, 2013.

[120] 
Z. S. Shen, S. N. Cao, W. X. Wang, Z. R. Di, H. E. Stanley. Locating the source of diffusion in complex networks by timereversal backward spreading. Physical Review E, vol. 93, no. 3, Article number 032301, 2016. DOI: 10.1103/PhysRevE.93.032301.

[121] 
L. Fu, Z. S. Shen, W. X. Wang, Y. Fan, Z. R. Di. Multisource localization on complex networks with limited observers. Europhysics Letters, vol. 113, no. 1, Article number 18006, 2016.

[122] 
E. Seo, P. Mohapatra, T. Abdelzaher. Identifying rumors and their sources in social networks. In Proceedings of Volume 8389, Ground/Air Multisensor Interoperability, Integration, and Networking for Persistent ISR III, SPIE, Baltimore, USA, 2012.

[123] 
H. S. Wang, P. Zhang, L. Chen, H. Liu, C. Q. Zhang. Online diffusion source detection in social networks. In Proceedings of International Joint Conference on Neural Networks, IEEE, Killarney, Ireland, pp. 1–8, 2015.

[124] 
A. Louni, S. Anand, K. P. Subbalakshmi. Identification of source of rumors in social networks with incomplete information. https://arxiv.org/abs/1509.00557, 2015.

[125] 
L. Bulteau, S. Fafianie, V. Froese, R. Niedermeier, N. Talmon. The complexity of finding effectors. Theory of Computing Systems, vol.60, no.2, pp.253279, 2017. DOI:10.1007/s0022401696708 
[126] 
D. T Nguyen, N. P. Nguyen, M. T. Thai. Sources of misinformation in online social networks: Who to suspect? In Proceedings of IEEE Military Communications Conference, IEEE, Orlando, USA, 2012.

[127] 
S. A. Myers, C. G. Zhu, J. Leskovec. Information diffusion and external influence in networks. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Beijing, China, pp. 33–41, 2012.

[128] 
Q. Y. Zhan, J. W. Zhang, S. Z. Wang, P. S. Yu, J. Y. Xie. Influence maximization across partially aligned heterogenous social networks. In Proceedings of the 19th PacificAsia Conference on Advances in Knowledge Discovery and Data Mining, Springer, Ho Chi Minh City, Vietnam, pp. 58–69, 2015.

[129] 
D. F. Du, H. Wang, T. Xu, Y. N. Lu, Q. Liu, E. H. Chen. Solving linkoriented tasks in signed network via an embedding approach. In Proceedings of IEEE International Conference on Systems, Man, and Cybernetics, IEEE, Banff, Canada, pp. 75–80, 2017.

[130] 
D. X. Wang, P. Cui, W. W. Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, San Francisco, USA, pp. 1225–1234, 2016.

[131] 
F. Liu, B. Q. Liu, C. J. Sun, M. Liu, X. L. Wang. Deep learning approaches for link prediction in social network services. In Proceedings of the 20th International Conference on Neural Information Processing, Springer, Daegu, Korea, pp. 425–432, 2013.

[132] 
S. Bourigault, S. Lamprier, P. Gallinari. Learning distributed representations of users for source detection in online social networks. In Proceedings of European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, Riva del Garda, Italy, pp. 265–281, 2016.

[133] 
L. Wu, Y. Ge, Q. Liu, E. H. Chen, R. C. Hong, J. P. Du, M. Wang. Modeling the evolution of users′ preferences and social links in social networking services. IEEE Transactions on Knowledge and Data Engineering, vol.29, no.6, pp.12401253, 2017. DOI:10.1109/TKDE.2017.2663422 
[134] 
T. Zhang, R. Z. Qin, Q. L. Dong, W. Gao, H. R. Xu, Z. Y. Hu. Physiognomy: Personality traits prediction by learning. International Journal of Automation and Computing, vol.14, no.4, pp.386395, 2017. DOI:10.1007/s1163301710858 
[135] 
G. W. Ma, Q. Liu, L. Wu, E. H. Chen. Identifying hesitant and interested customers for targeted social marketing. In Proceedings of the 19th PacificAsia Conference on Advances in Knowledge Discovery and Data Mining, Springer, Ho Chi Minh City, Vietnam, pp. 576–590, 2015.
