Incremental graph computation: Anchored Vertex Tracking in Dynamic Social Networks

Article

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
Article Title

Incremental graph computation: Anchored Vertex Tracking in Dynamic Social Networks

ERA Journal ID17876
Article CategoryArticle
AuthorsCai, Taotao, Yang, Shuiqiao, Li, Jianxin, Sheng, Quan Z., Yang, Jian, Wang, Xin, Zhang, Wei Emma and Gao, Longxiang
Journal TitleIEEE Transactions on Knowledge and Data Engineering
Journal Citation35 (7), pp. 7030-7044
Number of Pages15
Year2023
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.2022.3199494
Web Address (URL)https://ieeexplore.ieee.org/document/9860051
AbstractUser engagement has recently received significant attention in understanding the decay and expansion of communities in many online social networking platforms. When a user chooses to leave a social networking platform, it may cause a cascading dropping out among her friends. In many scenarios, it would be a good idea to persuade critical users to stay active in the network and prevent such a cascade because critical users can have significant influence on user engagement of the whole network. Many user engagement studies have been conducted to find a set of critical (anchored) users in the static social network. However, social networks are highly dynamic and their structures are continuously evolving. In order to fully utilize the power of anchored users in evolving networks, existing studies have to mine multiple sets of anchored users at different times, which incurs an expensive computational cost. To better understand user engagement in evolving network, we target a new research problem called Anchored Vertex Tracking (AVT) in this article, aiming to track the anchored users at each timestamp of evolving networks. Nonetheless, it is nontrivial to handle the AVT problem which we have proved to be NP-hard. To address the challenge, we develop a greedy algorithm inspired by the previous anchored k-core study in the static networks. Furthermore, we design an incremental algorithm to efficiently solve the AVT problem by utilizing the smoothness of the network structure’s evolution. The extensive experiments conducted on real and synthetic datasets demonstrate the performance of our proposed algorithms and the effectiveness in solving the AVT problem.
KeywordsAnchored vertex tracking; user engagement; dynamic social networks; k-core computation
Related Output
Is supplemented byhttps://dataportal.arc.gov.au/NCGP/Web/Grant/Grant/DP200102298
Is supplemented byhttps://dataportal.arc.gov.au/NCGP/Web/Grant/Grant/LP180100750
Contains Sensitive ContentDoes not contain sensitive content
ANZSRC Field of Research 2020460501. Data engineering and data science
Public NotesFiles associated with this item cannot be displayed due to copyright restrictions.
Byline AffiliationsMacquarie University
University of New South Wales
Deakin University
Tianjin University, China
University of Adelaide
Qilu University of Technology, China
Permalink -

https://research.usq.edu.au/item/z6030/incremental-graph-computation-anchored-vertex-tracking-in-dynamic-social-networks

Log in to edit
  • 58
    total views
  • 0
    total downloads
  • 3
    views this month
  • 0
    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
From wide to deep: dimension lifting network for parameter-efficient knowledge graph embedding
Cai, Borui, Xiang, Yong, Gao, Longxiang, Wu, Di, Zhang, He, Jin, Jiong and Luan, Tom. 2024. "From wide to deep: dimension lifting network for parameter-efficient knowledge graph embedding." IEEE Transactions on Knowledge and Data Engineering. 36 (12), pp. 8341-8348. https://doi.org/10.1109/TKDE.2024.3437479
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
EXVUL: Towards Effective and Explainable Vulnerability Detection for IoT Devices
Cao, Sicong, Sun, Xiaobing, Liu, Wei, Wu, Di, Zhang, Jiale, Li, Yan, Luan, Tom H. and Gao, Longxiang. 2024. "EXVUL: Towards Effective and Explainable Vulnerability Detection for IoT Devices." IEEE Internet of Things Journal. 11 (12), pp. 22385-22398. https://doi.org/10.1109/JIOT.2024.3381641
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. 36 (10), pp. 5153-5167. https://doi.org/10.1109/TKDE.2024.3382726
Reconnecting the Estranged Relationships: Optimizing the Influence Propagation in Evolving Networks
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
Adaptive Regularization and Resilient Estimation in Federated Learning
Uddin, Md Palash, Xiang, Yong, Zhao, Yao, Ali, Mumtaz, Zhang, Yushu and Gao, Longxiang. 2024. "Adaptive Regularization and Resilient Estimation in Federated Learning." IEEE Transactions on Services Computing. 17 (4), pp. 1369-1381. https://doi.org/10.1109/TSC.2023.3332703
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
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
Coupled online sequential extreme learning machine model with ant colony optimization algorithm for wheat yield prediction
Ali, Mumtaz, Deo, Ravinesh C., Xiang, Yong, Prasad, Ramendra, Li, Jianxin, Farooque, Aitazaz and Yaseen, Zaher Mundher. 2022. "Coupled online sequential extreme learning machine model with ant colony optimization algorithm for wheat yield prediction." Scientific Reports. 12 (1), pp. 1-23. https://doi.org/10.1038/s41598-022-09482-5
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
A Blockchain-based Multi-layer Decentralized Framework for Robust Federated Learning
Wu, Di, Wang, Nai, Zhang, Jiale, Zhang, Yuan, Xiang, Yong and Gao, Longxiang. 2022. "A Blockchain-based Multi-layer Decentralized Framework for Robust Federated Learning." 2022 International Joint Conference on Neural Networks (IJCNN). Padua, Italy 18 - 23 Jul 2022 IEEE (Institute of Electrical and Electronics Engineers). https://doi.org/10.1109/IJCNN55064.2022.9892039
Self-supervised cross-iterative clustering for unlabeled plant disease images
Fang, Uno, Li, J., Lu, X., Gao, Longxiang, Ali, Mumtaz and Xiang, Yong. 2021. "Self-supervised cross-iterative clustering for unlabeled plant disease images." Neurocomputing. 456, pp. 36-48. https://doi.org/10.1016/j.neucom.2021.05.066
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.