Jump to content

Kronecker graph

From Wikipedia, the free encyclopedia

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

[edit]
  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, archived from the original on 2016-07-29, retrieved 2016-07-05.
  2. ^ Bodine, E.; Hassibi, B.; Wierman, A. (2009-09-01). "Generalizing Kronecker graphs in order to model searchable networks". 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton). pp. 194–201. doi:10.1109/ALLERTON.2009.5394816. ISBN 978-1-4244-5870-7. S2CID 12692876. Archived from the original on 2020-09-17. Retrieved 2024-05-03.
  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. S2CID 6491828.