Inferring Diffusion Network from Information Cascades using Transitive Influence
محورهای موضوعی : Complex NetworksMehdi Emadi 1 , Maseud Rahgozar 2 , Farhad Oroumchian 3
1 - Faculty of Electrical & Computer Engineering, Babol Noshirvani University of Technology, Babol, Mazandaran, Iran
2 - School of Electrical & Computer Engineering, University College of Engineering, University of Tehran, Tehran, Iran.
3 - Faculty of Engineering and Information Sciences, University of Wollongong in Dubai, Dubai, UAE
کلید واژه: Transitive Influence, Network Inferring, Diffusion Network, link Prediction, Random Network.,
چکیده مقاله :
Nowadays, online social networks have a great impact on people’s life and how they interact. News, sentiment, rumors, and fashion, like contagious diseases, are propagated through online social networks. When information is transmitted from one person to another in a social network, a diffusion process occurs. Each node of a network that participates in the diffusion process leaves some effects on this process, such as its transmission time. In most cases, despite the visibility of such effects of diffusion process, the structure of the network is unknown. Knowing the structure of a social network is essential for many research studies such as: such as community detection, expert finding, influence maximization, information diffusion, sentiment propagation, immunization against rumors, etc. Hence, inferring diffusion network and studying the behavior of the inferred network are considered to be important issues in social network researches. In recent years, various methods have been proposed for inferring a diffusion network. A wide range of proposed models, named parametric models, assume that the pattern of the propagation process follows a particular distribution. What's happening in the real world is very complicated and cannot easily be modeled with parametric models. Also, the models provided for large volumes of data do not have the required performance due to their high execution time. However, in this article, a nonparametric model is proposed that infers the underlying diffusion network. In the proposed model, all potential edges between the network nodes are identified using a similarity-based link prediction method. Then, a fast algorithm for graph pruning is used to reduce the number of edges. The proposed algorithm uses the transitive influence principle in social networks. The time complexity order of the proposed method is O(n3). This method was evaluated for both synthesized and real datasets. Comparison of the proposed method with state-of-the-art on different network types and various models of information cascades show that the model performs better precision and decreases the execution time too.
Nowadays, online social networks have a great impact on people’s life and how they interact. News, sentiment, rumors, and fashion, like contagious diseases, are propagated through online social networks. When information is transmitted from one person to another in a social network, a diffusion process occurs. Each node of a network that participates in the diffusion process leaves some effects on this process, such as its transmission time. In most cases, despite the visibility of such effects of diffusion process, the structure of the network is unknown. Knowing the structure of a social network is essential for many research studies such as: such as community detection, expert finding, influence maximization, information diffusion, sentiment propagation, immunization against rumors, etc. Hence, inferring diffusion network and studying the behavior of the inferred network are considered to be important issues in social network researches. In recent years, various methods have been proposed for inferring a diffusion network. A wide range of proposed models, named parametric models, assume that the pattern of the propagation process follows a particular distribution. What's happening in the real world is very complicated and cannot easily be modeled with parametric models. Also, the models provided for large volumes of data do not have the required performance due to their high execution time. However, in this article, a nonparametric model is proposed that infers the underlying diffusion network. In the proposed model, all potential edges between the network nodes are identified using a similarity-based link prediction method. Then, a fast algorithm for graph pruning is used to reduce the number of edges. The proposed algorithm uses the transitive influence principle in social networks. The time complexity order of the proposed method is O(n3). This method was evaluated for both synthesized and real datasets. Comparison of the proposed method with state-of-the-art on different network types and various models of information cascades show that the model performs better precision and decreases the execution time too.
[1] A. Guille, H. Hacid, C. Favre, and D. A. Zighed, “Information Diffusion in Online Social Networks: A Survey,” ACM SIGMOD Record, vol. 42, no. 2, pp. 17–28, 2013.
[2] R. Badie, A. Aleahmad, M. Asadpour, and M. Rahgozar, “An efficient agent-based algorithm for overlapping community detection using nodes’ closeness,” Physica A: Statistical Mechanics and its Applications, vol. 392, no. 20, pp. 5231–5247, Oct. 2013.
[3] Z. Arefian and M.R. Khayyam Bashi. “Scalable Community Detection through Content and Link Analysis in Social Networks,” Journal of Information Systems and Telecommunication (JIST), vol. 4, no.12, pp. 1-10, 2015.
[4] A.H. Hosseinian and V. Baradaran. “A multi-objective multi-agent optimization algorithm for the community detection problem,” Journal of Information Systems and Telecommunication (JIST), vol. 6, no. 3, pp. 166-176, 2018.
[5] E. Sherkat, M. Rahgozar, and M. Asadpour, “Structural link prediction based on ant colony approach in social networks,” Physica A, vol. 419, pp. 80–94, 2015.
[6] V. Martínez, F. Berzal, and J.-C. Cubero, “A Survey of Link Prediction in Complex Networks,” ACM Computing Surveys, vol. 49, no. 4, pp. 1–33, Dec. 2016.
[7] M. P. Salvati, J. Bagherzadeh Mohasefi, and S. Sulaimany. “Overcoming the Link Prediction Limitation in Sparse Networks using Community Detection,” Journal of Information Systems and Telecommunication (JIST), vol. 3, no. 35, pp. 183-190, 2021.
[8] R. Safa, S. A. Mirroshandel, S. Javadi, and M. Azizi. “Publication venue recommendation based on paper title and co-authors network,” Journal of Information Systems and Telecommunication (JIST), vol. 6, no. 21, pp. 33-40, 2018.
[9] K. Rahimkhani, A. Aleahmad, M. Rahgozar, and A. Moeini, “A Fast Algorithm for Finding Most Influential People Based on the Linear,” Expert Systems With Applications, vol. 42, no. 3, pp. 1353–1361, Feb. 2014.
[10] M. Emadi and M. Rahgozar, “Twitter sentiment analysis using fuzzy integral classifier fusion,” Journal of Information Science, vol. 46, no. 2, 2020.
[11] A.A. Kardan and B. Bozorgi. “Analysis of Main Expert-Finding Algorithms in Social Network in Order to Rank the Top Algorithms,” Journal of Information Systems and Telecommunication (JIST), vol. 5, no. 20, pp. 217-224, 2017.
[12] A. Guille, H. Hacid, C. Favre, and D. A. Zighed, “Information Diffusion in Online Social Networks: A Survey,” ACM SIGMOD Record, vol. 42, no. 2, pp. 17–28, 2013.
[13] I. Brugere, B. Gallagher, and T. Y. Berger-Wolf, “Network Structure Inference, A Survey: Motivations, Methods, and Applications,” Oct. 2016.
[14] O. Gomes, “Sentiment cycles in discrete-time homogeneous networks,” Physica A: Statistical Mechanics and its Applications, vol. 428, pp. 224–238, Jun. 2015.
[15] L. Zhao, J. Wang, R. Huang, H. Cui, X. Qiu, and X. Wang, “Sentiment contagion in complex networks,” Physica A: Statistical Mechanics and its Applications, vol. 394, pp. 17–23, Jan. 2014.
[16] L. Prokhorenkova, A. Tikhonov, and Y. Nelly Litvak, “When Less Is More: Systematic Analysis of Cascade-Based Community Detection,” ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 16, no. 4, Jan. 2022.
[17] I. Brugere, B. Gallagher, and T. Y. Berger-Wolf, “Network Structure Inference, A Survey: Motivations, Methods, and Applications,” Oct. 2016.
[18] M. Gomez-Rodriguez, J. Leskovec, and A. Krause, “Inferring Networks of Diffusion and Influence,” ACM Transactions on Knowledge Discovery from Data, vol. 5, no. 4, pp. 1–37, Feb. 2010.
[19] M. Gomez Rodriguez, J. Leskovec, and B. Schölkopf, “Structure and dynamics of information pathways in online media,” in Proceedings of the sixth ACM international conference on Web search and data mining - WSDM ’13, 2013, pp. 23–32.
[20] M. G. RODRIGUEZ, J. LESKOVEC, D. BALDUZZI, and B. SCHÖLKOPF, “Uncovering the structure and temporal dynamics of information propagation,” Network Science, vol. 2, no. 01, pp. 26–65, Apr. 2014.
[21] LiHuacheng, XiaChunhe, WangTianbo, WenSheng, ChenChao, and XiangYang, “Capturing Dynamics of Information Diffusion in SNS: A Survey of Methodology and Techniques,” ACM Computing Surveys (CSUR), vol. 55, no. 1, pp. 1–51, Nov. 2021.
[22] C. Ravazzi, F. Dabbene, C. Lagoa, and A. v. Proskurnikov, “Learning Hidden Influences in Large-Scale Dynamical Social Networks: A Data-Driven Sparsity-Based Approach, in Memory of Roberto Tempo,” IEEE Control Systems, vol. 41, no. 5, pp. 61–103, Oct. 2021.
[23] H. Yang et al., “Towards embedding information diffusion data for understanding big dynamic networks,” Neurocomputing, vol. 466, pp. 265–284, Nov. 2021.
[24] S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, First Ed. Cambridge, United Kingdom: Cambridge University Press, 1994.
[25] K. Chen, P. Luo, and H. Wang, “An influence framework on product word-of-mouth (WoM) measurement,” Information and Management, vol. 54, no. 2, pp. 228–240, Mar. 2017.
[26] M. Gomez-Rodriguez, J. Leskovec, and A. Krause, “Inferring Networks of Diffusion and Influence,” ACM Transactions on Knowledge Discovery from Data, vol. 5, no. 4, pp. 1–37, Feb. 2010.
[27] M. G. RODRIGUEZ, J. LESKOVEC, D. BALDUZZI, and B. SCHÖLKOPF, “Uncovering the structure and temporal dynamics of information propagation,” Network Science, vol. 2, no. 01, pp. 26–65, Apr. 2014.
[28] S. Shaghaghian and M. Coates, “Online Bayesian Inference of Diffusion Networks,” IEEE Transactions on Signal and Information Processing over Networks, vol. 3, no. 3, pp. 500–512, Sep. 2016.
[29] M. Gomez Rodriguez, J. Leskovec, and B. Schölkopf, “Structure and dynamics of information pathways in online media,” in Proceedings of the sixth ACM international conference on Web search and data mining - WSDM ’13, 2013, pp. 23–32.
[30] S. A. S. Myers and J. Leskovec, “On the Convexity of Latent Social Network Inference,” in NIPS’10 Proceedings of the 23rd International Conference on Neural Information Processing Systems - Volume 2, 2010, pp. 1741–1749.
[31] S. Wang, X. Hu, P. S. Yu, and Z. Li, “MMRate: inferring multi-aspect diffusion networks with multi-pattern cascades,” Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’14, pp. 1246–1255, 2014.
[32] N. Du, L. Song, H. Woo, and H. Zha, “Uncover Topic-Sensitive Information Diffusion Networks,” in Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, 2013, vol. 31, pp. 229–237.
[33] D. H. Zhou, W. B. Han, Y. J. Wang, and B. Di Yuan, “Information diffusion network inferring and pathway tracking,” Science China Information Sciences, vol. 58, no. 9, pp. 1–15, Sep. 2015.
[34] C. E. Cormen, Thomas H., Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. MIT Press and McGraw-Hill, 2009.
[35] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, and Z. Ghahramani, “Kronecker Graphs: An Approach to Modeling Networks,” Journal of Machine Learning Research, vol. 11, no. Feb, pp. 985–1042, 2010.
[36] E. Cho, S. A. Myers, and J. Leskovec, “Friendship and mobility,” in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD ’11, 2011, pp. 1082-1090.
[37] J. Leskovec and R. Sosič, “SNAP: A General-Purpose Network Analysis and Graph-Mining Library,” ACM Transactions on Intelligent Systems and Technology, vol. 8, no. 1, pp. 1–20, Jul. 2016.
