Subgraph Frequencies by Johan Ugander.
From the webpage:
In our upcoming paper Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph Collections” (PDF), to appear in May 2013 at the 22nd ACM International World Wide Web Conference, we found that there are fundamental combinatorial constraints governing the frequency of subgraphs that constrain all graphs in previously undocumented ways. We also found that there are empirical properties of social graphs that relegate their subgraph frequencies to a seriously restricted subspace of the full feasible space. Together, we present two complementary frameworks that shed light on a fundamental question pertaining to social graphs:
What properties of social graphs are ‘social’ properties and what properties are ‘graph’ properties?
We contribute two frameworks for analyzing this question: one characterizing extremal properties of all graphs and one characterizing empirical properties of social graphs. Together the two frameworks offer a direct contribution to one of the most well-known observations about social graphs: the tendency of social relationships to close triangles, and the relative infrequency of what is sometimes called the ‘forbidden triad’: three people with two social relationships between them, but one absent relationship. Our frameworks show that the frequency of this ‘forbidden triad’ is non-trivially restricted not just in social graphs, but in all graphs.
Harnessing our results more generally, we are in fact able to show that almost all k node subgraphs have a frequency that is non-trivially bounded. Thus, there is an extent to which almost all subgraphs are mathematically ‘forbidden’ from occurring beyond a certain frequency.
Interesting to see “discovery” of “empirical properties” of social graphs.
What empirical properties will you discover while processing a social graph with graph software?