Influence Maximization using Time Delay based Harmonic Centrality in Social Networks

نوع مقاله : علمی-پژوهشی

نویسندگان

1 Department of Computer Engineering, Dezful Branch, Islamic Azad University, Dezful, Iran

2 Department of Computer Engineering, Dezful Branch, Islamic Azad University, Dezful, Iran/ Department of Engineering, Shahrekord Branch, Islamic Azad University, Shahrekord, Iran

چکیده

With the extension of social networks, research on influence maximization (IM) in time-sensitive graphs has increased in recent years. IM is a problem to find a seed set with k nodes to maximize the information propagation range in the graph. Most of the research in this area consists of greedy, heuristic, meta-heuristic methods. However, most of these methods ignore the time-sensitivity to propagation delay and duration. The preceding time-sensitive centrality measures as a part of heuristic approaches take the propagation delay but only consider the nodes locally so that each graph node considers only the direct neighbors. Based on the above analysis, this article focuses on the time-sensitive IM problem. Here, a propagation value for each path in the graph is defined in terms of the probability of affecting through the edge and freshness amount of the edge. To solve the problem, we propose time-sensitive centrality measures that consider propagation value and both the direct and the indirect neighbors. Therefore, four measures of time-sensitive closeness centrality (TSCloseness), time-sensitive harmonic (TSHarmonic), time-sensitive decay centrality (TSDecay), and time-sensitive eccentricity centrality (TSEccentricity) were proposed. The experiments on five datasets demonstrate the efficiency and influence performance of the TSHarmonic measure on evaluation metrics.

کلیدواژه‌ها

عنوان مقاله [English]

Influence Maximization using Time Delay based Harmonic Centrality in Social Networks

نویسندگان [English]

  • S. Mokhtarizadeh 1
  • B. Zamani Dehkordi 2
  • M. Mosleh 1
  • Ali Barati 1
1 Department of Computer Engineering, Dezful Branch, Islamic Azad University, Dezful, Iran
2 Department of Computer Engineering, Dezful Branch, Islamic Azad University, Dezful, Iran/ Department of Engineering, Shahrekord Branch, Islamic Azad University, Shahrekord, Iran
چکیده [English]

With the extension of social networks, research on influence maximization (IM) in time-sensitive graphs has increased in recent years. IM is a problem to find a seed set with k nodes to maximize the information propagation range in the graph. Most of the research in this area consists of greedy, heuristic, meta-heuristic methods. However, most of these methods ignore the time-sensitivity to propagation delay and duration. The preceding time-sensitive centrality measures as a part of heuristic approaches take the propagation delay but only consider the nodes locally so that each graph node considers only the direct neighbors. Based on the above analysis, this article focuses on the time-sensitive IM problem. Here, a propagation value for each path in the graph is defined in terms of the probability of affecting through the edge and freshness amount of the edge. To solve the problem, we propose time-sensitive centrality measures that consider propagation value and both the direct and the indirect neighbors. Therefore, four measures of time-sensitive closeness centrality (TSCloseness), time-sensitive harmonic (TSHarmonic), time-sensitive decay centrality (TSDecay), and time-sensitive eccentricity centrality (TSEccentricity) were proposed. The experiments on five datasets demonstrate the efficiency and influence performance of the TSHarmonic measure on evaluation metrics.

کلیدواژه‌ها [English]

  • Influence Maximization
  • Propagation Delay
  • Closeness centrality
  • Harmonic centrality
  • Decay centrality
  • Eccentricity centrality

مراجع

