Abstrakt. Hur kan vi skapa realistiska grafer? Hur kan vi dessutom göra det med en matematiskt dragbar modell som gör det möjligt att noggrant analysera deras egenskaper? Verkliga grafer lyder en lång lista med överraskande egenskaper: Tunga svansar för den in- och utgraderade fördelningen; tunga svansar för eigenvärden och eigenvektorer; små diametrar; och den nyligen upptäckta "Densification Power Law" (DPL). Alla publicerade grafgeneratorer antingen misslyckas med att matcha flera av ovanstående egenskaper, är mycket komplicerade att analysera matematiskt, eller båda. Här föreslår vi en grafgenerator som är matematiskt dragbar och matchar denna samling av egenskaper. Huvudidén är att använda en icke-standard matris operation, Kronecker produkten, för att generera grafer som vi kallar "Kronecker grafer". Vi visar att Kronecker grafer naturligt lyder alla ovanstående egenskaper; i själva verket kan vi rigoröst bevisa att de gör det. Vi tillhandahåller också empiriska bevis som visar att de mycket väl kan härma flera verkliga grafer.
I ett uppföljande dokument REF introducerade vi Kronecker Graphs, en matematiskt dragbar modell av graftillväxt och evolution.
Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication
{'venue': 'PKDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}