複雜網路中具縮影性質之階層: 分析及應用

Abstract

以複雜網路的型態來呈現複雜系統中的互動關係是一種方便且行之有年的研究方法，包括在生物學、生態學、社會學等等的領域上，除了讓研究者有不同於以往該領域傳統議題的新觀點外，許多新的方法也因此被提出來以解決在各種不同複雜系統上的問題。其中，最重要也最具挑戰性的一個問題就是，如何將複雜網路做分群(在社會學領域被稱之為共同體(community)或是群組(group)，在生物學上被稱為基塊(motif)或是模組(module))。如何(1)找出模組，(2)階層性的組織，及(3)這兩者對應到真實世界的關係，一直是研究者的焦點所在。儘管已經有一些成功的研究，但是至今仍沒有一個標準的衡量方法可以來找出模組或是階層性組織。以階層式組織來說，大多數的研究專注於其模組在不同階層上垂直面向的關係之探討-其可用來表示"包含(inclusion)"，"因果(causality)"和"調控(regulation)"關係;但往往忽略了其在同一階層上水平面向的關係之研究-其可用來提供給研究者在某一階層上的網路的縮影(abstraction)或是骨架(backbone)。在本論文研究中，我提出了一雙向式尋找模組及建構階層組織的方法，其同時考慮了各個模組間垂直和水平的關係來建構出該複雜系統的金字塔階層(pyramid hierarchies)， 此方法除了被人工網路驗證外，也被應用在生物及社會網路上，其結果顯示該方法在擷取複雜系統之資訊上卓越的效能。

The use of nodes and links to assemble networks is convenient for representing interactions in complex systems. This benefits researchers in biology, ecology, sociology and other biological and social sciences. In addition to supporting alternative views of complex domains, network research is also supporting new methods for solving problems in a range of domains. One particularly important and challenging problem is partitioning networks into clusters (called communities or groups in social science research and motifs or modules in biology). Research in these areas has focused on identifying modules and hierarchical organizations that correspond to real-world meanings (e.g., biological functions or economic and political constraints). Despite a number of successful examples, no uniform measure of modularity or standard hierarchical structure exists. Most current descriptions of hierarchical organizations are limited to vertical relationships between modules at different hierarchical levels, thus overlooking horizontal relationships that express associations among modules at the same level. Vertical relationships can be used to represent inclusion hierarchies and to describe causality/regulation. Horizontal relationships complement these by providing abstractions of original networks of interest at various levels in a hierarchy (Fig. 1). In this dissertation I describe a proposal for a two-way simultaneous module-finding and hierarchy-building strategy. I take both vertical and horizontal relationships between modules into consideration when building pyramid hierarchies in which each layer represents an abstraction of lower-level networks. This dissertation also contains descriptions of tests for this proposed approach, using networks consisting of anywhere from tens to hundreds of nodes and links, and in domains that include artificial random networks, social networks, and biological networks. The results demonstrate its performance for information mining from complex systems.