# 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] Mirela Domijan, Markus Kirkilionis. Graph theory and qualitative analysis of reaction networks. Networks & Heterogeneous Media, 2008, 3 (2) : 295-322. doi: 10.3934/nhm.2008.3.295 [2] Shuping Li, Zhen Jin. Impacts of cluster on network topology structure and epidemic spreading. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3749-3770. doi: 10.3934/dcdsb.2017187 [3] Liu Hui, Lin Zhi, Waqas Ahmad. Network(graph) data research in the coordinate system. Mathematical Foundations of Computing, 2018, 1 (1) : 1-10. doi: 10.3934/mfc.2018001 [4] Deena Schmidt, Janet Best, Mark S. Blumberg. Random graph and stochastic process contributions to network dynamics. Conference Publications, 2011, 2011 (Special) : 1279-1288. doi: 10.3934/proc.2011.2011.1279 [5] M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201 [6] Wu Chanti, Qiu Youzhen. A nonlinear empirical analysis on influence factor of circulation efficiency. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 929-940. doi: 10.3934/dcdss.2019062 [7] Mario Roy, Mariusz Urbański. Multifractal analysis for conformal graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 627-650. doi: 10.3934/dcds.2009.25.627 [8] Barton E. Lee. Consensus and voting on large graphs: An application of graph limit theory. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 1719-1744. doi: 10.3934/dcds.2018071 [9] Luigi Fontana, Steven G. Krantz and Marco M. Peloso. Hodge theory in the Sobolev topology for the de Rham complex on a smoothly bounded domain in Euclidean space. Electronic Research Announcements, 1995, 1: 103-107. [10] A. C. Eberhard, J-P. Crouzeix. Existence of closed graph, maximal, cyclic pseudo-monotone relations and revealed preference theory. Journal of Industrial & Management Optimization, 2007, 3 (2) : 233-255. doi: 10.3934/jimo.2007.3.233 [11] Mark G. Burch, Karly A. Jacobsen, Joseph H. Tien, Grzegorz A. Rempała. Network-based analysis of a small Ebola outbreak. Mathematical Biosciences & Engineering, 2017, 14 (1) : 67-77. doi: 10.3934/mbe.2017005 [12] Chun Zong, Gen Qi Xu. Observability and controllability analysis of blood flow network. Mathematical Control & Related Fields, 2014, 4 (4) : 521-554. doi: 10.3934/mcrf.2014.4.521 [13] Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete & Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253 [14] Daniel Roggen, Martin Wirz, Gerhard Tröster, Dirk Helbing. Recognition of crowd behavior from mobile sensors with pattern analysis and graph clustering methods. Networks & Heterogeneous Media, 2011, 6 (3) : 521-544. doi: 10.3934/nhm.2011.6.521 [15] 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 [16] Gheorghe Craciun, Baltazar Aguda, Avner Friedman. Mathematical Analysis Of A Modular Network Coordinating The Cell Cycle And Apoptosis. Mathematical Biosciences & Engineering, 2005, 2 (3) : 473-485. doi: 10.3934/mbe.2005.2.473 [17] Rumi Ghosh, Kristina Lerman. Rethinking centrality: The role of dynamical processes in social network analysis. Discrete & Continuous Dynamical Systems - B, 2014, 19 (5) : 1355-1372. doi: 10.3934/dcdsb.2014.19.1355 [18] Yacine Chitour, Frédéric Grognard, Georges Bastin. Equilibria and stability analysis of a branched metabolic network with feedback inhibition. Networks & Heterogeneous Media, 2006, 1 (1) : 219-239. doi: 10.3934/nhm.2006.1.219 [19] Thomas Hillen, Peter Hinow, Zhi-An Wang. Mathematical analysis of a kinetic model for cell movement in network tissues. Discrete & Continuous Dynamical Systems - B, 2010, 14 (3) : 1055-1080. doi: 10.3934/dcdsb.2010.14.1055 [20] D. Warren, K Najarian. Learning theory applied to Sigmoid network classification of protein biological function using primary protein structure. Conference Publications, 2003, 2003 (Special) : 898-904. doi: 10.3934/proc.2003.2003.898

Impact Factor: