Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks

Article


Cai, Taotao, Lei, Qi, Sheng, Quan Z., Cui, Ningning, Yang, Shuiqiao, Yang, Jian, Zhang, Wei Emma and Mahmood, Adnan. 2024. "Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks." IEEE Transactions on Knowledge and Data Engineering. 36 (5), pp. 2151-2165. https://doi.org/10.1109/TKDE.2023.3316268
Article Title

Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks

ERA Journal ID17876
Article CategoryArticle
AuthorsCai, Taotao, Lei, Qi, Sheng, Quan Z., Cui, Ningning, Yang, Shuiqiao, Yang, Jian, Zhang, Wei Emma and Mahmood, Adnan
Journal TitleIEEE Transactions on Knowledge and Data Engineering
Journal Citation36 (5), pp. 2151-2165
Number of Pages15
Year2024
PublisherIEEE (Institute of Electrical and Electronics Engineers)
Place of PublicationUnited States
ISSN1041-4347
1558-2191
Digital Object Identifier (DOI)https://doi.org/10.1109/TKDE.2023.3316268
Web Address (URL)https://ieeexplore.ieee.org/abstract/document/10254336
Abstract

Influence Maximization (IM), which aims to select a set of users from a social network to maximize the expected number of influenced users, has recently received significant attention for mass communication and commercial marketing. Existing research efforts dedicated to the IM problem depend on a strong assumption: the selected seed users are willing to spread the information after receiving benefits from a company or organization. In reality, however, some seed users may be reluctant to spread the information or need to be paid higher to be motivated. Furthermore, the existing IM works pay little attention to capture users’ influence propagation in the future period. In this paper, we target a new research problem named, Reconnecting Top-l Relationships (RT l R) query, which aims to find l number of previous existing relationships but being estranged later such that reconnecting these relationships will maximize the expected number of influenced users by the given group in a future period. We prove that the RT l R problem is NP-hard. An efficient greedy algorithm is proposed to answer the RT l R queries with the influence estimation technique and the well-chosen link prediction method to predict the near future network structure. We also design a pruning method to reduce unnecessary probing from candidate edges. Further, a carefully designed order-based algorithm is proposed to accelerate the RT l R queries. Finally, we conduct extensive experiments on real-world datasets to demonstrate the effectiveness and efficiency of our proposed methods.

KeywordsEvolving networks; graph query; influence maximization; link prediction
Contains Sensitive ContentDoes not contain sensitive content
ANZSRC Field of Research 2020460502. Data mining and knowledge discovery
460299. Artificial intelligence not elsewhere classified
Public Notes

The accessible file is the accepted version of the paper. Please refer to the URL for the published version.

Byline AffiliationsUniversity of Southern Queensland
Chang'an University, China
Macquarie University
Anhui University, China
Commonwealth Scientific and Industrial Research Organisation (CSIRO), Australia
University of Adelaide
Permalink -

https://research.usq.edu.au/item/z4xx6/reconnecting-the-estranged-relationships-optimizing-the-influence-propagation-in-evolving-networks

Download files


Accepted Version
2205.05236.pdf
File access level: Anyone

  • 41
    total views
  • 24
    total downloads
  • 5
    views this month
  • 2
    downloads this month

Export as

Related outputs

