淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0708201910524700
中文論文名稱 基於學習方法的動態網路預測
英文論文名稱 A Learning-based Dynamic Social Network Prediction
校院名稱 淡江大學
系所名稱(中) 資訊工程學系全英語碩士班
系所名稱(英) Master’s Program, Department of Computer Science and Information Engineering (English-taught program
學年度 107
學期 2
出版年 108
研究生中文姓名 陳瑄莉
研究生英文姓名 Hsuan-Li Chen
學號 606780053
學位類別 碩士
語文別 英文
口試日期 2019-07-17
論文頁數 40頁
口試委員 指導教授-王英宏
委員-陳以錚
委員-惠霖
中文關鍵字 動態網路  動態網路連結預測  自動編碼器  長短期記憶 
英文關鍵字 Dynamic Network  Dynamic Network Link Prediction  Autoencoder  Long Short-Term Memory(LSTM) 
學科別分類 學科別應用科學資訊工程
中文摘要 如今,在虛擬世界中,人與人之間的關係已然形成一種網路社會,從而形成了「社群網絡」。
為了將網路作為圖形處理並考慮其時間特性,我們設置時間點作為固定間隔,並將一系列快照劃分為「動態社群網絡」,以觀察節點的連結趨勢並預測哪些節點將出現或消失在圖中。 此過程稱為「動態網路連結預測」(Dynamic Network Link Prediction ,DNLP),這意味著我們可以根據其歷史行為來推斷將與目標用戶建立關係的特定人群。動態網路連結預測也可以應用於各個領域,並且由於其高靈活性,也非常適合與其他深度學習方法相結合。 我們提出了一種新的基於學習的模型,Enc-LSTM,用於動態網路的連結預測,並處理長期預測任務,以捕獲序列之間的向量相關性,並將它們映射至低維度以適應不同規模的網絡。 同時,它也具有更穩健的能力來預測將在下一個網路圖中將出現或消失的連結。
英文摘要 Nowadays, online society as the relationship between the person and others in the virtual world, so as to make the "social network". To deal with the network as the graph and considered its time characteristic, we set the fixed interval, timestamp, to divide a sequence of snapshots as the "dynamic social network", that can observe the link trend of nodes and predict which node will appear or disappear in the graph. This process called "dynamic network link prediction (DNLP)" which means we can infer the particular people who will make a relationship with the target user based on their historical behaviors. The dynamic network link prediction can also apply to various areas and has quite suitable to combine with other deep learning methods due to their high flexibility. We proposed a novel learning-based model, Enc-LSTM, to do the link prediction of dynamic social networks and deal with the long-term prediction tasks for capture the relevance of vectors between the sequences and maps them into low- dimension to suit the different scales network. At the same time, it also has a more robust ability to predict the links that are going to appear or disappear in the next network graphs.
論文目次 Table of Contents
Chinese Abstract I
Abstract III
Table of Contents IV
List of Figures VI
List of Tables VII

Chapter 1 Introduction 1
Chapter 2 Related Work 4
2.1 Static Network Link Prediction 4
2.2 Dynamic Network Link Prediction 5
2.3 Autoencoder 6
2.4 Long Short Term Memory (LSTM) 6
Chapter 3 Preliminaries 7
3.1 Problem Description 7
3.1.1 Dynamic Social Network 7
3.1.2 Compression Problem 8
3.1.3 Prediction Problem 8
3.2 Models Description 9
3.2.1 Autoencoder 9
3.2.2 LSTM 12
Chapter 4 Methodology 14
4.1 Framework 14
4.2 Autoencoder Application 17
4.2.1 Vector Embedding 17
4.2.2 Compression 18
4.3 LSTM Application 19
Chapter 5 Experiments Result 22
5.1 Datasets 22
5.2 Comparing Method 23
5.3 Evaluation Metrics 27
5.4 Experiment Result 29
5.5 Parameter Sensitivity 33
Chapter 6 Conclusion 36
Reference 37


List of Figures
Figure 1: An Illustration of Network Evolution 2
Figure 2: Autoencoder Architecture 10
Figure 3: Loss Calculation of Autoencoder 10
Figure 4: Basic Structure of LSTM 12
Figure 5: Schema of Proposed Method 14
Figure 6: Different Num. of Generated Snapshots 34
Figure 7: Different Num. of Units Setting in Same Datasets 35


List of Tables
Table 1: Terms and Notations in the Proposed Method
19
Table 2: Terms and Notations in LSTM 20
Table 3: Virtual Datasets Generated from Synfix 23
Table 4: The Units on the Encoder Processing of Enc-LSTM
27
Table 5: Accuracy of Methods on Dataset with 128 users
30
Table 6: Accuracy of Methods on Dataset with 200 users
30
Table 7: The Result on Dataset with 128 users and 50000 epochs 31
Table 8: The Result on Dataset with 200 users and 50000 epochs 31
Table 9: The Result on Dataset with 128 users and 55000 epochs 32
Table 10: The Result on Dataset with 200 users and 55000 epochs 32


參考文獻 [1] Nahla Mohamed Ahmed, Ling Chen, “An efficient algorithm for link prediction in temporal uncertain social networks” Information Sciences, 331:120–136, 2016.
[2] N. M. Ahmed, L. Chen, Y. Wang, B. Li, Y. Li, and W. Liu, “Sampling-based algorithm for link prediction in temporal networks,” Information Sciences, vol. 374, pp. 1–14, 2016.
[3] L. Backstrom, J. Leskovec, “Supervised Random Walks: Predicting and Recommending Links in Social Networks” in WSDM, 2011
[4] Pierre Baldi, I. Guyon, G. Dror, V. Lemaire, G. Taylor and D. Silver, “Autoencoders, Unsupervised Learning, and Deep Architectures” JMLR: Workshop and Conference Proceedings 27:37-50, 2012
[5] Jinyin Chen, Jian Zhang, Xuanheng Xu, Chengbo Fu, Dan Zhang, Qingpeng Zhang, and Qi Xuan. E-lstm-d: A deep learning framework for dynamic network link prediction. arXiv preprint arXiv:1902.08329, 2019.
[6] Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:1406.1078, 2014
[7] Rahul Dey, Fathi M. Salemt, “Gate-variants of Gated Recurent Unit (GRU) neural networks”, 2017 IEEE 60th International Midwest Symposium on Circuits and Systems (MWSCAS)
[8] Felix A. Gers, Jürgen Schmidhuber, and Fred Cummins, “Learning to Forget: Continual Prediction with LSTM”, In Artificial Neural Networks, 1999. ICANN 99. Ninth International Conference on (Conf. Publ. No. 470), volume 2, pages 850-855, 1999.
[9] Klaus Greff, Rupesh K. Srivastava, Jan Koutn ́ık, Bas R. Steunebrink, Jurgen Schmidhuber, “LSTM: A Search Space Odyssey”, TRANSACTIONS on NEURAL NETWORKS and LEARNING SYSTEMS, 2017
[10] Aditya Grover, Jure Leskovec, “Node2vec: Scalable Feature Learning for Networks”, in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016, pp.855-864.
[11] N. M. A. Ibrahim and L. Chen, “Link prediction in dynamic social networks by integrating different types of information,” Applied Intelligence, vol. 42, no. 4, pp. 738–750, 2015.
[12] D. Kempe, J. M. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network”, In KDD, 2003
[13] X. Li, N. Du, H. Li, K. Li, J. Gao, and A. Zhang, “A deep learning approach to link prediction in dynamic networks,” in Proceedings of the 2014 SIAM International Conference on Data Mining. SIAM, 2014, pp. 289–297.
[14] Sheng Li, Jaya Kawale, Yun Fu, “Deep Collaborative Filtering via Marginalized Denoising Autoencoder”, ACM, 2015
[15] Xiaopeng Li, James She, “Relational Variational Autoencoder for Link Prediction with Multimedia Data”, Thematic Workshops’ 17, Oct. 23-27, 2017, Mountain View, CA, USA
[16] T. Li, J. Zhang, S. Y. Philip, Y. Zhang, and Y. Yan, “Deep dynamic network embedding for link prediction,” IEEE Access, 2018.


[17] David Liben-Nowell, Jon Kleinberg, “The link-prediction problem for social networks”, Journal of the American Society for Information Science and Technology banner
[18] Siddharth Pal, Yuxiao Dong, Bishal Thapa, nitesh V. Chawla, Ananthram Swami, Ram Ramanathan, “Deep Learning for Network Analysis: Problems, Approaches and Challenges”, Milcom Track 5 – Selected Topics in Communications, 2016
[19] B. Perozzi, R. A1-Rfou, and S. Skiena, “DeepWalk: Online Learning of Social Representations”, I in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014, pp. 701-710.
[20] Rudy Raymond, Hisashi Kashima, “Fast and Scalable Algorithms for Semi-supervised Link Prediction on Static and Dynamic Graphs”, ECML PKDD 2010: Machine Learning and Knowledge Discovery in Databases pp 131-147
[21] Phi Vu Tran, “Learning to Make Predictions on Graphs with Autoencoders”, 2018 IEEE 5th International Conference on Data Science and Advanced Analytics
[22] D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016, pp. 1225–1234.
[23] Wenchao Yu, Wei Cheng, Charu C. Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang, “NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks”, KDD2018, August 19-23, 2018, London Kingdom
[24] L. Yao, L. Wang, L. Pan, and K. Yao, “Link prediction based on common-neighbors for dynamic social network,” Procedia Computer Science, vol.83, pp.82–89, 2016
[25] Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg, Aram Galstyan, “Scalable Temporal Latent Space Inference for Link Prediction in Dynamic Social Networks”, IEEE Transactions on Knowledge and Data Engineering, Vol. 28, No.10, October 2016
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2019-08-14公開。
  • 同意授權瀏覽/列印電子全文服務,於2019-08-14起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信