The explosive growth of the Web and of social networks motivates the need for analyzing the macroscopic structure of their underlying graphs. Since the pioneering study by Broder et al. that revealed the bow-tie structure of the Web, many subsequent studies observed a similar structure in large-scale Web and social graphs, all reporting the existence of a giant strongly connected component that is considered as the core of the graph. Although the characterization of the structure of a graph with respect to its pairwise connectivity has been known for over 15 years, no study further analyzed the structure inside the largest strongly connected component of Web and social graphs. In this paper, we investigate the pairwise 2-connectivity among the vertices inside the core of Web and social graphs. Our experiments reveal an inner bow-tie structure, with respect to the pairwise 2-connectivity, that is formed around a giant 2-connected components. Furthermore, our fundings report a surprisingly consistent structure across Web graphs and across social graphs, despite the diff erence in their sizes and characteristics.
Italiano, G.f., Parotsidis, N., & Perekhodko, E. (2017). What's inside a bow-tie: Analyzing the core of the web and of social networks. In ACM International Conference Proceeding Series (pp.39-43). Association for Computing Machinery [10.1145/3077584.3077589].
|Autori:||Italiano, Gf; Parotsidis, N; Perekhodko, E|
|Titolo:||What's inside a bow-tie: Analyzing the core of the web and of social networks|
|Nome del convegno:||2017 International Conference on Information System and Data Mining, ICISDM 2017|
|Luogo del convegno:||College of Charleston, usa|
|Anno del convegno:||2017|
|Data di pubblicazione:||2017|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1145/3077584.3077589|
|Settore Scientifico Disciplinare:||Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni|
|Tipologia:||Intervento a convegno|
|Citazione:||Italiano, G.f., Parotsidis, N., & Perekhodko, E. (2017). What's inside a bow-tie: Analyzing the core of the web and of social networks. In ACM International Conference Proceeding Series (pp.39-43). Association for Computing Machinery [10.1145/3077584.3077589].|
|Appare nelle tipologie:||02 - Intervento a convegno|