Mikhail Drobyshevskiy
Skip Abstract Section
Skip Supplemental Material SectionAbstract
Random graph (RG) models play a central role in complex networks analysis. They help us to understand, control, and predict phenomena occurring, for instance, in social networks, biological networks, the Internet, and so on.
Despite a large number of RG models presented in the literature, there are few concepts underlying them. Instead of trying to classify a wide variety of very dispersed models, we capture and describe concepts they exploit considering preferential attachment, copying principle, hyperbolic geometry, recursively defined structure, edge switching, Monte Carlo sampling, and so on. We analyze RG models, extract their basic principles, and build a taxonomy of concepts they are based on. We also discuss how these concepts are combined in RG models and how they work in typical applications like benchmarks, null models, and data anonymization.
Supplemental Material
Available for Download
zip
drobyshevskiy.zip (168.8 KB)
Supplemental movie, appendix, image and software files for, Random Graph Modeling: A Survey of the Concepts
- Emmanuel Abbe. 2017. Community detection and stochastic block models: Recent developments. J. Mach. Learn. Res. 18, 1 (2017), 6446--6531.Google Scholar
Digital Library
- William Aiello, Fan Chung, and Linyuan Lu. 2000. A random graph model for massive graphs. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. Acm, 171--180.Google ScholarDigital Library
- Leman Akoglu and Christos Faloutsos. 2009. RTG: A recursive realistic graph generator using random typing. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 13--28.Google ScholarCross Ref
- Réka Albert and Albert-László Barabási. 2002. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 1 (2002), 47.Google ScholarCross Ref
- Vespignani Alessandro and Caldarelli Guido. 2007. Large Scale Structure and Dynamics of Complex Networks: From Information Technology to Finance and Natural Science. Vol. 2. World Scientific.Google ScholarDigital Library
- Frédéric Amblard, Audren Bouadjio-Boulic, Carlos Sureda Gutiérrez, and Benoit Gaudou. 2015. Which models are used in social simulation to generate social networks? A review of 17 years of publications in JASSS. In Proceedings of the 2015 Winter Simulation Conference (WSC’15). IEEE, 4021--4032.Google ScholarCross Ref
- Weihua An. 2016. Fitting ERGMs on big networks. Soc. Sci. Res. 59 (2016), 107--119.Google ScholarCross Ref
- Alex Arenas, Albert Díaz-Guilera, and Conrad J Pérez-Vicente. 2006. Synchronization reveals topological scales in complex networks. Phys. Rev. Lett. 96, 11 (2006), 114102.Google ScholarCross Ref
- Chen Avin, Yuval Lando, and Zvi Lotker. 2010. Radio cover time in hyper-graphs. In Proceedings of the 6th International Workshop on Foundations of Mobile Computing. ACM, 3--12.Google ScholarDigital Library
- Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. 2007. Wherefore art thou r3579x?: Anonymized social networks, hidden patterns, and structural steganography. In Proceedings of the 16th International Conference on World Wide Web. ACM, 181--190.Google ScholarDigital Library
- Shweta Bansal, Shashank Khandelwal, and Lauren Ancel Meyers. 2009. Exploring biological network structure with clustered random networks. BMC Bioinform. 10, 1 (2009), 405.Google ScholarCross Ref
- Albert-László Barabási and Réka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509--512.Google Scholar
- Albert-László Barabási, Erzsebet Ravasz, and Tamas Vicsek. 2001. Deterministic scale-free networks. Physica A 299, 3-4 (2001), 559--564.Google ScholarCross Ref
- Alain Barrat, Marc Barthèlemy, and Alessandro Vespignani. 2008. Dynamical Processes on Complex Networks. Cambridge University Press. DOI:https://doi.org/10.1017/CBO9780511791383Google Scholar
- Marc Barthélemy, Alain Barrat, Romualdo Pastor-Satorras, and Alessandro Vespignani. 2005. Characterization and modeling of weighted networks. Physica A 346, 1--2 (2005), 34--43.Google ScholarCross Ref
- Edward A Bender and E Rodney Canfield. 1978. The asymptotic number of labeled graphs with given degree sequences. J. Combin. Theor. Ser. A 24, 3 (1978), 296--307.Google ScholarCross Ref
- Austin R. Benson, Carlos Riquelme, and Sven Schmit. 2014. Learning multifractal structure in large networks. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 1326--1335.Google ScholarDigital Library
- Noam Berger, Christian Borgs, Jennifer T. Chayes, Raissa M. D’Souza, and Robert D. Kleinberg. 2004. Competition-induced preferential attachment. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 208--221.Google Scholar
- M. M. Bernovskiy and N. N. Kuzyurin. 2012. Random graphs, models and generators of scale-free graphs. In Proceedings of the Institute for System Programming of the RAS 22 (2012).Google Scholar
- Stefano Boccaletti, Ginestra Bianconi, Regino Criado, Charo I. Del Genio, Jesús Gómez-Gardenes, Miguel Romance, Irene Sendina-Nadal, Zhen Wang, and Massimiliano Zanin. 2014. The structure and dynamics of multilayer networks. Phys. Rep. 544, 1 (2014), 1--122.Google ScholarCross Ref
- Béla Bollobás. 2001. Random Graphs. Number 73. Cambridge University Press.Google Scholar
- Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. 2003. Directed scale-free graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 132--139.Google Scholar
- Béla Bollobás and Oliver M. Riordan. 2003. Mathematical results on scale-free random graphs. Handbook of Graphs and Networks: From the Genome to the Internet (2003), 1--34.Google Scholar
- Anthony Bonato. 2008. A Course on the Web Graph. Vol. 89. American Mathematical Soc.Google Scholar
- Anthony Bonato. 2009. A survey of properties and models of on-line social networks. In Proceedings of the 5th International Conference on Mathematical and Computational Models (ICMCM’09). Citeseer.Google Scholar
- Ilaria Bordino, Debora Donato, Aristides Gionis, and Stefano Leonardi. 2008. Mining large networks with subgraph counting. In Proceedings of the 2008 8th IEEE International Conference on Data Mining. IEEE, 737--742.Google ScholarDigital Library
- Karl Bringmann, Ralph Keusch, and Johannes Lengler. 2016. Geometric inhomogeneous random graphs. Theoretical Computer Science 760 (2016), 35--54.Google ScholarCross Ref
- Andries E. Brouwer and Willem H. Haemers. 2011. Spectra of Graphs. Springer Science 8 Business Media.Google Scholar
- Guido Caldarelli. 2007. Scale-Free Networks: Complex Webs in Nature and Technology. Oxford University Press.Google Scholar
- Deepayan Chakrabarti and Christos Faloutsos. 2006. Graph mining: Laws, generators, and algorithms. ACM Comput. Surv. 38, 1 (2006), 2.Google ScholarDigital Library
- Deepayan Chakrabarti and Christos Faloutsos. 2012. Graph Mining: Laws, Tools, and Case Studies. Morgan 8 Claypool. http://dx.doi.org/10.2200/S00449ED1V01Y201209DMK006.Google Scholar
- Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. 2004. R-MAT: A recursive model for graph mining. In Proceedings of the 2004 SIAM International Conference on Data Mining. SIAM, 442--446.Google ScholarCross Ref
- Fan Chung and Linyuan Lu. 2002. The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. U.S.A. 99, 25 (2002), 15879--15882.Google ScholarCross Ref
- Fan Chung and Linyuan Lu. 2002. Connected components in random graphs with given expected degree sequences. Ann. Combin. 6, 2 (2002), 125--145.Google ScholarCross Ref
- Kyrylo Chykhradze, Anton Korshunov, Nazar Buzun, Roman Pastukhov, Nikolay Kuzyurin, Denis Turdakov, and Hangkyu Kim. 2014. Distributed generation of billion-node social graphs with overlapping community structure. In Complex Networks V. Springer, 199--208.Google Scholar
- Ton Coolen, Alessia Annibale, and Ekaterina Roberts. 2017. Generating Random Networks and Graphs. Oxford University Press.Google Scholar
- L. da F. Costa, Francisco A. Rodrigues, Gonzalo Travieso, and Paulino Ribeiro Villas Boas. 2007. Characterization of complex networks: A survey of measurements. Adv. Phys. 56, 1 (2007), 167--242.Google ScholarCross Ref
- Jörn Davidsen, Holger Ebel, and Stefan Bornholdt. 2002. Emergence of a small world from local interactions: Modeling acquaintance networks. Phys. Rev. Lett. 88, 12 (2002), 128701.Google ScholarCross Ref
- Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. 2011. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E 84, 6 (2011), 066106.Google ScholarCross Ref
- Sergey N. Dorogovtsev, Alexander V. Goltsev, and José Ferreira F. Mendes. 2002. Pseudofractal scale-free web. Phys. Rev. E 65, 6 (2002), 066122.Google ScholarCross Ref
- Sergei N. Dorogovtsev and José F. F. Mendes. 2003. Evolution of Networks: From Biological Nets to the Internet and WWW. Oxford University Press, Oxford.Google ScholarDigital Library
- Mikhail Drobyshevskiy, Anton Korshunov, and Denis Turdakov. 2017. Learning and scaling directed networks via graph embedding. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 634--650.Google ScholarCross Ref
- Mikhail Drobyshevskiy, Denis Turdakov, and Sergey Kuznetsov. 2017. Reproducing network structure: A comparative study of random graph generators. In Proceedings of the Ivannikov ISPRAS Open Conference (ISPRAS’17). IEEE, 83--89.Google ScholarCross Ref
- Richard Durrett. 2007. Random Graph Dynamics. Vol. 200. Cambridge University Press, Cambridge.Google Scholar
- Holger Ebel, Lutz-Ingo Mielsch, and Stefan Bornholdt. 2002. Scale-free topology of e-mail networks. Phys. Rev. E 66, 3 (2002), 035103.Google ScholarCross Ref
- Edward M. Lazzarin and Raj Jain. 2011. An overview of the analysis of online social networks. http://snap.stanford.edu/biodata.Google Scholar
- Nicole Eikmeier and David F. Gleich. 2017. Revisiting power-law distributions in spectra of real world networks. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 817--826.Google Scholar
- P. Erdős and A. Rényi. 1959. On random graphs I. Publ. Math. Debrec. 6 (1959), 290--297.Google Scholar
- Paul Erdős and Alfréd Rényi. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 1 (1960), 17--60.Google Scholar
- Alex Fabrikant, Elias Koutsoupias, and Christos H. Papadimitriou. 2002. Heuristically optimized trade-offs: A new paradigm for power laws in the Internet. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 110--122.Google Scholar
- Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On power-law relationships of the internet topology. In ACM SIGCOMM Computer Communication Review, Vol. 29. ACM, 251--262.Google ScholarDigital Library
- Zheng Fang, Jie Wang, Benyuan Liu, and Weibo Gong. 2012. Double Pareto lognormal distributions in complex networks. In Handbook of Optimization in Complex Networks. Springer, 55--80.Google Scholar
- András Faragó. 2009. Structural properties of random graph models. In Proceedings of the 15th Australasian Symposium on Computing: The Australasian Theory-Volume 94. Australian Computer Society, Inc., 131--138.Google ScholarDigital Library
- Bailey K. Fosdick, Daniel B. Larremore, Joel Nishimura, and Johan Ugander. 2018. Configuring random graph models with fixed degree sequences. SIAM Rev. 60, 2 (2018), 315--355.Google ScholarCross Ref
- Tobias Friedrich and Anton Krohmer. 2018. On the diameter of hyperbolic random graphs. SIAM J. Discr. Math. 32, 2 (2018), 1314--1334.Google ScholarCross Ref
- Alan Frieze and Michał Karoński. 2015. Introduction to Random Graphs. Cambridge University Press.Google Scholar
- Edgar N. Gilbert. 1959. Random graphs. Ann. Math. Stat. 30, 4 (1959), 1141--1144.Google ScholarCross Ref
- G. N. Gilbert and L. Hamill. 2009. Social circles: A simple structure for agent-based social network models. J. Artif. Soc. Soc. Simul. 12, 2 (2009).Google Scholar
- Michelle Girvan and Mark E. J. Newman. 2002. Community structure in social and biological networks. Proc. Natl. Acad. Sci. U.S.A. 99, 12 (2002), 7821--7826.Google ScholarCross Ref
- David F. Gleich and Art B. Owen. 2012. Moment-based estimation of stochastic Kronecker graph parameters. Internet Math. 8, 3 (2012), 232--256.Google ScholarCross Ref
- Anna Goldenberg, Alice X. Zheng, Stephen E. Fienberg, Edoardo M. Airoldi, et al. 2009. A survey of statistical network models. Found. Trends Mach. Learn. 2, 2 (2009), 129--233.Google ScholarDigital Library
- Palash Goyal and Emilio Ferrara. 2018. Graph embedding techniques, applications, and performance: A survey. Knowl.-Based Syst. 151 (2018), 78--94.Google ScholarCross Ref
- Mark S. Granovetter. 1977. The strength of weak ties. In Social Networks. Elsevier, 347--367.Google Scholar
- Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. 2012. Random hyperbolic graphs: Degree sequence and clustering. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 573--585.Google ScholarDigital Library
- Alexander Gutfraind, Ilya Safro, and Lauren Ancel Meyers. 2015. Multiscale network generation. In Proceedings of the 18th International Conference on Information Fusion (Fusion’15). IEEE, 158--165.Google Scholar
- Mark S. Handcock, Adrian E. Raftery, and Jeremy M. Tantrum. 2007. Model-based clustering for social networks. J. Roy. Stat. Soc.: Ser. A 170, 2 (2007), 301--354.Google ScholarCross Ref
- Jenine K. Harris. 2013. An Introduction to Exponential Random Graph Modeling. Vol. 173. Sage Publications.Google Scholar
- Lenwood S. Heath and Nidhi Parikh. 2011. Generating random graphs with tunable clustering coefficients. Physica A 390, 23--24 (2011), 4577--4587.Google ScholarCross Ref
- Javier Martın Hernández and Piet Van Mieghem. 2011. Classification of graph metrics. Delft University of Technology, Technical Report (2011), 1--8.Google Scholar
- Oleg U. Ivanov and Sergey O. Bartunov. 2015. Learning representations in directed networks. In Proceedings of the International Conference on Analysis of Images, Social Networks and Texts. Springer, 196--207.Google Scholar
- Svante Janson, Tomasz Łuczak, and Ilkka Norros. 2010. Large cliques in a power-law random graph. J. Appl. Probab. 47, 4 (2010), 1124--1135.Google ScholarCross Ref
- Ralph Keusch. 2018. Geometric Inhomogeneous Random Graphs and Graph Coloring Games. Ph.D. Dissertation. ETH Zurich.Google Scholar
- Marcos Kiwi and Dieter Mitsche. 2015. A bound for the diameter of random hyperbolic graphs. In Proceedings of the Meeting on Analytic Algorithmics and Combinatorics. Society for Industrial and Applied Mathematics, 26--39.Google ScholarCross Ref
- Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew S. Tomkins. 1999. The web as a graph: Measurements, models, and methods. In Proceedings of the International Computing and Combinatorics Conference. Springer, 1--17.Google Scholar
- Eric D. Kolaczyk. 2009. Statistical Analysis of Network Data: Methods and Models (1st ed.). Springer Publishing Company, Incorporated.Google Scholar
- I. N. Kovalenko. 1971. Theory of random graphs. Cybernetics 7, 4 (1971), 575--579.Google ScholarCross Ref
- Pavel L. Krapivsky and Sidney Redner. 2005. Network growth by copying. Phys. Rev. E 71, 3 (2005), 036118.Google ScholarCross Ref
- Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. 2010. Hyperbolic geometry of complex networks. Phys. Rev. E 82, 3 (2010), 036106.Google ScholarCross Ref
- Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, and Eli Upfal. 2000. Stochastic models for the web graph. In Proceedings ofthe 41st Annual Symposium on Foundations of Computer Science, 2000. IEEE, 57--65.Google ScholarCross Ref
- Jérôme Kunegis. 2013. Konect: The koblenz network collection. In Proceedings of the 22nd International Conference on World Wide Web. ACM, 1343--1350.Google ScholarDigital Library
- Jérôme Kunegis, Marcel Blattner, and Christine Moser. 2013. Preferential attachment in online networks: Measurement and explanations. In Proceedings of the 5th Annual ACM Web Science Conference. ACM, 205--214.Google ScholarDigital Library
- Andrea Lancichinetti and Santo Fortunato. 2009. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80, 1 (2009), 016118.Google ScholarCross Ref
- Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. 2008. Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78, 4 (2008), 046110.Google ScholarCross Ref
- Jurij Leskovec, Deepayan Chakrabarti, Jon Kleinberg, and Christos Faloutsos. 2005. Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. In Proceedings of the European Conference on Principles of Data Mining and Knowledge Discovery. Springer, 133--145.Google ScholarCross Ref
- Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. J. Mach. Learn. Res. 11, (Feb. 2010), 985--1042.Google Scholar
- Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2007. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 1 (2007), 2.Google ScholarDigital Library
- Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. 2008. Statistical properties of community structure in large social and information networks. In Proceedings of the 17th International Conference on World Wide Web. ACM, 695--704.Google Scholar
- László Lovász. 2012. Large Networks and Graph Limits. Vol. 60. American Mathematical Soc.Google Scholar
- Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat. 2006. Systematic topology analysis and generation using degree correlations. In ACM SIGCOMM Computer Communication Review, Vol. 36. ACM, 135--146.Google ScholarDigital Library
- Matteo Marsili, Fernando Vega-Redondo, and František Slanina. 2004. The rise and fall of a networked society: A formal model. Proc. Natl. Acad. Sci. U.S.A. 101, 6 (2004), 1439--1442.Google ScholarCross Ref
- Mary McGlohon, Leman Akoglu, and Christos Faloutsos. 2008. Weighted graphs and disconnected components: Patterns and a generator. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 524--532.Google ScholarDigital Library
- Miller McPherson, Lynn Smith-Lovin, and James M. Cook. 2001. Birds of a feather: Homophily in social networks. Annu. Rev. Sociol. 27, 1 (2001), 415--444.Google ScholarCross Ref
- Alberto Medina, Ibrahim Matta, and John Byers. 2000. On the origin of power laws in Internet topologies. ACM SIGCOMM Comput. Commun. Rev. 30, 2 (2000), 18--28.Google ScholarDigital Library
- Ulrich Meyer, Manuel Penschuck, et al. 2017. Large-scale graph generation and big data: An overview on recent results. Bull. EATCS 2, 122 (2017).Google Scholar
- Ron Milo, Nadav Kashtan, Shalev Itzkovitz, Mark E. J. Newman, and Uri Alon. 2003. On the uniform generation of random graphs with prescribed degree sequences. arXiv preprint cond-mat/0312028 (2003).Google Scholar
- Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (2002), 824--827.Google Scholar
- Roland Molontay. 2015. Fractal Characterization of Complex Networks. Ph.D. Dissertation. Department of Stochastics, Budapest University of Technology and Economics.Google Scholar
- Sebastian Moreno, Jennifer Neville, Sergey Kirshner, and SVN Vishwanathan. [n.d.]. Modeling the variance of network populations with mixed Kronecker product graph models. http://snap.stanford.edu/nipsgraphs2010.Google Scholar
- S. Moreno, P. Robles, and J. Neville. 2013. Block kronecker product graph model. In Workshop on Mining and Learning from Graphs.Google Scholar
- Mark Newman. 2010. Networks: An Introduction. Oxford University Press.Google ScholarCross Ref
- Mark Newman, Albert-Laszlo Barabasi, and Duncan J. Watts. 2006. The Structure and Dynamics of Networks. Princeton University Press.Google ScholarDigital Library
- Mark E. J. Newman. 2002. Assortative mixing in networks. Phys. Rev. Lett. 89, 20 (2002), 208701.Google ScholarCross Ref
- Mark E. J. Newman. 2003. The structure and function of complex networks. SIAM Rev. 45, 2 (2003), 167--256.Google ScholarDigital Library
- Mark E. J. Newman. 2004. Analysis of weighted networks. Phys. Rev. E 70, 5 (2004), 056131.Google ScholarCross Ref
- Mark E. J. Newman. 2006. Modularity and community structure in networks. Proc. Natl. Acad. Sci. U.S.A. 103, 23 (2006), 8577--8582.Google ScholarCross Ref
- Christine Leigh Myers Nickel. 2006. Random Dot Product Graphs a Model for Social Networks. Ph.D. Dissertation. The Johns Hopkins University.Google Scholar
- Furuzan Atay Onat, Ivan Stojmenovic, and Halim Yanikomeroglu. 2008. Generating random graphs for the simulation of wireless ad hoc, actuator, sensor, and internet networks. Perv. Mobile Comput. 4, 5 (2008), 597--615.Google ScholarDigital Library
- Gergely Palla, László Lovász, and Tamás Vicsek. 2010. Multifractal network generator. Proc. Natl. Acad. Sci. U.S.A. (2010).Google ScholarCross Ref
- Himchan Park and Min-Soo Kim. 2017. TrillionG: A trillion-scale synthetic graph generator using a recursive vector model. In Proceedings of the 2017 ACM International Conference on Management of Data. ACM, 913--928.Google ScholarDigital Library
- Mathew Penrose. 2003. Random Geometric Graphs. Number 5. Oxford University Press.Google Scholar
- L. Pofsneck, Henning Hofmann, and Ricardo Buettner. 2012. Physical theories of the evolution of online social networks: A discussion impulse. Dynam. Syst. 22 (2012), 4.Google Scholar
- Alex Pothen, Horst D. Simon, and Kang-Pu Liou. 1990. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11, 3 (1990), 430--452.Google ScholarDigital Library
- Raigorodsky. 2011. Models of Random Graphs. Litres.Google Scholar
- Erzsébet Ravasz and Albert-László Barabási. 2003. Hierarchical organization in complex networks. Phys. Rev. E 67, 2 (2003), 026112.Google ScholarCross Ref
- Hernán D. Rozenfeld, Shlomo Havlin, and Daniel Ben-Avraham. 2007. Fractal and transfractal recursive scale-free nets. New J. Phys. 9, 6 (2007), 175.Google ScholarCross Ref
- Alessandra Sala, Lili Cao, Christo Wilson, Robert Zablit, Haitao Zheng, and Ben Y. Zhao. 2010. Measurement-calibrated graph models for social network experiments. In Proceedings of the 19th International Conference on World Wide Web. ACM, 861--870.Google Scholar
- Erin N. Sawardecker, Marta Sales-Pardo, and Luıs A. Nunes Amaral. 2009. Detection of node group membership in networks with group overlap. Eur. Phys. J. B 67, 3 (2009), 277--284.Google ScholarCross Ref
- Comandur Seshadhri, Tamara G. Kolda, and Ali Pinar. 2012. Community structure and scale-free collections of Erdős-Rényi graphs. Phys. Rev. E 85, 5 (2012), 056109.Google ScholarCross Ref
- Comandur Seshadhri, Ali Pinar, and Tamara G. Kolda. 2011. An in-depth study of stochastic Kronecker graphs. In Proceedings of the IEEE 11th International Conference on Data Mining (ICDM’11). IEEE, 587--596.Google Scholar
- Mukund Seshadri, Sridhar Machiraju, Ashwin Sridharan, Jean Bolot, Christos Faloutsos, and Jure Leskove. 2008. Mobile call graphs: Beyond power-law and lognormal distributions. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 596--604.Google ScholarDigital Library
- Christian L. Staudt, Michael Hamann, Ilya Safro, Alexander Gutfraind, and Henning Meyerhenke. 2016. Generating scaled replicas of real-world complex networks. In Proceedings of the International Workshop on Complex Networks and Their Applications. Springer, Cham, 17--28.Google Scholar
- Lionel Tabourier, Camille Roth, and Jean-Philippe Cointet. 2011. Generating constrained random graphs using multiple edge switches. J. Exp. Algor. 16 (2011), 1--7.Google Scholar
- Richard Taylor. 1981. Constrained switchings in graphs. In Combinatorial Mathematics VIII. Springer, 314--336.Google Scholar
- Riitta Toivonen, Lauri Kovanen, Mikko Kivelä, Jukka-Pekka Onnela, Jari Saramäki, and Kimmo Kaski. 2009. A comparative study of social network models: Network evolution models and nodal attribute models. Soc. Netw. 31, 4 (2009), 240--254.Google ScholarCross Ref
- Riitta Toivonen, Jukka-Pekka Onnela, Jari Saramäki, Jörkki Hyvönen, and Kimmo Kaski. 2006. A model for social networks. Physica A 371, 2 (2006), 851--860.Google ScholarCross Ref
- Remco Van Der Hofstad. 2014. Random Graphs and Complex Networks. Cambridge University press.Google Scholar
- Marijtje A. J. Van Duijn, Krista J. Gile, and Mark S. Handcock. 2009. A framework for the comparison of maximum pseudo-likelihood and maximum likelihood estimation of exponential family random graph models. Soc. Netw. 31, 1 (2009), 52--62.Google ScholarCross Ref
- Piet Van Mieghem, Jasmina Omic, and Robert Kooij. 2009. Virus spread in networks. IEEE/ACM Trans. Netw. 17, 1 (2009), 1--14.Google ScholarDigital Library
- Alexei Vázquez. 2003. Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Phys. Rev. E 67, 5 (2003), 056104.Google ScholarCross Ref
- Venkat Venkatasubramanian, Santhoji Katare, Priyan R. Patkar, and Fang-ping Mu. 2004. Spontaneous emergence of complex optimal networks through evolutionary adaptation. Comput. Chem. Eng. 28, 9 (2004), 1789--1798.Google ScholarCross Ref
- Duncan J. Watts and Steven H. Strogatz. 1998. Collective dynamics of ’small-world’ networks. Nature 393, 6684 (1998), 440.Google Scholar
- Bernard M. Waxman. 1988. Routing of multipoint connections. IEEE J. Select. Areas Commun. 6, 9 (1988), 1617--1622.Google ScholarDigital Library
- Anatol Wegner. 2011. Random Graphs with Motifs. https://www.mis.mpg.de/preprints/2011/preprint2011_61.pdf.Google Scholar
- Ling Heng Wong, Philippa Pattison, and Garry Robins. 2006. A spatial model for social networks. Physica A 360, 1 (2006), 99--120.Google ScholarCross Ref
- Lifeng Xi, Lihong Wang, Songjing Wang, Zhouyu Yu, and Qin Wang. 2017. Fractality and scale-free effect of a class of self-similar networks. Physica A 478 (2017), 31--40.Google ScholarCross Ref
- Jaewon Yang and Jure Leskovec. 2014. Structure and overlaps of ground-truth communities in networks. ACM Trans. Intell. Syst. Technol. 5, 2 (2014), 26.Google ScholarDigital Library
- Jaewon Yang and Jure Leskovec. 2015. Defining and evaluating network communities based on ground-truth. Knowl. Inf. Syst. 42, 1 (2015), 181--213.Google ScholarDigital Library
- Xiaowei Ying and Xintao Wu. 2009. Graph generation with prescribed feature constraints. In Proceedings of the 2009 SIAM International Conference on Data Mining. SIAM, 966--977.Google ScholarCross Ref
- Soon-Hyung Yook, Hawoong Jeong, and Albert-László Barabási. 2002. Modeling the Internet’s large-scale topology. Proc. Natl. Acad. Sci. U.S.A. 99, 21 (2002), 13382--13386.Google ScholarCross Ref
- J. W. Zhang and Y. C. Tay. 2016. GSCALER: Synthetically scaling a given graph. In Proceedings of the International Conference on Extending Database Technology (EDBT’16). 53--64.Google Scholar
Index Terms
- Random Graph Modeling: A Survey of the Concepts
Recommendations
Automated design of random dynamic graph models
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference CompanionDynamic graphs are an essential tool for representing a wide variety of concepts that change over time. Examples include modeling the evolution of relationships and communities in a social network or tracking the activity of users within an enterprise ...
Automated design of random dynamic graph models for enterprise computer network applications
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference CompanionDynamic graphs are an essential tool for representing a wide variety of concepts that change over time. In the case of static graph representations, random graph models are often useful for analyzing and predicting the characteristics of a given ...
The random planar graph process
We consider the following variant of the classical random graph process introduced by Erdýs and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the ...
Comments