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

NCU Institutional Repository > 資訊電機學院 > 資訊工程研究所 > 博碩士論文 > Item 987654321/44544

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/44544

题名:	解決在社會網路分析中困難問題的DNA計算演算法;Applying DNA Computation to Intractable Problems in Social Network Analysis
作者:	陳仲軒;Chung-Shiuan Chen
贡献者:	資訊工程研究所
关键词:	可疑內聚子群體;社會網路分析;DNA分子計算;cohesive subgroup;N-clique;N-clan;N-club;DNA-computing;Social network analysis
日期:	2010-05-19
上传时间:	2010-12-09 13:48:37 (UTC+8)
出版者:	國立中央大學
摘要:	從遠古到現今，社會網路一直是形成各種社會組織或是社會行為的重要結構，因此在結構中的成員以及他們彼此之間的關係，可以清楚的被社會網路所描述，而藉由數學圖形理論的發展，社會網路分析(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.
显示于类别:	[資訊工程研究所] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	601	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....