Kroneckerův graf - Kronecker graph

Kroneckerovy grafy jsou konstrukcí pro generování grafy pro modelování systémů. Metoda konstruuje posloupnost grafů z malého základního grafu iterací Produkt Kronecker.[1] Existuje celá řada zobecnění Kroneckerových grafů.[2]

The Graph500 benchmark pro superpočítače je založen na použití stochastické verze grafů Kronecker. Stochastický kroneckerův graf je kroneckerův graf, přičemž každá složka matice je tvořena reálnými čísly mezi 0 a 1. Stochastická verze kroneckerova grafu eliminuje efekt schodiště, ke kterému dochází díky velké multiplicitě kroneckerova grafu.[3]

Reference

  1. ^ Leskovec, Jure; Chakrabarti, Deepayan; Kleinberg, Jon; Faloutsos, Christos; Ghahramani, Zoubin (2010), „Grafy Kronecker: přístup k modelování sítí“, Journal of Machine Learning Research, 11: 985–1042, arXiv:0812.4905, Bibcode:2008arXiv0812.4905L, PAN  2600637.
  2. ^ Bodine, E .; Hassibi, B .; Wierman, A. (2009-09-01). Zobecnění grafů Kronecker za účelem modelování prohledávatelných sítí. 47. výroční konference Allerton o komunikaci, řízení a práci na počítači, 2009. Allerton 2009. 194–201. doi:10.1109 / ALLERTON.2009.5394816. ISBN  978-1-4244-5870-7.
  3. ^ Seshadhri, C .; Pinar, Ali; Kolda, Tamara G. (2013-05-01). "Hloubková analýza stochastických kroneckerových grafů". J. ACM. 60 (2): 13:1–13:32. arXiv:1102.5046. doi:10.1145/2450142.2450149. ISSN  0004-5411.