[1] H. Huang, H. Shen, Z. Meng, H. Chang, H. He, “Community-based influence maximization for viral marketing”, Applied Intelligence, vol. 49, pp. 2137-2150, 2018.
[2] C. Budak, D. Agrawal, A. El Abbadi, “Limiting the spread of misinformation in social networks”, In the Proceedings of the 20th international conference on World Wide Web, 2011, pp. 665-674.
[3] M. A. Manouchehri, M. S. Helfroush, H. Danyali, “A Theoretically Guaranteed Approach to Efficiently Block the Influence of Misinformation in Social Networks”, IEEE Transactions on Computational Social Systems, vol. 8, pp. 716-727, 2021.
[4] D. Kempe, J. Kleinberg, É. Tardos, “Maximizing the spread of influence through a social network”, In the Proceedings of the 9th ACM SIGKDD international conference on Knowledge discovery and data mining, 2003, Washington, DC, USA, pp. 137-146.
[5] A. Mohammadi, M. Saraee, A. Mirzaei, “Time-sensitive influence maximization in social networks”, Journal of Information Science, vol. 41, no. 6, pp. 765-778, 2015.
[6] M. Adineh, M. Nouri-Baygi, “High Quality Degree Based Heuristics for the Influence Maximization Problem”, arXiv preprint arXiv:1904.12164, 2019.
[7] P. Domingos, M. Richardson, “Mining the network value of customers”, In the Proceedings of the 7th ACM SIGKDD international conference on Knowledge discovery and data mining, 2001, San Francisco, California, pp. 57-66.
[8] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective outbreak detection in networks”, In the Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007, San Jose, California, USA, pp. 420-429.
[9] A. Goyal, W. Lu, L.V.S. Lakshmanan, “CELF++: optimizing the greedy algorithm for influence maximization in social networks”, In the Proceedings of the 20th international conference companion on World wide web, 2011, Hyderabad, India, pp. 47-48.
[10] Y. Wang, G. Cong, G. Song, K. Xie, “Community-based greedy algorithm for mining top-K influential nodes in mobile social networks”, In the Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010, Washington, DC, USA, pp. 1039-1048.
[11]  K. Jung, W. Heo, and W. Chen, “IRIE: Scalable and Robust Influence Maximization in Social Networks”, In 2010 IEEE 12th International Conference on Data Mining, 2012, Brussels, Belgium, pp. 918-923,.
[12] A. Sheikhahmadi, M. A. Nematbakhsh, A. Zareie, “Identification of influential users by neighbors in online social networks”, Physica A: Statistical Mechanics and its Applications, vol. 486, pp. 517-534, 2017.
[13] W. Chen, C. Wang, Y. Wang, “Scalable influence maximization for prevalent viral marketing in large-scale social networks”, In the Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010, Washington, DC, USA, pp. 1029-1038.
[14] W. Chen, Y. Yuan, L. Zhang, “Scalable Influence Maximization in Social Networks under the Linear Threshold Model”, In 2010 IEEE International Conference on Data Mining, 2010, Sydney, Australia, pp. 88-97.
[15] A. Zareie, A. Sheikhahmadi, M. Jalili, “Identification of influential users in social network using gray wolf optimization algorithm”, Expert Systems with Applications, vol. 142, 2020.
[16] A. Zareie, A. Sheikhahmadi, M. Jalili, M.S.K. Fasaei, “Finding influential nodes in social networks based on neighborhood correlation coefficient”, Knowledge-based systems, vol. 194, 2020.
[17] Ch. Salavati, A. Abdollahpouri, Zh. Manbari, “A Multi-objective Algorithm for Identifying Influential Nodes in Social Networks”, Tabriz Journal of Electrical Engineering, vol. 50, no. 3, pp. 1293-1304, 2020 (in persian).
[18] M. Kitsak, L.K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H.E. Stanley, H.A. Makse, “Identification of influential spreaders in complex networks”, Nature physics, vol. 6, no. 11, pp. 888-893, 2010.
[19] W. Chen, Y. Wang, S. Yang, “Efficient influence maximization in social networks”, In the Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009, Paris, pp. 199-208.
[20] X. Wang, Y. Su, C. Zhao, D. Yi, “Effective identification of multiple influential spreaders by DegreePunishment”, Physica A: Statistical Mechanics and its Applications, vol. 461, pp. 238-247, 2016.
[21] A. Sheikhahmadi, M. A. Nematbakhsh, and A. Shokrollahi, “Improving detection of influential nodes in complex networks”, Physica A: Statistical Mechanics and its Applications, vol. 436, pp. 833-845, 2015.
[22] A. Zareie, A. Sheikhahmadi, K. Khamforoosh, “Influence maximization in social networks based on TOPSIS”, Expert Systems with Applications, vol. 108, pp. 96-107, 2018.
[23] L. Katz, “A new status index derived from sociometric analysis”, Psychometrika, vol. 18, no. 1, pp. 39-43, 1953.
[24] A. Zareie, A. Sheikhahmadi, and R. Sakellariou, “A composite centrality measure for improved identification of influential users”, arXiv preprint arXiv:2111.04529, 2021.
[25] K. Saito, M. Kimura, K. Ohara, H. Motoda, “Learning continuous-time information diffusion model for social behavioral data analysis”, In Asian Conference on Machine Learning,  2009, Berlin, Heidelberg, pp. 322-337.
[26] W. Chen, W. Lu, N. Zhang, “Time-critical influence maximization in social networks with time-delayed diffusion process”, In the Proceedings of the 26th AAAI Conference on Artificial Intelligence, 2012, Toronto, Ontario, Canada.
[27] J. Kim, W. Lee, H. Yu, “CT-IC: Continuously activated and time-restricted independent cascade model for viral marketing”, Knowledge-Based Systems, vol. 62, pp. 57-68, 2014.
[28] R. Yan, Y. Li, D. Li, Y. Zhu, Y. Wang, H. Du, “Activation probability maximization for target users under influence decay model”, in International Computing and Combinatorics Conference, 2019, Springer, pp. 603-614.
[29] N. Ohsaka, Y. Yamaguchi, N. Kakimura, K.I. Kawarabayashi, “Maximizing time-decaying influence in social networks”, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2016, Springer, Cham, pp. 132-147.
[30] M. Hu, Q. Liu, H. Huang, X. Jia, “Time-sensitive influence maximization in social networks”, in 18th International Conference on Communication Technology (ICCT), 2018, IEEE, pp. 1351-1356.
[31] M. Huiyu, C. Jiuxin, Y. Tangfei, B. Liu, “Topic based time-sensitive influence maximization in online social networks”, World Wide Web, vol. 23, no. 3, pp. 1831-1859, 2020.
[32] Y. Wang, Y. Zhang, F. Yang, D. Li, X. Sun, J. Ma, “Time-sensitive positive influence maximization in signed social networks”, Physica A: Statistical Mechanics and its Applications, vol. 584, pp. 126353, 2021.
[33] A. Goyal, F. Bonchi, L.V.S. Lakshmanan, “Learning influence probabilities in social networks”, In the Proceedings of the 3rd ACM international conference on web search and data mining, 2010, New York, USA, pp. 241-250.
[34] B. Liu, G. Cong, D. Xu, Y. Zeng, “Time constrained influence maximization in social networks”, in 12th international conference on data mining, 2012, IEEE, Brussels, Belgium, pp. 439-448.
[35] B. Liu, G. Cong, Y. Zeng, D. Xu, Y.M. Chee, “Influence spreading path and its application to the time constrained social influence maximization problem and beyond”, IEEE Transactions on Knowledge and Data Engineering, vol. 26, no. 8, pp. 1904-1917, 2013.
[36] L.C. Freeman, “Centrality in social networks conceptual clarification”, Social Networks, vol. 1, no. 3, pp. 215-239, 1978.
[37] L.C. Freeman, “A set of measures of centrality based on Betweenness”, Sociometry, pp. 35-41, 1977.
[38] M.O. Jackson, “Social and economic networks”, Princeton university press, 2010.
[39] P. Crescenzi, G. d’Angelo, L. Severini, Y. Velaj, “Greedily improving our own centrality in a network”, in International Symposium on Experimental Algorithms, 2015, Springer, pp. 43-55.
[40] U. Brandes, “A faster algorithm for Betweenness centrality”, Journal of mathematical sociology, vol. 25, no. 2, pp. 163-177, 2001.
[41] A. Raychaudhuri, S. Mallick, A. Sircar, S. Singh, “Identifying Influential Nodes Based on Network Topology: A Comparative Study”, in Information, Photonics and Communication, 2020, Springer, pp. 65-76.
[42] P. Jia, J. Liu, C. Huang, L. Liu, C. Xu, “An improvement method for degree and its extending centralities in directed networks”, Physica A: Statistical Mechanics and its Applications, vol. 532, pp. 121891, 2019.
[43] S. Babaei  S. Molaei  M. Salehi, “Modeling Information Diffusion in Bibliographic Multilayer Networks”, Tabriz Journal of Electrical Engineering, vol. 49, no. 2, pp. 503-515, 2019 (in persian).
[44] J. Kunegis, “Konect: the koblenz network collection”, in Proceedings of the 22nd international conference on World Wide Web, 2013, pp. 1343-1350.
[45] J. Leskovec, D. Huttenlocher, J. Kleinberg, “Predicting Positive and Negative Links in Online Social
Networks”, In Proceedings of the 19th international conference on World Wide Web, 2010, North Carolina, USA, pp. 641-650.
 

فایل ها

هم رسانی

ارجاع به این مقاله

آمار