Abstract
Large scale real-world network data such as social and information networks are ubiquitous. The study of such networks seeks to find patterns and explain their emergence through tractable models. In most networks, and especially in social networks, nodes have a rich set of attributes associated with them. We present the Multiplicative Attribute Graphs (MAG) model, which naturally captures the interactions between the network structure and the node attributes. We consider a model where each node has a vector of categorical latent attributes associated with it. The probability of an edge between a pair of nodes depends on the product of individual attribute-attribute similarities. The model yields itself to mathematical analysis. We derive thresholds for the connectivity and the emergence of the giant connected component, and show that the model gives rise to networks with a constant diameter. We also show that MAG model can produce networks with either log-normal or power-law degree distributions.
The full version of this paper appears in http://arxiv.org/abs/1009.3499.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: STOC (2000)
Airoldi, E.M., Blei, D.M., Fienberg, S.E., Xing, E.P.: Mixed membership stochastic blockmodels. JMLR (2007)
Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science (1999)
Borgs, C., Chayes, J., Daskalakis, C., Roch, S.: First to market is not everything: an analysis of preferential attachment with fitness. In: STOC (2007)
Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: SIGCOMM (1999)
Hoff, P., Raftery, A.: Latent space approaches to social network analysis. JASA (2002)
Kim, M., Leskovec, J.: Multiplicative attribute graph model of real-world networks (2010), http://arxiv.org/abs/1009.3499
Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: FOCS (2000)
Lattanzi, S., Sivakumar, D.: Affiliation networks. In: STOC (2009)
Leskovec, J., Chakrabarti, D., Kleinberg, J., Faloutsos, C., Ghahramani, Z.: Kronecker Graphs: An Approach to Modeling Networks. JMRL (2010)
Leskovec, J., Kleinberg, J.M., Faloutsos, C.: Graphs over time: densification laws, shrinking diameters and possible explanations. In: KDD (2005)
Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Statistical properties of community structure in large social and information networks. In: WWW (2008)
Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., Tomkins, A.: Geographic routing in social networks. PNAS (2005)
Mahdian, M., Xu, Y.: Stochastic kronecker graphs. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 179–186. Springer, Heidelberg (2007)
McPherson, M.: An ecology of affiliation. American Sociological Review (1983)
Mitzenmacher, M.: A brief history of generative models for power law and lognormal distributions. Internet Mathematics (2004)
Palla, G., Lovász, L., Vicsek, T.: Multifractal network generator. PNAS (2010)
Wasserman, S., Pattison, P.: Logit models and logistic regressions for social networks. Psychometrika (1996)
Watts, D.J., Strogatz, S.H.: Collective dynamics of ’small-world’ networks. Nature (1998)
Young, S.J., Scheinerman, E.R.: Random Dot Product Graph Models for Social Networks. In: Bonato, A., Chung, F.R.K. (eds.) WAW 2007. LNCS, vol. 4863, pp. 138–149. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kim, M., Leskovec, J. (2010). Multiplicative Attribute Graph Model of Real-World Networks. In: Kumar, R., Sivakumar, D. (eds) Algorithms and Models for the Web-Graph. WAW 2010. Lecture Notes in Computer Science, vol 6516. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18009-5_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-18009-5_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18008-8
Online ISBN: 978-3-642-18009-5
eBook Packages: Computer ScienceComputer Science (R0)