解決在社會網路分析中困難問題的DNA計算演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：28

、訪客IP：3.138.69.39

姓名

陳仲軒(Chung-Shiuan Chen) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

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

相關論文

★ 應用智慧分類法提升文章發佈效率於一企業之知識分享平台	★ 家庭智能管控之研究與實作
★ 開放式監控影像管理系統之搜尋機制設計及驗證	★ 資料探勘應用於呆滯料預警機制之建立
★ 探討問題解決模式下的學習行為分析	★ 資訊系統與電子簽核流程之總管理資訊系統
★ 製造執行系統應用於半導體機台停機通知分析處理	★ Apple Pay支付於iOS平台上之研究與實作
★ 應用集群分析探究學習模式對學習成效之影響	★ 應用序列探勘分析影片瀏覽模式對學習成效的影響
★ 一個以服務品質為基礎的網際服務選擇最佳化方法	★ 維基百科知識推薦系統對於使用e-Portfolio的學習者滿意度調查
★ 學生的學習動機、網路自我效能與系統滿意度之探討-以e-Portfolio為例	★ 藉由在第二人生內使用自動對話代理人來改善英文學習成效
★ 合作式資訊搜尋對於學生個人網路搜尋能力與策略之影響	★ 數位註記對學習者在線上學習環境中反思等級之影響

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

