Spectral evolution in dynamic networks

详细信息    查看全文

• 作者：Jér?me Kunegis ; Damien Fay ; Christian Bauckhage
• 关键词：Graph kernels ; Link prediction ; Spectral graph theory ; Network dynamics
• 刊名：Knowledge and Information Systems
• 出版年：2013
• 出版时间：October 2013
• 年：2013
• 卷：37
• 期：1
• 页码：1-36
• 全文大小：1108KB
• 参考文献：1. Adamic L, Adar E (2001) Friends and neighbors on the web. Soc Netw 25:211-30 CrossRef
  2. Barabási A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509-12 CrossRef
  3. Blei D, Ng A, Jordan M, Lafferty J (2003) Latent dirichlet allocation. J Mach Learn Res 3:993-022
  4. Bradley AP (1997) The use of the area under the ROC curve in the evaluation of machine learning algorithms. Pattern Recogn 30:1145-159 CrossRef
  5. Breese JS, Heckerman D, Kadie C (1998) Empirical analysis of predictive algorithms for collaborative filtering. In: Proceedings of conference on uncertainty in artificial intelligence, pp 43-2
  6. Brin S, Page L (1998) The anatomy of a large-scale hypertextual Web search engine. Comput Netw ISDN Syst 30(1-):107-17 CrossRef
  7. Chaintreau A, Hui P, Crowcroft J, Diot C, Gass R, Scott J (2007) Impact of human mobility on opportunistic forwarding algorithms. IEEE Trans Mobile Comput 6(6):606-20 CrossRef
  8. Chapelle O, Weston J, Sch?lkopf B (2003) Cluster kernels for semi-supervised learning. Adv Neural Inform Process Syst 15:585-92
  9. Chebotarev P, Shamis E (1997) The matrix-forest theorem and measuring relations in small social groups. Autom Remote Control 58(9):1505-514
  10. Choudhury MD, Lin Y-R, Sundaram H, Candan KS, Xie L, Kelliher A (2010) How does the data sampling strategy impact the discovery of information diffusion in social media? In: Proceedings of conference on weblogs and social media, pp 34-1
  11. Choudhury MD, Sundaram H, John A, Seligmann DD (2009) Social synchrony: predicting mimicry of user actions in online social media. In: Proceedings of the international conference on computational science and engineering, pp 151-58
  12. Chung F (1997) Spectral graph theory. American Mathematical Society, Providence
  13. Doyle PG, Snell JL (1984) Random walks and electric networks. Mathematical Association of America, Washington, DC
  14. Fouss F, Pirotte A, Renders J-M, Saerens M (2004) A novel way of computing dissimilarities between nodes of a graph, with application to collaborative filtering and subspace projection of the graph nodes. In: Proceedings of European conference on machine learning, pp 26-7
  15. Fouss F, Yen L, Pirotte A, Saerens M (2006) An experimental investigation of graph kernels on a collaborative recommendation task. In: Proceedings of the international conference on data mining, pp 863-68
  16. Goldenberg A, Kubica J, Komarek P (2003) A comparison of statistical and machine learning algorithms on the task of link completion. In Proceedings workshop on link analysis for detecting complex behavior
  17. Guha R, Kumar R, Raghavan P, Tomkins A (2004) Propagation of trust and distrust. In: Proceedings of the international world wide web conference, pp 403-12
  18. Guimerà R, Sales-Pardo M, Amaral LAN (2004) Modularity from fluctuations in random graphs and complex networks. Phys Rev E 70(2):025101 CrossRef
  19. Huang Z, Chung W, Chen H (2004) A graph model for e-commerce recommender systems. Am Soc Inf Sci Technol 55(3):259-74 CrossRef
  20. Huang Z, Zeng D, Chen H (2007) A comparison of collaborative-filtering recommendation algorithms for e-commerce. IEEE Intell Syst 22(5):68-8 CrossRef
  21. Ito T, Shimbo M, Kudo T, Matsumoto Y (2005) Application of kernels to link analysis. In: Proceedings of the international conference on knowledge discovery in data mining, pp 586-92
  22. J?rvelin K, Kek?l?inen J (2002) Cumulated gain-based evaluation of IR techniques. ACM Trans Inf Syst 20(4):422-46 CrossRef
  23. Kandola J, Shawe-Taylor J, Cristianini N (2002) Learning semantic similarity. In Advances in neural information processing systems, pp 657-64
  24. Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39-3 CrossRef
  25. Klein DJ, Randi? M (1993) Resistance distance. J Math Chem 12(1):81-5 CrossRef
  26. Klimt B, Yang Y (2004) The Enron corpus: A new dataset for email classification research. In: Proceedings of European conference on machine learning, pp 217-26
  27. Kondor R, Lafferty J (2002) Diffusion kernels on graphs and other discrete structures. In: Proceedings of the international conference on machine learning, pp 315-22
  28. Kunegis J, Fay D, Bauckhage C (2010) Network growth and the spectral evolution model. In: Proceedings of the international conference on information and knowledge management, pp 739-48
  29. Kunegis J, Lommatzsch A (2009) Learning spectral graph transformations for link prediction. In: Proceedings of the international conference on machine learning, pp 561-68
  30. Kunegis J, Lommatzsch A, Bauckhage C (2009) The slashdot zoo: mining a social network with negative edges. In: Proceedings of the international world wide web conference, pp 741-50
  31. Kunegis J, Schmidt S, Lommatzsch A, Lerner J (2010) Spectral analysis of signed graphs for clustering, prediction and visualization. In: Proceedings of SIAM international conference on data mining, pp 559-70
  32. Lü L, Jin C-H, Zhou T (2009) Similarity index based on local paths for link prediction of complex networks. Phys. Rev. E 80(4):046122 CrossRef
  33. Lax PD (1984) Linear algebra and its applications. Wiley, London
  34. Lee DD, Seung SH (2000) Algorithms for non-negative matrix factorization. In: Advances in neural information processing systems, pp 556-62
  35. Leskovec J, Backstrom L, Kumar R, Tomkins A (2008) Microscopic evolution of social networks. In: Proceedings of the international conference on knowledge discovery and data mining, pp 462-70
  36. Leskovec J, Huttenlocher D, Kleinberg J (2010) Governance in social media: A case study of the Wikipedia promotion process. In: Proceedings of th international conference on weblogs and social media
  37. Leskovec J, Kleinberg J, Faloutsos C (2007) Graph evolution: densification and shrinking diameters. ACM Trans Knowl Discov Data 1(1):1-0 CrossRef
  38. Ley M (2002) The DBLP computer science bibliography: evolution, research issues, perspectives. In: Proceedings of the international symposium on string processing and information retrieval, pp 1-0
  39. Liben-Nowell, D. and Kleinberg, J. (2003), The link prediction problem for social networks. In: Proceedings of the international conference on information and knowledge management, pp 556-59
  40. Liu W, Qian B, Cui J, Liu J (2009) Spectral kernel learning for semi-supervised classification. In: Proceedings of the international joint conference on artificial intelligence, pp 1150-155
  41. Long B, Zhang Z, Yu PS (2010) A general framework for relation graph clustering. J Knowl Inf Syst 24(3):393-13 CrossRef
  42. Lu Z, Jain P, Dhillon IS (2009) Geometry-aware metric learning In: Proceedings of the international conference on machine learning, pp 673-80
  43. von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395-16 CrossRef
  44. Manning CD, Raghavan P, Schütze H (2008) Introduction to information retrieval. Cambridge University Press, Cambridge CrossRef
  45. Massa P, Avesani P (2005) Controversial users demand local trust metrics: an experimental study on epinions.com community. In: Proceedings of American association for artificial intelligence conference, pp 121-26
  46. Mislove A (2009) Online social networks: measurement, analysis, and applications to distributed information systems. PhD thesis, Rice University
  47. Mislove A, Koppula HS, Gummadi KP, Druschel P, Bhattacharjee B (2008) Growth of the Flickr social network. In: Proceedings of the workshop on online social networks, pp 25-0
  48. Mohar B (1991) The Laplacian spectrum of graphs. Graph Theory Comb Appl 2:871-98
  49. Najork MA, Zaragoza H, Taylor MJ (2007) HITS on the Web: how does it compare? In: Proceedings of the international conference on research and development in information retrieval, pp 471-78
  50. Newman MEJ (2006) Finding community structure in networks using the eigenvectors of matrices. Phys Rev E 74(3):036104 CrossRef
  51. Peng W, Li T (2011) Temporal relation co-clustering on directional social network and author-topic evolution. J Knowl Inf Syst 26(3):467-86 CrossRef
  52. Radl A, von Luxburg U, Hein M (2009) The resistance distance is meaningless for large random geometric graphs. In: Proceedings of the workshop on analyzing networks and learning with graphs
  53. Sarwar B, Karypis G, Konstan J, Riedl J (2000) Application of dimensionality reduction in recommender systems-a case study. In: Proceedings of ACM WebKDD Workshop
  54. Smola A, Kondor R (2003) Kernels and regularization on graphs. In: Proceedings of the conference on learning theory and kernel machines, pp 144-58
  55. Stewart GW (1990) Perturbation theory for the singular value decomposition, Technical report. University of Maryland, College Park
  56. Sun J, Tao D, Faloutsos C (2006) Beyond streams and graphs: dynamic tensor analysis. In: Proceedings of the international conference on knowledge discovery and data mining, pp 374-83
  57. Thurau C, Kersting K, Wahabzada M, Bauckhage C (2011) Convex non-negative matrix factorization for massive datasets. J Knowl Inf Syst 29(2):457-78 CrossRef
  58. Viswanath B, Mislove A, Cha M, Gummadi KP (2009) On the evolution of user interaction in Facebook. FIn: Proceedings of the workshop on online social networks, pp 37-2
  59. Wax M, Sheinvald J (1997) A least-squares approach to joint diagonalization. IEEE Signal Process Lett 4(2):52-3 CrossRef
  60. Wedin P-? (1972) Perturbation bounds in connection with singular value decomposition. BIT Numer Math 12(1):99-11 CrossRef
  61. Weyl H (1912) Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differenzialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung). Math Ann 71(4):441-79 CrossRef
  62. Wilkinson JH (1965) The algebraic eigenvalue problem. Oxford University Press, Oxford
  63. Zhang B, Liu R, Massey D, Zhang L (2005) Collecting the internet AS-level topology. SIGCOMM Comput Commun Rev 35(1):53-1 CrossRef
  64. Zhang D, Mao R (2008) Classifying networked entities with modularity kernels. In Proceedings of the conference on information and knowledge management, pp 113-22
  65. Zhu X, Kandola J, Lafferty J, Ghahramani Z (2006) Semi-supervised learning, MIT Press, chapter graph kernels by Spectral Transforms
  
• 作者单位：Jér?me Kunegis (1)
  Damien Fay (2)
  Christian Bauckhage (3)
  
  1. Institute for Web Science and Technologies, Universit?t Koblenz–Landau, Universit?tsstra?e 1, 56070, Koblenz, Germany
  2. University College Cork, Cork, Ireland
  3. Fraunhofer IAIS, Sankt Augustin, Germany
  
• ISSN：0219-3116

文摘

We introduce and study the spectral evolution model, which characterizes the growth of large networks in terms of the eigenvalue decomposition of their adjacency matrices: In large networks, changes over time result in a change of a graph’s spectrum, leaving the eigenvectors unchanged. We validate this hypothesis for several large social, collaboration, rating, citation, and communication networks. Following these observations, we introduce two link prediction algorithms based on the learning of the changes to a network’s spectrum. These new link prediction methods generalize several common graph kernels that can be expressed as spectral transformations. The first method is based on reducing the link prediction problem to a one-dimensional curve-fitting problem which can be solved efficiently. The second algorithm extrapolates a network’s spectrum to predict links. Both algorithms are evaluated on fifteen network datasets for which edge creation times are known.