請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91326完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 王奕翔 | zh_TW |
| dc.contributor.advisor | I-Hsiang Wang | en |
| dc.contributor.author | 蕭郁澄 | zh_TW |
| dc.contributor.author | Yu-Cheng Hsiao | en |
| dc.date.accessioned | 2023-12-20T16:30:16Z | - |
| dc.date.available | 2023-12-21 | - |
| dc.date.copyright | 2023-12-20 | - |
| dc.date.issued | 2023 | - |
| dc.date.submitted | 2023-12-08 | - |
| dc.identifier.citation | [1] Daniel A Spielman. Spectral graph theory and its applications. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 29–38. IEEE, 2007.
[2] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808–828, 2018. [3] Phillip Bonacich. Some unique properties of eigenvector centrality. Social networks, 29(4):555–564, 2007. [4] Jiashun Jin. Fast community detection by score. The Annals of Statistics, 43(1):57–89, 2015. [5] David Kempe and Frank McSherry. A decentralized algorithm for spectral analysis. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 561–568, 2004. [6] Frederik Mallmann-Trenn, Cameron Musco, and Christopher Musco. Eigenvector computation and community detection in asynchronous gossip models. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. [7] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013. [8] David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 482–491. IEEE, 2003. [9] Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of mathematical biology, 15:267–273, 1982. [10] Sanjeev Chauhan, Michelle Girvan, and Edward Ott. Spectral properties of networks with community structure. Physical Review E, 80(5):056114, 2009. [11] Paul A White. The computation of eigenvalues and eigenvectors of a matrix. Journal of the Society for Industrial and Applied Mathematics, 6(4):393–437, 1958. [12] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508–2530, 2006. [13] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Advances in neural information processing systems, 27, 2014. [14] Mark Rudelson and Roman Vershynin. Smallest singular value of a random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707–1739, 2009. [15] Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of statistics, 48(3):1452, 2020. [16] Jerome Fellus, David Picard, and Philippe-Henri Gosselin. Decentralized k-means using randomized gossip protocols for clustering large datasets. In 2013 IEEE 13th International Conference on Data Mining Workshops, pages 599–606. IEEE, 2013. [17] Souptik Datta, Chris Giannella, and Hillol Kargupta. Approximate distributed kmeans clustering over a peer-to-peer network. IEEE Transactions on Knowledge and Data Engineering, 21(10):1372–1388, 2008. [18] Hoda Mashayekhi, Jafar Habibi, Tania Khalafbeigi, Spyros Voulgaris, and Maarten Van Steen. Gdcluster: a general decentralized clustering algorithm. IEEE transactions on knowledge and data engineering, 27(7):1892–1905, 2015. [19] Cheng Qiao and Kenneth N Brown. Asynchronous distributed clustering algorithm for wireless sensor networks. In Proceedings of the 2019 4th International Conference on Machine Learning Technologies, pages 76–82, 2019. [20] Paolo Di Lorenzo and Sergio Barbarossa. Distributed estimation and control of algebraic connectivity over random graphs. IEEE Transactions on Signal Processing, 62(21):5615–5628, 2014. [21] Dong Xue, Azwirman Gusrialdi, and Sandra Hirche. A distributed strategy for nearoptimal network topology design. In 21st International Symposium on Mathematical Theory of Networked and Systems (MTNS 2014), 2014. [22] Tuhin Sahai, Alberto Speranzon, and Andrzej Banaszuk. Wave equation based algorithm for distributed eigenvector computation. In 49th IEEE Conference on Decision and Control (CDC), pages 7308–7315. IEEE, 2010. [23] Hongyu Zhu, Stefan Klus, and Tuhin Sahai. A dynamic mode decomposition approach for decentralized spectral clustering of graphs. In 2022 IEEE Conference on Control Technology and Applications (CCTA), pages 1202–1207. IEEE, 2022. [24] Konstantin Avrachenkov, Philippe Jacquet, and Jithin K Sreedharan. Distributed spectral decomposition in networks by complex diffusion and quantum random walk. In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, pages 1–9. IEEE, 2016. [25] Luca Becchetti, Andrea E Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Find your place: Simple distributed algorithms for community detection. SIAM Journal on Computing, 49(4):821–864, 2020. [26] Jiasheng Xu, Luoyi Fu, Xiaoying Gan, and Bo Zhu. Distributed community detection on overlapping stochastic block model. In 2020 International Conference on Wireless Communications and Signal Processing (WCSP), pages 201–206. IEEE, 2020. [27] Reza Fathi, Anisur Rahaman Molla, and Gopal Pandurangan. Efficient distributed community detection in the stochastic block model. In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 409–419. IEEE, 2019. [28] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109–137, 1983. [29] Márk Jelasity and Alberto Montresor. Epidemic-style proactive aggregation in large overlay networks. In 24th International Conference on Distributed Computing Systems, 2004. Proceedings., pages 102–109. IEEE, 2004. [30] Carlos Baquero, Paulo Sérgio Almeida, Raquel Menezes, and Paulo Jesus. Extrema propagation: Fast distributed estimation of sums and network sizes. IEEE Transactions on Parallel and Distributed Systems, 23(4):668–675, 2011. [31] Mihail L Sichitiu and Chanchai Veerarittiphan. Simple, accurate time synchronization for wireless sensor networks. In 2003 IEEE Wireless Communications and Networking, 2003. WCNC 2003., volume 2, pages 1266–1273. IEEE, 2003. [32] Konstantinos Skiadopoulos, Athanasios Tsipis, Konstantinos Giannakis, George Koufoudakis, Eleni Christopoulou, Konstantinos Oikonomou, George Kormentzas, and Ioannis Stavrakakis. Synchronization of data measurements in wireless sensor networks for iot applications. Ad Hoc Networks, 89:47–57, 2019. [33] Ceferino Gabriel Ramirez, Anton Sergeyev, Assya Dyussenova, and Bob Iannucci. Longshot: Long-range synchronization of time. In Proceedings of the 18th International Conference on Information Processing in Sensor Networks, pages 289–300, 2019. [34] David Pallier, Vincent Le Cam, and Sébastien Pillement. Energy-efficient gps synchronization for wireless nodes. IEEE Sensors Journal, 21(4):5221–5229, 2020. [35] Terence Tao and Van Vu. Random matrices have simple spectrum. Combinatorica, 37:539–553, 2017. [36] Stephen Boyd, Persi Diaconis, and Lin Xiao. Fastest mixing markov chain on a graph. SIAM review, 46(4):667–689, 2004. [37] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. The Annals of Statistics, pages 215–237, 2015. [38] Emmanuel Abbe. Community detection and stochastic block models: recent developments. The Journal of Machine Learning Research, 18(1):6446–6531, 2017. [39] Anderson Ye Zhang. Fundamental limits of spectral clustering in stochastic block models. arXiv preprint arXiv:2301.09289, 2023. [40] Muhammad Aqib Javed, Muhammad Shahzad Younis, Siddique Latif, Junaid Qadir, and Adeel Baig. Community detection in networks: A multidisciplinary review. Journal of Network and Computer Applications, 108:87–111, 2018. [41] Gaurav Agarwal and David Kempe. Modularity-maximizing graph communities via mathematical programming. The European Physical Journal B, 66:409–418, 2008. [42] Mark EJ Newman. Finding community structure in networks using the eigenvectors of matrices. Physical review E, 74(3):036104, 2006. [43] Leon Bottou and Yoshua Bengio. Convergence properties of the k-means algorithms. Advances in neural information processing systems, 7, 1994. [44] Greg Hamerly and Charles Elkan. Alternatives to the k-means algorithm that find better clusterings. In Proceedings of the eleventh international conference on Information and knowledge management, pages 600–607, 2002. [45] Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An ℓp theory of pca and spectral clustering. The Annals of Statistics, 50(4):2359–2385, 2022. [46] Spyridon Leonardos, Victor Preciado, and Kostas Daniilidis. A dynamical systems approach to distributed eigenvector computation. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 2209–2215, 2017. [47] De Huang, Jonathan Niles-Weed, and Rachel Ward. Streaming k-pca: Efficient guarantees for oja＇s algorithm, beyond rank-one updates. In Conference on Learning Theory, pages 2463–2498. PMLR, 2021. [48] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms. Physical review E, 78(4):046110, 2008. [49] Santo Fortunato and Mark EJ Newman. 20 years of network community detection. Nature Physics, 18(8):848–850, 2022. [50] Anil Damle, Victor Minden, and Lexing Ying. Simple, direct and efficient multi-way spectral clustering. Information and Inference: A Journal of the IMA, 8(1):181–203, 2019. [51] Hermann Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen (mit einer anwendung auf die theorie der hohlraumstrahlung). Mathematische Annalen, 71(4):441–479, 1912. | - |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/91326 | - |
| dc.description.abstract | 譜圖分析是圖數據挖掘的基礎任務。當圖表示一個大規模網絡時，可以通過節點之間的協作來實現這一任務的去中心化執行。然而，現有的去中心化方法通常以批量的方式執行，換句話說，需要預先確定圖矩陣的特徵對數量，然後一次性計算它們，這導致每次迭代的通訊成本很高。此外，現有的去中心化方法缺乏按順序計算特徵對的靈活性，因此並不利於某些任務，例如，估計圖隱含的社群數量。為了解決這些問題，本文提出了一種替代的去中心化譜圖分析方法，它允許所有節點按順序計算對稱圖矩陣的主要特徵對。通過一系列數值評估，我們有效地展示了所提方法的實用性和效率。此外，我們還建立了個別特徵向量估計的非漸進保證，證明了所提方法能達到與集中式方法相同的理論極限。此外，我們將所提方法與去中心化的K-means 演算法結合，以解決更廣泛的社群偵測問題。數值結果顯示，當流言演算法的迭代次數足夠大時，去中心化演算法得到的準確率近似於集中式方法。最後，我們強調，理論分析去中心化K-means 演算法仍然存在一個根本上的挑戰，而這是一個有趣的研究方向。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-12-20T16:30:16Z No. of bitstreams: 0 | en |
| dc.description.provenance | Made available in DSpace on 2023-12-20T16:30:16Z (GMT). No. of bitstreams: 0 | en |
| dc.description.tableofcontents | Acknowledgements iii
摘要v Abstract vii Contents ix List of Figures xiii Chapter 1 Introduction 1 1.1 Related Works 4 1.2 Organization 5 1.3 Notation 6 Chapter 2 Problem Formulation and Background 7 2.1 Eigendecomposition: Power Method 9 2.2 Decentralization: Gossip Algorithm 11 2.3 Benchmark and Method for Community Detection 14 2.3.1 Benchmark: Stochastic Block Model 14 2.3.2 Method: Spectral Clustering 16 Chapter 3 Main Results 21 3.1 Proposed algorithm 21 3.2 Non-asymptotic guarantees 24 3.2.1 Approximating the top 2 eigenvectors 24 3.2.2 Sketch the proof of Theorem 3.1 29 3.2.3 Approximating the top K eigenvectors 35 3.2.4 Sketch the proof of Theorem 3.3 38 3.3 Extending non-asymptotic performance guarantees of existing decentralized method 44 Chapter 4 Application: Decentralized Community Detection 49 4.1 Exact recovery: SBM with 2 equal-sized Communities 49 4.2 Decentralized K-means clustering 52 4.2.1 Proposed algorithm 53 4.2.2 Discussion 55 Chapter 5 Simulation 57 5.1 Communication Complexity 57 5.2 Community Detection 62 5.2.1 Achieving exact recovery on the SBM 62 5.2.2 Lancichinetti–Fortunato–Radicchi benchmark 63 Chapter 6 Theoretical analysis 67 6.1 Centralized estimation error in Theorem 3.1 67 6.2 Decentralized estimation error in Theorem 3.1 69 6.2.1 Upper bound for the former term in Equation (6.1) 70 6.2.2 Upper bound for the latter term in Equation (6.1) 79 6.2.3 Upper bound for the length of estimated eigenvectors 80 6.3 Proof of Theorem 3.1 84 6.4 Proof of Theorem 3.3 87 Chapter 7 Conclusion and Future Works 99 7.1 Conclusion 99 7.2 Future Works 100 References 101 Appendix A — Auxiliary Lemmas 109 A.1 Stochastic Block Model 109 A.2 Power Method 114 | - |
| dc.language.iso | en | - |
| dc.subject | 譜圖分析 | zh_TW |
| dc.subject | 社群偵測 | zh_TW |
| dc.subject | 流言演算法 | zh_TW |
| dc.subject | 冪迭代方法 | zh_TW |
| dc.subject | 去中心化 | zh_TW |
| dc.subject | 譜圖分析 | zh_TW |
| dc.subject | 去中心化 | zh_TW |
| dc.subject | 冪迭代方法 | zh_TW |
| dc.subject | 流言演算法 | zh_TW |
| dc.subject | 社群偵測 | zh_TW |
| dc.subject | Gossip algorithm | en |
| dc.subject | Decentralization | en |
| dc.subject | Power method | en |
| dc.subject | Community detection | en |
| dc.subject | Gossip algorithm | en |
| dc.subject | Power method | en |
| dc.subject | Spectral graph analysis | en |
| dc.subject | Decentralization | en |
| dc.subject | Community detection | en |
| dc.subject | Spectral graph analysis | en |
| dc.title | 去中心化圖探勘 | zh_TW |
| dc.title | Decentralized Graph Mining | en |
| dc.type | Thesis | - |
| dc.date.schoolyear | 112-1 | - |
| dc.description.degree | 碩士 | - |
| dc.contributor.oralexamcommittee | 洪樂文;謝宏昀 | zh_TW |
| dc.contributor.oralexamcommittee | Yao-Win Peter Hong;Hung-Yun Hsieh | en |
| dc.subject.keyword | 譜圖分析,去中心化,冪迭代方法,流言演算法,社群偵測, | zh_TW |
| dc.subject.keyword | Spectral graph analysis,Decentralization,Power method,Gossip algorithm,Community detection, | en |
| dc.relation.page | 119 | - |
| dc.identifier.doi | 10.6342/NTU202300918 | - |
| dc.rights.note | 同意授權(限校園內公開) | - |
| dc.date.accepted | 2023-12-08 | - |
| dc.contributor.author-college | 電機資訊學院 | - |
| dc.contributor.author-dept | 電信工程學研究所 | - |
| dc.date.embargo-lift | 2028-11-27 | - |
| 顯示於系所單位： | 電信工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-112-1.pdf 未授權公開取用 | 1.49 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。