Random graph generator for bipartite networks modeling

• Autorzy: Chojnacki Sz. , Kłopotek M. A.
• Języki publikacji: EN

Abstrakty

EN

The purpose of this article is to introduce a new bipartite graph generation algorithm. Bipartite graphs consist of two types of nodes and edges join only nodes of different types. This data structure appears in various applications (e.g. recommender systems or text clustering). Both real-life datasets and formal tools enable us to evaluate only a limited set of properties of the algorithms that are used in such situations. Therefore, artificial datasets are needed to enhance development and testing of the algorithms. Our generator can be used to produce a wide range of synthetic datasets.

Słowa kluczowe

EN

complex networks; bipartite graphs; recommender systems; affiliation networks

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2011
• Tom: Vol. 40, no 3
• Strony: 697--714
• Opis fizyczny: Bibliogr. 16 poz., il. wykr.

Twórcy

autor

Chojnacki Sz.

autor

Kłopotek M. A.

• Institute of Computer Science, Polish Academy of Sciences Ordona 21, 01-237 Warsaw, Poland

Bibliografia

• Barabási, A.L. and Albert, R. (1999) Emergence of Scaling in Random Networks. Science, 286(5439), 509-512.
• Burda, Z., Duda, J., Luck, J.M. and Waclaw, B. (2009) Localization of the Maximal Entropy Random Walk. Phys. Rev. Lett., 102(16), http://prl.aps.org/abstract/PRL/v102/i16/e160602.
• Chojnacki, Sz. and K lopotek, M.A. (2011a) Random Graphs for Performance Evaluation of Recommender Systems. Control and Cybernetics, 40 (2), 237-257.
• Chojnacki, Sz. and K lopotek, M.A. (2011b) Scale invariant bipartite graph generative model. In: International Joint Conference Security and Intelligent Information Systems. LNCS 7053, Springer.
• Erdős, P. and Rényi, A. (1960) On the Evolution of Random Graphs. In: Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 17-61.
• Guillaume, J.-L. and Latapy, M. (2004) Bipartite structure of all complex networks. Inf. Process. Lett., 90(5), 215-221.
• Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A. and Upfal, E. (2000) Stochastic Models for the Web Graph. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS). IEEE CS Press, Redondo Beach, CA, USA, 57-65.
• Lattanzi, S. and Sivakumar, D. (2009) Affiliation networks. In: STOC’09: Proceedings of the 41st annual ACM symposium on Theory of computing. ACM, New York, NY, USA, 427-434.
• Liu, Z., Lai, Y.Ch., Ye, N. and Dasgupta, P. (2002) Connectivity distribution and attack tolerance of general networks with both preferential and random attachments. Physics Letters A, 303(5-6), 337-344.
• Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P. and Bhattacharjee, B. (2007) Measurement and Analysis of Online Social Networks. In: Proceedings of the 5th ACM/USENIX Internet Measurement Conference (IMC’07), San Diego, CA.
• Newman, M. (2010) Networks: An Introduction, Oxford University Press.
• Newman, M., Strogatz, S. and Watts, D.J. (2001) Random graphs with arbitrary degree distributions and their applications. Physical Review E, 64, 2.
• Potter, T. and Chojnacki, Sz. (2011) Mahout Clustering Benchmarks. In: G.S. Ingersoll, T.S. Morton and A.L. Farris, eds., Taming Text. How to Find, Organize, and Manipulate It. Manning, 211-216.
• Vázquez, A. (2003) Growing network with local rules: Preferential attachment, clustering hierarchy, and degree correlations. Phys. Rev. E, 67(5).
• Wasserman, S. and Faust, K. (1994) Social Network Analysis: Methods and Applications. Cambridge University Press.
• Zheleva, E., Sharara, H. and Getoor, L. (2009) Co-evolution of social and affiliation networks. In: J.F. Elder IV, F. Fogelman-Soulié, P.A. Flach and M. Zaki, eds., KDD. ACM, 1007-1016.