{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:26:06Z","timestamp":1760243166603,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T00:00:00Z","timestamp":1449532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/H049606\/1"],"award-info":[{"award-number":["EP\/H049606\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fundamental Research Funds for Central Universities","award":["2013XZ11"],"award-info":[{"award-number":["2013XZ11"]}]},{"name":"National Prevention Research Initiative","award":["G0802045"],"award-info":[{"award-number":["G0802045"]}]},{"DOI":"10.13039\/100008303","name":"Department for Employment and Learning","doi-asserted-by":"publisher","award":["M6003CPH"],"award-info":[{"award-number":["M6003CPH"]}],"id":[{"id":"10.13039\/100008303","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Generative algorithms for random graphs have yielded insights into the structure and evolution of real-world networks. Most networks exhibit a well-known set of properties, such as heavy-tailed degree distributions, clustering and community formation. Usually, random graph models consider only structural information, but many real-world networks also have labelled vertices and weighted edges. In this paper, we present a generative model for random graphs with discrete vertex labels and numeric edge weights. The weights are represented as a set of Beta Mixture Models (BMMs) with an arbitrary number of mixtures, which are learned from real-world networks. We propose a Bayesian Variational Inference (VI) approach, which yields an accurate estimation while keeping computation times tractable. We compare our approach to state-of-the-art random labelled graph generators and an earlier approach based on Gaussian Mixture Models (GMMs). Our results allow us to draw conclusions about the contribution of vertex labels and edge weights to graph structure.<\/jats:p>","DOI":"10.3390\/a8041143","type":"journal-article","created":{"date-parts":[[2015,12,9]],"date-time":"2015-12-09T15:21:41Z","timestamp":1449674501000},"page":"1143-1174","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Generating Realistic Labelled, Weighted Random Graphs"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1523-2870","authenticated-orcid":false,"given":"Michael","family":"Davis","sequence":"first","affiliation":[{"name":"Organisation Europ\u00e9ene pour la Recherche Nucl\u00e9aire (CERN), Route de Meyrin 385, 1217 Meyrin, Switzerland"}]},{"given":"Zhanyu","family":"Ma","sequence":"additional","affiliation":[{"name":"Pattern Recognition and Intelligent Systems (PRIS) Lab, Beijing University of Posts and Telecommunications (BUPT), 100876 Beijing, China"}]},{"given":"Weiru","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Electrical and Electronic Engineering and Computer Science, Queen\u2019s University Belfast, University Road, Belfast BT7 1NN, UK"}]},{"given":"Paul","family":"Miller","sequence":"additional","affiliation":[{"name":"School of Electrical and Electronic Engineering and Computer Science, Queen\u2019s University Belfast, University Road, Belfast BT7 1NN, UK"}]},{"given":"Ruth","family":"Hunter","sequence":"additional","affiliation":[{"name":"Centre for Public Health, Queen\u2019s University Belfast, University Road, Belfast BT7 1NN, UK"}]},{"given":"Frank","family":"Kee","sequence":"additional","affiliation":[{"name":"Centre for Public Health, Queen\u2019s University Belfast, University Road, Belfast BT7 1NN, UK"}]}],"member":"1968","published-online":{"date-parts":[[2015,12,8]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of Scaling in Random Networks","volume":"286","author":"Albert","year":"1999","journal-title":"Science"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., and Faloutsos, C. (2012). Graph Mining: Laws, Tools, and Case Studies, Morgan & Claypool Publishers.","DOI":"10.1007\/978-3-031-01903-6"},{"key":"ref_3","first-page":"17","article-title":"On the Evolution of Random Graphs","volume":"5","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., and Faloutsos, C. (2007). Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data.","DOI":"10.1145\/1217299.1217301"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Newman, M. (2010). Networks: An Introduction, OUP.","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., and Faloutsos, C. R-MAT: A Recursive Model for Graph Mining. Proceedings of the 2004 SIAM International Conference on Data Mining, Lake Buena Vista, FL, USA.","DOI":"10.1137\/1.9781611972740.43"},{"key":"ref_7","first-page":"985","article-title":"Kronecker Graphs: An Approach to Modeling Networks","volume":"11","author":"Leskovec","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1198\/016214502388618906","article-title":"Latent Space Approaches to Social Network Analysis","volume":"97","author":"Hoff","year":"2002","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1080\/15427951.2012.625257","article-title":"Multiplicative Attribute Graph Model of Real-World Networks","volume":"8","author":"Kim","year":"2012","journal-title":"Internet Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1080\/01621459.1987.10478385","article-title":"Stochastic Block Models for Directed Graphs","volume":"82","author":"Wang","year":"1987","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_11","unstructured":"Zaki, M.J., Yu, J.X., Ravindran, B., and Pudi, V. (2010). OddBall: Spotting Anomalies in Weighted Graphs, Springer. Lecture Notes in Computer Science."},{"key":"ref_12","unstructured":"Bramer, M., Petridis, M., and Hopgood, A. (2010). On the Usefulness of Weight-Based Constraints in Frequent Subgraph Mining, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10844-013-0299-7","article-title":"Finding the most descriptive substructures in graphs with discrete and numeric labels","volume":"42","author":"Davis","year":"2014","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_14","unstructured":"Cozman, F.G., and Pfeffer, A. (2011). Modeling Social Networks with Node Attributes Using the Multiplicative Attribute Graph Model, AUAI Press."},{"key":"ref_15","unstructured":"Bishop, C.M. (2011). Pattern Recognition and Machine Learning, Springer. [3rd ed.]."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/34.824819","article-title":"Statistical Pattern Recognition: A Review","volume":"22","author":"Jain","year":"2000","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/34.990138","article-title":"Unsupervised Learning of Finite Mixture Models","volume":"24","author":"Figueiredo","year":"2002","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_18","first-page":"121","article-title":"Variational inference for Dirichlet process mixtures","volume":"1","author":"Blei","year":"2005","journal-title":"Bayesian Anal."},{"key":"ref_19","unstructured":"Sch\u00f6lkopf, B., Platt, J.C., and Hoffman, T. (2006). Accelerated Variational Dirichlet Process Mixtures, MIT Press."},{"key":"ref_20","unstructured":"Davis, M., Liu, W., and Miller, P. (2014). New Frontiers in Mining Complex Patterns."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1109\/TSA.2002.805639","article-title":"Bounded support Gaussian mixture modeling of speech spectra","volume":"11","author":"Lindblom","year":"2003","journal-title":"IEEE Transa. Speech Audio Process."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s11222-006-8451-7","article-title":"Practical Bayesian estimation of a finite Beta mixture through Gibbs sampling and its applications","volume":"16","author":"Bouguila","year":"2006","journal-title":"Stat. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2118","DOI":"10.1093\/bioinformatics\/bti318","article-title":"Applications of beta-mixture models in bioinformatics","volume":"21","author":"Ji","year":"2005","journal-title":"Bioinformatics"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ma, Z., and Leijon, A. (2009, January 7\u201310). Beta mixture models and the application to image classification. Proceedings of 16th IEEE International Conference on Image Processing (ICIP), Cairo, Egypt.","DOI":"10.1109\/ICIP.2009.5414043"},{"key":"ref_25","unstructured":"McLachlan, G.J., and Krishnan, T. (1997). The EM Algorithm and Extensions, Wiley. [1st ed.]."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"2160","DOI":"10.1109\/TPAMI.2011.63","article-title":"Bayesian Estimation of Beta Mixture Models with Variational Inference","volume":"33","author":"Ma","year":"2011","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3143","DOI":"10.1016\/j.patcog.2014.04.002","article-title":"Bayesian Estimation of Dirichlet Mixture Model with Variational Inference","volume":"47","author":"Ma","year":"2014","journal-title":"Pattern Recognit."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1214\/aos\/1176344611","article-title":"Conjugate Priors for Exponential Families","volume":"7","author":"Diaconis","year":"1979","journal-title":"Ann. Stat."},{"key":"ref_29","unstructured":"Kostkova, P., Szomszor, M., and Fowler, D. (2011). The Physical Activity Loyalty Card Scheme: Development and Application of a Novel System for Incentivizing Behaviour Change, Springer."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Fagiolo, G. (2007). Clustering in complex directed networks. Phys. Rev. E.","DOI":"10.1103\/PhysRevE.76.026107"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321992.321993","article-title":"Efficient Algorithms for Shortest Paths in Sparse Networks","volume":"24","author":"Johnson","year":"1977","journal-title":"J. ACM"},{"key":"ref_32","unstructured":"Solla, S.A., Leen, T.K., and M\u00fcller, K.R. (1999). A Variational Bayesian Framework for Graphical Models, MIT Press."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Opper, M., and Saad, D. (2001). Advanced Mean Field Methods: Theory and Practice, MIT Press.","DOI":"10.7551\/mitpress\/1100.001.0001"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1008932416310","article-title":"Bayesian parameter estimation via variational methods","volume":"10","author":"Jaakkola","year":"2000","journal-title":"Stat. Comput."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1016\/S0893-6080(02)00040-0","article-title":"Bayesian model search for mixture models based on optimizing variational bounds","volume":"15","author":"Ueda","year":"2002","journal-title":"Neural Netw."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1140\/epjb\/e2004-00316-5","article-title":"Problems with fitting to the power-law distribution","volume":"41","author":"Goldstein","year":"2004","journal-title":"Eur. Phys. J. B Condens. Matter Complex Syst."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/4\/1143\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:53:38Z","timestamp":1760216018000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/8\/4\/1143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,8]]},"references-count":36,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2015,12]]}},"alternative-id":["a8041143"],"URL":"https:\/\/doi.org\/10.3390\/a8041143","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2015,12,8]]}}}