Types of Networks

一般來說，最簡單的網路（network, 這裡泛指所謂的 "graph"）是由一些 nodes 以 edges 相互連結所組成；然而，在許多關於 network 的研究議題上，對於 nework 的表示其實是比最初的型態還要複雜許多的。以下大略將 network 分為四種基本的型態，應用在許多領域或問題上的變化大多由此四類型所衍生的，如圖所示。

(a)
An Undirected network with only a single type of node and a single type of edge。傳統的 graph mining 欲解決的問題多為此類型的 network，最經典的論文為 Diane J. Cook 於 IEEE Intelligent Systems 2000 所發表的 Graph-based Data Mining。然而，目前所謂 Social Network 所著重的並非此類型，但許多傳統 graph 上的研究議題，如 graph classification, partition, motif discovery, subgraph discovery 等，卻重新被拿出來在 social network 上討論。

(b)
A network with multiple types of discrete nodes and multiple types of edges。也就是根據 domain knowledge 或者問題的定義，賦予 node 或 edge 各種不同的性質。以一個以人為主體的 social network 來說，nodes 表示的可以是男人或女人、不同國籍、居住地等，而 edge 可表示朋友、敵對、親人、學術、工作、或地理上的接近程度等。這是最常見的 social network 類型，也是 social network 根本的結構。

(c)
A network with varying weight of nodes and edges。直接舉例，node's weight 可以是一個人在 network 中的重要程度、收入、階級高低等；而 edge's weight 可以是兩個人有多熟、來往密切程度、居住距離、共同參與事件的次數等。

(d)
A directed network in which each edge has a direction。一個由 directed edges 所組成的 graph 通常被稱為 directed graph 或 digraph。最顯而易見的例子為 telephone calls, msn messages，訊息的交流是 "你來我往" 的。此外，digraph 允許存在 cycle，也就是連結許多 edge 可以形成一個具方向性的 loop，食物鏈（food web）就是最好的例子。

除了以上四種基本類型外，其他還有兩種比較有名的 network 表示方式：

hypergraph：簡單來說，它是由一種特殊的 edge（稱為 hyperedge）所組成，而 hyperedge 是指一個 edge 可連結 2 個以上的node，更準確地來說，n 個個體以某種關係相互連結，此時 edge 有 C(n,2) 個，但是用一個 hyperedge 就可以將這原本的 edges 都包含。hypergraph 較常用於生物資訊中，蛋白質與化學分子的關係表示上。hyperedge 的一個簡單的圖例。

bipartite graph：這就比較常見了。此種 graph 的 nodes 有兩種不同的類型，而 edge 只建立在不同類型的 nodes 之間。所謂的 "affiliation network" 正是此類型的一個代表，它指的是共同參與事件的關係，graph 的一種 node type 為 people，另一種 node type 為 events，共同參與某一事件的人都會與該事件的 node 建立連結，但這些人彼此間並沒有 edges 存在。