# 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] Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 [2] John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004 [3] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [4] Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075 [5] Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 [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, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 [7] W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 [8] Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159 [9] Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021016 [10] Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225 [11] Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024 [12] Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023 [13] Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 [14] Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446 [15] Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1 [16] Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034 [17] Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056 [18] Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197 [19] Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205 [20] Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

Impact Factor: