En känd brist på många populära slumpmässiga graf modeller är att Aldous-Hoover Theorem garanterar dessa grafer är täta med sannolikhet en; det vill säga antalet kanter växer fyrsidigt med antalet noder. Detta beteende anses orealistiskt i observerade grafer. Vi definierar ett begrepp om kant utbytbarhet för slumpmässiga grafer i motsats till den etablerade begreppet oändlig utbytbarhet för slumpmässiga grafer-som traditionellt har förlitat sig på utbytbarhet av noder (snarare än kanter) i en graf. Vi visar att, till skillnad från node utbytbarhet, kant utbytbarhet omfattar modeller som är kända för att ge en projektiv sekvens av slumpmässiga grafer som kringgår Aldous-Hoover Theorem och uppvisar gleshet, dvs sub-kvadratisk tillväxt av antalet kanter med antalet noder. Vi visar hur kantutbyte av grafer naturligt förhåller sig till befintliga begrepp om utbytbarhet från klusterbildning (alias. partitioner) och andra välbekanta kombinatoriska strukturer.
En variant av de kant utbytbara grafer som är särskilt relevant för vårt arbete är de flera kanter per steg kant utbytbara nätverk föreslås av REF.
Edge-exchangeable graphs and sparsity
{'venue': 'NIPS', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}