解決在社會網路分析中困難問題的DNA計算演算法 ; Applying DNA Computation to Intractable Problems in Social Network Analysis

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/44544

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/44544

Title:	解決在社會網路分析中困難問題的DNA計算演算法;Applying DNA Computation to Intractable Problems in Social Network Analysis
Authors:	陳仲軒;Chung-Shiuan Chen
Contributors:	資訊工程研究所
Keywords:	可疑內聚子群體;社會網路分析;DNA分子計算;cohesive subgroup;N-clique;N-clan;N-club;DNA-computing;Social network analysis
Date:	2010-05-19
Issue Date:	2010-12-09 13:48:37 (UTC+8)
Publisher:	國立中央大學
Abstract:	從遠古到現今，社會網路一直是形成各種社會組織或是社會行為的重要結構，因此在結構中的成員以及他們彼此之間的關係，可以清楚的被社會網路所描述，而藉由數學圖形理論的發展，社會網路分析(SNA)則被大量的發展以及使用在各種不同領域之中，例如Web 2.0的相關應用以及工業界的生產流程等等…。然而很多被定義在社會網路分析之中的結構，對於傳統的計算機結構而言仍然是屬於NP-complete的問題，例如尋找社會網路之中的clique、N-clique、N-clan、N-club 以及K-plex。因此為社會網路分析的發展以及他的使用造成嚴重的限制。本篇論文將使用記憶空間大而且具有平行運算的DNA計算方法，針對其中的三種定義：N-clique、N-clan及N-club提出正確而可行的演算法。他們的正確性以及時間複雜度分析將可以證明DNA計算方法有助於社會網路分析的發展。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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	601	View/Open

社群 sharing

Loading...