Chen Rick C S, Yang Stephen J H
Department of Computer Science & Information Engineering, National Central University, Taiwan.
Biosystems. 2010 Sep;101(3):222-32. doi: 10.1016/j.biosystems.2010.05.006. Epub 2010 Jun 4.
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.
从古至今，社交网络在一系列社会行为的各种组织形成过程中都发挥了重要作用。因此，社交网络本质上描述了世界各地元素之间的复杂关系。基于数学图论，社交网络分析（SNA）得以发展并应用于多个领域，如用于Web应用的Web 2.0以及各行业的产品开发等。然而，社交网络分析的一些定义，如寻找团、N团、N族、N俱乐部和K-核，都是NP完全问题，通过传统计算机架构不易解决。这些挑战限制了社交网络分析的应用。本文提供了基于DNA计算的方法，这些方法具有固有的高信息密度和大规模并行性。利用这些方法，我们旨在解决社交网络的三个主要问题：N团、N族和N俱乐部。本文中讨论的它们的准确性和可行的时间复杂度将证明DNA计算可用于促进社交网络分析的发展。
