簡易檢索 / 詳目顯示

研究生: 吳漢陽
Hang-Yang Wu
論文名稱: 基於生成對抗網路之圖形稀疏化
Graph Sparsification with Generative Adversarial Networks
指導教授: 陳怡伶
Yi-Ling Chen
口試委員: 陳冠宇
Guan-Yu Chen
戴碧如
Bi-Ru Dai
學位類別: 碩士
Master
系所名稱: 電資學院 - 資訊工程系
Department of Computer Science and Information Engineering
論文出版年: 2020
畢業學年度: 108
語文別: 英文
論文頁數: 30
中文關鍵詞: 深度學習社群網路分析圖形稀疏化
外文關鍵詞: deep learning, social network analysis, graph sparsification
相關次數: 點閱:270下載:0
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

  • Abstract in Chinese . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Abstract in English . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Graph Sparsification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.1 Preserving network properties . . . . . . . . . . . . . . . . . . . 6 2.1.2 Application-based sparsifiers . . . . . . . . . . . . . . . . . . . . 7 2.2 Network Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 Training . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 Reward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 Assembling Social Network . . . . . . . . . . . . . . . . . . . . . . . . 16 4 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Evaluation Metrics and Baselines . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3.1 Comparison with baselines . . . . . . . . . . . . . . . . . . . . . 23 4.3.2 Analysis of artificial edges . . . . . . . . . . . . . . . . . . . . . 26 4.3.3 Ablation test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3.4 Time reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.3.5 Graph visualization . . . . . . . . . . . . . . . . . . . . . . . . . 28 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

    [1] Sorour E Amiri Bijaya Adhikari Aditya and Bharadwaj B Aditya Prakash. Netgist: Learning to generate
    task-based network summaries.
    [2] Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein gan. arXiv preprint arXiv:
    1701.07875, 2017.
    [3] Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding
    of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10):
    P10008, 2008.
    [4] Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. Netgan: Generating
    graphs via random walks. arXiv preprint arXiv:1803.00816, 2018.
    [5] Yi-Ling Chen, Ming-Syan Chen, and S Yu Philip. Ensemble of diverse sparsifications for link prediction
    in large-scale networks. In 2015 IEEE International Conference on Data Mining, pages 51–60.
    IEEE, 2015.
    [6] Aaron Clauset, Mark EJ Newman, and Cristopher Moore. Finding community structure in very large
    networks. Physical review E, 70(6):066111, 2004.
    [7] Gennaro Cordasco and Luisa Gargano. Community detection via semi-synchronous label propagation
    algorithms. In 2010 IEEE International Workshop on: Business Applications of Social Network
    Analysis (BASNA), pages 1–8. IEEE, 2010.
    [8] Peter Dayan and Bernard W Balleine. Reward, motivation, and reinforcement learning. Neuron, 36
    (2):285–298, 2002.
    [9] Wai-Shing Fung, Ramesh Hariharan, Nicholas JA Harvey, and Debmalya Panigrahi. A general framework
    for graph sparsification. SIAM Journal on Computing, 48(4):1196–1223, 2019.
    [10] Aristides Gionis, Polina Rozenshtein, Nikolaj Tatti, and Evimaria Terzi. Community-aware network
    sparsification. In Proceedings of the 2017 SIAM International Conference on Data Mining, pages
    426–434. SIAM, 2017.
    [11] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair,
    Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information
    processing systems, pages 2672–2680, 2014.
    [12] Michael Hamann, Gerd Lindner, Henning Meyerhenke, Christian L Staudt, and Dorothea Wagner.
    Structure-preserving sparsification methods for social networks. Social Network Analysis and Mining,
    6(1):22, 2016.
    [13] Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1):193–218,
    1985.
    [14] Emmanuel John and Ilya Safro. Single-and multi-level network sparsification by algebraic distance.
    Journal of Complex Networks, 5(3):352–388, 2016.
    [15] Jure Leskovec and Julian J Mcauley. Learning to discover social circles in ego networks. In Advances
    in neural information processing systems, pages 539–547, 2012.
    [16] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking
    diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1):2, 2007.
    [17] Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen. Sparsification
    of influence networks. In Proceedings of the 17th ACM SIGKDD international conference
    on Knowledge discovery and data mining, pages 529–537. ACM, 2011.
    [18] Tomáš Mikolov, Martin Karafiát, Lukáš Burget, Jan Cernocky, and Sanjeev Khudanpur. Recurrent
    neural network based language model. In Eleventh annual conference of the international speech
    communication association, 2010.
    [19] Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparsek-connected
    spanning subgraph of ak-connected graph. Algorithmica, 7(1-6):583–596, 1992.
    [20] David Peleg and Alejandro A Schäffer. Graph spanners. Journal of graph theory, 13(1):99–116, 1989.
    [21] Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep
    convolutional generative adversarial networks. arXiv preprint arXiv:1511.06434, 2015.
    [22] Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering.
    In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data,
    pages 721–732. ACM, 2011.
    [23] Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal
    on Computing, 40(6):1913–1926, 2011.
    [24] Martin Sundermeyer, Ralf Schlüter, and Hermann Ney. Lstm neural networks for language modeling.
    In Thirteenth annual conference of the international speech communication association, 2012.
    [25] Sahar Tavakoli, Alireza Hajibagheri, and Gita Sukthankar. Learning social graph topologies using
    generative adversarial neural networks. In International Conference on Social Computing, Behavioral-
    Cultural Modeling ? Prediction, 2017.
    [26] Petrie Wong, Cliz Sun, Eric Lo, Man Lung Yiu, Xiaowei Wu, Zhichao Zhao, T-H Hubert Chan, and
    Ben Kao. Finding k most influential edges on flow graphs. Information Systems, 65:93–105, 2017.
    [27] Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on groundtruth.
    Knowledge and Information Systems, 42(1):181–213, 2015.
    [28] Fang Zhou, Sebastien Malher, and Hannu Toivonen. Network simplification with minimal loss of
    connectivity. In 2010 IEEE international conference on data mining, pages 659–668. IEEE, 2010.
    [29] Fang Zhou, Sébastien Mahler, and Hannu Toivonen. Simplification of networks by edge pruning. In
    Bisociative Knowledge Discovery, pages 179–198. Springer, 2012.

    無法下載圖示 全文公開日期 2025/06/16 (校內網路)
    全文公開日期 2025/06/16 (校外網路)
    全文公開日期 2025/06/16 (國家圖書館:臺灣博碩士論文系統)
    QR CODE