# American Institute of Mathematical Sciences

August  2018, 1(3): 201-253. doi: 10.3934/mfc.2018010

## Influence analysis: A survey of the state-of-the-art

 1 Kennesaw State University, 1100 South Marietta Pkwy, Marietta, GA, 30060, USA 2 Georgia State University, 25 Park place, Atlanta, GA, 30303, USA

* Corresponding author: Meng Han

Received  December 2017 Revised  February 2018 Published  July 2018

Online social networks have seen an exponential growth in number of users and activities recently. The rapid proliferation of online social networks provides rich data and infinite possibilities for us to analyze and understand the complex inherent mechanism which governs the evolution of the new online world. This paper summarizes the state-of-art research results on social influence analysis in a broad sense. First, we review the development process of influence analysis in social networks based on several basic conceptions and features in a social aspect. Then the online social networks are discussed. After describing the classical models which simulate the influence spreading progress, we give a bird's eye view of the up-to-date literatures on influence diffusion models and influence maximization approaches. Third, we present the applications including web services, marketing, and advertisement services which based on the influence analysis. At last, we point out the research challenges and opportunities in this area for both industry and academia reference.

Citation: Meng Han, Yingshu Li. Influence analysis: A survey of the state-of-the-art. Mathematical Foundations of Computing, 2018, 1 (3) : 201-253. doi: 10.3934/mfc.2018010
##### References:

show all references

##### References:
Publications Related Influence Analysis in the Recent Years
A Social Network
Common Neighbors in a Community
Models of Social Influence by Different Networks
Diffusion Models of Social Influence
Probing Community for Dynamic Network
Influence Maximization Models in Social Network
Influence Diffusion Processing 1.
Influence Diffusion Processing 2.
Heterogeneous Models of Social Influence
Models of Social Influence based on Biological Transmission
Comprehensive Models of Social Influence
Influence Analysis based Applications
Extensions or improvements of $IC/LT$ models
 References Extender $IC$ $LT$ Remarks Goyal [71] Learnt probability from the action log, simulation on both $IC$ and $LT$ models $\surd$ $\surd$ Chen et al.[42] Address the scalability issue, they proposed efficiency heuristic algorithm by restricting computations on the local influence regions of nodes $\surd$ $\times$ Showed that computing influence spread in the independent cascade model is #P-hard problem Chen et al.[41] Extended the classical $IC$ model to study time-delayed influence diffusion $\surd$ $\times$ Their technical report version paper provides the NP-complete hardness of LT with their time-delay feature Masahiro et al. [127] Improved the basic $IC$ and $LT$ by estimating marginal influence degrees $\surd$ $\surd$ Chen et al. [43] Degree discount heuristics achieve almost matching influence thread with the greedy algorithm, and run only in milliseconds which the traditional method run in hours $\surd$ $\surd$ Wang et al. [236] Heuristic algorithm for $IC$ model $\surd$ $\times$ Chen et al. [37] Extended the classical $IC$ model to incorporating negative opinions $\surd$ $\times$ Nam et al. [188] Focused on how to limit viral propagation of misinformation in OSNs $\surd$ $\surd$ Wang et al. [239] Extended $IC$ to mobile social networks, and use a dynamic programming algorithm to select communities then find influential nodes $\surd$ $\surd$ Kyomin et al. [121] Algorithm IRIE where IR for influence ranking, and IE for influence maximization are proposed to improve the classical algorithm developed previously $\surd$ $\times$ The algorithm was used in both classical $IC$ model and the extension $IC$-$N$ [37] Thang [58] Extended the $LT$ model by constrain the influence distance as constant $d$ $\times$ $\surd$
 References Extender $IC$ $LT$ Remarks Goyal [71] Learnt probability from the action log, simulation on both $IC$ and $LT$ models $\surd$ $\surd$ Chen et al.[42] Address the scalability issue, they proposed efficiency heuristic algorithm by restricting computations on the local influence regions of nodes $\surd$ $\times$ Showed that computing influence spread in the independent cascade model is #P-hard problem Chen et al.[41] Extended the classical $IC$ model to study time-delayed influence diffusion $\surd$ $\times$ Their technical report version paper provides the NP-complete hardness of LT with their time-delay feature Masahiro et al. [127] Improved the basic $IC$ and $LT$ by estimating marginal influence degrees $\surd$ $\surd$ Chen et al. [43] Degree discount heuristics achieve almost matching influence thread with the greedy algorithm, and run only in milliseconds which the traditional method run in hours $\surd$ $\surd$ Wang et al. [236] Heuristic algorithm for $IC$ model $\surd$ $\times$ Chen et al. [37] Extended the classical $IC$ model to incorporating negative opinions $\surd$ $\times$ Nam et al. [188] Focused on how to limit viral propagation of misinformation in OSNs $\surd$ $\surd$ Wang et al. [239] Extended $IC$ to mobile social networks, and use a dynamic programming algorithm to select communities then find influential nodes $\surd$ $\surd$ Kyomin et al. [121] Algorithm IRIE where IR for influence ranking, and IE for influence maximization are proposed to improve the classical algorithm developed previously $\surd$ $\times$ The algorithm was used in both classical $IC$ model and the extension $IC$-$N$ [37] Thang [58] Extended the $LT$ model by constrain the influence distance as constant $d$ $\times$ $\surd$