從遠古到現今，社會網路一直是形成各種社會組織或是社會行為的重要結構，因此在結構中的成員以及他們彼此之間的關係，可以清楚的被社會網路所描述，而藉由數學圖形理論的發展，社會網路分析(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.

關鍵字(中)

★ 可疑內聚子群體
★ 社會網路分析
★ DNA分子計算

關鍵字(英)

★ cohesive subgroup
★ N-clique
★ N-clan
★ N-club
★ DNA-computing
★ Social network analysis

論文目次

Chinese Abstract•••••••••••••••••••••••••••••••••••••••••••••• i
English Abstract•••••••••••••••••••••••••••••••••••••••••••••• ii
Table of Content•••••••••••••••••••••••••••••••••••••••••••••• iii
List of Figures•••••••••••••••••••••••••••••••••••••••••••••••• v
List of Tables••••••••••••••••••••••••••••••••••••••••••••••••• vi
1. Introduction••••••••••••••••••••••••••••••••••••••••••••••• 1
1.1. Impact of the social network analysis••••••••••••••••••••••••••••• 1
1.2. SNA and its challenge••••••••••••••••••••••••••••••••••••••• 1
1.3. DNA computation•••••••••••••••••••••••••••••••••••••••••• 2
1.4. Using DNA-computing methods to solve the NP-complete problems in SNA•• 3
2. Related work•••••••••••••••••••••••••••••••••••••••••••••• 4
2.1. Social network analysis•••••••••••••••••••••••••••••••••••••• 4
2.2. DNA computing••••••••••••••••••••••••••••••••••••••••••• 8
3. Background of DNA computation••••••••••••••••••••••••••••• 9
3.1. DNA structure and the intrinsic features••••••••••••••••••••••••••• 9
3.2. Biochemical operations•••••••••••••••••••••••••••••••••••••• 10
3.3. Ouyang’s algorithm to find maximal clique••••••••••••••••••••••••• 15
4. DNA solution to solve N-cliques, N-clans and N-clubs••••••••••••• 17
4.1. Generate all paths of a graph by DNA solution•••••••••••••••••••••• 17
4.2. Delete strands with cycle path••••••••••••••••••••••••••••••••• 18
4.3. Separate the strands in which the distance is bigger and small than N••••••• 19
4.4. DNA algorithm for three kinds of graph in social networks•••••••••••••• 21
4.4.1. N-clique••••••••••••••••••••••••••••••••••••••••••• 21
4.4.2. N-clan••••••••••••••••••••••••••••••••••••••••••••• 24
4.4.3. N-club••••••••••••••••••••••••••••••••••••••••••••• 26
5. Demonstrate the procedures by simulation••••••••••••••••••••• 32
5.1. The 2-cliques••••••••••••••••••••••••••••••••••••••••••••• 33
5.2. The 2-clans•••••••••••••••••••••••••••••••••••••••••••••• 34
5.3. The 2-clubs•••••••••••••••••••••••••••••••••••••••••••••• 35
6. Conclusion•••••••••••••••••••••••••••••••••••••••••••••••• 37
References••••••••••••••••••••••••••••••••••••••••••••••••••• 38

參考文獻

[1] Batallas, D.A., Yassine, A.A., 2006. Information Leaders in Product Development Organizational Networks: Social Network Analysis of the Design Structure Matrix. IEEE Trans., Eng. Manage, Vol. 53, no. 3, pp. 570-582.
[2] Wey, T., Blumstein, D. T., Shen, W., Jordán, F. 2007. Social network analysis of animal behaviour: a promising tool for the study of sociality, Anim Behav 75: 333–344
[3] Mayer, A. 2009. Online social networks in economics, Decision Support Systems, Volume 47, Issue 3
[4] Wasserman, S., Faust, K., 1994. Social Networks Analysis: Methods and Applications. Cambridge: Cambridge University Press.
[5] Adleman, L., 1994. Molecular computation of solutions to combinatorial problems. Science, 266, 1021-1024.
[6] Lipton, R. J., 1995. DNA solution of hard computational problems. Science, 268, 542-545.
[7] Ouyang, Q., Kaplan, P. D., Liu, S., Libchaber, A., 1997. DNA Solution of the Maximal Clique Problem. Science 17, Vol. 278, no. 5337, 446 – 449.
[8] Moreno, J. L., 1934. Who shall survive? Nervous and Mental Disease publishing company.
[9] Borgatti, S.P., 1998. What Is Social Network Analysis? Available from: http://www.analytictech.com/networks/whatis.htm.
[10] Mitchell, J.C., 1969: The concept and use of social networks, in: Mitchell, J.C.(ed.): Social networks in urban settings, Manchester, Manchester U.P.
[11] Knoke, D., Burt, R.S., 1983. Prominence. In: Burt, R.S , and Minor, M.J., (eds.), Applied Network Analysis, pages 195-222.
[12] Luce, R., Perry, A., 1949. A method of matrix analysis of group structure. Psychometrika 14, 95-116.
[13] Harary, F., 1969. Graph Theory. Reading, Mass, Addison-Wesley.
[14] Luce, R.D., 1950. Connectivity and generalized cliques in sociometric group structure. Psychometrika. 15, 159-190.
[15] Mokken, R.J., 1979. Cliques, clubs and clans. In: Quality and Quantity 13, 161-173.
[16] Seidman, S., Foster, B., 1978. A graph theoretic generalization of the clique concept. Journal of Mathematical sociology, 6, 139-154.
[17] Seidman, S.B., 1983. Network structure and minimum degree. Social Networks, 269-287.
[18] Seidman, S.B., 1983. LS Sets as Cohesive Subsets of Graphs and Hypergraphs. Social Networks 5, 92–96.
[19] Seidman, S.B., 1983. Internal cohesion of LS sets in graphs. Social Networks 5, 97–107.
[20] Borgatti S.P., Everett, M.G., Shirey, P.R., 1990. LS Sets, Lambda Sets and Other Cohesive Subsets, Social Networks 12, 337–357.
[21] von Neumann, J., 1945 First draft of a report on the EDVAC. Technical report, University of Pennsylvania.
[22] Backus, J., 1977. Can Programming be Liberated from the von Neumann Style? ACM Turing Award Lecture. Communications of the ACM, August 1978, Volume 21, Number 8.
[23] Cook, S.A., 1971. The complexity of theorem proving procedures. Proceedings, Third Annual ACM Symposium on the Theory of Computing, 151–158.
[24] Garey, M.R., Johnson, D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. W.H.Freeman and Company, 194.
[25] Balasundaram, B., Butenko, S., Trukhanov, S., 2005. Novel approaches for analyzing biological networks. Journal of Combinatorial Optimization, 10, 23-39.
[26] Balasundaram, B., Butenko, S., Hicks, I.V., Sachdeva, S., 2008. Clique relaxations in social network analysis:The maximum k-plex problem. Manuscript.
[27] Amos, M., 2004. Theoretical and Experimental DNA computation. Springer.
[28] Paun, G., Rozenberg, G., Salomaa, A., 1998. DNA Computing: New Computing Paradigms. Springer-Verlag.
[29] Yeh, C.W., Chu, C.P., 2008. Molecular verification of rule-based systems based on DNA computation. IEEE Transactions on Knowledge and Data Engineering, Vol. 20, Number 7, 965-975.

指導教授

楊鎮華(Stephen J.H. Yang)

審核日期

2010-5-19

推文