Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Network growth and the spectral evolution model

: Kunegis, J.; Fay, D.; Bauckhage, C.


Huang, X.J.; Jones, Gareth; Koudas, Nick; Wu, Xindong; Collins-Thompson, Kevyn ; Association for Computing Machinery -ACM-, Special Interest Group on Information Retrieval -SIGIR-; Association for Computing Machinery -ACM-, Special Interest Group on Hypertext, Hypermedia, and Web; Association for Computing Machinery -ACM-, Special Interest Group on Knowledge Discovery and Data Mining -SIGKDD-:
CIKM 2010, 19th International Conference on Information & Knowledge Management and Co-located Workshops. CD-ROM : October 26-30, 2010, Toronto, Ontario, Canada, proceedings
New York: ACM, 2010
ISBN: 978-1-4503-0099-5
International Conference on Information and Knowledge Management (CIKM) <19, 2010, Toronto>
Fraunhofer IAIS ()

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, authorship, rating, citation, communication and tagging networks, covering unipartite, bipartite, signed and unsigned graphs. Following these observations, we introduce a link prediction algorithm based on the extrapolation of a network's spectral evolution. This new link prediction method generalizes several common graph kernels that can be expressed as spectral transformations. In contrast to these graph kernels, the spectral extrapolation algorithm does not make assumptions about speci c growth patterns beyond the spectral evolution model. We thus show that it performs particularly well for networks with irregular, but spectral, growth patterns.