Analysen av massiva grafer håller nu på att bli en mycket viktig del av vetenskap och industriell forskning. Detta har lett till konstruktion av ett stort antal grafmodeller, var och en med sina egna fördelar. Modellen Stochastic Kronecker Graph (SKG) har valts av Graph500 styrgruppen för att skapa superdatorriktmärken för grafalgoritmer. De viktigaste orsakerna till detta är dess enkla parallellisering och förmåga att spegla verkliga data. Även om SKG är lätt att genomföra, finns det liten förståelse för egenskaperna och beteendet hos denna modell. Vi visar att den parallella varianten av den kantkonfigurationsmodell som ges av Chung och Lu (kallas CL) i hög grad liknar SKG-modellen. Grafegenskaperna hos ett SKG är extremt nära egenskaperna hos ett CL-diagram som genereras med lämpliga parametrar. Den slutliga sannolikhetsmatrisen som används av SKG är nästan identisk med den för en CL-modell. Detta innebär att den graffördelning som SKG representerar är nästan densamma som den som ges av en CL-modell. Vi visar också att när det gäller montering av verkliga data, CL utför såväl som SKG baserat på empiriska studier av grafegenskaper. CL har den extra fördelen av en trivialt enkel monteringsprocedur och exakt matchar examensfördelningen. Våra resultat tyder på att användare av SKG-modellen bör överväga CL-modellen på grund av dess liknande egenskaper, enklare struktur och förmåga att passa ett bredare utbud av gradfördelningar. CL är åtminstone en bra kontrollmodell att jämföra med.
Grafer som genereras av Chung-Lu modellen och SKG modellen är i själva verket mycket liknande REF.
The Similarity between Stochastic Kronecker and Chung-Lu Graph Models
{'venue': 'SDM12: Proceedings of the Twelfth SIAM International Conference on Data Mining, pp. 1071-1082, April 2012', 'journal': None, 'mag_field_of_study': ['Computer Science']}