# 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] 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 [2] 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 [3] 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 [4] Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051 [5] Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346 [6] Laurence Cherfils, Stefania Gatti, Alain Miranville, Rémy Guillevin. Analysis of a model for tumor growth and lactate exchanges in a glioma. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020457 [7] Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020446 [8] Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219 [9] 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, , () : -. doi: 10.3934/cpaa.2020276 [10] Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341 [11] A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

Impact Factor:

## Tools

Article outline

Figures and Tables