Local bow-tie structure of the web

Abstract

Abstract Social networks often has the graph structure of giant strongly connected component (GSCC) and its upstream and downstream portions (IN and OUT), known as a bow-tie structure since a pioneering study on the World Wide Web (WWW). GSCC, on the other hand, has community structure, namely tightly knitted clusters, reflecting how the networks developed in time. By using our visualization of enhanced multidimensional scaling (MDS) and force-directed graph drawing for large and directed graphs, we discovered that a bow-tie in the WWW usually has clusters, which are locally-located mini bow-ties that are loosely connected to each other, resulting in a formation of GSCC as a whole. To quantify the mutual connectivity among such local bow-tie, we define a quantity to measure how a local bow-tie connects to others in comparison with random graphs. We found that there are striking difference between the WWW and other social and artificial networks including a million firms’ nationwide supply chain network in Japan and thousands of symbols’ dependency in the programming language of Emacs LISP, in which a global bow-tie exits. Presumably the difference comes from a self-similar structure and development of the WWW speculated by others.

Keywords

• Bow-tie
• Locality
• Visualization