The Bow-Tie Structure

World Wide Web(WWW)到底能不能被視為一種Social Network？至少，他們之間存在一個特性上的差異－－WWW具有蝴蝶結結構(Bow-Tie Structure)，而Social Network則未必。Bow-Tie Structure是Broder等人於2000年發現的，他們設計Web Crawler從整個網際網路抓回網頁當作節點(vertex)，並透過Hyperlink將網頁與網頁之間建立邊(edge)，整理歸納出了的類似下圖的圖形(graph)，展示WWW的結構與蝴蝶結極為相似。這些研究人員將此結構分為五大部分作進一步的解釋：


(1) SCC: WWW的核心是其結構中的Strongly Connected Component (SCC)，所有SCC中的網頁均存在「具方向性的路徑」(directed path)與該SCC中的其他網頁相互連通。
(2) OUT: 能夠被SCC中的網頁以「具方向性的路徑」到達的網頁集合，稱為OUT元件。
(3) IN: 能夠以「具方向性的路徑」與SCC中所有網頁連通的網頁集合，稱為IN元件。
(4) TENDRILS: 所有能夠以「具方向性的路徑」到達OUT Component的網頁，以及所有能夠被IN Component中的網頁以「具方向性的路徑」到達的網頁，所形成的網頁集合，稱之。TUBE: 所有能夠從IN Component以「具方向性的路徑」到達OUT Component之網頁集合，稱之。
(5) 不符合上述四大類的網頁，即Disconnected Components。在WWW中，這類網頁佔有率高達50%。

P.S. 「具方向性的路徑」是不容許反向的，必須順從超連結hyperlink的方向。

後來2001年，Dill等人以不同scales之subgraphs of WWW Graph進一步闡述Bow-Tie Structure，其中這些subgraph是具有具有相似特性的網頁所組成，如內容主題類似、同屬某一地理位置的網頁。

(1) Recursive Bow-Tie Structure:
對整個Web Graph來說，Bow-tie結構是階層式的(Hierarchy)，如下圖。換句話說，根據網頁特性將WWW的網頁分成多個Subgraphs，各subgraph依舊存在bow-tie structure。
(2) Ease of Navigation:
所以具有bow-tie structures之subgraphs中的SCCs是透過最上層(最大的)SCC而緊密連結的，這提供我們很好的網頁瀏覽機制：可透過該目的網頁所屬之bow-tie structure之SCC來與整個WWW的相通。
(3) Resilience:
由於Bow-Tie Structures中的SCCs緊密連結的特性，使得當WWW Graph中某些網頁突然失聯時，還能夠透過其他網頁(也就是透過其他瀏覽路徑)來保持整個Web Graph之特性。此與Social Network之Resilience from Scale-free有異曲同工之妙。