Influenced node discovery in a temporal contact network based on common nodes

Jinjing Huang; Xi Wang; Jinjing Huang; Xi Wang

doi:10.3934/mbe.2023609

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 8: 13660-13680. doi: 10.3934/mbe.2023609

Previous Article Next Article

Research article Special Issues

Influenced node discovery in a temporal contact network based on common nodes

Jinjing Huang ¹,
Xi Wang ^{1,2
,
,}

1.
School of Software and Services Outsourcing, Suzhou Vocational Institute of Industrial Technology, Suzhou 215004, China
2.
Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China

Academic Editor: Chunwei Tian

Received: 02 May 2023 Revised: 01 June 2023 Accepted: 01 June 2023 Published: 15 June 2023

Verification is the only way to make sure if a node is influenced or not because of the uncertainty of information diffusion in the temporal contact network. In the previous methods, only $ N $ influenced nodes could be found for a given number of verifications $ N $. The target of discovering influenced nodes is to find more influenced nodes with the limited number of verifications. To tackle this difficult task, the common nodes on the temporal diffusion paths is proposed in this paper. We prove that if a node $ v $ is confirmed as the influenced node and there exist common nodes on the temporal diffusion paths from the initial node to the node $ v $, these common nodes can be regarded as the influenced nodes without verification. It means that it is possible to find more than $ N $ influenced nodes given $ N $ verifications. The common nodes idea is applied to search influenced nodes in the temporal contact network, and three algorithms are designed based on the idea in this paper. The experiments show that our algorithms can find more influenced nodes in the existence of common nodes.
- temporal contact network,
- information diffusion,
- temporal diffusion path,
- influenced nodes,
- infection probability
Citation: Jinjing Huang, Xi Wang. Influenced node discovery in a temporal contact network based on common nodes[J]. Mathematical Biosciences and Engineering, 2023, 20(8): 13660-13680. doi: 10.3934/mbe.2023609

Related Papers:

Abstract

Verification is the only way to make sure if a node is influenced or not because of the uncertainty of information diffusion in the temporal contact network. In the previous methods, only $ N $ influenced nodes could be found for a given number of verifications $ N $. The target of discovering influenced nodes is to find more influenced nodes with the limited number of verifications. To tackle this difficult task, the common nodes on the temporal diffusion paths is proposed in this paper. We prove that if a node $ v $ is confirmed as the influenced node and there exist common nodes on the temporal diffusion paths from the initial node to the node $ v $, these common nodes can be regarded as the influenced nodes without verification. It means that it is possible to find more than $ N $ influenced nodes given $ N $ verifications. The common nodes idea is applied to search influenced nodes in the temporal contact network, and three algorithms are designed based on the idea in this paper. The experiments show that our algorithms can find more influenced nodes in the existence of common nodes.

References

