nips nips2005 nips2005-60 nips2005-60-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Purnamrita Sarkar, Andrew W. Moore
Abstract: This paper explores two aspects of social network modeling. First, we generalize a successful static model of relationships into a dynamic model that accounts for friendships drifting over time. Second, we show how to make it tractable to learn such models from data, even as the number of entities n gets large. The generalized model associates each entity with a point in p-dimensional Euclidian latent space. The points can move as time progresses but large moves in latent space are improbable. Observed links between entities are more likely if the entities are close in latent space. We show how to make such a model tractable (subquadratic in the number of entities) by the use of appropriate kernel functions for similarity in latent space; the use of low dimensional kd-trees; a new efficient dynamic adaptation of multidimensional scaling for a first pass of approximate projection of entities into latent space; and an efficient conjugate gradient update rule for non-linear local optimization in which amortized time per entity during an update is O(log n). We use both synthetic and real-world data on upto 11,000 entities which indicate linear scaling in computation time and improved performance over four alternative approaches. We also illustrate the system operating on twelve years of NIPS co-publication data. We present a detailed version of this work in [1]. 1
[1] P. Sarkar and A. Moore. Dynamic social network analysis using latent space models. SIGKDD Explorations: Special Issue on Link Mining, 2005.
[2] J. Schroeder, J. J. Xu, and H. Chen. Crimelink explorer: Using domain knowledge to facilitate automated crime association analysis. In ISI, pages 168–180, 2003.
[3] J. J. Carrasco, D. C. Fain, K. J. Lang, and L. Zhukov. Clustering of bipartite advertiser-keyword graph. In ICDM, 2003. ´
[4] J. Palau, M. Montaner, and B. Lopez. Collaboration analysis in recommender systems using social networks. In Eighth Intl. Workshop on Cooperative Info. Agents (CIA’04), 2004. Koch C KochC Manwani ManwaniA Burges A C Vapnik V Viola Sejnowski T BurgesC P VapnikV ViolaP SejnowskiT HintonG Jordan M Hinton G Ghahramani Z JordanM GhahramaniZ (A) (B) 1 ManwaniA KochC quadratic score score using kd−tree 0.9 0.8 Viola P SejnowskiT HintonG GhahramaniZ JordanM BurgesC VapnikV Time in Seconds 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 300 (C) 400 500 600 700 Number of entities 800 900 1000 (D) Figure 4: NIPS coauthorship data at A. Timestep 1: green stars in upper-left corner, magenta pluses in top right, cyan spots in lower right, and blue crosses in the bottom-left. B. Timestep 2. C. Timestep 3. D. Time taken for score calculation vs number of entities.
[5] A. E. Raftery, M. S. Handcock, and P. D. Hoff. Latent space approaches to social network analysis. J. Amer. Stat. Assoc., 15:460, 2002.
[6] R. L. Breiger, S. A. Boorman, and P. Arabie. An algorithm for clustering relational data with applications to social network analysis and comparison with multidimensional scaling. J. of Math. Psych., 12:328–383, 1975.
[7] I. Borg and P. Groenen. Modern Multidimensional Scaling. Springer-Verlag, 1997.
[8] R. Sibson. Studies in the robustness of multidimensional scaling : Perturbational analysis of classical scaling. J. Royal Stat. Soc. B, Methodological, 41:217–229, 1979.
[9] David S. Watkins. Fundamentals of Matrix Computations. John Wiley & Sons, 1991.
[10] F. Preparata and M. Shamos. Computational Geometry: An Introduction. Springer, 1985.
[11] A. G. Gray and A. W. Moore. N-body problems in statistical learning. In NIPS, 2001.