En växande uppsättning on-line applikationer genererar data som kan ses som mycket stora samlingar av små, täta sociala grafer - dessa sträcker sig från grupper av sociala grupper, evenemang, eller samarbetsprojekt till den stora samlingen av graf stadsdelar i stora sociala nätverk. En naturlig fråga är hur man på ett användbart sätt definierar ett domänoberoende "koordinatsystem" för en sådan samling grafer, så att uppsättningen av möjliga strukturer kan representeras och förstås på ett kompakt sätt inom ett gemensamt utrymme. I detta arbete bygger vi på teorin om graf homomorfism för att formulera och analysera en sådan representation, baserad på beräkning av frekvenser av små inducerade subgrafer inom varje graf. Vi finner att utrymmet för subgraf frekvenser styrs både av dess kombinatoriska egenskaper - baserade på extrem resultat som begränsar alla grafer - liksom av dess empiriska egenskaper - manipuleras på det sätt som verkliga sociala grafer verkar ligga nära en enkel endimensionell kurva genom detta utrymme. Vi utvecklar flexibla ramar för att studera var och en av dessa aspekter. För att fånga empiriska egenskaper karakteriserar vi en enkel stokastisk generativ modell, en enkelparameter förlängning av Erdős-Rényi slumpmässiga grafer, vars stationära fördelning över subgrafer noga följer den endimensionella koncentrationen av de verkliga sociala graffamiljerna. För de yttre egenskaperna utvecklar vi ett dragbart linjärt program för att begränsa det möjliga utrymmet för subgraffrekvenser genom att utnyttja en verktygslåda med känd extremal grafteori. Tillsammans kastar dessa två kompletterande ramar ljus över en grundläggande fråga om sociala grafer: vilka egenskaper hos sociala grafer är "sociala" egenskaper och vilka egenskaper är "grafegenskaper"? Vi avslutar med en kort demonstration av hur det koordinatsystem vi undersöker också kan användas för att utföra klassificeringsuppgifter och skilja mellan strukturer som uppstår från olika typer av sociala grafer.
Några tidigare arbeten använde till exempel hela spektrumet av grafletfrekvenser för att definiera ett domänoberoende koordinatsystem där samlingar av grafer kan vara kompakt representerade och analyseras inom ett gemensamt utrymme REF.
Subgraph frequencies: mapping the empirical and extremal geography of large graph collections
{'venue': "WWW '13", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}