TY - JOUR
T1 - Applying DNA computation to intractable problems in social network analysis
AU - Chen, Rick C.S.
AU - Yang, Stephen J.H.
N1 - Funding Information:
This work is supported by National Science Council, Taiwan under grants NSC96-2628-S-008-008-MY3, NSC98-2511-S-008-006-MY3 and NSC98-2511-S-008-007-MY3.
PY - 2010/9
Y1 - 2010/9
N2 - 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.
AB - 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.
KW - Cohesive subgroup
KW - DNA-computing
KW - N-clan
KW - N-clique
KW - N-club
KW - Social network analysis
UR - http://www.scopus.com/inward/record.url?scp=77955917451&partnerID=8YFLogxK
U2 - 10.1016/j.biosystems.2010.05.006
DO - 10.1016/j.biosystems.2010.05.006
M3 - 期刊論文
C2 - 20566337
AN - SCOPUS:77955917451
SN - 0303-2647
VL - 101
SP - 222
EP - 232
JO - BioSystems
JF - BioSystems
IS - 3
ER -