Random Graphs

近年, random simplicial complex やより一般の random object のトポロジーが盛んに研究されているが, その起源となったのは random graph の研究, だと思う。

Kozlov の [Koz10] や Babson らの [BHK11] によると, random graph の研究としては Erdős と Rényi の結果 [ER59; ER60] が有名らしい。

Kahle の survey [Kah14] の最初に歴史的なことがまとめられている。その最初に引用されている Singer の Interview [RS05] によると, Singer は “statistical topology” の出現を予言したらしい。Adler らの [YSA17] の §1.2 にも簡単に歴史についてまとめられている。

Erdős-Rényi model の他にも様々なモデルが提案されている。 目についたものを以下に挙げる:

• Watts-Strogatz model ([WS98])
• Barabási-Albert model ([BA99; AB02])
• Bohman-Frieze process (Kangと Perkinsと Spencer [KPS13; KPS15])
• inhomogeneous random graph model (Söderberg [Söd02]) と Bollobas, Janson, Riordan [BJR07] によるその拡張
• Panafieu と Ravelomanana [PR15] の random multigraph
• stochastic block model (AbbeとSandon [AS15])
• Bienvenu, Débarre, Lambert の生物学の問題に基づいたモデル [BDL19]

Gromov と Guth [GG12] によると, random graph は本質的には expander であるらしい。これは, Kolmogorov と Barzdin [Kol93] の observation だそうである。

Random graph の neighborhood complex や clique complex のトポロジーについては, Kahle が [Kah07; Kah09] で調べている。

グラフからは, simplicial complex 以外にも様々な幾何学的, あるいは代数的対象が定義されるので, それらのホモロジーなどを調べるという問題が考えられる。

例えば, Costa と Farber は, right-angled Artin group を [CF11] で考え, そのBetti数などを調べている。 Michael Davis と Kahle [DK14] は, より一般に, graph product のホモロジーを調べている。

グラフからは多面体を作ることができるので, それらの random 版の組み合せ論的構造を考えることもできる。 例えば, symmetric edge polytope については, Kahle らにより [BBK] で調べられている。

他にもグラフや simplicial complex から作られるものについては, 基本的に何でも“random 〜” が考えられる。

References

[AB02]

Réka Albert and Albert-László Barabási. “Statistical mechanics of complex networks”. In: Rev. Modern Phys. 74.1 (2002), pp. 47–97. url: https://doi.org/10.1103/RevModPhys.74.47.

[AS15]

Emmanuel Abbe and Colin Sandon. “Community detection in general stochastic block models: fundamental limits and efficient algorithms for recovery”. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science—FOCS 2015. IEEE Computer Soc., Los Alamitos, CA, 2015, pp. 670–688. arXiv: 1503.00609. url: https://doi.org/10.1109/FOCS.2015.47.

[BA99]

Albert-László Barabási and Réka Albert. “Emergence of scaling in random networks”. In: Science 286.5439 (1999), pp. 509–512. url: https://doi.org/10.1126/science.286.5439.509.

[BBK]

Benjamin Braun, Kaitlin Bruegge, and Matthew Kahle. Facets of Random Symmetric Edge Polytopes, Degree Sequences, and Clustering. arXiv: 2204.07239.

[BDL19]

François Bienvenu, Florence Débarre, and Amaury Lambert. “The split-and-drift random graph, a null model for speciation”. In: Stochastic Process. Appl. 129.6 (2019), pp. 2010–2048. arXiv: 1706. 01015. url: https://doi.org/10.1016/j.spa.2018.06.009.

[BHK11]

Eric Babson, Christopher Hoffman, and Matthew Kahle. “The fundamental group of random 2-complexes”. In: J. Amer. Math. Soc. 24.1 (2011), pp. 1–28. arXiv: 0711 . 2704. url: http://dx.doi.org/10.1090/S0894-0347-2010-00677-7.

[BJR07]

Béla Bollobás, Svante Janson, and Oliver Riordan. “The phase transition in inhomogeneous random graphs”. In: Random Structures Algorithms 31.1 (2007), pp. 3–122. arXiv: math/0504589. url: https://doi.org/10.1002/rsa.20168.

[CF11]

Armindo Costa and Michael Farber. “Topology of random right angled Artin groups”. In: J. Topol. Anal. 3.1 (2011), pp. 69–87. arXiv: 0909.0887. url: https://doi.org/10.1142/S1793525311000490.

[DK14]

