Document Zbl 1440.13114

Ogawa, Mitsunori; Hara, Hisayuki; Takemura, Akimichi

Graver basis for an undirected graph and its application to testing the beta model of random graphs. (English) Zbl 1440.13114

Ann. Inst. Stat. Math. 65, No. 1, 191-212 (2013).

Summary: In this paper, we give an explicit and algorithmic description of Graver basis for the toric ideal associated with a simple undirected graph and apply the basis for testing the beta model of random graphs by Markov chain Monte Carlo method.

Cited in 11 Documents

MSC:

13P10	Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
05C80	Random graphs (graph-theoretic aspects)
62H17	Contingency tables

Keywords:

Markov basis; Markov chain Monte Carlo; Rasch model; toric ideal

Software:

4ti2

Cite Review PDF

Full Text: DOI arXiv

References:

[1]	Blitzstein J., Diaconis P. (2010) A sequential importance sampling algorithm for generating random graphs with prescribed degrees. Internet Mathematics. 6(4): 489–522 · Zbl 1238.60084 · doi:10.1080/15427951.2010.557277
[2]	Chatterjee S., Diaconis P., Sly A. (2011) Random graphs with a given degree sequence. The Annals of Applied Probability. 21(4): 1400–1435 · Zbl 1234.05206 · doi:10.1214/10-AAP728
[3]	Diaconis P., Sturmfels B. (1998) Algebraic algorithms for sampling from conditional distributions. The Annals of Statistics. 26(1): 363–397 · Zbl 0952.62088 · doi:10.1214/aos/1030563990
[4]	Drton M., Sturmfels B., Sullivant S. (2009). Lectures on algebraic statistics, Oberwolfach seminars, vol 39. Basel: Birkhäuser Verlag. · Zbl 1166.13001
[5]	Erdös P., Rényi A. (1960) On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences. 5: 17–61
[6]	Goldenberg A., Zheng A. X., Fienberg S. E., Airoldi E. M. (2009) A survey of statistical network models. Foundations and Trends in Machine Learning. 2: 129–233 · Zbl 1184.68030 · doi:10.1561/2200000005
[7]	Hara, H., Takemura, A. (2010). Connecting tables with zero-one entries by a subset of a markov basis. In: Algebraic methods in statistics and probability II, Contemporary mathematics, vol 516 (pp. 199–213), Providence, RI: American Mathematical Society. · Zbl 1196.62073
[8]	Holland P., Leinhardt S. (1981) An exponential family of probability distribution for directed graphs. Journal of American Statistical Society. 76(373): 33–50 · Zbl 0457.62090 · doi:10.1080/01621459.1981.10477598
[9]	Linacre J. M. (1994) Many-facet Rasch Measurement, 2nd ed. MESA Press, Chicago
[10]	Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Review, 45(2), 167–256 (electronic). · Zbl 1029.68010
[11]	Ohsugi H., Hibi T. (1999a) Koszul bipartite graphs. Advances in Applied Mathematics. 22(1): 25–28 · Zbl 0916.05046 · doi:10.1006/aama.1998.0615
[12]	Ohsugi H., Hibi T. (1999b) Toric ideals generated by quadratic binomials. Journal of Algebra. 218(2): 509–527 · Zbl 0943.13014 · doi:10.1006/jabr.1999.7918
[13]	Ohsugi H., Hibi T. (2005) Indispensable binomials of finite graphs. Journal of Algebra and Its Applications. 4(4): 421–434 · Zbl 1093.13020 · doi:10.1142/S0219498805001265
[14]	Onn, S. (2010). Nonlinear Discrete Optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society (EMS), Zürich (an algorithmic theory). · Zbl 1219.90003
[15]	Park J., Newman M.E.J. (2004) Statistical mechanics of networks. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics. 70(6): 066117 · doi:10.1103/PhysRevE.70.066117
[16]	Petrović, S., Rinaldo, A., Fienberg, S. E. (2010). Algebraic statistics for a directed random graph model with reciprocation. In: Algebraic methods in statistics and probability II, Contemporary mathematics, vol 516 (pp. 261–283) Providence, RI: American Mathematical Society. · Zbl 1197.13025
[17]	Rasch G. (1980) Probabilistic Models for Some Intelligence and Attainment Tests. University of Chicago Press, Chicago
[18]	Reyes E., Tatakis C., Thoma A. (2012) Minimal generators of toric ideals of graphs. Advances in Applied Mathematics. 48(1): 64–78 · Zbl 1266.14041
[19]	Solomonoff R., Rapoport A. (1951) Connectivity of random nets. Bulletin of Mathematical Biology. 13: 107–117
[20]	Sturmfels, B. (1996). Gröbner Bases and Convex Polytopes, University Lecture Series, vol 8. Providence, RI: American Mathematical Society. · Zbl 0856.13020
[21]	4ti2 team (2008). 4ti2–a software package for algebraic, geometric and combinatorial problems on linear spaces. Available at http://www.4ti2.de .
[22]	Ulanowicz, R. E. (2005). Ecosystem network analysis web page. http://www.cbl.umces.edu/\(\sim\)ulan/ntwk/network.html .
[23]	Wattz D. J., Strogatz S. H. (1998) Collective dynamics of small-world networks. Nature. 393: 440–442 · Zbl 1368.05139 · doi:10.1038/30918

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.