Kronecker graph

Kronecker graphs are a construction for generating graphs for modeling systems. The method constructs a sequence of graphs from a small base graph by iterating the Kronecker product.[1] A variety of generalizations of Kronecker graphs exist.[2]

The Graph500 benchmark for supercomputers is based on the use of a stochastic version of Kronecker graphs. Stochastic kronecker graph is a kronecker graph with each component of the matrix made by real numbers between 0 and 1. The stochastic version of kronecker graph eliminates the staircase effect, which happens due to large multiplicity of kronecker graph.[3]

References

Leskovec, Jure; Chakrabarti, Deepayan; Kleinberg, Jon; Faloutsos, Christos; Ghahramani, Zoubin (2010), "Kronecker graphs: an approach to modeling networks", Journal of Machine Learning Research, 11: 985–1042, arXiv:0812.4905, Bibcode:2008arXiv0812.4905L, MR 2600637.
Bodine, E.; Hassibi, B.; Wierman, A. (2009-09-01). Generalizing Kronecker graphs in order to model searchable networks. 47th Annual Allerton Conference on Communication, Control, and Computing, 2009. Allerton 2009. pp. 194–201. doi:10.1109/ALLERTON.2009.5394816. ISBN 978-1-4244-5870-7.
Seshadhri, C.; Pinar, Ali; Kolda, Tamara G. (2013-05-01). "An In-depth Analysis of Stochastic Kronecker Graphs". J. ACM. 60 (2): 13:1–13:32. arXiv:1102.5046. doi:10.1145/2450142.2450149. ISSN 0004-5411.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Leskovec, Jure; Chakrabarti, Deepayan; Kleinberg, Jon; Faloutsos, Christos; Ghahramani, Zoubin (2010), "Kronecker graphs: an approach to modeling networks", Journal of Machine Learning Research, 11: 985–1042, arXiv:0812.4905, Bibcode:2008arXiv0812.4905L, MR 2600637.

[2] Bodine, E.; Hassibi, B.; Wierman, A. (2009-09-01). Generalizing Kronecker graphs in order to model searchable networks. 47th Annual Allerton Conference on Communication, Control, and Computing, 2009. Allerton 2009. pp. 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). "An In-depth Analysis of Stochastic Kronecker Graphs". J. ACM. 60 (2): 13:1–13:32. arXiv:1102.5046. doi:10.1145/2450142.2450149. ISSN 0004-5411.