Extensions or improvements of $IC/LT$ models
 References Extender $IC$ $LT$ Remarks Chen et al. [44] A scalable heuristic algorithm for $LT$ were developed by constructing a local directed acyclic graphs (DAGs) $\times$ $\surd$ Showed that computing influence spread in the linear threshold model is #P-hard problem Borodin et al. [22] Introduced $K$-$LT$ as the extension of $LT$ involved the competition of influence $\times$ $\surd$ He et al. [104] Under the $LT$ model, they extended it to influence blocking maximization problem $\times$ $\surd$ Goyal et al. [77] Improved the $LT$ by cutting down on the number of calls made in the first iteration which is the key to estimation procedure. $\times$ $\surd$ Goyal et al. [74] Under both $IC$ and $LT$ model, pursing the alternative goals which motivated by resource and time constraints $\surd$ $\surd$ Barbieri et al. [16] Extended both $IC$ and $LT$ to topic-aware models $\surd$ $\surd$ Wang et al. [238] Extended $IC$ to incorporate similarity in social network $\surd$ $\times$ Rodriguez et al. [198] General case of $IC$ model with time constraint $\surd$ $\times$
 References Extender $IC$ $LT$ Remarks Chen et al. [44] A scalable heuristic algorithm for $LT$ were developed by constructing a local directed acyclic graphs (DAGs) $\times$ $\surd$ Showed that computing influence spread in the linear threshold model is #P-hard problem Borodin et al. [22] Introduced $K$-$LT$ as the extension of $LT$ involved the competition of influence $\times$ $\surd$ He et al. [104] Under the $LT$ model, they extended it to influence blocking maximization problem $\times$ $\surd$ Goyal et al. [77] Improved the $LT$ by cutting down on the number of calls made in the first iteration which is the key to estimation procedure. $\times$ $\surd$ Goyal et al. [74] Under both $IC$ and $LT$ model, pursing the alternative goals which motivated by resource and time constraints $\surd$ $\surd$ Barbieri et al. [16] Extended both $IC$ and $LT$ to topic-aware models $\surd$ $\surd$ Wang et al. [238] Extended $IC$ to incorporate similarity in social network $\surd$ $\times$ Rodriguez et al. [198] General case of $IC$ model with time constraint $\surd$ $\times$
 [1] Yancong Xu, Lijun Wei, Xiaoyu Jiang, Zirui Zhu. Complex dynamics of a SIRS epidemic model with the influence of hospital bed number. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021016 [2] Gökhan Mutlu. On the quotient quantum graph with respect to the regular representation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020295 [3] Yunping Jiang. Global graph of metric entropy on expanding Blaschke products. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1469-1482. doi: 10.3934/dcds.2020325 [4] Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033 [5] Qiang Fu, Yanlong Zhang, Yushu Zhu, Ting Li. Network centralities, demographic disparities, and voluntary participation. Mathematical Foundations of Computing, 2020, 3 (4) : 249-262. doi: 10.3934/mfc.2020011 [6] Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451 [7] Kung-Ching Chang, Xuefeng Wang, Xie Wu. On the spectral theory of positive operators and PDE applications. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3171-3200. doi: 10.3934/dcds.2020054 [8] Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170 [9] Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2021002 [10] Rajendra K C Khatri, Brendan J Caseria, Yifei Lou, Guanghua Xiao, Yan Cao. Automatic extraction of cell nuclei using dilated convolutional network. Inverse Problems & Imaging, 2021, 15 (1) : 27-40. doi: 10.3934/ipi.2020049 [11] George W. Patrick. The geometry of convergence in numerical analysis. Journal of Computational Dynamics, 2021, 8 (1) : 33-58. doi: 10.3934/jcd.2021003 [12] Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458 [13] Sergey Rashkovskiy. Hamilton-Jacobi theory for Hamiltonian and non-Hamiltonian systems. Journal of Geometric Mechanics, 2020, 12 (4) : 563-583. doi: 10.3934/jgm.2020024 [14] Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310 [15] Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051 [16] Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060 [17] Yu-Jhe Huang, Zhong-Fu Huang, Jonq Juang, Yu-Hao Liang. Flocking of non-identical Cucker-Smale models on general coupling network. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1111-1127. doi: 10.3934/dcdsb.2020155 [18] Min Chen, Olivier Goubet, Shenghao Li. Mathematical analysis of bump to bucket problem. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5567-5580. doi: 10.3934/cpaa.2020251 [19] Ziang Long, Penghang Yin, Jack Xin. Global convergence and geometric characterization of slow to fast weight evolution in neural network training for classifying linearly non-separable data. Inverse Problems & Imaging, 2021, 15 (1) : 41-62. doi: 10.3934/ipi.2020077 [20] Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, 2021, 20 (1) : 449-465. doi: 10.3934/cpaa.2020276

Impact Factor: