×

Generating realistic labelled, weighted random graphs. (English) Zbl 1461.05208

Summary: 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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C80 Random graphs (graph-theoretic aspects)
62F15 Bayesian inference

Software:

KronFit; PRMLT; OddBall
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Barabási, A.L.; Albert, R.; Emergence of Scaling in Random Networks; Science: 1999; Volume 286 ,509-512. · Zbl 1226.05223
[2] Chakrabarti, D.; Faloutsos, C.; ; Graph Mining: Laws, Tools, and Case Studies: San Rafael, CA, USA 2012; .
[3] Erdős, P.; Rényi, A.; On the Evolution of Random Graphs; Publ. Math. Inst. Hung. Acad. Sci.: 1960; Volume 5 ,17-61.
[4] Leskovec, J.; Kleinberg, J.; Faloutsos, C.; Graph evolution: Densification and shrinking diameters; ACM Trans. Knowl. Discov. Data: 2007; .
[5] Newman, M.; ; Networks: An Introduction: New York, NY, USA 2010; . · Zbl 1195.94003
[6] Chakrabarti, D.; Zhan, Y.; Faloutsos, C.; R-MAT: A Recursive Model for Graph Mining; Proceedings of the 2004 SIAM International Conference on Data Mining: 2004; ,442-446.
[7] Leskovec, J.; Chakrabarti, D.; Kleinberg, J.M.; Faloutsos, C.; Ghahramani, Z.; Kronecker Graphs: An Approach to Modeling Networks; J. Mach. Learn. Res.: 2010; Volume 11 ,985-1042. · Zbl 1242.05256
[8] Hoff, P.D.; Raftery, A.E.; Handcock, M.S.; Latent Space Approaches to Social Network Analysis; J. Am. Stat. Assoc.: 2002; Volume 97 ,1090-1098. · Zbl 1041.62098
[9] Kim, M.; Leskovec, J.; Multiplicative Attribute Graph Model of Real-World Networks; Internet Math.: 2012; Volume 8 ,113-160. · Zbl 1245.05119
[10] Wang, Y.; Wong, G.; Stochastic Block Models for Directed Graphs; J. Am. Stat. Assoc.: 1987; Volume 82 ,8-19.
[11] Akoglu, L.; McGlohon, M.; Faloutsos, C.; ; OddBall: Spotting Anomalies in Weighted Graphs: Berlin, Germany 2010; Volume Volume 6119 ,410-421.
[12] Eichinger, F.; Huber, M.; Böhm, K.; ; On the Usefulness of Weight-Based Constraints in Frequent Subgraph Mining: Berlin, Germany 2010; ,65-78. · Zbl 1209.68365
[13] Davis, M.; Liu, W.; Miller, P.; Finding the most descriptive substructures in graphs with discrete and numeric labels; J. Intell. Inf. Syst.: 2014; Volume 42 ,307-332.
[14] Kim, M.; Leskovec, J.; ; Modeling Social Networks with Node Attributes Using the Multiplicative Attribute Graph Model: Arlington, VA, USA 2011; ,400-409.
[15] Bishop, C.M.; ; Pattern Recognition and Machine Learning: New York, NY, USA 2011; .
[16] Jain, A.K.; Duin, R.P.W.; Mao, J.; Statistical Pattern Recognition: A Review; IEEE Trans. Pattern Anal. Mach. Intell.: 2000; Volume 22 ,4-37.
[17] Figueiredo, M.A.T.; Jain, A.K.; Unsupervised Learning of Finite Mixture Models; IEEE Trans. Pattern Anal. Mach. Intell.: 2002; Volume 24 ,381-396.
[18] Blei, D.M.; Jordan, M.I.; Variational inference for Dirichlet process mixtures; Bayesian Anal.: 2005; Volume 1 ,121-144. · Zbl 1331.62259
[19] Kurihara, K.; Welling, M.; Vlassis, N.A.; ; Accelerated Variational Dirichlet Process Mixtures: Cambridge, MA, USA 2006; ,761-768.
[20] Davis, M.; Liu, W.; Miller, P.; Agwan: A Generative Model for Labelled, Weighted Graphs; New Frontiers in Mining Complex Patterns: 2014; ,181-200.
[21] Lindblom, J.; Samuelsson, J.; Bounded support Gaussian mixture modeling of speech spectra; IEEE Transa. Speech Audio Process.: 2003; Volume 11 ,88-99.
[22] Bouguila, N.; Ziou, D.; Monga, E.; Practical Bayesian estimation of a finite Beta mixture through Gibbs sampling and its applications; Stat. Comput.: 2006; Volume 16 ,215-225.
[23] Ji, Y.; Wu, C.; Liu, P.; Wang, J.; Coombes, K.R.; Applications of beta-mixture models in bioinformatics; Bioinformatics: 2005; Volume 21 ,2118-2122.
[24] Ma, Z.; Leijon, A.; Beta mixture models and the application to image classification; Proceedings of 16th IEEE International Conference on Image Processing (ICIP): ; ,2045-2048.
[25] McLachlan, G.J.; Krishnan, T.; ; The EM Algorithm and Extensions: New York, NY, USA 1997; . · Zbl 0882.62012
[26] Ma, Z.; Leijon, A.; Bayesian Estimation of Beta Mixture Models with Variational Inference; IEEE Trans. Pattern Anal. Mach. Intell.: 2011; Volume 33 ,2160-2173.
[27] Ma, Z.; Rana, P.K.; Taghia, J.; Flierl, M.; Leijon, A.; Bayesian Estimation of Dirichlet Mixture Model with Variational Inference; Pattern Recognit.: 2014; Volume 47 ,3143-3157. · Zbl 1342.62034
[28] Diaconis, P.; Ylvisaker, D.; Conjugate Priors for Exponential Families; Ann. Stat.: 1979; Volume 7 ,269-281. · Zbl 0405.62011
[29] Hunter, R.F.; Davis, M.; Tully, M.A.; Kee, F.; ; The Physical Activity Loyalty Card Scheme: Development and Application of a Novel System for Incentivizing Behaviour Change: Berlin, Germany 2011; Volume Volume 91 ,170-177.
[30] Fagiolo, G.; Clustering in complex directed networks; Phys. Rev. E: 2007; .
[31] Johnson, D.B.; Efficient Algorithms for Shortest Paths in Sparse Networks; J. ACM: 1977; Volume 24 ,1-13. · Zbl 0343.68028
[32] Attias, H.; ; A Variational Bayesian Framework for Graphical Models: Cambridge, MA, USA 1999; ,209-215.
[33] Jaakkola, T.S.; Tutorial on Variational Approximation Methods; Advanced Mean Field Methods: Theory and Practice: Cambridge, MA, USA 2001; ,129-159.
[34] Jaakkola, T.S.; Jordan, M.I.; Bayesian parameter estimation via variational methods; Stat. Comput.: 2000; Volume 10 ,25-37.
[35] Ueda, N.; Ghahramani, Z.; Bayesian model search for mixture models based on optimizing variational bounds; Neural Netw.: 2002; Volume 15 ,1223-1241.
[36] Goldstein, M.; Morris, S.; Yen, G.; Problems with fitting to the power-law distribution; Eur. Phys. J. B Condens. Matter Complex Syst.: 2004; Volume 41 ,255-258.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.