A Survey on Truth Discovery: Concepts, Methods, Applications, and Opportunities
Wang, Shuang, Zhang, He, Sheng, Quan Z., Li, Xiaoping, Sun, Zhu, Cai, Taotao, Zhang, Wei Emma, Yang, Jian and Gao, Qing. 2024. "A Survey on Truth Discovery: Concepts, Methods, Applications, and Opportunities." IEEE Transactions on Big Data. https://doi.org/10.1109/TBDATA.2024.3423677
ECS-STPM: An Efficient Model for Tunnel Fire Anomaly Detection
Song, Huansheng, Wen, Ya, Song, Xiangyu, Sun, ShiJie, Cai, Taotao and Li, Jianxin. 2024. "ECS-STPM: An Efficient Model for Tunnel Fire Anomaly Detection." 7th International Joint Conference on Asia-Pacific Web and Web-Age Information Management (APWeb-WAIM 2023). Wuhan, China 06 - 08 Oct 2023 Singapore . Springer. https://doi.org/10.1007/978-981-97-2421-5_19
MDCGA-Net: Multi-Scale Direction Context-Aware Network with Global Attention for Building Extraction from Remote Sensing Images
Niu, Penghui, Gu, Junhua, Zhang, Yajuan, Zhang, Ping, Cai, Taotao, Xu, Wenjia and Han, Jungong. 2024. "MDCGA-Net: Multi-Scale Direction Context-Aware Network with Global Attention for Building Extraction from Remote Sensing Images." IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing. 17, pp. 8461-8476. https://doi.org/10.1109/JSTARS.2024.3387969
YOLO-SA: An Efficient Object Detection Model Based on Self-attention Mechanism
Li, Ang, Song, Xiangyu, Sun, ShiJie, Zhang, Zhaoyang, Cai, Taotao and Song, Huansheng. 2024. "YOLO-SA: An Efficient Object Detection Model Based on Self-attention Mechanism." 7th International Joint Conference on Asia-Pacific Web and Web-Age Information Management (APWeb-WAIM 2023). Wuhan, China 06 - 08 Oct 2023 Singapore. Springer. https://doi.org/10.1007/978-981-97-2421-5_1
Special issue on link prediction in complex networks
Sheng, Michael, Cai, Taotao and Mahmood, Adnan. 2024. "Special issue on link prediction in complex networks." Computing. 106 (7), pp. 2079-2079. https://doi.org/10.1007/s00607-024-01298-7
Optimal Treatment Strategies for Critical Patients with Deep Reinforcement Learning
Job, Simi, Tao, Xiaohui, Li, Lin, Xie, Haoran, Cai, Taotao, Yong, Jianming and Li, Qing. 2024. "Optimal Treatment Strategies for Critical Patients with Deep Reinforcement Learning ." ACM Transactions on Intelligent Systems and Technology. 15 (2), pp. 1-22. https://doi.org/10.1145/3643856
Robust equivalent circuit model parameters identification scheme for State of Charge (SOC) estimation based on maximum correntropy criterion
Zhang, Kexin, Zhao, Xuezhuan, Chen, Yu, Wu, Di, Cai, Taotao, Wang, Yi, Li, Lingling and Zhang, Ji. 2024. "Robust equivalent circuit model parameters identification scheme for State of Charge (SOC) estimation based on maximum correntropy criterion." International Journal of Electrochemical Science. 19 (5). https://doi.org/10.1016/j.ijoes.2024.100558
FRAMU: Attention-based Machine Unlearning using Federated Reinforcement Learning
Shaik, Thanveer, Tao, Xiaohui, Li, Lin, Xie, Haoran, Cai, Taotao, Zhu, Xiaofeng and Li, Qing. 2024. "FRAMU: Attention-based Machine Unlearning using Federated Reinforcement Learning ." IEEE Transactions on Knowledge and Data Engineering. https://doi.org/10.1109/TKDE.2024.3382726
Dynamic Correlation Adjacency Matrix Based Graph Neural Network for Traffic Flow Prediction
Gu, Junhua, Jia, Zhihao, Cai, Taotao, Song, Xiangyu and Mahmood, Adnan. 2023. "Dynamic Correlation Adjacency Matrix Based Graph Neural Network for Traffic Flow Prediction." Sensors. 23 (6). https://doi.org/10.3390/s23062897
Top-k socio-spatial co-engaged location selection for social users
Hasan Haldar, Nur Al, Li, Jianxin, Ali, Mohammed Eunus, Cai, Taotao, Chen, Yunliang, Sellis, Timos and Reynolds, Mark. 2023. "Top-k socio-spatial co-engaged location selection for social users." IEEE Transactions on Knowledge and Data Engineering. 35 (5), pp. 5325-5340. https://doi.org/10.1109/TKDE.2022.3151095
Towards Multi-User, Secure, and Verifiable kNN Query in Cloud Database
Cui, Ningning, Qian, Kang, Cai, Taotao, Li, Jianxin, Yang, Xiaochun, Cui, Jie and Zhong, Hong. 2023. "Towards Multi-User, Secure, and Verifiable kNN Query in Cloud Database." IEEE Transactions on Knowledge and Data Engineering. 35 (9), pp. 9333-9349. https://doi.org/10.1109/TKDE.2023.3237879
Incremental graph computation: Anchored Vertex Tracking in Dynamic Social Networks
Cai, Taotao, Yang, Shuiqiao, Li, Jianxin, Sheng, Quan Z., Yang, Jian, Wang, Xin, Zhang, Wei Emma and Gao, Longxiang. 2023. "Incremental graph computation: Anchored Vertex Tracking in Dynamic Social Networks." IEEE Transactions on Knowledge and Data Engineering. 35 (7), pp. 7030-7044. https://doi.org/10.1109/TKDE.2022.3199494
Robust cross-network node classification via constrained graph mutual information
Yang, Shuiqiao, Cai, Borui, Cai, Taotao, Song, Xiangyu, Jiang, Jiaojiao, Li, Bing and Li, Jianxin. 2022. "Robust cross-network node classification via constrained graph mutual information." Knowledge-Based Systems. 257. https://doi.org/10.1016/j.knosys.2022.109852
A survey on deep learning based knowledge tracing
Song, Xiangyu, Li, Jianxin, Cai, Taotao, Yang, Shuiqiao, Yang, Tingting and Liu, Chengfei. 2022. "A survey on deep learning based knowledge tracing." Knowledge-Based Systems. 258. https://doi.org/10.1016/j.knosys.2022.110036
Target-Aware Holistic Influence Maximization in Spatial Social Networks
Cai, Taotao, Li, Jianxin, Mian, Ajmal, Li, Rong-Hua, Sellis, Timos and Yu, Jeffrey Xu. 2022. "Target-Aware Holistic Influence Maximization in Spatial Social Networks ." IEEE Transactions on Knowledge and Data Engineering. 34 (4), pp. 1993-2007. https://doi.org/10.1109/TKDE.2020.3003047
Community-diversity Driven Influence Maximization on Social Networks
Li, Jianxin, Cai, Taotao, Ke, Deng, Wang, Xinjue, Sellis, Timos and Xia, Feng. 2020. "Community-diversity Driven Influence Maximization on Social Networks." Information Systems. 92. https://doi.org/10.1016/j.is.2020.101522
Anchor vertex selection for enhanced reliability of traffic offloading service in edge-enabled mobile P2P social networks
Zhang, Hengda, Wang, Xiaofei, Fan, Hao, Cai, Taotao, Li, Jianxin, Li, Xiuhua and Leung, Victor C. M.. 2020. "Anchor vertex selection for enhanced reliability of traffic offloading service in edge-enabled mobile P2P social networks." Journal of Communications and Information Networks. 5 (2), pp. 217-224. https://doi.org/10.23919/JCIN.2020.9130437
Anchored Vertex Exploration for Community Engagement in Social Networks
Cai, Taotao, Li, Jianxin, Hasan Haldar, Nur Al, Mian, Ajmal, Yearwood, John and Sellis, Timos. 2020. "Anchored Vertex Exploration for Community Engagement in Social Networks ." 2020 IEEE 36th International Conference on Data Engineering (ICDE). Dallas, United States 20 - 24 Apr 2020 United States. IEEE (Institute of Electrical and Electronics Engineers). https://doi.org/10.1109/ICDE48307.2020.00042
Correlate Influential News Article Events to Stock Quote Movement
Mandalapu, Arun Chaitanya, Gunabalan, Saranya, Sadineni, Avinash, Cai, Taotao, Hasan, Nur Al Hasan and Li, Jianxin. 2019. "Correlate Influential News Article Events to Stock Quote Movement ." Li, Jianxin, Wang, Sen, Qin, Shaowen, Li, Xue and Wang, Shuliang (ed.) 15th International Conference on Advanced Data Mining and Applications. Dalian, China 21 - 23 Nov 2019 Switzerland. Springer. https://doi.org/10.1007/978-3-030-35231-8_24
Holistic Influence Maximization for Targeted Advertisements in Spatial Social Networks
Li, Jianxin, Cai, Taotao, Mian, Ajmal, Li, Rong-Hua, Sellis, Timos and Yu, Jeffrey Xu. 2018. "Holistic Influence Maximization for Targeted Advertisements in Spatial Social Networks ." 2018 IEEE 34th International Conference on Data Engineering (ICDE). Paris, France 16 - 19 Apr 2018 United States. IEEE (Institute of Electrical and Electronics Engineers). https://doi.org/10.1109/ICDE.2018.00145
Efficient Distance-based Representative Skyline Computation in 2D Space
Mao, Rui, Cai, Taotao, Li, Rong-Hua, Yu, Jeffery Xu and Li, Jianxin. 2017. "Efficient Distance-based Representative Skyline Computation in 2D Space." World Wide Web. 20 (4), pp. 621-638. https://doi.org/10.1007/s11280-016-0406-0
Efficient Algorithms for Scheduling XML Data in a Mobile Wireless Broadcast Environment
Qin, Yongrui, Wang, Hua, Zhang, Ji, Tao, Xiaohui, Zhang, Wei Emma, Taylor, Kerry and Sheng, Quan Z.. 2015. "Efficient Algorithms for Scheduling XML Data in a Mobile Wireless Broadcast Environment." 21st IEEE International Conference on Parallel and Distributed Systems (ICPADS 2015). Melbourne, Australia 14 - 17 Dec 2015 Australia. https://doi.org/10.1109/ICPADS.2015.96
Efficient Algorithms for Distance-Based Representative Skyline Computation in 2D Space
Cai, Taotao, Li, Rong-Hua, Yu, Jeffrey Xu, Mao, Rui and Cai, Yadi. 2015. "Efficient Algorithms for Distance-Based Representative Skyline Computation in 2D Space ." 17th Asia-Pacific Web Conference (APWeb2015). Guangzhou, China 18 - 20 Sep 2015 Switzerland . Springer. https://doi.org/10.1007/978-3-319-25255-1_10
Effectively delivering XML information in periodic broadcast environments
Qin, Yongrui, Sheng, Quan Z. and Wang, Hua. 2013. "Effectively delivering XML information in periodic broadcast environments ." Decker, Hendrik, Lhotska, Lenka, Link, Sebastian, Basl, Josef and Tjoa, A. Min (ed.) 24th International Conference on Database and Expert Systems Applications (DEXA 2013). Prague, Czech Republic 26 - 29 Aug 2013 Berlin, Germany. https://doi.org/10.1007/978-3-642-40285-2_16
Effectively delivering XML information in periodic broadcast environments
Qin, Yongrui, Sheng, Quan Z. and Wang, Hua. 2012. Effectively delivering XML information in periodic broadcast environments. Adelaide, Australia. University of Adelaide.