Graphs resulting from human behavior (the web graph, friendship graphs, etc.) have hitherto been viewed as a monolithic class of graphs with similar characteristics; for instance, their degree distributions are markedly heavy-tailed. In this paper we take our understanding of behavioral graphs a step further by showing that an intriguing empirical property of web graphs their compressibility - cannot be exhibited by well-known graph models for the web and for social networks. We then develop a more nuanced model for web graphs and show that it does exhibit compressibility, in addition to previously modeled web graph properties.
Models for the Compressible Web / Chierichetti, Flavio; Ravi, Kumar; Lattanzi, Silvio; Panconesi, Alessandro; Prabhakar, Raghavan. - (2009), pp. 331-340. (Intervento presentato al convegno 50th Annual IEEE Symposium on Foundations of Computer Science tenutosi a Atlanta, GA nel OCT 25-27, 2009) [10.1109/focs.2009.63].
Models for the Compressible Web
CHIERICHETTI, FLAVIO;LATTANZI, SILVIO;PANCONESI, Alessandro;
2009
Abstract
Graphs resulting from human behavior (the web graph, friendship graphs, etc.) have hitherto been viewed as a monolithic class of graphs with similar characteristics; for instance, their degree distributions are markedly heavy-tailed. In this paper we take our understanding of behavioral graphs a step further by showing that an intriguing empirical property of web graphs their compressibility - cannot be exhibited by well-known graph models for the web and for social networks. We then develop a more nuanced model for web graphs and show that it does exhibit compressibility, in addition to previously modeled web graph properties.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
