簡易檢索 / 詳目顯示

回結果列表
研究生： 李修齊
Li, Shiou-Chi
論文名稱： 節點刪除後的多類型動態社群網路高效重建
Efficient Reconstruction of Dynamic Social Networks After Node Deletion Across Multiple Network Types
指導教授： 黃仁暐
Huang, Jen-Wei
學位類別： 博士
Doctor
系所名稱： 電機資訊學院 - 電腦與通信工程研究所
Institute of Computer & Communication Engineering
論文出版年： 2026
畢業學年度： 114
語文別： 英文
論文頁數： 125
中文關鍵詞： 動態社群網路重建 、替代點選擇 、最短路徑理論 、資訊傳遞 、動態社群網路分析
外文關鍵詞： Dynamic social network reconstruction, Substitution node selection, Shortest path theorems, Information diffusion, Dynamic social network analysi
相關次數： 點閱：5  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 近年來，隨著社群網路的快速發展，相關的社群網路分析已成為資料探勘領域中的重要研究主題。多數既有研究主要針對靜態社群網路進行分析；但在實際情境中，社群網路通常具備動態特性，其結構會隨時間不斷演變。為因應此特性，研究者逐漸將焦點轉向各式動態社群網路分析問題。本研究聚焦於其中一項核心議題：社群網路重建。當網路中的節點因故消失時，我們希望能從現有節點中選擇一個最適合的替代節點，並允許其新增少量邊，以重建原先的網路結構，使結構相似度或資訊傳遞能力的損失降至最低。過往研究多以中心度指標(Centrality)衡量節點的重要性，進而選擇替代節點；或使用圖核心（graph kernel）評估重建後之網路與原網路的相似度，以尋找最佳替代節點。然而，這些方法普遍面臨計算成本高、運算時間過長的問題。為更有效率地解決社群網路重建問題，本研究提出多種適用於不同類型社群網路的演算法，這些方法皆基於最短路徑推導理論或資訊傳遞模型，以更快速地定位最佳替代節點。實驗結果顯示，在各類社群網路上，本研究所提出的演算法無論在運算時間或重建品質方面，均大幅優於先前相關研究，展現本研究方法在動態社群網路重建上的卓越效能。

    In recent years, social networks have become a prominent research topic in the fields of data mining, with numerous studies addressing various problems in social network analysis. However, most existing research focuses on static social networks, where the network topology remains unchanged. In contrast, in the real world, the topology of social networks evolves over time. To address this issue, several studies have investigated dynamic social network analysis. In this work, we focus on the dynamic social network reconstruction problem, which aims to preserve the network topology and prevent information loss after a node is deleted. Specifically, researchers attempt to identify substitute nodes for the deleted nodes and allow a limited number of newly added edges to achieve this goal. Previous works in this area primarily rely on centrality measures or graph kernel–based methods to select the best substitute nodes, which are often computationally expensive. To address this limitation, we propose several efficient algorithms based on shortest-path theorems and the concept of information diffusion, applicable to various types of social networks, including undirected, directed, weighted, and labeled networks. Experimental results demonstrate that the proposed methods outperform existing approaches in both execution time and reconstruction performance.

    中文摘要 ii Abstract iii Acknowledgment iv Table of Contents v List of Tables x List of Figures xii 1 Introduction 1 1.1 Background on Social Network Analysis 1 1.2 Dynamic Social Networks and Incremental Analysis 2 1.3 Dynamic Network Reconstruction after Node Deletion 2 1.4 Practical Applications of Dynamic Network Reconstruction 3 1.5 Related Work and Limitations 5 1.6 Overview of the Proposed Reconstruction Frameworks 5 1.7 Distinction between Network Reconstruction and Machine Unlearning 8 1.8 Organization of This Thesis 9 2 Related Works 10 2.1 Researches Related to Dynamic Social Networks 10 2.1.1 Dynamic Influence Maximization 10 2.1.2 Betweenness Centrality Updates in Dynamic Networks 11 2.1.3 Dynamic Update Techniques for Closeness Centrality 12 2.1.4 Representation Learning in Dynamic Social Networks 12 2.2 Dynamic Social Network Reconstruction 13 2.3 Dynamic Team Formation 15 2.4 Summary of Related Works 15 3 Reconstructing Undirected Social Networks 16 3.1 Overview 16 3.2 Definitions 17 3.2.1 Problem Definition 17 3.3 Local Structure Properties 18 3.4 Proposed Methods 19 3.4.1 The Strategy for Selecting the Substitute Node 19 3.4.2 CLOMADE (Choosing LOcal MAximum DEgree) 24 3.5 Computational Hardness of the Undirected Social Network Reconstruction Problem 25 3.6 Experimental Results 25 3.6.1 Experiment Settings 25 3.6.2 Illustrative Example for Comparing Reconstruction Performance 29 3.6.3 The Results on Different Sparse Networks 31 3.6.4 The Results on Different Medium-Density Networks 35 3.6.5 The Results on Different Dense Networks 37 3.6.6 Analysis 39 4 Reconstructing Directed Social Networks 40 4.1 Overview 40 4.2 Problem Formulation and Reduction 40 4.2.1 Definitions 40 4.2.2 Propositions and Lemmas 45 4.2.3 Theorems 49 4.3 Computational Hardness of the Directed Social Network Reconstruction Problem 50 4.4 Methodology 51 4.4.1 Overview 51 4.4.2 Finding Information Loss 52 4.4.3 Identifying the Best Connected Node 52 4.4.4 Overall Algorithm 53 4.5 Experiments 54 4.5.1 Experiment Settings 54 4.5.2 Performance of Loss After Reconstruction 57 4.5.3 Performance of Single Deletion on Random Graphs 58 4.5.4 Performance of Continuous Deletion of Random Graphs 61 4.5.5 Performance of Large Synthetic Graphs 65 4.5.6 Performance of Real-world Networks 68 4.6 Proofs of the Problem Reductions 70 4.6.1 Proof of Proposition 1 70 4.6.2 Proof of Lemma 6 70 4.6.3 Proof of Lemma 7 71 4.6.4 Proof of Lemma 8 72 5 Reconstructing Weighted Social Networks 73 5.1 Theorems Related to Shortest Paths 73 5.1.1 Definitions 73 5.1.2 Theorems of Shortest Paths 74 5.2 Methodology 75 5.2.1 Overview 75 5.2.2 Loss Estimation 76 5.2.3 Best Substitution Node Selection 77 5.2.4 Social Network Reconstructing via the Substitute Node 79 5.3 Computational Hardness of the Weighted Social Network Reconstruction Problem 79 5.4 Experiments 81 5.4.1 Datasets 81 5.4.2 Evaluation Metrics 82 5.4.3 Experimental Environments 82 5.4.4 Compared Methods 82 5.4.5 Results 82 6 Reconstructing Labeled Social Networks 84 6.1 Basic Definitions and Problem Formulation 84 6.2 Affected Nodes Determination 85 6.3 Substitute Node Finding 87 6.4 Network Reconstruction 88 6.5 Computational Hardness of the Labeled Social Network Reconstruction Problem 88 6.6 Experimental Results 92 6.6.1 Datasets 92 6.6.2 Evaluation Metrics 93 6.6.3 Compared Methods 94 6.6.4 Experimental Environments 94 6.6.5 Experimental Results on Random Deletion 94 6.6.6 Experimental Results on the Most Critical Deletion 95 7 Conclusions 100 8 Future Works 101 8.1 Integrating Dynamic Network Reconstruction with Machine Learning and Deep Learning 101 8.2 Modeling Different Relationship Types for Reconstructed Edges 101 8.3 Dynamic Reconstruction with Reversible Node Deletion 102 References 103

    [1] Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida. Fast exact shortest-path distance queries on large networks by pruned landmark labeling. In Proceedings of the 2013 ACM International Conference on Management of Data, pages 349–360, 2013.
    [2] Miriam Baglioni, Filippo Geraci, Marco Pellegrini, and Ernesto Lastres. Fast exact computation of betweenness centrality in social networks. In Proceedings of the 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pages 450– 456, 2012.
    [3] Christian Borgs, Michael Brautbar, Jennifer T. Chayes, and Brendan Lucier. Maximizing social influence in nearly optimal time. In Chandra Chekuri, editor, Proceedings of the 25th Annual Symposium on Discrete Algorithms, 2014, Portland, Oregon, USA, 2014, pages 946–957. SIAM, 2014.
    [4] Ulrik Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25:163–177, 2001.
    [5] Fu-Kai Chang, Shiou-Chi Li, and Jen-Wei Huang. Efficient influence maximization in signed networks with positive influence increasing and negative influence decreasing simultaneously via edge-view influence estimation. In Aijun An, Alfredo Cuzzocrea, and Hongxin Hu, editors, Social Networks Analysis and Mining, pages 142—-150, Cham, 2026. Springer Nature Switzerland.
    [6] Mostafa Haghir Chehreghani. An efficient algorithm for approximate betweenness centrality computation. The Computer Journal, 57:1371–1382, 2014.
    [7] Yuan-Chang Chen, Hao-Shang Ma, and Jen-Wei Huang. Multi-state open opinion model based on positive and negative social influences. In Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM 2015, Paris, France, August 25 28, 2015, pages 170–177, 2015.
    [8] V. Chvatal. A greedy heuristic for the set-covering problem. Math. Oper. Res., 4(3):233– 235, August 1979. 103
    [9] Zeyu Cui, Zekun Li, Shu Wu, Xiaoyu Zhang, Qiang Liu, Liang Wang, and Mengmeng Ai. Dygcn: Efficient dynamic graph embedding with graph convolutional network. IEEE Trans. Neural Networks Learn. Syst., 35(4):4635–4646, 2024.
    [10] Kempe David, Kleinberg Jon, and Tardos ´Eva. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’03, pages 137–146, New York, NY, USA, 2003. ACM.
    [11] Linton C. Freeman. Centrality in social networks conceptual clarification. Social Networks, 1(3):215 – 239, 1978.
    [12] Keshav Goel, Rishi Ranjan Singh, Sudarshan Iyengar, and Sukrit Gupta. A faster algorithm to update betweenness centrality after node alteration. Internet Math., 11(4-5):403– 420, 2015.
    [13] David Goldberg, David Nichols, Brian M. Oki, and Douglas Terry. Using collaborative filtering to weave an information tapestry. Commun. ACM, 35(12):61–70, December 1992.
    [14] Amit Goyal, Wei Lu, and Laks V.S. Lakshmanan. Celf++: Optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference Companion on World Wide Web, WWW ’11, pages 47–48, New York, NY, USA, 2011. Association for Computing Machinery.
    [15] Oded Green, Robert McColl, and David A. Bader. A fast algorithm for streaming betweenness centrality. In 2012 International Conference on Privacy, Security, Risk and Trust and 2012 International Confernece on Social Computing, pages 11–20, 2012.
    [16] Daniel Gruhl, Guha R., Liben-Nowell David, and Tomkins Andrew. Information diffusion through blogspace. In Proceedings of the 13th International Conference on World Wide Web, WWW ’04, pages 491–501, New York, NY, USA, 2004. ACM.
    [17] R. Chulaka Gunasekara, Kishan Mehrotra, and Chilukuri K. Mohan. Multi-objective restructuring in social networks. In Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM ’13, pages 277–281, New York, NY, USA, 2013. Association for Computing Machinery. 104
    [18] Chengbin Hou, Han Zhang, Shan He, and Ke Tang. Glodyne: Global topology preserving dynamic network embedding. IEEE Trans. Knowl. Data Eng., 34(10):4826–4837, 2022.
    [19] Jen-Wei Huang, Hao-Shang Ma, Chih-Chin Chung, and Zhi-Jia Jian. Unknown but interesting recommendation using social penetration. Soft Computing, 23(16):7249–7262, 2019.
    [20] Goldenberg Jacob, Libai Barak, and Muller Eitan. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing Letters, 12(3):211—-223, Aug 2001.
    [21] Ruoming Jin, Ning Ruan, Yang Xiang, and Victor Lee. A highway-centric labeling approach for answering distance queries on large sparse graphs. In Proceedings of the 2012 ACM International Conference on Management of Data, pages 445–456, 2012.
    [22] Paul W. Olsen Jr., Alan G. Labouseur, and Jeong-Hyon Hwang. Efficient top-k closeness centrality search. In IEEE 30th International Conference on Data Engineering, pages 196–207, 2014.
    [23] Wang-Cheng Kang and Julian McAuley. Self-Attentive Sequential Recommendation . In 2018 IEEE International Conference on Data Mining (ICDM), pages 197–206, Los Alamitos, CA, USA, November 2018. IEEE Computer Society.
    [24] Mehdi Kargar, Aijun An, and Morteza Zihayat. Efficient bi-objective team formation in social networks. In Peter A. Flach, Tijl De Bie, and Nello Cristianini, editors, Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2012. Proceedings, Part II, volume 7524 of Lecture Notes in Computer Science, pages 483–498, 2012.
    [25] Miray Kas, Kathleen M. Carley, and L. Richard Carley. Incremental closeness centrality for dynamically changing social networks. In Jon G. Rokne and Christos Faloutsos, editors, Advances in Social Networks Analysis and Mining 2013, ASONAM ’13, Niagara, ON, Canada August 25 29, 2013, pages 1250–1258. ACM, 2013.
    [26] Miray Kas, Matthew Wachs, Kathleen M. Carley, and L. Richard Carley. Incremental algorithm for updating betweenness centrality in dynamically growing networks. In Jon G. 105 Rokne and Christos Faloutsos, editors, Advances in Social Networks Analysis and Mining 2013, ASONAM ’13, Niagara, ON, Canada August 25 29, 2013, pages 33–40. ACM, 2013.
    [27] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30–37, 2009.
    [28] Srijan Kumar, Bryan Hooi, Disha Makhija, Mohit Kumar, Christos Faloutsos, and VS Subrahmanian. Rev2: Fraudulent user prediction in rating platforms. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 333–341. ACM, 2018.
    [29] Srijan Kumar, Francesca Spezzano, VS Subrahmanian, and Christos Faloutsos. Edge weight prediction in weighted signed networks. In Data Mining (ICDM), 2016 IEEE 16th International Conference on, pages 221–230. IEEE, 2016.
    [30] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms. Physical Review E, 78:046110, 2008.
    [31] Min-Joong Lee, Jungmin Lee, Jaimie Yejean Park, Ryan Hyun Choi, and Chin-Wan Chung. QUBE: a quick algorithm for updating betweenness centrality. In Alain Mille, Fabien Gandon, Jacques Misselis, Michael Rabinovich, and Steffen Staab, editors, Proceedings of the 21st World Wide Web Conference 2012, WWW 2012, Lyon, France, April 16-20, 2012, pages 351–360. ACM, 2012.
    [32] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne M. VanBriesen, and Natalie S. Glance. Cost-effective outbreak detection in networks. In Pavel Berkhin, Rich Caruana, and Xindong Wu, editors, Proceedings of the 13th ACM International Conference on Knowledge Discovery and Data Mining, San Jose, California, USA, 2007, pages 420–429. ACM, 2007.
    [33] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.
    [34] Cheng-Te Li and Man-Kwan Shan. Team formation for generalized tasks in expertise social networks. In Ahmed K. Elmagarmid and Divyakant Agrawal, editors, Proceedings 106 of the 2010 IEEE Second International Conference on Social Computing, SocialCom / IEEE International Conference on Privacy, Security, Risk and Trust, pages 9–16, 2010.
    [35] Chung-Lun Li, S.Thomas McCormick, and David Simchi-Levi. On the minimumcardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Operations Research Letters, 11(5):303–308, 1992.
    [36] Liangyue Li, Hanghang Tong, Nan Cao, Kate Ehrlich, Yu-Ru Lin, and Norbou Buchler. Replacing the irreplaceable: Fast algorithms for team member recommendation. In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, pages 636–646, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee.
    [37] Liangyue Li, Hanghang Tong, Nan Cao, Kate Ehrlich, Yu-Ru Lin, and Norbou Buchler. Enhancing team composition in professional networks: Problem definitions and fast solutions. IEEE Trans. Knowl. Data Eng., 29(3):613–626, 2017.
    [38] Shiou-Chi Li and Jen-Wei Huang. Let the information fly: Reconstructing social network after a node deleted. IEEE Transactions on Knowledge and Data Engineering, 36(3):1198– 1209, 2024.
    [39] Shiou-Chi Li and Jen-Wei Huang. Reconstructing weighted social networks after a node deleted with substitute node selection. In 2025 IEEE Symposium on Computational Intelligence in Natural Language Processing and Social Media (CI-NLPSoMe Companion), pages 1–5, 2025.
    [40] Shiou-Chi Li and Jen-Wei Huang. Substitute node selection for reconstructing labeled social networks after a node is deleted. In The 24th IEEE/WIC International Conference on Web Intelligence and Intelligent Agent Technology, 2025.
    [41] Shiou-Chi Li, Yu-Hao Ke, Fa-Yuan Liu, and Jen-Wei Huang. Reconstructing dynamic social network by choosing local maximum degree substitute. In IEEE/ACM International Conference on Social Network Analysis and Mining, pages 1604–1605, 2015.
    [42] Fa-Yuan Liu, Shiou-Chi Li, and Jen-Wei Huang. Forming a team of cost-effective and wellcollaborated experts in social networks based on hierarchical skill model. In Proceedings of 107 the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM ’21, pages 134–137, New York, NY, USA, 2022. Association for Computing Machinery.
    [43] Xiaodong Liu, Xiangke Liao, Shanshan Li, Si Zheng, Bin Lin, Jingying Zhang, Lisong Shao, Chenlin Huang, and Liquan Xiao. On the shoulders of giants: Incremental influence maximization in evolving social networks. Complex., 2017:5049836:1–5049836:14, 2017.
    [44] Karp Richard M. Reducibility among Combinatorial Problems, pages 85—-103. Springer US, Boston, MA, 1972.
    [45] Hao Ma, Haixuan Yang, Michael R. Lyu, and Irwin King. Mining social networks using heat diffusion processes for marketing candidates selection. In Proceedings of the 17th ACM Conference on Information and Knowledge Management, CIKM ’08, pages 233–242, New York, NY, USA, 2008. ACM.
    [46] Rokia Missaoui, Elsa Negre, Dyah Anggraini, and Jean Vaillancourt. Network restructuring after a node removal. International Journal of Web Engineering and Technology, 2009.
    [47] Elsa Negre, Rokia Missaoui, and Jean Vaillancourt. Predicting a social network structure once a node is deleted. In International Conference on Advances in Social Networks Analysis and Mining, pages 297–304, 2011.
    [48] Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. Dynamic influence analysis in evolving networks. Proc. VLDB Endow., 9(12):1077–1088, 2016.
    [49] K. (Lynn) Putman, Hanjo D. Boekhout, and Frank W. Takes. Fast incremental computation of harmonic closeness centrality in directed weighted networks. In Francesca Spezzano, Wei Chen, and Xiaokui Xiao, editors, ASONAM ’19: International Conference on Advances in Social Networks Analysis and Mining, Vancouver, British Columbia, Canada, 27-30 August, 2019, pages 1018–1025. ACM, 2019.
    [50] Idrissa Sarr and Rokia Missaoui. Managing node disappearance based on information flow in social networks. In IEEE/ACM International Conference on Social Network Analysis and Mining, 2012. 108
    [51] Paulo Shakarian, Abhinav Bhatnagar, Ashkan Aleali, Elham Shaabani, and Ruocheng Guo. The Independent Cascade and Linear Threshold Models, pages 35—-48. Springer International Publishing, Cham, 2015.
    [52] Zhenzhen Shao, Na Guo, Yu Gu, Zhigang Wang, Fangfang Li, and Ge Yu. Efficient closeness centrality computation for dynamic graphs. In Yunmook Nah, Bin Cui, SangWon Lee, Jeffrey Xu Yu, Yang-Sae Moon, and Steven Euijong Whang, editors, Database Systems for Advanced Applications 25th International Conference, DASFAA 2020, Jeju, South Korea, September 24-27, 2020, Proceedings, Part II, volume 12113 of Lecture Notes in Computer Science, pages 534–550. Springer, 2020.
    [53] Guojie Song, Yuanhao Li, Xiaodong Chen, Xinran He, and Jie Tang. Influential node tracking on dynamic social network: An interchange greedy approach. IEEE Trans. Knowl. Data Eng., 29(2):359–372, 2017.
    [54] Fei Sun, Jun Liu, Jian Wu, Changhua Pei, Xiao Lin, Wenwu Ou, and Peng Jiang. Bert4rec: Sequential recommendation with bidirectional encoder representations from transformer. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management, CIKM ’19, pages 1441–1450, New York, NY, USA, 2019. Association for Computing Machinery.
    [55] Lappas Theodoros, Liu Kun, and Terzi Evimaria. Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 467–476, 2009.
    [56] Fang Wei. Tedi: Efficient shortest path query answering on graphs. In Proceedings of the 2010 ACM International Conference on Management of Data, pages 99–110, 2010.
    [57] Wan-Jhen Wu, Shiou-Chi Li, and Jen-Wei Huang. Isgp: Influence maximization on dynamic social networks using influence subgraph propagation. In 2023 IEEE 10th International Conference on Data Science and Advanced Analytics (DSAA), pages 1–10, 2023.
    [58] Vijaya Krishna Yalavarthi and Arijit Khan. Steering top-k influencers in dynamic graphs via local updates. In IEEE International Conference on Big Data, 2018, Seattle, WA, USA, 2018, pages 576–583. IEEE, 2018. 109
    [59] Pei-Yi Yeh, Shiou-Chi Li, Hao-Shang Ma, and Jen-Wei Huang. Greedy-based precise expansion algorithm for customized group team formation problem. In 2022 International Conference on Technologies and Applications of Artificial Intelligence (TAAI), pages 119– 124, 2022.
    [60] Chia-Chen Yen, Mi-Yen Yeh, and Ming-Syan Chen. An efficient approach to updating closeness centrality and average path length in dynamic networks. In IEEE 13th International Conference on Data Mining (ICDM), pages 867–876, 2013.
    [61] Yuichi Yoshida. Almost linear-time algorithms for adaptive betweenness centrality using hypergraph sketches. In Proceedings of the 20th ACM International Conference on Knowledge Discovery and Data Mining, pages 1416–1425, 2014.
    [62] Aakas Zhiyuli, Xun Liang, YanFang Chen, and Xiaoyong Du. Modeling large-scale dynamic social networks via node embeddings. IEEE Trans. Knowl. Data Eng., 31(10):1994–2007, 2019. 110

    QR CODE