Michael W. Davis and Matthew Kahle. “Random graph products of finite groups are rational duality groups”. In: J. Topol. 7.2 (2014), pp. 589–606. arXiv: 1210 . 4577. url: https://doi.org/10.1112/jtopol/jtt047.

[ER59]

P. Erdős and A. Rényi. “On random graphs. I”. In: Publ. Math. Debrecen 6 (1959), pp. 290–297.

[ER60]

P. Erdős and A. Rényi. “On the evolution of random graphs”. In: Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), pp. 17–61.

[GG12]

Misha Gromov and Larry Guth. “Generalizations of the Kolmogorov-Barzdin embedding estimates”. In: Duke Math. J. 161.13 (2012), pp. 2549–2603. arXiv: 1103.3423. url: https://doi.org/10.1215/00127094-1812840.

[Kah07]

Matthew Kahle. “The neighborhood complex of a random graph”. In: J. Combin. Theory Ser. A 114.2 (2007), pp. 380–387. arXiv: math/ 0512077. url: https://doi.org/10.1016/j.jcta.2006.05.004.

[Kah09]

Matthew Kahle. “Topology of random clique complexes”. In: Discrete Math. 309.6 (2009), pp. 1658–1671. arXiv: math/0605536. url: https://doi.org/10.1016/j.disc.2008.02.037.

[Kah14]

Matthew Kahle. “Topology of random simplicial complexes: a survey”. In: Algebraic topology: applications and new directions. Vol. 620. Contemp. Math. Amer. Math. Soc., Providence, RI, 2014, pp. 201–221. arXiv: 1301.7165. url: https://doi.org/10.1090/conm/620/12367.

[Kol93]

A. N. Kolmogorov. Selected works of A. N. Kolmogorov. Vol. III. Vol. 27. Mathematics and its Applications (Soviet Series). Information theory and the theory of algorithms, With a biography of Kolmogorov by N. N. Bogolyubov, B. V. Gnedenko and S. L. Sobolev, With commentaries by R. L. Dobrushin, A. Kh. Shen\('\), V. M. Tikhomirov, Ya. M. Barzdin, Ya. G. Sinaı̆, V. A. Uspenski [V. A. Uspenskiı̆] and A. L. Semyonov, Edited by A. N. Shiryayev [A. N. Shiryaev], Translated from the 1987 Russian original by A. B. Sossinsky [A. B. Sosinskiı̆]. Dordrecht: Kluwer Academic Publishers Group, 1993, pp. xxvi+275. isbn: 90-277-2798-8.

[Koz10]

Dmitry N. Kozlov. “The threshold function for vanishing of the top homology group of random \(d\)-complexes”. In: Proc. Amer. Math. Soc. 138.12 (2010), pp. 4517–4527. arXiv: 0904.1652. url: http://dx.doi.org/10.1090/S0002-9939-2010-10596-8.

[KPS13]

Mihyun Kang, Will Perkins, and Joel Spencer. “The Bohman-Frieze process near criticality”. In: Random Structures Algorithms 43.2 (2013), pp. 221–250. arXiv: 1106.0484. url: https://doi.org/10.1002/rsa.20437.

[KPS15]

Mihyun Kang, Will Perkins, and Joel Spencer. “Erratum to “The Bohman-Frieze process near criticality” [ 3085769]”. In: Random Structures Algorithms 46.4 (2015), p. 801. url: https://doi.org/10.1002/rsa.20588.

[PR15]

Élie de Panafieu and Vlady Ravelomanana. “Analytic description of the phase transition of inhomogeneous multigraphs”. In: European J. Combin. 48 (2015), pp. 186–197. arXiv: 1409 . 8424. url: https://doi.org/10.1016/j.ejc.2015.02.020.

[RS05]

Martin Raussen and Christian Skau. “Interview with Michael Atiyah and Isadore Singer”. In: Notices Amer. Math. Soc. 52.2 (2005), pp. 225–233.

[Söd02]

Bo Söderberg. “General formalism for inhomogeneous random graphs”. In: Phys. Rev. E (3) 66.6 (2002), pp. 066121, 6. url: http://dx.doi.org/10.1103/PhysRevE.66.066121.

[WS98]

Duncan J. Watts and Steven H. Strogatz. “Collective dynamics of ‘small-world’ networks”. In: Nature 393.6684 (1998), pp. 440–442.

[YSA17]

D. Yogeshwaran, Eliran Subag, and Robert J. Adler. “Random geometric complexes in the thermodynamic regime”. In: Probab. Theory Related Fields 167.1-2 (2017), pp. 107–142. arXiv: 1403. 1164. url: https://doi.org/10.1007/s00440-015-0678-9.