請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91326
標題: | 去中心化圖探勘 Decentralized Graph Mining |
作者: | 蕭郁澄 Yu-Cheng Hsiao |
指導教授: | 王奕翔 I-Hsiang Wang |
關鍵字: | 譜圖分析,去中心化,冪迭代方法,流言演算法,社群偵測, Spectral graph analysis,Decentralization,Power method,Gossip algorithm,Community detection, |
出版年 : | 2023 |
學位: | 碩士 |
摘要: | 譜圖分析是圖數據挖掘的基礎任務。當圖表示一個大規模網絡時,可以通過節點之間的協作來實現這一任務的去中心化執行。然而,現有的去中心化方法通常以批量的方式執行,換句話說,需要預先確定圖矩陣的特徵對數量,然後一次性計算它們,這導致每次迭代的通訊成本很高。此外,現有的去中心化方法缺乏按順序計算特徵對的靈活性,因此並不利於某些任務,例如,估計圖隱含的社群數量。為了解決這些問題,本文提出了一種替代的去中心化譜圖分析方法,它允許所有節點按順序計算對稱圖矩陣的主要特徵對。通過一系列數值評估,我們有效地展示了所提方法的實用性和效率。此外,我們還建立了個別特徵向量估計的非漸進保證,證明了所提方法能達到與集中式方法相同的理論極限。此外,我們將所提方法與去中心化的K-means 演算法結合,以解決更廣泛的社群偵測問題。數值結果顯示,當流言演算法的迭代次數足夠大時,去中心化演算法得到的準確率近似於集中式方法。最後,我們強調,理論分析去中心化K-means 演算法仍然存在一個根本上的挑戰,而這是一個有趣的研究方向。 Spectral graph analysis is a fundamental task in graph data mining. When the graph represents a large-scale network of agents, it is tempting for them to conduct the task collectively in a decentralized manner. However, existing decentralized methods are executed in batches, that is, one needs to fix the number of eigenpairs of the graph matrix a priori and compute them all together, resulting in high per-iteration communication cost. Moreover, lacking the flexibility to sequentially compute the eigenpairs is not favorable in tasks such as determining the number of communities in community detection. To address these issues, an alternative approach of decentralized spectral graph analysis is proposed in this paper, and it facilitates all agents to sequentially compute the leading eigenpairs for symmetric graph matrices. Through a series of numerical evaluations, the practicality and efficiency of the proposed method is demonstrated. Non-asymptotic guarantees for individual eigenvector estimations are also established, which proves that the proposed approach achieves the same fundamental limits as the centralized method. Moreover, the proposed approach is integrated with a decentralized K-means algorithm to address community detection problems in a decentralized manner. Numerical evaluations show that the clustering accuracy is equivalent to the centralized counterpart as the number of gossip iterations is sufficiently large. Ultimately, we highlight that there remains a fundamental challenge in theoretically analyzing decentralized K-means algorithms, which is an intriguing research direction. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91326 |
DOI: | 10.6342/NTU202300918 |
全文授權: | 同意授權(限校園內公開) |
顯示於系所單位: | 電信工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-112-1.pdf 目前未授權公開取用 | 1.49 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。