Reducing Cumulative Errors of Incremental CP Decomposition in Dynamic Online Social Networks
Article No.: 42, Pages 1 - 33
Abstract
CANDECOMP/PARAFAC (CP) decomposition is widely used in various online social network (OSN) applications. However, it is inefficient when dealing with massive and incremental data. Some incremental CP decomposition (ICP) methods have been proposed to improve the efficiency and process evolving data, by updating decomposition results according to the newly added data. The ICP methods are efficient, but inaccurate because of serious error accumulation caused by approximation in the incremental updating. To promote the wide use of ICP, we strive to reduce its cumulative errors while keeping high efficiency. We first differentiate all possible errors in ICP into two types: the cumulative reconstruction error and the prediction error. Next, we formulate two optimization problems for reducing the two errors. Then, we propose several restarting strategies to address the two problems. Finally, we test the effectiveness in three typical dynamic OSN applications. To the best of our knowledge, this is the first work on reducing the cumulative errors of the ICP methods in dynamic OSNs.
References
[1]
2018. Behance.net social network. Retrieved from http://www.behance.net/.
[2]
Evrim Acar, Daniel M. Dunlavy, and Tamara G. Kolda. 2009. Link prediction on evolving data using matrix and tensor factorizations. In Proceedings of the 2009 IEEE International Conference on Data Mining Workshops. IEEE, 262–269.
[3]
Mohammad Al Hasan and Mohammed J. Zaki. 2011. A survey of link prediction in social networks. In Social Network Data Analytics. Springer, 243–275.
[4]
Peng Bao, Hua-Wei Shen, Junming Huang, and Xue Qi Cheng. 2013. Popularity prediction in microblogging network: A case study on sina weibo. In Proceedings of the 22nd International Conference on World Wide Web. ACM, 177–178.
[5]
Qi Cao, Huawei Shen, Hao Gao, Jinhua Gao, and Xueqi Cheng. 2017. Predicting the popularity of online content with group-specific models. Communications of the ACM 53, 8 (2017), 80–88.
[6]
Chen Chen and Hanghang Tong. 2015. Fast eigen-functions tracking on dynamic graphs. In Proceedings of the 2015 SIAM International Conference on Data Mining.
[7]
Yunqi Dong and Wenjun Jiang. 2019. Brand purchase prediction based on time-evolving user behaviors in e-commerce. Concurrency and Computation: Practice and Experience 31, 1 (2019), e4882.
[8]
Daniel M. Dunlavy, Tamara G. Kolda, and Evrim Acar. 2011. Temporal link prediction using matrix and tensor factorizations. ACM Trans Knowledge Discovery from Data 5, 2 (2011), 1–27.
[9]
Ye Yuan, Guy-Bart Stan, Sean Warnick, and Jorge Goncalves. 2011. Robust dynamical network structure reconstruction. Automatica 47, 6 (2011), 1230--1235
[10]
Ziwei Zhang, Peng Cui, Jian Pei, XiaoWang, and Wenwu Zhu. 2018. TIMERS: Error-bounded SVD restart on dynamic networks. Proceedings of the 32nd AAAI Conference on Artificial Intelligence 32, 1 (2018), 224--231.
[11]
Sheng Gao, Ludovic Denoyer, and Patrick Gallinari. 2011. Link pattern prediction with tensor decomposition in multi-relational networks. In Proceedings of the 2011 IEEE Symposium on Computational Intelligence and Data Mining. IEEE, 333–340.
[12]
Sheng Gao, Ludovic Denoyer, and Patrick Gallinari. 2011. Temporal link prediction by integrating content and structure information. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management. ACM, 1169–1174.
[13]
Xiaofeng Gao, Zhenhao Cao, Sha Li, Bin Yao, Guihai Chen, and Shaojie Tang. 2019. Taxonomy and evaluation for microblog popularity prediction. ACM Transactions on Knowledge Discovery from Data 13, 2 (2019), 15.
[14]
Hancheng Ge, James Caverlee, and Haokai Lu. 2016. TAPER: A contextual tensor-based approach for personalized expert recommendation. In Proceedings of the 10th ACM Conference on Recommender Systems. ACM, 261–268.
[15]
Lars Grasedyck, Daniel Kressner, and Christine Tobler. 2013. A literature survey of low-rank tensor approximation techniques. GAMM-Mitteilungen 36, 1 (2013), 53–78.
[16]
Ekta Gujral, Ravdeep Pasricha, and Evangelos E. Papalexakis. 2018. Sambaten: Sampling-based batch incremental tensor decomposition. In Proceedings of the 2018 SIAM International Conference on Data Mining. SIAM, 387–395.
[17]
Johan Håstad. 1990. Tensor rank is NP-complete. Journal of Algorithms 11, 4 (1990), 644–654.
[18]
Laurent Hébert-Dufresne, Joshua A. Grochow, and Antoine Allard. 2016. Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition. Scientific Reports 6, 1 (2016), 1--9.
[19]
Minh X. Hoang, Xuan-Hong Dang, Xiang Wu, Zhenyu Yan, and Ambuj K. Singh. 2017. GPOP: Scalable group-level popularity prediction for online content in social networks. In Proceedings of the 26th International Conference on World Wide Web. 725–733.
[20]
Chunli Huang, Wenjun Jiang, Jie Wu, and Guojun Wang. 2020. Personalized review recommendation based on users’ aspect sentiment. ACM Transactions on Internet Technology 20, 4 (2020), 1--26.
[21]
Junming Huang, Chao Li, Wen-Qiang Wang, Hua-Wei Shen, Guojie Li, and Xue-Qi Cheng. 2014. Temporal scaling in information propagation. Scientific Reports 4, 1 (2014), 1--6.
[22]
Wenjun Jiang, Guojun Wang, Md Zakirul Alam Bhuiyan, and Jie Wu. 2016. Understanding graph-based trust evaluation in online social networks: Methodologies and challenges. ACM Computing Surveys 49, 1 (May 2016), 10:1--10:35.
[23]
W. Jiang, J. Wu, G. Wang, and H. Zheng. 2016. Forming opinions via trusted friends: Time-evolving rating prediction using fluid dynamics. IEEE Transactions on Computers 65, 4 (2016), 1211–1224.
[24]
George Karypis and Vipin Kumar. 1998. Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed computing 48, 1 (1998), 96–129.
[25]
Tamara G. Kolda and Brett W. Bader. 2009. Tensor decompositions and applications. SIAM Review 51, 3 (2009), 455–500.
[26]
Jérôme Kunegis and Andreas Lommatzsch. 2009. Learning spectral graph transformations for link prediction. In Proceedings of the 26th Annual International Conference on Machine Learning.
[27]
Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a social network or a news media?. In Proceedings of the 19th International Conference on World Wide Web. ACM, 591–600.
[28]
Kristina Lerman and Tad Hogg. 2010. Using a model of social dynamics to predict popularity of news. In Proceedings of the 19th International Conference on World Wide Web.
[29]
Norman Levinson. 1946. The Wiener (root mean square) error criterion in filter design and prediction. Journal of Mathematics and Physics 25, 1–4 (1946), 261–278.
[30]
Shiou-Chi Li, Yu-Hao Ke, Fa-Yuan Liu, and Jen-Wei Huang. 2015. Reconstructing dynamic social network by choosing local maximum degree substitute. In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. ACM, 1604–1605.
[31]
Jin Xiaojie Zhang Luming Xu Xianghua Yan Shuicheng Li Ping, Feng Jiashi. 2017. Online robust low-rank tensor learning ping. In Proceedings of the 26th International Joint Conference on Artificial Intelligence. 2180–2186.
[32]
David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology 58, 7 (2007), 1019–1031.
[33]
Linyuan Lü and Tao Zhou. 2011. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and Its Applications 390, 6 (2011), 1150–1170.
[34]
Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. 2017. A survey of link prediction in complex networks. ACM Computing Surveys 49, 4 (2017), 69.
[35]
Aditya Krishna Menon and Charles Elkan. 2011. Link prediction via matrix factorization. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 437–452.
[36]
Elisa Mussumeci and Flávio Codeço Coelho. 2018. Reconstructing news spread networks and studying its dynamics. Social Network Analysis and Mining 8, 1 (2018), 6.
[37]
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. 2016. Asymmetric transitivity preserving graph embedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1105–1114.
[38]
Evangelos E. Papalexakis, Christos Faloutsos, and Nicholas D. Sidiropoulos. 2017. Tensors for data mining and data fusion: Models, applications, and scalable algorithms. ACM Transactions on Intelligent Systems and Technology 8, 2 (2017), 16.
[39]
Ashwin Paranjape, Austin R. Benson, and Jure Leskovec. 2017. Motifs in temporal networks. In Proceedings of the 10th ACM International Conference on Web Search and Data Mining. ACM.
[40]
Tiago P. Peixoto. 2019. Network reconstruction and community detection from dynamics. Physical Review Letters 123, 12 (2019), 128301.
[41]
Henrique Pinto, Jussara M. Almeida, and Marcos A. Gonçalves. 2013. Using early view patterns to predict the popularity of Youtube videos. In Proceedings of the 2013 ACM International Conference on Web Search and Data Mining. ACM, 365–374.
[42]
Justin Ruths and Derek Ruths. 2014. Control profiles of complex networks. Science 343, 6177 (2014), 1373–1376.
[43]
Nigel Swain. 2010. Patterns and dynamics of users’ behavior and interaction: Network analysis of an online community.Journal of the Association for Information Science and Technology 60, 5 (2010), 911–932.
[44]
Gabor Szabo and B. A. Huberman. 2010. Predicting the popularity of online content. Communications of the ACM 53, 8 (2010), 80--88.
[45]
Alexandru Tatar, Panayotis Antoniadis, Marcelo Dias De Amorim, and Serge Fdida. 2014. From popularity prediction to ranking online news. Social Network Analysis and Mining 4, 1 (2014), 174.
[46]
Alexandru Tatar, Marcelo Dias De Amorim, Serge Fdida, and Panayotis Antoniadis. 2014. A survey on predicting the popularity of web content. Journal of Internet Services and Applications 5, 1 (2014), 8.
[47]
Alexandru Tatar, Jérémie Leguay, Panayotis Antoniadis, Arnaud Limbourg, Marcelo Dias de Amorim, and Serge Fdida. 2011. Predicting the popularity of online articles based on user comments. In Proceedings of the International Conference on Web Intelligence, Mining and Semantics. ACM, 67.
[48]
Chao Wang, V. Satuluri, and S. Parthasarathy. 2007. Local probabilistic models for link prediction. In Proceedings of the 7th IEEE International Conference on Data Mining.
[49]
Feng Wang, Jinhua She, Yasuhiro Ohyama, Wenjun Jiang, Geyong Min, Guojun Wang, and Min Wu. 2021. Maximizing positive influence in competitive social networks: A trust-based solution. Information Sciences 546 (2021), 559–572.
[50]
Jingjing Wang, Wenjun Jiang, and Guojun Wang. 2021. Incremental group-level popularity prediction in online social networks. Work in Progress (2021).
[51]
Peng Wang, BaoWen Xu, YuRong Wu, and XiaoYu Zhou. 2015. Link prediction in social networks: The state-of-the-art. Science China Information Sciences 58, 1 (2015), 1–38.
[52]
Xian Wu, Baoxu Shi, Yuxiao Dong, Chao Huang, and Nitesh V. Chawla. 2019. Neural tensor factorization for temporal interaction learning. In Proceedings of the 12th ACM International Conference on Web Search and Data Mining. ACM, 537–545.
[53]
Peike Xia, Wenjun Jiang, Jie Wu, Surong Xiao, and Guojun Wang. 2020. Exploiting temporal dynamics in product reviews for dynamic sentiment prediction at the aspect level. ACM Transactions on Knowledge Discovery from Data 1, 1, Article 1 (2021), 27 pages. https://doi.org/10.1145/3441451
[54]
Jie Xu, Mihaela Van Der Schaar, Jiangchuan Liu, and Haitao Li. 2015. Forecasting popularity of videos using social media. IEEE Journal of Selected Topics in Signal Processing 9, 2 (2015), 330–343.
[55]
Jie Xu, Mihaela Van Der Schaar, Jiangchuan Liu, and Haitao Li. 2015. Timely video popularity forecasting based on social networks. In Proceedings of the 2015 IEEE Conference on Computer Communications. IEEE, 2308–2316.
[56]
Jaewon Yang and Jure Leskovec. 2011. Patterns of temporal variation in online media. In Proceedings of the 4th ACM International Conference on Web Search and Data Mining. ACM, 177–186.
[57]
Enoch Yeung, Jongmin Kim, Jorge Gonçalves, and Richard M. Murray. 2015. Global network identification from reconstructed dynamical structure subnetworks: Applications to biochemical reaction networks. In Proceedings of the 2015 54th IEEE Conference on Decision and Control. IEEE.
[58]
Jifeng Zhang, Wenjun Jiang, Jinrui Zhang, Jie Wu, and Guojun Wang. 2021. Exploring weather data to predict activity attendance in event-based social network: From the organizer’s view. ACM Transactions on the Web 1, 1, Article 1 (2021), 25 pages. https://doi.org/10.1145/3440134
[59]
Shuo Zhou, S. Erfani, and J. Bailey. 2018. Online CP Decomposition for Sparse Tensors. In Proceedings of the 2018 IEEE International Conference on Data Mining. IEEE Computer Society.
[60]
Shuo Zhou, Nguyen Xuan Vinh, James Bailey, Yunzhe Jia, and Ian Davidson. 2016. Accelerating online CP decompositions for higher order tensors. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1375–1384.
[61]
Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg, and Aram Galstyan. 2016. Scalable temporal latent space inference for link prediction in dynamic social networks. IEEE Transactions on Knowledge and Data Engineering 28, 10 (2016), 2765–2777.
Index Terms
- Reducing Cumulative Errors of Incremental CP Decomposition in Dynamic Online Social Networks
Recommendations
Incremental CP Tensor Decomposition by Alternating Minimization Method
In practical applications, incremental tensors are very common: only a portion of tensor data is available, and new data are arriving in the next time step or continuously over time. To handle this type of tensors time-saving algorithms are required for ...
Incremental Group-Level Popularity Prediction in Online Social Networks
Predicting the popularity of web contents in online social networks is essential for many applications. However, existing works are usually under non-incremental settings. In other words, they have to rebuild models from scratch when new data occurs, ...
Reducing Soft Errors through Operand Width Aware Policies
Soft errors are an important challenge in contemporary microprocessors. Particle hits on the components of a processor are expected to create an increasing number of transient errors with each new microprocessor generation. In this paper, we propose ...
Comments
Information & Contributors
Information
Published In
Copyright © 2021 Association for Computing Machinery.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 April 2021
Accepted: 01 December 2020
Revised: 01 November 2020
Received: 01 October 2019
Published in TKDD Volume 15, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Funding Sources
- NSFC
- Guangdong Provincial NSF
- Open Project of Zhejiang Lab
- China Scholarships Council
- Science and Technology Program of Changsha City
- NSF
- National Outstanding Youth Science Program of NSFC
- NSFC
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 327Total Downloads
- Downloads (Last 12 months)148
- Downloads (Last 6 weeks)20
Reflects downloads up to 09 Jan 2025
Other Metrics
Citations
Cited By
View allView Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatLogin options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in