[1]	A. Guille, H. Hacid, C. Favre, D. A. Zighed, Information diffusion in online social networks: A survey, ACM SIGMOD Record, 42 (2013), 17–28. https://doi.org/10.1145/2503792.2503797 doi: 10.1145/2503792.2503797
[2]	J. Byun, S. Woo, D. Kim, Chronograph: Enabling temporal graph traversals for efficient information diffusion analysis over time, IEEE Trans. Knowl. Data Eng., 32 (2020), 424–437. https://doi.org/10.1109/TKDE.2019.2891565 doi: 10.1109/TKDE.2019.2891565
[3]	J. J. Huang, T. Q. Lin, A. Liu, Z. Li, H. Yin, L. Zhao, Influenced nodes discovery in temporal contact network, in Proceedings of the 18th International Conference on Web Information Systems Engineering, (2017), 472–487. https://doi.org/10.1007/978-3-319-68783-4_32
[4]	T. Q. Lin, Diffusion range prediction in temporal diffusion networks, Master's thesis, Soochow University, 2017.
[5]	Y. X. Wang, H. Z. Wang, J. Z. Li, H. Gao, Efficient influence maximization in weighted independent cascade model, in Proceedings of the 21st International Conference on Database Systems for Advanced Applications, (2016), 49–64. https://doi.org/10.1007/978-3-319-32049-6_4
[6]	T. Iwata, A. Shah, Z. Ghahramani, Discovering latent influence in online social activities via shared cascade poisson processes, in Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, (2013), 266–274. https://doi.org/10.1145/2487575.2487624
[7]	M. Gomez-Rodriguez, L. Song, Diffusion in social and information networks: Research problems, probabilistic models and machine learning methods, in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2015), 2315–2316. https://doi.org/10.1145/2783258.2789991
[8]	M. Nickel, M. Le, Modeling sparse information diffusion at scale via lazy multivariate hawkes processes, in Proceedings of the 21th International Conference of World Wide Web, (2021), 706–717. https://doi.org/10.1145/3442381.3450094
[9]	L. Sun, Y. Rao, X. B. Zhang, Y. Lan, S. Yu, MS-HGAT: memory-enhanced sequential hypergraph attention network for information diffusion prediction, in Proceedings of the 36th AAAI Conference on Artificial Intelligence, (2022), 4156–4164. https://ojs.aaai.org/index.php/AAAI/article/view/20334
[10]	M. Gomez-Rodriguez, J. Leskovec, A. Krause, Inferring networks of diffusion and influence, in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, (2010), 1019–1028. https://doi.org/10.1145/1835804.1835933
[11]	K. Kutzkov, A. Bifet, F. Bonchi, A. Gionis, STRIP: stream learning of influence probabilities, in Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2013), 275–283. https://doi.org/10.1145/2487575.2487657
[12]	A. Sepehr, H. Beigy, Viral cascade probability estimation and maximization in diffusion networks, IEEE Trans. Knowl. Data Eng., 31 (2019), 589–600. https://doi.org/10.1109/TKDE.2018.2840998 doi: 10.1109/TKDE.2018.2840998
[13]	H. Wang, C. Yang, C. Shi, Neural information diffusion prediction with topic-aware attention network, in Proceedings of the 30th ACM International Conference on Information and Knowledge Management, (2021), 1899–1908. https://doi.org/10.1145/3459637.3482374
[14]	D. A. Vega-Oliveros, L. Zhao, A. Rocha, L. Berton, Link prediction based on stochastic information diffusion, IEEE Trans. Neural Networks Learn. Syst., 33 (2022), 3522–3532. https://doi.org/10.1109/TNNLS.2021.3053263 doi: 10.1109/TNNLS.2021.3053263
[15]	J. Y. Chen, J. Zhang, Z. Chen, M. Du, Q. Xuan, Time-aware gradient attack on dynamic network link prediction, IEEE Trans. Knowl. Data Eng., 35 (2023), 2091–2102. https://doi.org/10.1109/TKDE.2021.3110580 doi: 10.1109/TKDE.2021.3110580
[16]	F. Granese, D. Gorla, C. Palamidessi, Enhanced models for privacy and utility in continuous-time diffusion networks, Int. J. Inf. Sec., 20 (2021), 763–782. https://doi.org/10.1007/s10207-020-00530-7 doi: 10.1007/s10207-020-00530-7
[17]	D. Gorla, F. Granese, C. Palamidessi, Enhanced models for privacy and utility in continuous-time diffusion networks, in Proceedings of the 16th International Conference on Theoretical Aspects of Computing, (2019), 313–331. https://doi.org/10.1007/978-3-030-32505-3_18
[18]	X. D. Wu, L. Y. Fu, H. Long, D. Yang, Y. Lu, X. Wang, Adaptive diffusion of sensitive information in online social networks, IEEE Trans. Knowl. Data Eng., 33 (2021), 3020–3034. https://doi.org/10.1109/TKDE.2020.2964242 doi: 10.1109/TKDE.2020.2964242
[19]	W. Wang, H. L. Yang, Y. F. Lu, Y. Zou, X. Zhang, S. Guo, et al., Influence maximization in multi-relational social networks, in Proceedings of the 30th ACM International Conference on Information and Knowledge Management, (2021), 4193–4202. https://doi.org/10.1145/3459637.3481928
[20]	T. T. Cai, J. X. Li, A. Mian, R. H. Li, T. Sellis, J. X. Yu, Target-aware holistic influence maximization in spatial social networks, IEEE Trans. Knowl. Data Eng., 34 (2022), 1993–2007. https://doi.org/10.1109/TKDE.2020.3003047 doi: 10.1109/TKDE.2020.3003047
[21]	S. X. Huang, W. Q. Lin, Z. F. Bao, J. C. Sun, Influence maximization in real-world closed social networks, Proc. VLDB Endow., 16 (2022), 180–192.
[22]	C. Feng, L. Y. Fu, B. Jiang, H. Zhang, X. Wang, F. Tang, et al., Neighborhood matters: Influence maximization in social networks with limited access, IEEE Trans. Knowl. Data Eng., 34 (2022), 2844–2859. https://doi.org/10.1109/TKDE.2020.3015387 doi: 10.1109/TKDE.2020.3015387
[23]	G. D'Angelo, L. Severini, Y. Velaj, Influence maximization in the independent cascade model, in Proceedings of the 17th Italian Conference on Theoretical Computer Science, (2016), 269–274.
[24]	G. M. Tong, R. Q. Wang, Z. Dong, X. Li, Time-constrained adaptive influence maximization, IEEE Trans. Comput. Soc. Syst., 8 (2021), 33–44. https://doi.org/10.1109/TCSS.2020.3032616 doi: 10.1109/TCSS.2020.3032616
[25]	C. Wang, Y. M. Liu, X. F. Gao, G. H. Chen, A reinforcement learning model for influence maximization in social networks, in Proceedings of the 26th International Conference on Database Systems for Advanced Applications, (2021), 701–709. https://doi.org/10.1007/978-3-030-73197-7_48
[26]	R. Michalski, Linear threshold model in temporal networks: Seed selection for social influence, in Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, (2015), 922–923. https://doi.org/10.1145/2808797.2809346
[27]	C. W. Tian, M. H. Zheng, W. M. Zuo, B. Zhang, Y. Zhang, D. Zhang, Multi-stage image denoising with the wavelet transform, Pattern Recognit., 134 (2023), 109050. https://doi.org/10.1016/j.patcog.2022.109050 doi: 10.1016/j.patcog.2022.109050
[28]	C. W. Tian, Y. N. Zhang, W. M. Zuo, C. W. Lin, D. Zhang, Y. Yuan, A heterogeneous group CNN for image super-resolution, IEEE Trans. Neural Networks Learn. Syst., https://doi.org/10.48550/arXiv.2209.12406 doi: 10.48550/arXiv.2209.12406
[29]	Q. Zhang, J. Xiao, C. W. Tian, J. C. Lin, S. Zhang, A robust deformed convolutional neural network (CNN) for image denoising, CAAI Trans. Intell. Technol., 2022. https://doi.org/10.1049/cit2.12110 doi: 10.1049/cit2.12110
[30]	C. W. Tian, X. Y. Zhang, J. C. Lin, W. Zuo, Y. Zhang, C. Lin, Generative adversarial networks for image super-resolution: A survey, preprint, arXiv: 2204.13620.
[31]	C. W. Tian, Y. Xu, W. M. Zuo, B. Zhang, L. Fei, Coarse-to-fine CNN for image super-resolution, IEEE Trans. Multim., 23 (2021), 1489–1502. https://doi.org/10.1109/TMM.2020.2999182 doi: 10.1109/TMM.2020.2999182
[32]	C. W. Tian, Y. Xu, W. M. Zuo, C. W. Lin, D. Zhang, Asymmetric CNN for image superresolution, IEEE Trans. Syst. Man Cybern. Syst., 52 (2022), 3718–3730. https://doi.org/10.1109/TSMC.2021.3069265 doi: 10.1109/TSMC.2021.3069265
[33]	S. S. Feng, G. Cong, A. Khan, X. Li, Y. Liu, Y. M. Chee, Inf2vec: Latent representation model for social influence embedding, in Proceedings of the 34th IEEE International Conference on Data Engineering, (2018), 941–952, https://doi.org/10.1109/ICDE.2018.00089
[34]	Y. Y. Liu, J. R. Gao, Z. F. Zhao, H. Wu, Z. Yue, J. Li, Evolving interest for information diffusion prediction on social network, in Proceedings of the 25th International Conference on Advanced Communication Technology, IEEE, (2023), 130–136. https://doi.org/10.23919/ICACT56868.2023.10079436
[35]	Y. Wu, H. Huang, H. Jin, Information diffusion prediction with personalized graph neural networks, in Proceedings of the 13th International Conference on Knowledge Science, (2020), 376–387. https://doi.org/10.1007/978-3-030-55393-7_34
[36]	C. Yang, H. Wang, J. Tang, C. Shi, M. Sun, G. Cui, et al., Full-scale information diffusion prediction with reinforced recurrent networks, IEEE Trans. Neural Networks Learn. Syst., 34 (2023), 2271–2283. https://doi.org/10.1109/TNNLS.2021.3106156 doi: 10.1109/TNNLS.2021.3106156
[37]	N. Du, Y. Y. Liang, M. Balcan, L. Song, Influence function learning in information diffusion networks, in Proceedings of the 31st International Conference on Machine Learning, (2014), 2016–2024.
[38]	J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, Z. Ghahramani, Kronecker graphs: An approach to modeling networks, J. Mach. Learn. Res., 3 (2010), 985–1042.

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)