DC 欄位 值 語言 DC.contributor 資訊工程學系 zh_TW DC.creator 陳仲軒 zh_TW DC.creator Chung-Shiuan Chen en_US dc.date.accessioned 2010-5-19T07:39:07Z dc.date.available 2010-5-19T07:39:07Z dc.date.issued 2010 dc.identifier.uri http://ir.lib.ncu.edu.tw:444/thesis/view_etd.asp?URN=945402025 dc.contributor.department 資訊工程學系 zh_TW DC.description 國立中央大學 zh_TW DC.description National Central University en_US dc.description.abstract 從遠古到現今，社會網路一直是形成各種社會組織或是社會行為的重要結構，因此在結構中的成員以及他們彼此之間的關係，可以清楚的被社會網路所描述，而藉由數學圖形理論的發展，社會網路分析(SNA)則被大量的發展以及使用在各種不同領域之中，例如Web 2.0的相關應用以及工業界的生產流程等等…。然而很多被定義在社會網路分析之中的結構，對於傳統的計算機結構而言仍然是屬於NP-complete的問題，例如尋找社會網路之中的clique、N-clique、N-clan、N-club 以及K-plex。因此為社會網路分析的發展以及他的使用造成嚴重的限制。本篇論文將使用記憶空間大而且具有平行運算的DNA計算方法，針對其中的三種定義：N-clique、N-clan及N-club提出正確而可行的演算法。他們的正確性以及時間複雜度分析將可以證明DNA計算方法有助於社會網路分析的發展。 zh_TW dc.description.abstract From ancient times to the present day, social networks have played an important role in the formation of various organizations for a range of social behaviors. As such, social networks inherently describe the complicated relationships between elements around the world. Based on mathematical graph theory, social network analysis (SNA) has been developed in and applied to various fields such as Web 2.0 for Web applications and product developments in industries, etc. However, some definitions of SNA, such as finding a clique, N-clique, N-clan, N-club and K-plex, are NP-complete problems, which are not easily solved via traditional computer architecture. These challenges have restricted the uses of SNA. This paper provides DNA-computing-based approaches with inherently high information density and massive parallelism. Using these approaches, we aim to solve the three primary problems of social networks: N-clique, N-clan, and N-club. Their accuracy and feasible time complexities discussed in the paper will demonstrate that DNA computing can be used to facilitate the development of SNA. en_US DC.subject 可疑內聚子群體 zh_TW DC.subject 社會網路分析 zh_TW DC.subject DNA分子計算 zh_TW DC.subject cohesive subgroup en_US DC.subject N-clique en_US DC.subject N-clan en_US DC.subject N-club en_US DC.subject DNA-computing en_US DC.subject Social network analysis en_US DC.title 解決在社會網路分析中困難問題的DNA計算演算法 zh_TW dc.language.iso zh-TW zh-TW DC.title Applying DNA Computation to Intractable Problems in Social Network Analysis en_US DC.type 博碩士論文 zh_TW DC.type thesis en_US DC.publisher National Central University en_US